Find Number of elements X in the Tree that lie between a and b Question
Suppose there is a balanced binary search tree with n nodes, where at
each node, in addition to the key, we store the number of elements in
the sub tree rooted at that node.
Now, given two elements a and b, such that a$<$b, we want to find the
number of elements x in the tree that lie between a and b, that is,
$a≤x≤b$ This can be done with (choose the best solution).

O(logn)  comparisons and O(logn) additions.
O(logn) comparisons but no further additions.
O(√n) comparisons but O(logn) additions.
O(logn) comparisons but a constant number of additions.
O(n) comparisons and O(n) additions, using depth-first- search.

My Approach
Now there are two possibilities,

$b$ can be in the right subtree of $a$
We simply search for b, in the right subtree of aa and at each step we add the number of elements in the left subtree +1 (BST being balanced, this can be retrieved from the depth of the node without any finding method), if we are moving right and simply 1 if we are moving left. When we find $b$, this sum will give as the required number of elements. This requires $O(logn)$

$b$ can be in the right subtree of any of the parents of $a$.

For the second case also we do the same method. But first we find the common ancestor of $a$ and $b$ (possible in $O(logn)$- say $p$ and also count the no. of nodes in the right subtree of each node from $a$ to $p$ excluding $p$. Now, from $p$ to $a$ we proceed the counting as in the earlier case when $b$ was in the subtree at $a$. So, in the worst case we have to do $O(logn)$ additions
How to make use of the nuber count more efficiently than this ?
Answer is given by my professor is

O(logn) comparisons but a constant number of additions.

Please elaborate the efficient approach using neat diagrams for clear cut understanding for both (when $b$ is right subtree of $a$  and $b$ is right subtree of parent of $a$ )

We may assume without loss of generality that the lowest common ancestor of $a$ and $b$ is the root. Let $S = \{x \in T| key(a) \le x \le key(b) \} $. Observe that $|S| = |T| - |\bar{S}|$, and that $|\bar{S}|$ is the sum of the sizes of the left subtree of $a$ and of the right subtree of $b$.


Fastest known complexity for combinatorial ILP algorithm? I'm wondering, what is the best known algorithm, in terms of Big-$O$ notation, to solve Integer Linear Programming?

I know that the problem is $NP$-complete, so I'm not expecting anything polynomial. And I know there are lots of heuristics and such that are used in practical applications like CPLEX, but I'm more interested in the formal, worst-case complexity of an exact algorithm.

Some $NP$-complete problems have algorithms in time $O(b^n p(n))$ where $1 < b < 2$ and $p$ is a polynomial. Vertex cover, independent set and 3SAT fall into this category, but general-SAT and TSP don't (as far as we know).

Can any such statements be made about Integer Programming, or particular sub-instances?

If anyone has a reference for the related problem of Quantifier Free Presburger Arithmetic, I'd be very interested in that too.

From what I can tell by searching, the definite survey seems to be:

Aardal, Karen, Robert Weismantel, and Laurence A. Wolsey. "Non-standard approaches to integer programming." Discrete Applied Mathematics 123.1 (2002): 5-74.

In particular, Section 2.1 discusses integer programming in bounded dimension, and presents algorithms due to different authors. Indeed, the survey lists many references, and discusses some practical implementations.

For a fixed number of variables, integer linear programming is polynomial time solvable by Lenstra's algorithm.


A* algorithm how to choose $h(n)$, a heuristic estimation of the cost of node n I'm trying to understand the A$^*$ search algorithm. I read in wikipedia that A$^*$ chooses nodes based on their cost, calculated as $f(n)=g(n)+h(n)$, where $h(n)$ is a heuristic estimation of the cost to reach the target from node $n$. But I don't understand how to determine its value.

Thanks for your help.

Let's try to walk together through the $f$ function!

The intuition here is that we want to choose nodes in our exploration frontier which are:

Close to the start state
Close to a goal state

The shortest distance to the start state can be calculated recursively for every node in the search space pretty much as we do in uniform cost search.

However, the distance of a node to a goal state cannot be precisely calculated (for that we would need to know the shortest path to a goal, which would mean we have already solved the problem).

Thus the best we can do is try estimating it, using a heuristic function $h$. Obviously, we want this estimation to be as precise as possible, but we also want some other properties to hold:

(admissibility) we want $h$ to never overestimate the cost to the goal from any given node.
(consistency) we want $h(n)$ to not be greater than $h(n')+c(n,n')$ for any successor $n'$ of $n$, where $c(n,n')$ is the cost of the path that joins both states. In other words, the true cost of going from any given node to another must be less than the difference between the heuristic value of both nodes.

If we impose the restriction that $h(n)=0$ if $n$ is a goal state, then it is easy to see that consistency implies admissibility.

These properties guarantee that the algorithm is sound, complete and optimal for tree-search (admissibility) and graph-search (consistency).

Now, there are many heuristics out there for each problem.

One example is the trivial heuristic which assigns $h(n)=0$ for every $n$. This heuristic is indeed consistent. In this case, $A^*$ behaves as uniform cost search.

We can find heuristics better suited to solve a problem. One way to do so is by relaxing the conditions to solve the problem, and calculating the exact solution of the relaxed problem from the state we are in.

For example, we can take the $n$-queens problem, where each step consists in moving one queen, and take as a heuristic the number of queens under attack minus one (or zero if no queen is under attack).


How does sorting come into play with convex hull? I am investigating a convex hull algorithm that involves sorting. In fact, its running time is limited by sorting, so it is $O(n \log n)$, where $n$ is the number of points on the plane.

That algorithm first sorts the points by x-coordinates. It then includes the first and last points in the convex hull. From there on, I am confused. How could an algorithm like this get the other points of the hull?

It is easier to catch the connection with sorting if you first sort the points by their polar angle. This is the basic idea for the Graham scan. Though, the idea with sorting points by the x-coordinates also works: you need then to apply just a slight modification of the same Graham's algorithm.


Magic Square Check for NxN Matrix - with Minimum Complexity? Is there any algorithm that works better than $\Theta(n^2)$ to verify whether a square matrix is a magic one? (E.g. such as sum of all the rows, cols and diagonally are equal to each other).
I did see someone mention a $O(n)$ time on a website a few days ago but could not figure out how.

If you have an $N \times N$ matrix, then it has $N^2$ entries, and as you need to check all entries at least once to see if the square is a magic square, any algorithm must have a running time of $\Omega(N^2)$.

For a square to be a magic square, all rows, columns and both diagonals must sum to the same number. There are $N$ rows, $N$ columns and 2 diagonals, each of which have $N$ entries, so you can check this property in $O((2N+2)N) = O(N^2)$ time.

Combining the above: verifying the magicness of a square is in $\Theta(N^2)$.


Computer Organization and Assembly Language Programming Why do we need to learn MIPS Assembly language before learning computer organization? What are the implications of learning it first?

As a computer scientist, why do we need to learn this one and where will these topics will become handy?

with references:

-Computer Organization and Design by Patterson and Hennessy

-Introduction to Digital Logic Design by John Hayes

Learning assembly language will be helpful for you in understanding computer architecture, because the CPU is designed to run the instructions that are part of its assembly language.  So, to understand what the CPU is doing and why it was designed that way, you need to know what operations it is designed to support.


Single-source shortest paths as a linear program I saw that I can formulate single-source shortest path as the following linear program:

Given $G=(V,E)$ and $w\colon E\to R$ and with negative cycles, find
$\max\,d(s,t)$ such that

\begin{align*}
    d(s,v) &\le d(s,u)+w(u,v) \quad \forall (u,v)\in E \\
    d(s,s) &=0
\end{align*}

We want to find the shortest path from $s$ to $t$ so we are we maximizing $d(s,t)$?

What you have here is a dual formulation of the problem (not the standard one, but an equivalent one). According to strong duality, both the optimal primal and the optimal dual problem have the same objective value (i.e., the shortest path distance from $s$ to $t$). The constraints of the dual problem are then the optimality criteria of the shortest path problem. Note that you can obtain the actual shortest path by finding any $s$-$t$-path in the subgraph that is induced by the edges for which the corresponding dual constraint is tight.

By the way, there is a neat interpretation of this formulation: For each edge $(u,v)$, consider a string with length $w(u,v)$ and tie the ends of these strings together at the corresponding nodes they share. If you put the knot for $s$ and the knot for $t$ as far away from each other as possible, you will end up with several tight strings, which then describe the shortest path.


np-complete proof, turing reduction I have some difficulties with a complexity proof : I work with 3 problems : A, B and C I know :

A-> B
A-> C
C -> B

A-> B meaning : if I have a "yes answer " for A , then I have a "yes answer" for B. I know that A belongs to NP, B and C are NP-complete. Moreover I can write an algorithm for A with a quadratic number of calls to C.
can I deduce something about the complexity of A?

You know that:

A belongs to NP
B is NP-Complete
C is NP-Complete
If A accepts given word then B accepts this word as well
If we can solve C - we can solve A.

To prove that A is NP-Complete you need to prove that it belongs to NP (which is given to us) and that any problem from NP can be reduced to it (so that it is NP-Hard). To show the second one you need to show a reduction from an NP-Complete problem to A.

The last (5th) of our information basically means you have a polynomial reduction from A to C which is no surprise, since A is in NP and C is NP-Complete (meaning, among others, that every NP problem can be reduced to it, including A). This doesn't give you much about A (it only confirms that A is no harder than C).

The 4th information gives us knowledge like this: if some word belongs to A it also belongs to B, but there are some possible words that belong to B but not to A. In other words, A is a subset of B. This does not gives us much about A either, because A could belong to P only and still be a subset of B (as NP "contains" P).

In my opinion, if I understood this well, this information is not sufficient to say more about the complexity of A.


What is the importance of disjoint edges in k-opt algorithms? I'm trying to implement a k-opt algorithm and I'm bogged down on a detail: the importance of choosing disjoint edges.

My question: Is there any benefit to considering adjacent edges, or is the full power of the heuristic achieved when only disjoint edges are considered?

Wikipedia seems confused on this question. Its description of k-opt explicitly says "k mutually disjoint edges", but then it describes 2-opt and 2.5-opt as special cases of k-opt, and describes both those algorithms as processing adjacent edges. Is there something I'm not understanding here?

I have a partial answer to my own question. I believe there is a benefit to considering adjacent edges. The full power of the heuristic is not achieved when only disjoint edges are considered.

To arrive at this conclusion, I implemented two versions of the 4-opt algorithm in C#. One version considers only disjoint edges and the other considers both disjoint and adjacent edges. Then, I used both algorithms to solve the Travelling Salesman problem for 1000 scenarios of 25 nodes each.

The two algorithms found the same solution 52.7% of the time.
The disjoint+adjacent algorithm found a better solution than the disjoint-only algorithm 45.7% of the time.
The disjoint-only algorithm found a better solution than the disjoint+adjacent algorithm 1.6% of the time.

The disjoint+adjacent algorithm found tours that were, on average, 99.1% of the length of the tours found by the disjoint-only algorithm.

Based on these results, I'm fairly confident that there is a benefit to exploring adjacent edges in the k-opt algorithm.

I call this a partial answer because I'm not yet clear on whether it is efficient to explore adjacent edges. Yes, exploring adjacent edges in my experiment improved the tour length by an average of 0.9%, but perhaps I could have improved the tour length more than that by using the same computing effort exploring some 5-opt steps instead.

My experimentation suggests that it is optimal to first explore 2-opt steps, then to explore 3-opt steps that include adjacent edges, then to explore 3-opt steps that include no adjacent edges, then to explore 4-opt steps that include adjacent edges, then to explore 4-opt steps that include no adjacent edges, etc. However, that is preliminary speculation. If anyone knows of k-opt documentation that covers this level of detail, please let me know about it.


Correctness proof for greedy algorithm based on ratio I've an issue stated as follows:

  We have 10000 jobs to do, each with some length $l_i$ and weight
  (importance) $w_i$. Our goal is to arrange the schedule of doing these
  jobs (in other words, the order of doing jobs) in such way that
  minimizes the weighted sum of completion times

For this, I'm using the ratio greedy algorithm, that is ratio weight/length to order the jobs, and it is working fine. But now I've to do its correctness proof and I'm stuck with it.

The strategy to prove your ratio greedy algorithm is what I called "unimprovable solution by exchange of elements".

Instead of proving that an algorithm produces the optimal solution, this strategy require you to show that every optimal solution that cannot be improved by an exchange of two or more elements must be or must be equivalent to the solution produced by that algorithm.

Firstly, there must be at least one optimal solution in this scheduling problem. You may want to take a moment to verify that this is indeed true.

Now suppose $OPT$ is an optimal solution. Let us analyze two adjacent jobs in $OPT$. Note that we can switch these two adjacent jobs without changing the contribution of other jobs to the weighted sum of completion times, since the switch does not change the completion times of other jobs. How should these two jobs be arranged so that the total contribution of these two jobs to the weight sum of completion times might be smaller? Now it is time to show the power of arithmetic using unknowns. You will be able to conclude that, the job whose weight/length ratio is bigger must be scheduled earlier than the other job. Assuming the ratio weight/length of each job is distinct, you can then deduce that $OPT$ must schedule all jobs by the descending order of their weight/length ratio; otherwise you will find two adjacent jobs in ascending order of their weight/length ratio. Well, the only scheduling that schedules all jobs by the descending order of their weight/length ratio is produced by your greedy algorithm!

I will let you fill the detail of a complete rigorous proof, which should mention why there should no idle time between two adjacent jobs and which should deal with the case when there are jobs of the same weight/length ratio.


complexity class of functions What would these statements mean if f(n) and g(n) are functions over natural numbers?

g(n) is in Θ(f(n)).
and

An algorithm is in the complexity class Θ(f(n)).

$g(n)$ is in $O(f(n))$ means that there exists a positive number $c$ such that $g(n) \leq c \cdot f(n)$ for all $n$ (or at least all large $n$s). In other words, $g(n)$ does not grow faster than $cf(n)$.

We say "is in" because $O(f(n))$ is a class of all functions that satisfy above condition. It is also sometimes said just "is" and written $g(n) = O(f(n))$ but in my opinion this is too misleading because equality here is not symmetric.

That an algorithm is in a complexity class $O(f(n))$ means that a function $g$ that measures the number of basic calculation steps (dependant of the input size $n$) of this algorithm is in $O(f(n))$.

Useful links:

Big O notation
Time complexity


Proving that the conversion from CNF to DNF is NP-Hard How can I prove that the conversion from CNF to DNF is NP-Hard?

I'm not asking for an answer, just some suggestions about how to go about proving it.

Informally:

In DNF, you can pick any clause to be true, to make the formula true. This means that a DNF that is equivalent to a certain CNF, is basically an enumeration of all the solutions to boolean sat on the CNF. Note, there can be an exponential number of solutions. Since solving boolean sat for CNF for a single solution is NP-complete, converting to DNF essentially means solving for every solution. So it is at least as hard as Boolean SAT, and is thus NP-hard.


Is complexity class $\Sigma^1_1$ from polynomial hierarchy decidable? It is within polynomial hierarchy so I assumed it is decidable. The picture like this further hinted in that direction.
Yet, in a paper on page 2 I read

  Satisfiability of [...] is highly undecidable (i.e., $\Sigma^1_1$-hard)

which implies that $\Sigma^1_1$-hard is undecidable. Do authors mean something else by "highly undecidable" or $\Sigma^1_1$-hard is really undecidable?
In the latter case, why is it included inside decidable PSPACE?
(or I misunderstanding things...)

The confusion lies in using the same notation for the polynomial hierarchy and the arithmetical hierarchy.

The similarities are obvious, both notations talk about formulas with increasing quantifier complexity. The important distinction is that the polynomial hierarchy talks about bounded quantification, i.e. your space is limited (the witnesses must be of polynomial size). If the quantification is not bounded you have much more power, e.g. a formula for "program $p$ halts on input $x$" can be written in a $\Sigma_1$ form, which means that the halting problem is in the first level of the arithmetical hierarchy.

To avoid confusion the levels of the polynomial hierarchy are actually denoted by $\Sigma_i^p$, however when it is obvious from the context the $p$ is usually omitted. Note that the superscript in $\Sigma_1^1$ means that the quantification is over sets, which puts it above any level in the arithmetical hierarchy with quantification over the naturals.


Solving recurrence relation $T(n)=\sqrt{n} \cdot T(\sqrt{n}) + n$ using method of guessing and confirm? The book I am following explains the solution as,

  As we can see,the size of sub problems at the first level of recursion
  is $n$.So, let us guess that $T(n)=O(n\log n)$ and try to prove that our guess is correct.

Doubt- Does initial problem size(i.e n) give a hint to reach $O(n\log n)$ ? How it does?

furthermore ,the book says

  Let's start by trying to prove an upper bound $T(n)\le c\cdot n\log n$

  \begin{align*}
T(n)=\sqrt{n} \cdot T(\sqrt{n}) + n  \tag{1}
\\
\le \sqrt{n}\cdot c\sqrt{n}\log(\sqrt{n}) + n \tag{2}
\\
  =n\cdot c\log (\sqrt{n})+ n \tag{3}
\\
 =n\cdot c\cdot\frac{1}{2}\log n+ n \tag{4}
\\ \le c\cdot n\log n  \tag{5}
\end{align*}
  Last inequality assumes only that $$1\le c\cdot\frac{1}{2}\cdot \log n$$
  This is correct if n is sufficiently large and for any constant c,no matter how small.So we are correct for upper bound.

I am not getting what's happening from $(1)$ to $(2)$ and that from $(4)$ to $(5)$. Also What does the last line prove ?

The book answer skips over some things. Here's a more detailed explanation.

You want to show $T(n)=O(n\log n)$, in other words there exists a $c>0$ such that $T(n)\le c\cdot n\log n$. [Actually, you need also to show that this inequality holds for all $n$ greater than some constant $N$, but we'll put this off temporarily.]

We'll use strong induction here; our induction hypothesis is that

  $T(k)\le c\cdot k\log k$, for all $k<n$.

Now we'll expand the book's answer.
$$\begin{align}
T(n) &= \sqrt{n}\;T(\sqrt{n}) + n &\text{by definition} \\
     &\le\sqrt{n}\;[c\cdot\sqrt{n}\log{\sqrt{n}}]+n &\text{by induction hypothesis, since $\sqrt{n}<n$}\\
     &= cn(\log\sqrt{n})+n
\end{align}$$
which answers your question about the step from $(1)\rightarrow(2)$. To get $(4) \rightarrow(5)$ the text wants to end up with $T(n)\le c\cdot n\log n$, so to conclude this they need
$$
n\cdot c\cdot\frac{1}{2}\log n+n\le c\cdot n\log n
$$
Dividing both sides of the desired equality by $n$ yields the needed condition:
$$
\frac{c}{2}\log n+1\le c\log n
$$
and this will be true when $1\le \frac{c}{2}\log n$. [The book actually doesn't need an unspecified $c$: in fact, $c=2$ will work perfectly here, since as long as $n\ge 2$ we'll have $1\le\log n$, satisfying our needed condition.]

In sum, we've shown by induction that the recurrence $T(n)= \sqrt{n}\log\sqrt{n}+n$ is satisfied by any function $T(n)=c\cdot n\log n$, as long as we pick a suitable $c$, which is exactly what was required.

It's worth pointing out that $O(n\log n)$ is an upper bound, but it's not the tightest upper bound possible. As gnasher729 pointed out, a better bound is $O(n\log\log n)$. It's a good exercise to do the same argument (with $c=1$) to show that $T(n)=n\log\log n$ is a solution to $T(n)=\sqrt{n}\;T(\sqrt{n})+n$.


Randomized vs deterministic approach for multiset equality Let $S_1$ and $S_2$ are two multi sets. We want to find, Is $S_1 =S_2$?

Algo 1:

Sort $S_1$ and $S_2$ and then check $S_1 = S_2$

Running time : $O(n \log {n})$, where $n$ is the size of the multi sets.

Algo 2:

Contruct two polynomials using $S_1$ and $S_2$ (example if $S_1 = \{1,1,2\}$ then polynomial will be $(x-1)(x-1)(x-2)$)

Let us say we have now two polynomials $p(x)$ and $q(x)$, do $p(x)-q(x)$, now using polynomial identity testing check whether $p(x)-q(x) =0 $ or not. If it is zero then $S_1$ equals to $S_2$.

Question : Which algorithm is better Algo 1 or Algo 2?

To understand the complexity of the randomized algorithm, you must delve into the implementation details.

Suppose $S_1,S_2$ consist of $m$ elements, each bounded by $n$ in absolute value, i.e. the input size is $O(m\log n)$. Let $P_S=\prod\limits_{w\in s}\left(x-w\right)$ be the polynomial corresponding to the set $S$. $P_{s_1},P_{S_2}$ are degree $m$ polynomials. Thus, in order to succeed with constant probability in testing whether $q(x)=P_{S_1}(x)-P_{S_2}(x)$ is the zero polynomial, you need to evaluate it at numbers in the range $[0,cm]$, for some constant $c$.

Suppose you choose $y$ uniformly at random from this range, then in order to avoid blowup in the intermediate values while computing $q(y)$, you need to compute the values modulo some $k$ (the standard trick in PIT).

Note that the blowup here is not exponential, unlike in PIT where the polynomials are given as algebraic circuits, so you can in fact directly compute $q(y)$. However, this will lead to handling $\Omega(m)$ bit numbers, which will result in quadratic running time, so you can still compute $q(y) \bmod k$ for a random $k$ chosen appropriately to save some time.

If $k$ is chosen at random from some range $[1,R]$, then a "good" event is that $k$ does not divide $q(y)$, in that case $q(y)\neq 0$ iff $q(y) \bmod k \neq 0$. To lower bound this probability, note that $k$ is prime with probability $\approx \frac{1}{\log R}$ (here you need some finite version of the prime number theorem), and that $q(y)\le (cm+n)^m$, hence it has at most $m \log (cm+n)$ different prime factors.

$
\begin{align*}
&
\Pr\limits\left[\text{$k$ is prime $\land$ $k$ is not a product of $q(y)$}\right]=
\Pr\left[\text{$k$ is prime}\right]\cdot\\
&
\Pr\limits\big[\text{$k$ is a product of $q(y)$} \big| \text{$k$ is prime}\big]\approx \frac{1}{\log R}\left(1-\frac{\log (cm+n)^m}{R/\log R}\right)
\end{align*}
$

Choosing $R=(m+n)^2$ suffices to make the above probability high enough, and yields constant success probability after $\approx\log R$ evaluations. Each evaluation requires $O(m)$ additions/multiplications of numbers with $\log R$ bits, thus the overall running time is $O(m\log ^2 R\log\log R)$, which is worse than sorting. Perhaps sharper bounds on the success probability will allow you to get rid of one of the logarithmic factors, but taking numeric operations into account will eventually show that you cant beat naive sorting. However, the randomized approach is not without merits, as it allows you to determine multiset equality between two parties with logarithmic communication (you only need to send $y,k$ and the evaluations of $P_{S_1},P_{S_2}$ on $y$ modulo $k$).


Placing a fixed number of points on a curve to make the finite second derivative constant I am given a 1D curve $f(x)$ that starts at $a$ and ends at $b$. I have $n$ points I have to place on the curve, and I have to place two points at $a$ and $b$, respectively. Is there a way to place points $a=x_1<...<x_n=b$ along the line so that the finite second derivative (i.e., $f(x_{i-1})-2f(x_i)+f(x_{i+1})$) is constant for all $i=2,...,n-1$? In my particular problem, $f(x)=-\log(x)$ on the interval $[\frac{1}{t},1]$. Maybe this additional structure makes the problem more tractable.

In a nutshell

The problem can be solved algebraically by considering the equations as
defining $y_i=f(x_i)$. This gives $n-1$ equations with $n$ unknowns ($y_i$ for $i\in[2,n-1]$, and the values of $c$ and $u$ defined below),
resulting in the abitrary choice of one value. The answers are given
by the formula
$$x_i=f^{-1}(f(a)-(i-1)u+c\frac{(i-2)(i-1)}{2})$$

and the value of $u=f(a)-f(x_2)$ is determined from that of the
constant finite second derivative $c$, or the reverse, with the linear
relation
$$f(b)=f(a)-(n-1)u+c\frac{(n-2)(n-1)}{2}$$

However I wonder if the formula used is really that of a finite second
derivative.

Full proof

With the formula used, your question seems rather tractable, and solvable algebraically.

Like the previous answer, I note $c$ the value of the constant finite second derivative, as defined in the question (though this is further discussed below).

You should see it as a set of equations in $y$, with $y=f(x)$.
If you note $y_i=f(x_i)$, you get a set of $n-2$ equations
 $$y_{i-1}-2y_{i}+y_{i+1}=c\;\; \text{ for }i\in [2,n-1]$$
with $n-1$ unknown : $y_{i} \text{ for }i\in [2,n-1]$ and $c$, given
that you have $y_1=f(a)$ and $y_n=f(b)

This probably means an infinity of solutions, which may means that you
can choose arbitrarily one of the values, for example that of $c$.
I have not worked out the equations.

However, given the strictly monotonically decreasing function $f$ of your example, you have the
additional constaints that:
$$ \forall i\in[2,n-1], \;\;y_i\in(f(a), f(b)) \;\wedge\; y_i>y_{i+1} $$

One way to start resolving it is by defining $u_i=y_i-y_{i+1}$ and $v_i=y_i-y_{i+2}$ for $i\in [1,n-2]$. Then the equations become
$y_i-2(y_i-u_1)+(y_i-v_i)=c$ which simplifies into
$2u_i-v_i=c$, from which we derive $v_i-u_i=u_i-c$.

From the definition of $u_i$, $u_{i+1}$, and $v_i$, we derive $u_{i+1}=v_i-u_i$. Hence $u_{i+1}=u_i-c$. From this recurrence relation we get $u_i=u-(i-1)c$, where $u$ is defined as $u=u_1=y_1-y_2$.

So we now have the simpler recurrence relation: $y_{i+1}=y_i-u_i=y_i-(u-(i-1)c)$, i.e., $y_{i+1}=y_i-u+(i-1)c$, from which we get
\begin{align}
 y_i&=y_1+\sum_{k=1}^{i-1}{u_k} \\
 &=y_1+\sum_{k=1}^{i-1}{-u+(k-1)c} \\
 &=y_1-(i-1)u+c\sum_{k=0}^{i-2}{k} \\
y_i&=y_1-(i-1)u+c\frac{(i-2)(i-1)}{2}
\end{align}
This last formula is valid for $i\in[1,n-1]$, since the recurrence formula is defined for $y_{i+1}$ and the equations used were defined for all values of $i$ up to $n-2$.
We must now consider $y_n$. Since $v_{n-2}-u_{n-2}=u_{n-2}-c$, we get $y_n=y_{n-1}-(u_{n-2}-c)$.
Since $u_{n-2}=u-(n-3)c$, we finally obtain
$\begin{align}
 y_n&=y_1-(n-2)u+c\frac{(n-3)(n-2)}{2}-u+(n-3)c+c \\
 &=y_1-(n-1)u+c\frac{(n-2)(n-1)}{2}
\end{align}
$

Hence our formula for $y_i$ is correct for all $i\in[1,n]$.

Note: a much simpler technique for $y_n$ would be to consider an extra point at $y_{n+1}$ on the curve, so as to have more equations. But all this was already written when I thought of it.

Considering that we have the last constraint $y_n=f(b)$, we can use it
with the equation for $y_n$ to determine $u=y_1-y_2$ if we wish to
choose $c$, or to determine $c$ if we rather choose $u$.

This is easily rephrased into the result given at the beginning of this answer. Then it should be easy to apply it to the example in the
question.
However, I do wonder whether all this is useful, because I am not sure this is the question you intended to
ask.

The reason is that the formula given in the question is not the formula of the finite
second derivative. The proper formula is something like:
$$4\times\frac{f(x_{i-1})-2f(x_i)+f(x_{i+1})}{(x_{i+1}-x_{i-1})^2}$$

See for example higher-order finite differences in wikipedia. Though I am not sure that even this corrected formula is meaningful as, the formula normally given assumes that $x_i= (x_{i-1}+x_{i+1})/2$. But the expression you use is somewhere between the formulae for forward and backward finite differences, and should thus be usable with some meaning.

Thus, if I am correct, you should edit your question to make it consistent, either by
removing the reference to the finite
second derivative, or by using the proper formula for it.


Comparing the efficiecy of 2 run times I have a heap with $n$ elements.
$k$ represent a number that is the height of one of the elements in the tree.

I need to compare two run times and prove what i claim.

The 2 run times are:
$$
(1)O(\lg n \cdot (\lg n - k))
$$

And:
$$
(2)O(2^k \cdot \lg n)
$$

Where:
$$
\lg n - k
$$
Is a constant value.

For the first run time formula, its seems that we get: $O(\lg n)$

But how do i find the run time (and prove) for the second run time?

Thanks.

$\log(n)-k$ is const $\implies$ $2^{\log(n)-k}$ is const $\implies O(2^{k} \cdot \log(n)) = O(2^{\log(n)-k} \cdot 2^{k} \cdot \log(n)) = O(2^{\log(n)} \cdot \log(n)) = O(n \cdot \log(n))$


Vertex coloring with an upper bound on the degree of the nodes Consider the set of graphs in which the maximum degree of the vertices is a constant number $\Delta$ independent of the number of vertices. Is the vertex coloring problem (that is, color the vertices with minimum number of colors such that no pair of adjacent nodes have the same color) on this set still NP-hard? Why?

Yes, it's still NP-hard. 3-COL is still NP-complete for planar degree 4 graphs [1].

Dailey, D. P. (1980), "Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete", Discrete Mathematics 30 (3): 289–293, DOI:10.1016/0012-365X(80)90236-8


Why are so many internet protocols text-based? From what I have found, a very large amount of protocols that travel over the internet are "text-based" rather than binary. The protocols in question include, but are not limited to HTTP, SMTP, FTP (I think this one is all text-based?), WHOIS, IRC.
In fact, some of these protocols jump through some hoops whenever they want to transmit binary data.
Is there a reason behind this? Text-based protocols obviously have a bit of an overhead as they require sending more data to transmit the same amount of information (see example below). What benefits outweigh this?

By text-based, I mean most of the characters used in the protocol are between 0x20 (space) and 0x7E (~), with the occasional "special character" used for very special purposes, such as the newlines, null, ETX, and EOT. This is opposed to transmitting raw, binary data over the connection.
For instance, transmitting the integer 123456 as text would involve sending the string 123456 (represented in hex as 31 32 33 34 35 36), whereas the 32-bit binary value would be sent as (represented in hex) 0x0001E240 (and as you can see, "contains" the special null character.

When the world was younger, and computers weren't all glorified PCs, word sizes varied (a DEC 2020 we had around here had 36 bit words), format of binary data was a contentious issue (big endian vs little endian, and even weirder orders of bits were reasonably common). There was little consensus on character size/encoding (ASCII, EBCDIC were the main contenders, our DEC had 5/6/7/8 bits/character encodings). ARPAnet (the Internet predecessor) was designed to connect machines of any description. The common denominator was (and still is) text. You could be reasonably certain that 7-bit encoded text wouldn't get mangled by the underlying means to ship data around (until quite recently, sending email in some 8-bit encoding carried a guarantee that the recipient would get mutilated messages, serial lines were normally configured as 7-bit with one bit parity).

If you rummage around in e.g. the telnet or FTP protocol descriptions (the first Internet protocols, the network idea then was to connect remotely to a "supercomputer", and shuffle files to and fro), you see that the connection includes negotiating lots of details we take as uniform,

Yes, binary would be (a bit) more efficient. But machines and memories (and also networks) have grown enormously, so the bit scrimping of yore is a thing of the past (mostly). And nobody in their right mind will suggest ripping out all existing protocols to replace them with binary ones. Besides, text protocols offer a very useful debugging technique. Today I never install the telnet server (better use the encrypted SSH protocol for remote connections), but have to telnet client handy to "talk" to some errant server to figure out snags. Today you'd probably use netcat or ncat for futzing around...


What is the period of N xored identical random number generators, with differing seeds? This question is a kinda spin off from Why do we not combine random number generators?

If for example we had N identical type random number generators, with N different seeds, what would the period be if their outputs were xored together?  Would it be period, N x period or period (power N)?

So a numerical example would be:

2 linear feedback shift registers of 10 bits.

1 LFSR's period = 1023.

2 xored LFSRs' period = 1023, 2046 or 1046529?

(I have a sense that it's period but I can't overcome that fact that the state size is so much bigger.)

I will assume the N random generators have independent seeds and states.  Suppose their periods are $t_1,\dots,t_N$.  Then the period of their xor is a divisor of $\operatorname{lcm}(t_1,\dots,t_N)$.  Typically, it will be exactly $\operatorname{lcm}(t_1,\dots,t_N)$, but I don't know whether that is guaranteed in all cases.

If all $N$ generators have the same period $t$, then the period of their xor is a divisor of $t$ (and thus cannot be any larger than $t$).


Is there an analog of "regular" for infinite strings? Consider the sequence $s_1 = (1, 0, 1, 0,\dots)$.  It seems "regular" in a way that, e.g. $s_2 = (1, 2, 3, 4,\dots)$ is not.

I'm not sure how to formalize this intuition though. One thing which jumps out at me is that $L =\{(0 1)^n\}$ is a regular language, and $s_1$ is in some sense the limit of the strings in this language.

Is there a terminology for considering these infinite strings? Do we have something analogous to the pumping lemma, whereby we can state that any such "infinite regular" string is of the form $x y^ {\infty}z$ with $x$, $y$, $z$ finite?

Probably the most specific term to describe your first string, $010101\dots$ is periodic. A string $x_1x_2\dots$ (finite or infinite) is periodic if there is some $t$ such that, for all $i$, $x_i=x_{i+t}$. In the case of this example, we can take $t=2$. A slightly weaker notion is that a string is eventually periodic if there are $n$ and $t$ such that $x_i=x_{i+t}$ for all $i\geq n$.

More generally, though, there is a direct analogue of the regular languages, which is the $\omega$-regular languages. These are recognized by natural generalizations of finite automata. The state set is still finite but the acceptance criterion must be modified to deal with infinite words – in particular, we can't just say "Accept if the automaton finishes in an accepting state" because the automaton never finishes processing its infinite input.

The simplest class of automata for infinite words are Büchi automata. They are defined exactly like the finite automata you're used to, and they accept their input if at least one accepting state is visited infinitely often during the automaton's run. One difference from ordinary finite automata is that it turns out that nondeterministic Büchi automata are more powerful than deterministic ones, and the $\omega$-regular languages are the ones accepted by nondeterministic Büchi automata.  Other sensible acceptance criteria lead to other automaton models which accept the same class of langauges.

Note that it doesn't quite make sense to write $xy^\omega z$, since you can't have anything after an infinite sequence of $y$s. At least, you can't if the positions in your string are indexed by the natural numbers. If they're indexed by larger ordinals this can make sense.

I can't actually remember if there's an analogue of the pumping lemma for $\omega$-regular languages. This is slightly embarrassing, though it is most of a decade since I taught a graduate class on this stuff.


Is it possible to decide if a given algorithm is asymptotically optimal? Is there an algorithm for the following problem:

  Given a Turing machine $M_1$ that decides a language $L$,
  Is there a Turing machine $M_2$ deciding $L$ such that
  $t_2(n) = o(t_1(n))$?

The functions $t_1$ and $t_2$ are the worst-case running times of Turing machines $M_1$ and $M_2$ respectively.

What about space complexity?

Here is a simple argument to show that they are undecidable, i.e. there are no algorithms to check if a given algorithm is optimal regarding its running-time or memory usage.

We reduce the halting problem on blank tape to your problem about running-time optimality.

Let $M$ be a given Turing machine. Let N be the following Turing machine:

$N$: on input $n$
1. Run $M$ on blank tape for (at most) $n$ steps.
2. If $M$ does not halt in $n$ steps, run a loop of size $2^n$, then return NO.
3. Otherwise, return YES.

There are two cases:

If $M$ does not halt on blank tape, the machine $N$ will run for $\Theta(2^n)$ steps on input $n$. So its running time is $\Theta(2^n)$. In this case, $N$ is obviously not optimal.
If $M$ halts on blank tape, then machine $N$ will run for constant number of steps for all large enough $n$, so the running time is $O(1)$. In this case, $N$ is obviously optimal.

In short:

$$M \text{ halts on blank tape } \Leftrightarrow N \text{ is optimial }$$

Moreover given the code for $M$ we can compute the code for $N$. Therefore we have reduction from halting problem on blank tape to running-time optimality problem. If we could decide if a given Turing machine $N$ is optimal, we could use the above reduction to check if a given machine $M$ halts on blank tape. Since halting on blank tape is unecidable your problem is also undecidable.

A similar argument can be used for space, i.e. it is also undecidable to check if a given Turing machine is optimal regarding the space it uses.

Even a stronger statement is true: we can't decide if a given computable function is an upper-bound on the time complexity of computing a given computable function. Similarly for space. I.e. even basic complexity theory cannot be automatized by algorithms (which can be considered a good news for complexity theorists ;).


Are all computer viruses man-made? I'm curious if the origin of any successful computer virus is known to NOT have an intentional, human originator.  To put it another way, do computer viruses ever "spontaneously" originate through the process of natural selection in the same way biological viruses originate; without an intentional "designer?"

I imagine (though I'm not sure) that it's possible for sufficiently knowledgable software engineer to make use of software engineering tools like neural networks, genetic algorithms, adversarial networks, etc to write a virus according to his/her specifications, but that's not what I want to know.  I want to know if computer viruses ever begin on their own, and if they don't, why not?

The three core tenets of evolution by natural selection are descent with modification, variable fitness, and resource limitation. Some scientists say that wherever these conditions are in place, evolution occurs necessarily.  Importantly, being alive is not a prerequisite, which is why biological viruses continue to evolve even though they are not technically alive.  Richard Dawkins says that thoughts and ideas survive and proliferate through the same mechanism.  So, does computer code ever evolve organically without human intervention to form a successfully self-replicating entity?  If not, why not?

Interesting question. I think the biggest barrier preventing something like that from happening is that computers are engineered to be extremely robust to random, non-human errors. Computers will do what programmers instruct them to do, and unless the hardware is being pushed beyond its limits or subjected to extreme environments like cosmic radiation in space, they do not deviate from programmer instruction.

It is necessary for computers to have these near-zero error rates due to the sheer quantity of operations they perform. An error rate of one in a million seems pretty good...until you consider that a modern desktop computer is capable of performing about 100 billion operations per second. A one in a million error rate  would result in 100,000 errors per second, rendering your computer completely unusable due to constant crashes!

The same reasoning applies to storage mediums as well. If you assume that one in a million bits stored on a 1TB drive gets corrupted every day, then that would result in 360 megabytes of corrupted data per year!

The necessary low error rates are achieved through a combination of robust engineering and manufacturing, as well as software tricks to detect and repair errors such as checksums and error-correcting codes. In situations where these measures are insufficient, such as on spacecraft computers where cosmic radiation can wreak havoc, fully redundant computers check each others' results though voting.

Therefore I'd argue that "descent with modification" doesn't really exist here. Computers operate more or less deterministically and without error by design, so it would be very difficult for an unexpected program to spontaneously emerge.

If we designed computers that were much more error-prone, then it would be more likely that such an event could happen. But such a computer is also likely to be pretty useless, so we don't build computers like that.


How can I make my algorithm more efficient? I came across an algorithmic problem. I do not know how to do it optimally.
The problem is as follows:

There is an increasing array $A$ of size $n_1$

There is an array $M$ of queries of size $n_2$
where $1 \le n_1, n_2 \le 10^7$

For each query element $m \in M$, it is required to find the count of elements in array $A$ that are strictly less than the query element $m$.
For example:

$A = [1,2,3,5]$
$M = [4,2]$
for $m = 4$ answer $3$
for $m = 2$ answer $1$

My idea works for a $O(nlogn)$. The algorithm is simple; for each request I do a binary search in array $A$. But can it be faster? Maybe B-tree?

If values in both arrays are positive integers, there is an algorithm in $O(n_1 + n_2 + \max(A))$. This algorithm is interesting if those three values are of the same order of magnitude.
The steps are as follow:

check last element of $A$ to know $\max(A)$;
create an array $B$ of size $\max(A)$;
browse $A$ and modify $B$ so that $B[i]$ represents the smallest index $j$ such that $A[j] \geq i$ (that means the number of elements of $A$ that are $<i$);
browse $M$; for $m \in M$, if $m > \max(A)$, return $n_1$, else return $B[m]$.


Detecting palindromes in binary numbers using a finite state machine In my first algorithms class we're creating these patterns that are supposed to model a finite state machine. We were given a task to think if we can figure out a way to detect palindromes in binary sequences (no points if we do, it's just a food for thought).

I specifically asked the professor, knowing a little about CS and that palindromes aren't regular, and that a finite state machine can only detect a regular language. But his answer surprised me, since he said that it is indeed possible and that he thinks we should be able to come up with a sotluion.

This brings two questions:

Maybe the binary sequence is a special type of palindrome that is regular? (I'm a little fuzzy on this)
Or the technique we're using to represent the state machine is more powerful than I think.

In case it's 2), I'll try to explain how we're representing the problem.

Imagine a finite wall, which is supposed to be filled with a predefined types of tiles. Each tile has four colors

You can design any tile you want, and as many as you want, but there has to be a finite number of tiles. They can be arranged in a single row, or into multiple rows, but the topmost row has to always match against the 0 and 1 colors. The end colors of the wall also have to be defined ahead of time, and the tiles have to match those, and they also have to match the adjacent tiles.

Here's an example of a pattern that detects a sequence of 01010101...01

The question is, is this pattern more than just modeling a finite state machine? If not, how can I use this to detect palindromes?

Update: There has to be a finite number of tile designs, and the number of tiles has to be finite as well (the input will always be finite as well). As for the rows, there can be an arbitrary number of rows, the only condition is that the tiles on a second row must match in the top color with the tiles on the row above them. The number of colors isn't limited as well, though it can't be infinite.

In a nutshell: As presented, with a single row of tiles, the tiling system is equivalent to a finite state automaton. It cannot recognize the set of palindromes which is context-free, but not regular.
However, if the tiling system is extended, allowing as many rows as needed (possibly with the addition of a column on each side), then it becomes as powerful as a linear bounded automaton, recognizing context-sensitive languages, and thus also palindromes. The last section is a simple set of tiles to recognize palindromes.

Recognizing palindromes with a single row of tiles

Regarding your tiling system, I am missing some
details. Is the number of tiles finite, or just the number of
different tile designs. More precisely, while the number of designs can be finite, i.e. the same for all sequences to be recognized, the number of tiles  of each design should be sufficient in number, which may depend on the sequence to be recognized, though each recognition would use only a finite number of tiles.

If the number of tile is finite, less than some fixed number $n$ that is independent of the sequence to be recognized, you can at
best recognize finite sets of sequences, which is much less than all regular languages.

Second point:  is the number of different colors
can be set at any value, the same for all sequences of the language to be recognized. If not you cannot recognize all regular languages.

If you have any number of tiles, finite number of designs, any number
of colors, that is indeed equivalent to finite state automata, where
the colors stand for the states, and the tiles stand for the
transitions.

I am assuming you have only a single row of tiles, with the blue at bottom, as seems to be implied by your drawing.

I do wonder whether It helps understanding. Maybe so?

As you said, palindromes do not form a regular set. One disputable
intuitive explanation is that palindrome recognition implies counting,
and finite state machines cannot count. But there are formal ways of
proving that.

The language of palindromes is actually a Context-Free (CF)
language. Context-free languages are strictly a superclass to regular
languages recognized with finite state automata. So any regular
language is context-free, but the converse is false. For example the
language of palindromes is CF but not regular.

Thus, palindromes cannot be recognized with a single row of tiles.

What more could be said.

Finite state automaton (FSA) is implicitely the name of a device that
has only a finite number of states, used to control a reading head
that read-input from left to right on a tape, without ever leaving the
input string area, and never writes.

Finite state machines are usually considered as doing the same, except
that some can also write on an output tape.

If we are not too attached to established terminology, we could try to
relax some of these constraints, while keeping the finite number of
states.

A first attempt could be to allow the head to move in any direction.

That gives you what is called a two-way finite state automata. They
seem more powerful, but it can be proved that they do no more than
FSA (whether deterministic or not).

Another possibility is to allow the automaton to overwrite the tape it
is reading, but still without ever leaving the area that was occupied
by the input string. This is called a linear bounded automaton
(LBA). The LBA is actually one of the most powerful automata there
is. They recognize all the context-sensitive (CS) languages, which
include the CF languages.

The problem is that they are so powerful that they are difficult to
control, analyze or use.  But they will recognize palindromes with a
finite number of states.

I have been excluding other type of automata which do have a finite number of state for control, but use unlimited memory, which one could perceive as having unbounded number of states.

Extending the tiling system

In FrankW's answer, it is shown that, by extending the tiling system
with several rows, one can recognize palindromes. He has there a very
interesting idea, which I am trying to push here.

It can be pushed further. If you allow an arbitrary number of rows,
and add a column on each side, it seems that the tiles can actually
mimic a linear bounded automaton.  Hence, it becomes a very powerful
computational system.

I am saying "it seems" because I did not go through all the tedious
details of the construction, but only tried to convince myself.

However, rather than go through even the basic aspects of the construction, which are already complex, I
will rely on existing results in automata theory.

A row of tiles may be seen as the configuration of a one-dimensional
bounded cellular automaton (BCA). Columns represent the evolution of individual cells.

The colors of left and right sides of tiles represent the information exchanged
between adjacent cells, while the top and bottom colors represent the state
of the cells before and after transitions.

So it seems that a BCA can be simulated by the extended tiling system.

David Milgram showed in 1976 that BCA can simulate a LBA.

Hence the extended tiling system can simulate a LBA.

The extended tiling system is therefore a very powerful computational
system, that can recognize context sensitive languages.

Hence the extended tiling system can recognize palindromes, among many other things.

Now, I am not giving you the details of the recipe to recognize palindromes and other things in this way, simply because it is very complicated, and no one would read it anyway, if I were able to write it without bugs.

A set of tiles to recognize palindromes

The general construction is far too complex to be used. However, here
is a simple set of tiles to recognize palindromes on the alphabet
$\{0,1\}$ as requested.

As one might expect it is symmetrical.

R and B stand for red and blue

Matching leftmost and rightmost symbol 1, and removing them

 1      1      0     1
R 1    1 1    1 1   1 R
 R      1      0     R

Matching leftmost and rightmost symbol 0, and removing them

 0      1      0     0
R 0    0 0    0 0   0 R
 R      1      0     R

Filling in the sides with fully red tiles

 R
R R
 R

Creating the bottom line in blue

 R
R R
 B

But this has nothing to do with finite state machines, as far as I can tell.


binary representation of ip prefixes How does an ip prefix

90.0.0.0/4

translate to

0101∗

in binary

and

10.0.0.0/2

to this:

00*

I'm trying to understand it since a while now but I am unable to derive the logic.

For a netmasked IP address xxx.xxx.xxx.xxx/N, convert each xxx octet in the address to binary.  The masked address is the leftmost N bits with all other bits replaced with zeroes.

So 10.0.0.2/2 becomes 00001010 00000000 00000000 00000010 which is then masked to 00000000 00000000 00000000 00000000, because 00 are the leftmost 2 bits.

90.0.0.0/4 becomes 01011010 00000000 00000000 00000000 which is then masked to 01010000 00000000 00000000 00000000, because 0101 are the leftmost 4 bits.


What is the complexity of finding a regular expression equivalent to a given DFA? I had taken a course long ago on complexity theory. I only remember basic things,
so I am reading "Introduction to the Theory of Computation by Michael Sipser". The book in its first chapter introduces DFA and NFA.

If we are given a DFA $D$ where $\sum=\{0,1\}$ ( the alphabets ), then how difficult is the  problem of finding a regular expression of the language that $D$ recognises?

By difficulty I mean to which class does this problem belong like NP,PSPACE etc ( sorry for vague definition of difficulty, I only have a broad understanding of what classes NP,PSPACE etc are as of now ).

"Find an equivalent regular expression" is not a decision problem, so it can not be in any of these classes. See also our reference questions on complexity theory.

There are polynomial-time algorithms that solve your computational problem, though, so it is in some flavor of P.


min-cut with extra condition I have a undirected graph with no edge costs. A subset of the nodes are labeled $c_1, c_2, ..., c_k$ and one node is labeled $K$. I want to find the minimum cut of the graph with the extra condition that all nodes $c_i$ are in the same half of the cut and the node K is in the other cut.

My idea was to begin by doing a BFS from $K$ to all nodes $c_i$, saving predecessors and then finding all paths from $K$ to a node $c_i$ and finally picking the minimum set of edges from the paths so that at least one edge from each path was chosen. Unfortunately, if I understand this correctly, this is equivalent to the NP-complete set cover problem.

Is there  anything sane with this approach? Do you have any hints to push me in the right direction?

Note: this is homework so I'd rather have some hints than a full solution.

We'll use the max-flow min-cut theorem to solve this.

Therefore we map each instance $(G,K,\{c_{1},\dots,c_{k}\})$ to the network $N:=(V(G) \stackrel{.}{\cup} \{C\},E(N),e,K,C)$, where $C$ is a new vertex not in $V(G)$ (our sink), $K$ is our source and $e$ denotes the edge capacities,

$$E(N) := \{(u,v)|\{u,v\}\in E(G)\} \cup \{(c_i,C)|i\in\{1,\dots,k\}\}$$ and
$$e((u,v)) := \begin{cases}2|E(G)|+1&v=C\\1&\text{else} \end{cases}\qquad.$$

Then $(V_1,V_2)$ is a minimum $K$-$C$-cut in $N$ if and only if $(V_1,V_2\setminus\{C\})$ is  minimum cut in $G$ subject to the condition that $K\in V_1,\forall i: \, c_i\in V_2$:

"$\Rightarrow$": Every $K$-$C$-cut with the property $\forall i: \, c_i\in V_2$ has a capacity of at most $2E(G)$, every cut with $\exists i: \, c_i\in V_1$ has capacity of at least $2E(G)+1$. Therefore only those having the desired property can be a minimum cut. Since for each $(u,v), u\in V_1, v \in V_2$ of a minimum cut the edge capacity is $1$, $\mathrm{cap}(V_1,V_2)=||\{\{u,v\}\in E(G)|u\in V_1,v\in V_2\}||$.

"$\Leftarrow$": analogous to second part of "$\Rightarrow$".

If we have computed a maximum flow $f$ by e.g. the Edmonds–Karp algorithm, we compute the residual Network $N_f$ where $e(N_f)=e-f$ and $E(N_f)=E(N)\setminus\{(u,v)|f((u,v))=1\}$, i.e. we remove the edges used by the maximum flow. Let $V_1$ be the set of vertices reachable from $K$ in $N_f$ and $V_2=V(G)\setminus V_1$. Then $(V_1,V_2\cup\{C\})$ is a minimum cut in $N$ and thus $(V_1.V_2)$ is a minimum cut in $G$ separating $K$ and $\{c_1,\dots,c_k\}$.


Modification of dynamic programming for a knapsack problem We have the following recursive function for the dynamic programming problem for a knapsack problem:

\begin{align}
V(i,w)=&max[ V(i-1,w), v_i +V(i-1,w-w_i)], \quad 1\leq i \leq n, 0\leq w \leq W \\
\end{align}
and $V(0,w)=0$.

But is it possible to add a constraint on the items to this function? If we for instance only are allowed to put one of the items 1 or 2 in: $x_1 + x_2 \leq 1$? And how to do this?

Apply the golden rule of DP (that is how I name it), namely, adding another parameter to the subproblems/object function when there is an extra condition or dimension of freedom. This rule is simple and powerful, yet it can be overlooked by DP beginners and sometimes experienced guys.

In this particular question, instead of $V(i,w)$, define $V(i,w,c)$, where $V(i,w,0)$ means no item 1 and no item 2,  $V(i,w,1)$ means one item, and  $V(i,w,2)$ means one item 2. Rewrite the recurrence relation accordingly. Compute the values either recursively or iteratively with memoization. Select the desired result among possible candidates.

This answer can be seen as a formalization of @fade2black's answer, although I had/have been calling/using the golden rules too many times in my DP adventure.


Number of minimum cuts in a graph Situation :

I started watching Algorithm Lectures from Stanford University (Corsera). I stuck on one video lecture(https://www.coursera.org/lecture/algorithms-divide-conquer/counting-minimum-cuts-96RUg).
In the lecture the professor is proving largest number of minimum cut in a graph.

My Problem :

To prove largest number of minimum cut in a graph. Prof. first stared proving Lower Bound. To get a lower bound he took a cyclic graph. My confusion is why he took cyclic graph?

My way of Thinking :

To get a lower bound we need to select the best case input (like for selection sort best case input will be an sorted array) and here Prof. was selected cyclic graph as an input but it doesn't seems to be the best case input. Like if we choose a star (https://en.wikipedia.org/wiki/Star_(graph_theory)) we could have easily get a lower bound which is n-1.

I don't know the lecture you are referring to, but I do know the topic.

In this case "lower bound" is meant in an existential sense.
That is, for every sufficiently large $n$, there exists a graph $G$ on $n$ nodes such that the number of minimum cuts in $G$ is $\binom{n}{2}$. In particular $G$ is a cycle on $n$ nodes.

The easiest way to see why this definition of lower bound is interesting is to think of upper bounds first.
It is possible to show that the number of minimum cuts in any graph with $n$ nodes is at most $\binom{n}{2}$. Then one natural question is whether this upper bound is tight or whether it can be improved.

Your lower bound answers the above question: it is not possible to prove any upper bound smaller than $\binom{n}{2}$ since there is always at least one graph on $n$ nodes for which there are at least $\binom{n}{2}$ minimum cuts.

Note that, in this sense, the lower bound of $n-1$ that you can obtain by considering a star is a worse lower bound than the one you obtain by considering a cycle.

To summarize: an existential lower bound of $f(n)$ means that, in general, there can be no better upper bound than $f(n)$. Often times you'll find that lower bounds are expressed using asymptotic notation. A lower bound of $\Omega(f(n))$ means that there can be no upper bound better than $c f(n)$ for some constant $c>0$.


Discrete solution space in NP-complete problems While there are many known NP-complete problems, they all seem to be discrete in the solution space. What is the underlying principle for this?

It could appear to be the case that "discrete problems" are hard while "continuous problems" are easy. In fact, the exact question has already been asked on TCS.SE here. The answers list some continuous problems that area actually hard to solve.

As usual, computational problems come in all colors, shapes, and sizes. It is not a rule that continuous problems are always easy. In this sense, there is no "underlying principle". I think the following comment by Sasho Nikolov puts it well:

  I think the whole discrete vs continuous thing is a red herring. A problem has to have very special structure to be efficiently solvable. I think the real difference here is that in the case of easy continuous problems the special structure tends to be convexity, while in the case of easy discrete problems things look more complicated: sometimes the structure is submodularity or matroid intersection, but often it's not. This probably has more to do with the fact that we don't yet understand discrete math very well.


What's the average number of transistor switches needed to do an N-bit x N-bit multiply? I want to know how switch-efficient a multiplier can be. If I need to do many $N$-bit by $N$-bit multiplies, and each bit is determined by flipping a coin, what's the average number of transistor switches that will be required per multiply, in terms of $N$?

I haven't edited my question, but in case others are here: this thesis addresses the question I was intending (https://core.ac.uk/download/pdf/52104064.pdf), finding e.g. 1189 average transitions required for a certain architecture for a 16-bit by 16-bit multiply that's completely random bits.
\


How to verify number with Bob without Eve knowing? You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number?

Note: This question is on a list of "google interview questions". As a result, there are tons of versions of this question on the web, and many of them don't have clear, or even correct answers.

Note 2: The snarky answer to this question is that Bob should write "call me". Yes, that's very clever, 'outside the box' and everything, but doesn't use any techniques that field of CS where we call our hero "Bob" and his eavesdropping adversary "Eve".

Update:
Bonus points for an algorithm that you and Bob could both reasonably complete by hand.

Update 2:
Note that Bob doesn't have to send you any arbitrary message, but only confirm that he has your correct phone number without Eve being able to decode it, which may or may not lead to simpler solutions.

First we must assume that Eve is only passive. By this, I mean that she truthfully sends the card to Bob, and whatever she brings back to Alice is indeed Bob's response. If Eve can alter the data in either or both directions (and her action remains undetected) then anything goes.

(To honour long-standing traditions, the two honest parties involved in the conversation are called Alice and Bob. In your text, you said "you". My real name is not "Alice", but I will respond just as if you wrote that Alice wants to verify Bob's phone number.)

The simple (but weak) answer is to use a hash function. Alice writes on the card: "return to me the SHA-256 hash of your phone number". SHA-256 is a cryptographic hash function which is believed to be secure, as far as hash functions go. Computing it by hand would be tedious but still doable (that's about 2500 32-bit operations, where each operation is an addition, a word shift or rotate, or a bitwise combination of bits; Bob should be able to do it in a day or so).

Now what's weak about that ? SHA-256, being a cryptographic hash function, is resistant to "preimages": this means that given a hash output, it is very hard to recover a corresponding input (that's the problem that Eve faces). However, "very hard" means "the easiest method is brute force: trying possible inputs until a match is found". Trouble is that brute force is easy here: there are not so many possible phone numbers (in North America, that's 10 digits, i.e. a mere 10 billions). Bob wants to do things by hand, but we cannot assume that Eve is so limited. A basic PC can try a few millions SHA-256 hashes per second so Eve will be done in less than one hour (less than 5 minutes if she uses a GPU).

This is a generic issue: if Bob is deterministic (i.e. for a given message from Alice, he would always return the same response), Eve can simulate him. Namely, Eve knows everything about Bob except the phone number, so she virtually runs 10 billions of Bobs, who differ only by their assumed phone number; and she waits for one of the virtual Bobs to return whatever the real Bob actually returned. The flaw affects many kinds of "smart" solutions involving random nonces and symmetric encryption and whatsnot. It is a strong flaw, and its root lies in the huge difference in computing power between Eve and Bob (now, if Bob also had a computer as big as Eve's, then he could use a slow hash function through the use of many iterations; that's more or less what password hashing is about, with the phone number in lieu of the password; see bcrypt and also this answer).

Hence, a non-weak solution must involve some randomness on Bob's part: Bob must flip a coin or throw dice repeatedly, and inject the values in his computations. Moreover, Eve must not be able to unravel what Bob did, but Alice must be able to, so some information is confidentialy conveyed from Bob to Alice. This is called asymmetric encryption or, at least, asymmetric key agreement. The simplest algorithm of that class to compute, but still reasonably secure, is then RSA with the PKCS#1 v1.5 padding. RSA can use $e = 3$ as public exponent. So the protocol goes thus:

Alice generates a big integer $n = pq$ where $p$ and $q$ are similarly-sized prime integer, such that the size of $n$ is sufficient to ensure security (i.e. at least 1024 bits, as of 2012). Also, Alice must arrange for $p-1$ and $q-1$ not to be multiples of 3.
Alice writes $n$ on the card.
Bob first pads his phone number into a byte sequence as long as $n$, as described by PKCS#1 (this means: 00 02 xx xx ... xx 00 bb bb .. bb, where 'bb' are the ten bytes which encode the phone number, and the 'xx' are random non-zero byte values, for a total length of 128 bytes if $n$ is a 1024-bit integer).
Bob interprets his byte sequence as a big integer value $m$ (big-endian encoding) and computes $m^3 \mathrm{\ mod\ } n$ (so that's a couple of multiplications with very big integers, then a division, the result being the remainder of the division). That's still doable by hand (but, there again, it will probably take the better part of a day). The result is what Bob sends back to Alice.
Alice uses her knowledge of $p$ and $q$ to recover $m$ from the $m^3 \mathrm{\ mod\ } n$ sent by Bob. The Wikipedia page on RSA has some reasonably clear explanations on that process. Once Alice has $m$, she can remove the padding (the 'xx' are non-zero, so the first 'bb' byte can be unambiguously located) and she then has the phone number, which she can compare with the one she had.

Alice's computation will require a computer (what a computer does is always elementary and doable by hand, but a computer is devilishly fast at it, so the "doable" might take too much time to do in practice; RSA decryption by hand would take many weeks).

(Actually we could have faster by-hand computation by using McEliece encryption, but then the public key -- what Alice writes on the card -- would be huge, and a card would simply not do; Eve would have to transport a full book of digits.)


Programming question for a new approach There is a matrix of size (M x N) in which the cells are marked by one of the three letters (either 'a','b' or 'c'). Now given that there is only one cell that is marked with value 'a' but more than one cells can be marked with value 'b' or 'c'.

There is 8 ways in which one can move form one cell to another, considering rowwise, columnwise, diagonal and anti-diagonal movements to the next cell. taking the cell marked by 'a' as starting cell and cells marked by 'c' as destination cells. The length of a route is defined as the total number of steps taken while moving from starting to a destination cell without going through the cells marked by value 'b'.

What is the minimum length of the route for a given matrix with all the cells properly marked with values either 'a','b' or 'c'?  I tried using the recursive implementation which basically is taking long time (as it checks all the 8 directions and then it gives the best of them). Can I get a better solution approach may be through DP? Any help is greatly appreciated.

Construct a graph in which the vertices are all cells not marked 'b', and in which two vertices are connected if they are adjacent in the matrix. Use BFS from the 'a' vertex to go over all vertices in order of distance from 'a', until you find the first 'c' vertex. The overall complexity is $O(MN)$.


Non-trivial bin-packing instance with 5 objects Bin packing problem is a problem, where one has to find the minimum number of bins of size $v$ required to store $n$ objects of sizes $s_1, \ldots, s_n$. Object sizes are never greater than $v$.

For example, if $v = 10$ and the objects sizes are $2, 5, 4, 7, 1, 3, 8$, we can store objects with 3 bins: [8, 2], [7, 3], [5, 4, 1], but not with 2 bins or less, as this would leave some items unpacked. Therefore 3 is the minimum number of bins required.

The best-fit-decreasing heuristic is a packing strategy, which aims to produce a packing close to optimal. It first sorts all the items in descending order. Then it iterates over all items, and for each item attempts to find an existing bin, which can both fit the item and whose spare capacity is closest to the size of the item. If such bin exists, it puts the object in the bin. If it doesn't, it creates a new bin and puts it there.

A non-trivial bin-packing instance is an instance of the problem, which can't be optimally solved by the best-fit-decreasing heuristic.

For example, the instance $v = 7$, $n=6$ where sizes are $3, 2, 3, 2, 2, 2$ is non-trivial, because the best-fit decreasing heuristic will:

Sort the items to give $3, 3, 2, 2, 2, 2$
Put the first two items in the first bin, producing a bin $[3, 3]$
Put the next three items in the second bin, producing a bin $[2, 2, 2]$
Put the last item in the third bin, producing a packing $[3, 3], [2, 2, 2], [2]$

This is a valid packing, but non-optimal, as it requires 3 bins, and there exists a valid packing with two bins: $[3, 2, 2], [3, 2, 2]$.

Is there a non-trivial bin-packing instance with $n=5$?

Let's look at two algorithms: Best Fit Ordered, and First Fit Ordered. Both take the items in descending order and put them into a non-empty bin if possible, or into a new empty bin if they don't fit into any existing bin. Best Fit Ordered puts an item into the filled bin with least available space, First Fit Ordered puts an item into the first filled bin with enough space.

Question: Are there five items A ≥ B ≥ C ≥ D ≥ E such that BFO or FFO are not optimal?

If all items fit into one bin then BFO and FFO will fit them into one bin, because both will just put items in the first bin. Both are optimal.

If five bins are optimal then BFO and FFO cannot be non-optimal, since they can't use more than five bins.

If four bins are optimal then there are two items fitting into one bin, therefore D and E fit into one bin, therefore when BFO and FFO finally try to find a bin for E, either four bins are filled and E fits into the bin with D, or there are only three bins filled and E goes into the fourth bin.

So the only cases to consider are those where two or three bins are optimal. I'll consider cases systematically:

A, B and another fit -> 2 bins, BFO and FFO are optimal
A, B fit, C, D, E fit -> 2 bins, BFO and FFO are optimal
A, B fit, C, D, E don’t fit -> 3 bins required, BFO and FFO are optimal.

We now assume A and B don't fit into a bin, so A goes in the first and B in the second:

A, C and another fit -> 2 bins, BFO and FFO are optimal
A, C fit, B, D, E fit -> 2 bins, BFO and FFO are optimal
A, C fit, B, D, E don’t fit: A, D, E don’t fit, A, D or A, E doesn’t help -> 3 bins required -> BFO and FFO are optimal.

We now assume neither A and B, nor A and C, fit into one bin. If B and C don't fit, then A, B, C go in three different bins. 3 bins are optimal, so D and E can be made to fit, and BFO and FFO will both find a way.

So we assume B and C fit in one bin. Both BFO and FFO will fit them in one bin. D  E must also fit into one bin, so if three bins are optimal, then BFO and FFO will find a solution.

If two bins are optimal, then one bin must contain A, one must contain B and C. D and E fit, so BFO and FFO will fit them.


How can a 32bit CPU have an addressable memory size of 16TB? Frequently, on a 32-bit CPU, each page-table entry is 4 bytes long, but that
size can vary as well.

A 32-bit entry can point to one of $2^{32}$ physical page frames.

If frame size is 4 KB (212), then a system with 4-byte entries can address $2^{44}$ bytes
(or 16 TB) of physical memory.

The above statement is taken from the book "Operating System Principles" by Galvin.

If all 32 bits in a 32-bit CPU are used to refer to pages , then we can have $2^{32}$ pages. But then no more bits will be left to point to memory inside a page of size $2^{12}$ bits since all 32-bits have been used up.

How can we thus say that $2^{44}$ bytes are addressable?

The $32$ bit page frame address acts as a base address and will be typically stored in an index register.

An individual machine code instruction (e.g. a branch instruction) will then contain a $12$ byte bit offset. The offset is added to the base address to create the complete $44$ byte bit address.


Dijkstra's algorithm: why are distances initialized to infinity and not some negative number? I'm a high schooler who has been self-learning graph algorithms for a month or two now.

I was wondering why the distance array in Dijkstra's algorithm is initialized to infinity (INT_MAX in C++) when it could just be set to a negative number? Since Dijkstra's isn't even used for negative numbers, why isn't the distance array set to some arbitrary negative number (say, -1) and instead a very large number which takes up far more space? It's possible that I'm overestimating the space occupied in memory by a very large INT value.

I'd appreciate any constructive feedback.

If you read the algorithm closely, you'll not that edge weight relaxation is triggered if new_weight < old_weight. This comparison is naturally true if all undiscovered edges are initialized with infinity (or, in programming, the largest representable value), and the algorithm correctly picks up the first "real" value it finds.

If you used a negative value, you'd have to treat it as a special case which is a lot less nice.

Note that in classic algorithms, we often disregard the size of the stored numbers (RAM model, uniform cost model). If that is not a good model for your application you have to describe more closely how you represent numbers, and in particular infinity. In practice, you can represent infinity either by a special value that is larger than any number (that's the C++ constant you mention), or you just use the maximum weight you see in the input graph plus one.


How do I simplify $O\left({n^2}/{\log{\frac{n(n+1)}{2}}}\right)$ I'm not very certain about how to deal with asymptotics when they are in the denominator. For $$O\left(\frac{n^2}{\log{\frac{n(n+1)}{2}}}\right)$$, my intuition tells me that it should be treated in a similar way as little o. Would that be correct?

Also, is this in any way comparable with $O(n)$ or $O(n^2)$?

Your expression is

$$ E = \frac{cn^2}{\log \frac{n(n+1)}{2}}$$

where $c$ is some constant. The simple upper bound for $E$ is

$$ E\le c n^2$$

which implies that $\mathcal{O}(n^2)$. For a better bound

$$E  = \frac{cn^2}{\log \frac{n(n+1)}{2}} = \frac{cn^2}{ 2 \log n + \log n - \log 2 } $$

Now it is an easy verification that $E$ is $\mathcal{O}(\frac{n^2}{\log n})$. In other words $E$ is $o(n^2)$(weaker statement as compare to the previous one).


Is there any merging procedure for multiple scenes taking from RGB-D to avoid noise? To avoid the noise as much as possible, I'm planning to take multiple scenes from RGB-D then try to merge them ....

so is there any research papers , thoughts , ideas , algorithms or anything to help

Yes, one technique is known as super-resolution imaging.  There's a rich literature on the subject, at least for RGB images.  You could check Google Scholar to see if there has been any research on super-resolution for RGB-D images (e.g., from 3D cameras such as Kinect, Intel RealSense, etc.).


Unification --- removing equations and updating the solution This question is concerned with the first order unification. Suppose I have a set $D$ of equations and a solution to these equations. Let this solution be a set $S$ of substitutions. Now, suppose I remove some equations from $D$. Is there an algorithm that just uses these removed equations and quickly updates $D$, or the unification
needs to be done from scratch?

(In my application, I tend to have a lot of equations, so that is why I am interested in a solution that does not recompute everything.)

If all you have is the solution to these equations (the most general unifier for $D$), I don't know of any good algorithm for your problem that will be better than "compute the answer from scratch" in general.

However, if you are willing to save some extra information on the side while you are solving $D$, then yes there are methods to do what you want -- with some caveats.  In particular, you can use a persistent union-find data structure to help.  Normally, we'd use union-find for unification (to compute the solution, i.e., the most general unifier).  Here the idea is to instead use a persistent union-find data structure.  This provides the ability to "roll back" some of the union operations and then go forward from there.

See the following research paper:

A persistent union-find data structure.  Sylvain Conchon, Jean-Christophe Filliâtre.  ACM SIGPLAN Workshop on ML, 2007.  See also https://www.lri.fr/~filliatr/puf/ .

Caveats: Their data structure is only semi-persistent, i.e., only partially persistent.  This means you can roll back to an earlier version of the data structure and make modifications from there, but you can't do any more than that.

One consequence is that the efficiency of the above approach will depend upon the order in which you process the equations.  If you want to remove a few equations that were processed near the end and then compute the new solution, this will be very efficient (with the above data structure).  But if you want to remove an equation that was processed near the beginning and then compute the new solution, this will be relatively slow.  In other words, suppose your equations are $D=\{D_1,\dots,D_n\}$ and you compute the solution (most general unifier) by processing the equations in the order $D_1,D_2,\dots,D_n$ (to process an equation you call the Union operation on the union-find data structure).  Now suppose you want to remove equation $D_i$.  With the above partially persistent union-find data structure, you can do this by rolling back the state of the union-find data structure to its state after processing $D_1,\dots,D_{i-1}$, then processing equations $D_{i+1},\dots,D_n$ starting from there.  If $i$ is close to $n$, this will be efficient (it will take $n-i$ Union operations), but if $i$ is small, it won't be much better than just starting from scratch.

In principle if we had a confluently persistent union-find data structure we could remove this limitation.  However, I don't personally know of any efficient confluently persistent union-find data structure.  I'm not sure whether such a thing has been studied in the literature or not; this answer seems to suggest it was an open problem, at least as of 2010.  (Here is a survey on confluent persistence.)


The Entropy of the phrase "Eile Mit Weile" I want to calculate the Entropy of the phrase "Eile mit Weile". I found the probability of each letter as the following

$$P(e)=\frac{4}{12}$$
$$P(i)=\frac{3}{12}$$
$$P(l)=\frac{2}{12}$$
$$P(m)=\frac{1}{12}$$
$$P(t)=\frac{1}{12}$$
$$P(w)=\frac{1}{12}$$

Then I used the formula for entropy
$$H(p_1,...,p_k)=-\sum_{i=1}^{k}p_i\log_2(p_i)$$
$$H(p_1,...,p_k)=-(\frac{4}{12}\log_2(\frac{4}{12})+\frac{3}{12}\log_2(\frac{3}{12})+\frac{2}{12}\log_2(\frac{2}{12})+\frac{1}{12}\log_2(\frac{1}{12})+\frac{1}{12}\log_2(\frac{1}{12})+\frac{1}{12}\log_2(\frac{1}{12}))≈2.355388542 \ Bits$$
But the correct answer is $1.63263$ Bits. I've made a mistake somewhere but can't figure out what I did wrong.

The two answers agree, with the following change: it's 1.63263 nats, not bits. That is, the value 1.63263 is calculated using the natural logarithm.


Number of combinations to put n items into 2 bags I’m currently working on a finger exercise for mit6.00.2x, a MOOC in computaional thinking, and was having some issues.

First of all: don’t worry, I don’t need you to do my homework for me, I just want to clarify an aspect of the question.

So, the original question asked us to program the computer to find all subsets of a list of items to go into a bag. It said that "The number of possible combinations to put n items into one bag is $2^n$."

So far, so good.

However, the extension of the question is to program the computer to output the amount of combinations possible to put n items into 2 bags: an item must be in either bag or neither.

Now we arrive at my question: At this point it is said that there are $3^n$ possible combinations for this, as each item has three possibilities instead of two.

This makes sense, but I actually did the problem with two items and only found seven combinations:

[][1], 2 outside

[1][], 2 outside

[][], 1 and 2 outside

[][1,2]

[2][1]

[1,2][]

[1][2]

So, there are 2 items, there should be $3^2=9$ combinations, but there are only 7.

I'm sure I'm missing something....help!

You forgot the "1 outside" case.

[2][] 1 outside
[][2] 1 outside


Finding number of smaller elements for each element in an array efficiently I am stuck on this problem:

  Given an array $A$ of the first $n$ natural numbers randomly permuted, an array $B$ is
  constructed, such that
  $B(k)$ is the number of elements from $A(1)$ to $A(k-1)$ which are smaller than $A(k)$.

  i) Given $A$ can you find $B$ in $O(n)$ time?
  ii) Given $B$ can you find $A$ in $O(n)$ time?

Here, $B(1) = 0$. For a concrete example:
$$\begin{vmatrix}
  A & 8 & 4 & 3 & 1 & 7 & 2 & 9 & 6 & 5 \\
  B & 0 & 0 & 0 & 0 & 3 & 1 & 6 & 4 & 4 \\
\end{vmatrix}$$

Can anyone help me? Thanks.

The naive algorithm for determining $B$ from $A$:

  For $k=1,\dots,n$, determine the value of $B(k)$ by comparing each $A(i)$ to $A(k)$ for
  $i=1,\dots,k$ and counting those that satisfy $A(i)<A(k)$.

This algorithm compares $A(1)$ to all others ($n-1$ times), $A(2)$ to $n-2$ others, etc. so the total number of comparisons is $\frac{(n-1)(n-2)}{2}$. But that's not the best we can do. For example, looking at $B(n)$, we don't have to do any comparisons! $B(n)=A(n)-1$ because it's the first $n$ natural numbers, and it’s guaranteed (regardless of the permutation) that the $n-1$ lower natural numbers will be there. What about $B(n-1)$? Instead of checking $A(1)$ through $A(n-2)$, we could just check $A(n)$. That is:

  For $k=1, \dots,\frac{n}{2}$, use the algorithm above; for
  $k=\frac{n}{2},\dots,n$ use the reverse algorithm: determine $B(k)$ by
  setting it initially to $A(n)-1$ and then subtracting $1$ for each
  entry $A(i)$ for $i=k+1,\dots,n$ that is less than $A(k)$.

This would take $2\times\frac{(\frac{n}{2}-1) (\frac{n}{2}-2)}{2}=\frac{(n-2)(n-4)}{4}$ steps, which is still $O(n^2)$. Note also that in constructing $A$ from $B$, if $B(n)=A(n)-1$ then $A(n)=B(n)+1$.

But now for more finesse. If we’re allowed some additional space or sort in-place, we can sort the numbers as we’re comparing them. For example:
$$\begin{vmatrix}
  A & 8 & 4 & 3 & 1 & 7 & 2 & 9 & 6 & 5 \\
  S & 9 & 8 & 7 & 4 & 3 & 2 & 1 & 6 & 5 \\
  B & 0 & 0 & 0 & 0 & 3 & 1 & 6 &  &  \\
\end{vmatrix}$$

Instead of checking all of them (or checking them in order), we could use binary search to determine each $B(k)$. However, the sorting still takes time $O(n\log n)$.


Hypothetical question on floating point normalization I've seen a few questions posted regarding the upsides/downsides of floating point formats that have explicit integrals vs. formats that have implicit integrals, but have not seen an answer that really handles my question about it. By integral, I mean the single digit to the left of the radix point.

Let's assume that the hypothetical formats in question both have adequate precision for every possible use they will be put to (so that we can avoid the obvious point that the implicit integral adds more precision in most circumstances).

In one format we have an implicit integral and the requirement that all operation results must be normalized. In the other format we have an explicit integral and do not have the requirement that operation results be normalized. What are the upsides/downsides to this second format in comparison to the first format?

My first observations are that:
1) The format with the explicit integral will have multiple valid representations for a large subset of representable numbers. The format with the implicit integral will have only one valid representation for any given representable number. I don't immediately see a reason why this would be a downside, but I feel like it could be.

2) The format with the explicit integral seems like it would have a marginally simpler hardware or software implementation. This doesn't look like much of an upside unless you are going for really intense performance optimizations, but it ought to be mentioned.

3) The big upside for the explicit integral is that it makes a special arrangement for subnormal numbers unnecessary. Every number that would have fallen into the not-quite-zero gap would just be another representable result with the same gap as between any other pair of results for a given exponent. It seems like this would also slightly simplify design implementations, but I don't take that as a certainty.

Is there anything obvious I'm missing? Anything non-obvious? I'm just trying to really understand this concept better from a purely theoretical CS perspective.

So first off, the implicit digit to the left of the radix point is not called an "integral". That's a very confusing use of that word. But I digress.

Having an unnormalised representation for floating-point numbers may simplify the final step of any basic floating point operation, because you don't need to re-normalise the result. But in turn, the initial steps of just about every floating point operation become more complex.

Let's take division as an example. Most modern floating-point hardware use Goldschmidt's algorithm, which is based on this idea:

Suppose that we want to calculate $\frac{n}{d}$, where $d$ is close to (but not equal to) one. Then we multiply both the numerator and the denominator by $2-d$.

Suppose $d = 1 + \epsilon$, then the new division problem is:

$$\frac{n}{1+\epsilon} = \frac{n(2-d)}{(1+\epsilon)(1-\epsilon)} = \frac{n(2-d)}{1-\epsilon^2}$$

This results in a denominator which is quadratically closer to 1. Repeat this operation until it gets close enough.

So Goldschmidt's algorithm works as follows. To calculate the quotient of two floating point numbers:

$$\frac{m_1 \times 2^{e_1}}{m_2 \times 2^{e_2}}$$

where $m_1$ and $m_2$ are between 1 and 2, we use a lookup table to find an approximation to $\frac{1}{m_2}$, which we will call $R$. Then we calculate:

$$n_1 = m_1 R$$
$$d_1 = m_2 R$$
$$n_{i+1} = n_i (2-d_i)$$
$$d_{i+1} = d_i (2-d_i)$$

and when we have done enough iterations (say $j$), we return:

$$n_j \times 2^{e_1 - e_2}$$

The final step will involve normalisation; $n_j$ will not, in general, be between 1 and 2. So if we could have unnormalised floating point numbers, the final step will be a bit simpler.

But in return, the table lookup operation will be more complex. With normalised numbers, you can just use the first few bits of the significand. ("Significand", incidentally, refers to the part of the mantissa that is actually stored in a normal floating-point number, without the implicit leading 1.)

So in that sense, there is no advantage to having an unnormalised representation for floating-point numbers. What you gain in a simpler final step you lose by having more complex initial steps.


Finding all paths between a set of vertices in a DAG Given a  graph G= (V, E) that is:

directed,
acyclic,
non-weighted,
may have more than one edge between two vertices (thus, source and destination are not enough to determine an edge).

And given a set of vertices, let's  call them vSet; that contains a vertex vRoot; I need to find ALL paths pSet between vSet elements respecting the following:

any vertex that appears as a source for some path in pSet must be reachable from vRoot.
any path in pSet must has its source and destination from vSet, and must not contain any other vertex of vSet.

I've developed an algorithm similar to BFS, that starts from vRoot (according to 1 above),  grow each of the current paths with one edge per an iteration until it reaches another vertex v1 of vSet; then store this reaching path and start growing new set of paths staring from v1.

Here is a pseudo code

output = ∅;
maxLengthPaths = ∅;
1. add all edges that vRoot is there source to maxLengthPaths
2. while size(maxlengthpaths) != ∅ do
  (a) paths := ∅;
  (b) extendedPaths := ∅;
  (c) foreach path p in maxLengthPaths do
    i. if (destination of p in vSet)
      1. add p to output
      2. for each edge e that destination of p is its source
        A. add e to extendedPaths
    ii. else
      1. add p to paths
    iii. for path p1 in paths
      1. for each edge that destination of p1  is its source
        A. extend p1 by a edge and add it to extendedPaths
  (d) maxLengthPaths = extendedPaths

Here are my questions:
1. Is this the best way to achieve my task?
2. I was trying to figure out its time complexity; I found that its exponential of pow(maxNumberOfOutGoingEdgesFormAVertex, maxLengthPath). Is this really the complexity?

Any algorithm for your problem will have to take exponential time in the worst case.  However, if you're willing to live with this, there is a straightforward recursive algorithm to solve your problem.  Details below.

Generalizing a little bit, your problem is essentially the following:

Input: a dag $G=(V,E)$, three sets $S_0,S_1,S_2 \subseteq V$ of vertices

Output: the set of all paths that start some element of $S_0$, end at some element of $S_1$, and all of whose intermediate vertices are from $S_2$

To see the relationship to your problem statement, let $S_0$ be the set of vertices that are reachable from vRoot and also contained in vSet; let $S_1$ be vSet; and let $S_2$ be the complement of vSet.

There is no efficient algorithm for this problem, because in the worst case there could be exponentially many such paths.  Therefore, any algorithm to print all such paths will necessarily have to take exponential time, in the worst case.  Of course you could build algorithms that are efficient on some inputs, but no algorithm will be efficient on all possible inputs.

However if you are willing to live with this limitation, here is an approach you could use.  Basically, it's easy to come up with a recursive algorithm for this problem:

Compute the set $S_0$ of vertices that are reachable from vRoot and are contained in vSet.  This can be found in linear time using DFS or BFS.  You can also compute $S_1$ and $S_2$ in linear time.
Enumerate all paths of the desired form recursively.  We will build a procedure $F$ so that, for a vertex $v \in V$, $F(v)$ returns the set of all paths that start at vertex $v$ and end at some vertex in $S_1$ and where all other nodes (the intermediate nodes) are all within $S_2$.  You can compute $F$ via a simple recursive procedure:

For each $w \in S_2$ such that there is an edge $(v,w) \in E$, compute $F(w)$.
Now we can return $$F(v) = B(v) \cup B'(v) \cup \{v@p : w \in S_2, (v,w) \in E, p \in F(w)\},$$

where $v@p$ denotes the path that starts at $v$, goes to $w$, and then follows the path $p$; and where $B(v),B'(v)$ are defined as follows:

if $v \in S_1$, then $B(v)$ is a singleton set containing the path of length 0 that starts at $v$ and stops there; if $v \notin S_1$, then $B(v)$ is the empty set.
$B'(v) = \{v \to w : w \in S_1, (v,w) \in E\}$.

Finally, calculate $F(v)$ for each $v \in S_0$ and output the union of all of those paths.
For better performance, I recommend that you use memoization to avoid ever calculating $F(v)$ more than once for any particular vertex $v$.

This immediately gives you a recursive algorithm that solves your problem, and whose running time is linear in the size of the graph plus the size of the desired output.  In other words, this algorithm is about as efficient as you could possibly hope for, given the problem statement.


What are the advantages of x86 CPUs over ARM? Now that Apple is switching the MacOS platform to ARM chips, much has been said about the benefits of ARM processors (they save energy, are passively cooled, and the Apple M1 seems to be faster than even an Intel Core i9 processor).
I'd like to know what advantages of the x86 platform are left. Are there any specific circumstances where the x86 CPUs still have the edge? AFAIK they have an much bigger instruction set than the ARM chips. Under what circumstances is the bigger instruction set an advantage, and why?
Note that I'm not asking about a specific software ecosystem like Windows. I know that Windows has many software titles (e.g. games) that don't run (yet) on any ARM platform. That's not the answer I want to hear. An ecosystem advantage like that of Windows is more or less baggage from previous years. It does not necessarily mean that the CPU platform is in any way better, today.

I'll start with the commonly known stuff, that are currently talked about the most.
x86
All x86 processors are developed from the CISC (Complex Instruction Set Computers) architecture. The x86 processors allow you to perform several activities at the same time from a single instruction. Also, they can perform numerous simultaneous tasks without any of them being affected.
This makes them very sophisticated and advanced processors, allowing many complex calculations in a short time. The disadvantage of this design is that they need a lot of power to function and more power means more heat.
Summary: x86 chips are designed to be power hungry and high clocked, multi-thread, high instructions per cycle. In the general use-case they will be a lot faster than your common ARM chip.
ARM
As for ARM processors, they are based on the RISC (Reduced Instruction Set Computer) architecture, which is much simpler than CISC. These processors can do a much smaller number of calculations since they require several commands to act.
RISC instructions are smaller and faster to process, so in part, the disadvantage of having to process several commands for a single action is minimized. Still, ARM processors are much less powerful than the x86.
Summary: ARM chips are designed for low power draw, flexibility, low cost and low heat with good performance.
source of the info above
SoC M1
M1 is not a CPU. It is a whole system of multiple chips put into one large silicon package. The CPU is just one of these chips. And that's the main reason why it's so different and fast compared to the typical ARM chip.
Basically, the M1 is one whole computer onto a chip. The M1 contains a CPU, graphical processing unit (GPU), memory, input and output controllers, and many more things making up a whole computer. This is what is call a system on a chip (SoC).
In the past computers would have multiple physically separate chips on the motherboard of the computer. However because we are able to put so many transistors on a silicon die today, companies such as Intel and AMD began putting multiple microprocessors onto one chip (CPU cores). One core is basically a full independent chip that can read instructions from memory and perform calculations. This has for a long time been the name of the game in terms of increasing performance - just add more general-purpose CPU cores.
Instead of adding ever more general-purpose CPU cores, Apple has followed another strategy - they have started adding ever more specialized chips doing a few specialized tasks. The benefit of this is that specialized chips tend to be able to perform their tasks significantly faster using much less electric current than a general-purpose CPU core.
Hope that answers your question.
You can find more details on the M1 where I got the info for the second part of the answer. There is a lot of additional and interesting info on the CPU market and the software differences inside the M1 and Intel/AMD chips: link


Descriptive complexity: 3-colorability example So in Neil Immerman's book http://books.google.co.kr/books?id=kWSZ0OWnupkC&pg=PA113&lpg=PA113#v=onepage&q&f=false, 3-colorability problem in descriptive complexity fashion is expressed as following: $\exists R \exists Y \exists B \forall x \left[(R(x) \vee Y(x) \vee B(x)) \wedge (\forall y) (E(x,y) \rightarrow \neg(R(x) \wedge R(y)) \wedge \neg(Y(x) \wedge Y(y)) \wedge \neg (B(x) \wedge B(y))) \right]$.

My previous question seems to have been misunderstood - I was not asking about what first-order or second-order logic is, but rather on the use of quantifier. Here $\forall x$ seems to imply that universe is already predefined to refer to vertices only. Is this correct understanding? If so, why is it the case? Is it pre-defined rule of descriptive complexity usage of logic?

Also for any similar graph problems, is universe of sets restricted to vertices only, or are we allowed to add sensible sets to universe?

The convention in descriptive complexity is that for graph properties, the universe always consists of the set of vertices, and there is an additional two-place edge relation.