Sum of size of distinct set of descendants $d$ distance from a node $u$, over all $u$ and $d$ is $\mathcal{O}(n\sqrt{n})$ Let's consider a rooted tree $T$ of $n$ nodes. For any node $u$ of the tree, define $L(u,d)$ to be the list of descendants of $u$ that are distance $d$ away from $u$. Let $|L(u,d)|$ denote the number of nodes that are present in the list $L(u,d)$.

Prove that the sum of $|L(u,d)|$ over all distinct lists $L(u,d)$ is bounded by $\mathcal{O}(n\sqrt{n})$.

My work

Consider all $L(u,d)$ such that the left most node on the level $Level(u) + d$ is some node $v$. The pairs $u, d$ for all such $L(u,d)$ must be distinct and the sum of all $d_i$ will correspond to the number of nodes $x$ in the tree with $Level(x) \le Level(u) + d$.

This is because if some sequence of nodes $v_1, v_2, \dots v_k$ corresponds to the descendants of some node $u$ at a distance $d$ and the sequence of nodes $v_1, v_2, \dots v_{k'}$ where $k' > k$ corresponds to the descendants of some node $u'$ at a distance $d+1$, then there must also exist a node $u''$ such that $L(u'', d) = v_{k+1}, v_{k+2}, \dots v_{k'}$. This would also mean that $u''$ is not in the subtree of $u$ and thus there are at least $d$ distinct nodes in the subtree of $u''$ upto a distance $d$ from $u''$.

If the distinct distances are $d_1, d_2, \dots d_k$ then, $n \ge \sum_{i}d_i \ge \sum_{i=1}^{k}i \ge \frac{k(k+1)}{2}$. =

$\implies k \le \sqrt{n}$

After this I tried to show that there can be only $\mathcal{O}(\sqrt{n})$ distinct lists $L(u,d)$ so that I can then trivially obtain the upper-boud of $n\sqrt{n}$ but I could not make any more useful observations.

This link claims that such an upper bound does exist but has not provided the proof.

Any ideas how we might proceed to prove this?

Let us start by giving an alternative formula for $\sum_{u,d} |L(u,d)|$. For a node $x$, let $\pi^{(d)}(x)$ be its $d$'th parent, and let $h(x)$ be its height. Then
$$
 \sum_{u,d} |L(u,d)| = \sum_x |\{ L(\pi^{(d)}(x),d) : 0 \leq d \leq h(x)\}|.
$$
It suffices to show that $|\{ L(\pi^{(d)}(x),d) : 0 \leq d \leq h(x)\}| = O(\sqrt{n})$ for all nodes $x$.

Let $y = \pi^{(d-1)}(x)$ and $\pi(y)$ be $y$'s parent. If $L(\pi(y),d) \neq L(y,d-1)$ then $y$ must have a sibling $z$ with a leaf at depth $d$. We can associate the $d$ vertices on the path leading to the leaf (including $z$) to $\pi(y)$; note that vertices associated to different parents of $x$ are distinct.

For each element in $\{L(\pi^{(d)}(x),d) : 0 \leq d \leq h(x)\}$ choose a representative $\pi^{(d)}(x)$ with the maximal $d$, and let $I$ be the set of all such $d$'s. In particular, if $\pi^{(d)}(x)$ is a representative then $L(\pi^{(d)}(x),d) \neq L(\pi^{(d-1)}(x),d)$, and so $\pi^{(d)}(x)$ has $d$ vertices associated to it. We deduce that
$$
\sum_{d \in I} d \leq n.
$$
In particular, $I$ can contain at most $\sqrt{n}$ numbers larger than $\sqrt{n}$, and so $|I| = O(\sqrt{n})$.


From where does the Fetch Unit get its instructions? In the ARM Architecture pipelining stages, we know that the instructions pass from fetch to decode and so on? But, from where does the fetch unit get the instructions?

The instructions come from some part of memory, pointed to by the Program Counter (PC) aka Instruction Pointer (IP).

In modern computers, instructions tend to share the same RAM used for everything else (with protections in place to keep things sane), but especially in older or special-purpose machines it's not uncommon for instructions to be baked into ROM instead.


Why doesn't diagonalization require taking a limit? When we quantify infinite sums, we do so by taking the limit as $i$ goes to infinity. For example, we look at $\lim_{n\rightarrow \infty}\sum_{n\in \mathbb{N}}n$, and then we say that this diverges and does not have a sum.
When we do diagonalization, we iterate over an infinite list while indexing each list item by a natural number, and then talk about the result. Why can we do this instead of having to invoke limits?
In the same way, would it be fine to assign a value to $\sum_{n\in \mathbb{N}}n$ with the value being an infinite sequence?

Some diagonalization arguments might require limits to be able to nail down all the details (e.g. if they involve an infinite sum, or an infinite decimal expansion, which is formally just an infinite convergent sum of a certain kind), but they do not require limits in general.
The most popular diagonalization argument proves that $|\mathbb{N}| \neq |\mathbb{R}|$. Depending on how you've seen this, resolving some of the details might end up requiring limits because of the nature of $\mathbb{R}$. So let's look at a decidely discrete example of diagonalization instead:
Theorem $|\mathbb{N}| \neq |\{0, 1\}^\mathbb{N}|$
We take $\{0, 1\}^\mathbb{N}$ to be the set of all infinite sequences of ones and zeros (you can also think of it as the function space $\mathbb{N} \to \{0,1\}$). So for example, we could have the sequences $a = (0, 1, 0, 1, 0, 1, 0, 1, \cdots)$ such that $a_{2i} = 0$ and $a_{2i+1} = 1$.
Since this is a diagonalization argument, we proceed via contradiction. We first assume that it's possible to enumerate all elements of $\{0, 1\}^\mathbb N$ via some function $f$, so that for all $i \geq 0$, $f(i)$ is an infinite sequence of 0s and 1s.
We will construct an explicit infinite sequence which doesn't show up in the image of $f$, which proves that no such $f$ can enumerate all infinite sequences of 0s and 1s, which means that $|\mathbb N| \neq |\{0,1\}^\mathbb N|$ as desired:
$$
a_i \triangleq 1 - f(i)_i
$$
And now we can immediately see by construction that for each $i \geq 0$, $a \neq f(i)$, since if $a = f(i)$ then for all $k$, $a_k = f(i)_k$, but in particular for $k = i$ we have $a_i = 1 - f(i)_i \neq f(i)_i$. $\blacksquare$

This construction clearly doesn't involve any limits - all of the objects are discrete. The equivalent complete proof specifically for $\mathbb R$ might involve a limit or an (easy and automatic) proof of convergence for the construction of the real number $a$, but there's nothing particularly insightful about that step.


Find the language an NFA recognizes For example, I have an NFA $A_n$ with alphabet $\Sigma = \{0, 1\}$.

The language recognized by this NFA is known to be $\{u1v\ |\ u, v \in \Sigma^*, |v| = n − 1\}$.

I was unable to get the answer on my own. What got me stuck was that there is a $1$ between $s$ and $q_1$, plus the $q_n$ toward $s$. I know without the edge $q_n \rightarrow s$, the answer should be $\{0,1\}^* \cdot 1 \cdot \{0,1\}^{n-1}$, which is exactly the solution our lecturer provides. Why doesn't the "go back to start" edge matter?

The "go back to start" edge doesn't matter because of nondeterminism and the fact that you can read any string at all while staying in state $s$. Any string that the automaton accepts has an accepting run that doesn't use the "go back to start" edge.


Parallel Algorithm for Donor/Recipient Matching - Graph Matching/Optimization I'm not certain I can accurately describe the problem using my knowledge of discrete math, so pardon any inaccuracies. Happy to clarify any part of the question which is unclear.

Given the following constraints:

Two sets, each with 'n' elements: 'donors' and 'recipients'. $|D| = |R| = n $
Each donor has a maximal number of times they are able to be matched with a recipient: "max donations". $ maxd: D \to \mathbb{Z}_{+}$
A distance function, returning a real number representing the suitability of match between a donor and a recipient, given the number of times a donor has already "donated" / been matched with a recipient. $ distance: D \times R \times \mathbb{Z}_{+} \to \mathbb{R}_{+} $

Devise a parallel algorithm to determine the list of optimal matching. i.e. find functions $m: D \to \mathcal{P}(R)$ which defines a partition of $R$ and $l: D \times R \to \mathbb{Z}_{+} $ such that $\forall d \in D$   $ | m(d) | \leq  maxd(d)$

which minimize the following cost:

$$
\sum_{d \in D} \sum_{r \in m(d)} distance(d, r, l(d, r))
$$

Intuitively, I think this is NP-hard. So I was satisfied with my solution - using BSP treat the donations per donor in phases, where each iteration is a graph matching problem.

Is this the best I can do? Any suggestions?

This can be reduced to an instance of the minimum-cost flow problem.

Build a flow network from your graph, with an edge from each donor to each recipient whose maximum flow is $1$ and whose cost is the negation of the value of that matching.  Add a source vertex $s$, with an edge of weight $\text{maxd}(d)$ and cost $0$ to each donor $d \in D$.  Add a sink vertex $t$ with an edge of cost $0$ and maximum weight $\infty$ from each recipient to $t$.  Now compute the minimum-cost flow.  This can be done in polynomial time, so your problem can be solved in polynomial time.

So your question boils down to asking whether there are parallel algorithms for min-cost flow.  Searching the literature will turn up a bunch of algorithms for that.  If you use Google Scholar, you can find a number of papers on that subject.


Is there a path of length $k$ between given vertex to a subset of vertices in a connected directed graph I am trying to find an efficient algorithm that on input
$ (G,s,A,k) $ returns true iff $G$ is a connected directed graph, $s$ is a vertex in $G$, $A$ is a set of vertices in $G$ and there is a path of length $k$ from $s$ to a vertex in $A$

What is the best run time we can get here?

I am currently stuck with this slow algorithm (there might be some minor problems but the concept is of the importance) $T$ that on input $(G,s,A,k)$:

for all vertices $t$ in $A$:

if $k=1$ and $t$ is a neighbor of $s$ return TRUE

if $k=0$ and $s=t$ return TRUE

for all neighbors $r$ of $s$ return $T(G,r,\{t \},k-1)$

this algorithm is rather slow because it exhausts all possibilities.

*cycles of any size (1 or more) are allowed in the graph and in the paths

From the algorithm you describe and the comment you made on your question I understand that you are interested in walks and not in simple paths and that the graph is unweighted.

The algorithm you describe has at least exponential complexity since you examine each possible subset of $A$ (it has $2^{|A|} = O(2^N)$ subsets). We can use a much faster polynomial time algorithm.

One such algorithm has $O(k(N + M))$ computational complexity. You will need $k + 1$ boolean matrices, $B_0, B_1, \dots, B_k$, of size $N$. $B_0$ will be initialized to false, excluding its $s$-th position which will be initiallized to true. That is:

$B_0[u] = 1$, iff $u = s$

You will execute $k$ steps. In the $i$-th step you will calculate $B_i$ using the following formula:

$B_i[u] = 1$, iff $\exists v: (v, u) \in E \wedge B_{i - 1}[v] = 1$

This way $B_i[u]$ will be true iff there is a walk of length $i$ from $s$ to $u$. When you have calculated $B_k$ you can find the answer by checking $B_k$'s positions that match to $A$'s nodes' ids. Iff at least one of these array positions make $B_k$ true, then the answer is positive. The computational complexity of this algorithm is $O(k(N + M))$ and its space complexity is $O(kN)$. You can drop the space complexity to $O(N + M)$ if you observe that only the previous and the current boolean matrix $B_{i - 1}, B_i, \forall i \in \{1, 2, \dots, k\}$ are needed during each step. Bellow you can see a C++ implementation of this algorithm.

#include <iostream>
#include <vector>
using namespace std;

#define MAXN 100005  // Equal to maximum possible N + 5

vector<int> E[MAXN];  // Adjacency lists
vector<int> A;  // Nodes that belong in set A

bool PB[MAXN];  // boolean array of the previous step
bool B[MAXN];  // current boolean array

int main()
{
    int N, M, S_A, s, k;
    // N: number of nodes
    // M: number of directed edges
    // S_A: size of set A
    // s: starting node
    // k: length of walk to be done
    cin >> N >> M >> S_A >> s >> k;
    for (int i = 0; i < M; i++)
    {
        int u, v;
        cin >> u >> v;
        E[u].push_back(v);  // there is an edge from u to v
    }
    for (int i = 0; i < S_A; i++)
    {
        int a;
        cin >> a;
        A.push_back(a);  // a belongs to A
    }

    // Create B_0
    for (int i = 0; i < N; i++) B[i] = false;
    B[s] = true;

    // Perform the k repetitions
    for (int i = 1; i <= k; i++)
    {
        // Copy B (B_i) to PB (B_{i-1}) and initialize B
        for (int j = 0; j < N; j++)
        {
            PB[j] = B[j];
            B[j] = false;
        }
        for (int j = 0; j < N; j++) if (PB[j])
        {
            // There is a walk from s to j of length i-1...
            for (int l = 0; l < E[j].size(); l++)
            {
                // ...and an edge from j to E[j][l]...
                B[E[j][l]] = true;
                // ...so there is a walk of length i from s to E[j][l]
            }
        }
    }
    // Now B = B_k

    for (int i = 0; i < S_A; i++)
    {
        int a = A[i];
        if (B[a])
        {
            // There is a walk of length k from s to a
            cout << "YES\n";
            return(0);
        }
    }
    // There is no walk of length k from k to any node of A
    cout << "NO\n";
    return(0);
}

This algorithm is fast if $k$ is small but when $k$ becomes larger its computational complexity increases significantly. We will now describe an algorithm which is faster for large values of $k$.

You can use the fact that the $(i, j)$ cell of $Adj^p$ (where $Adj$ is the adjacency matrix of the graph) is equal to the number of walks from $i$ to $j$ in the graph with length equal to $p$ (easy to prove using mathematical induction). In your case you are interested in walks of length equal to $k$ so you have to calculate $Adj^k$. You can efficiently calculate $Adj^k$ in $\lceil log_2k \rceil$ steps using exponentiation by squaring. Each step of the above calculation requires squaring an $N \times N$ matrix. This can be done in $O(N^3)$ using the naive algorithm or in $O(N^{2.373})$ using the fastest known algorithm. The fact that you want to know if a path between two nodes exists and not the number of different paths allows you to avoid large numbers by making the integer matrix boolean after each multiplication. When you have $Adj^k$ (in boolean format) you can check if there is a path of length $k$ from $s$ to a vertex in $A$ by checking the $s$-th row of $Adj^k$ and specifically the columns regarding nodes of $A$. Formally the result is positive iff
$$\exists u \in A: Adj^k(s, u) = 1$$
The algorithm is the following:

Read input and calculate adjacency matrix of the graph: $O(N^2)$
Calculate $Adj^k$ using exponentiation by squaring, fast matrix multiplication and making matrix boolean after each multiplication: $O(N^{2.373}logk)$
Check if there exists a cell $Adj^k(s, u) = 1$ where $u \in A$: $O(N)$
Output the reslt: $O(1)$

The total computational complexity of this algorithm is $O(N^{2.373}logk)$ and it is better than the first algorithm for large values of $k$. Both of them also include possibility of self edges as you mention in your comment on your question.

You are able to combine the two algorithms and run the fastest one based on the values of the parameters and achive $O(\min \{k(N + M), N^{2.373}logk\})$ computational complexity.


How to show that a "reversed" regular language is regular I'm stuck on the following question:

"Regular languages are precisely those accepted by finite automata. Given this fact, show that if the language $L$ is accepted by some finite automaton, then $L^{R}$ is also accepted by some finite; $L^{R}$ consists of all words of $L$ reversed."

So given a regular language $L$, we know (essentially by definition) that it is accepted by some finite automaton, so there's a finite set of states with appropriate transitions that take us from the starting state to the accepting state if and only if the input is a string in $L$. We can even insist that there's only one accepting state, to simplify things. Then, to accept the reverse language, all we need to do is reverse the direction of the transitions, change the start state to an accept state, and the accept state to the start state. Then we have a machine that is "backwards" compared to the original, and accepts the language $L^{R}$.


How do you calculate the running time using Big-O notatation? I'm still new to Data Structure and Algorithm and therefore I would like to ease my doubts. I'm required to find the Big-O running time of myMethod():
 Static int doIt(int n) {
           for ←1  100 do    -> 100
             for ←1   do    -> n x 100
                 ←1;←       -> 1
           while < do       -> lg n
          ←(+)/2           -> lg n/2
        end while
        end for
        end for

    }

 static int myMethod(int n) {
                   ←1
                  ℎ ( < ) {          -> lg n
                        ()            -> ?
                         ←×2             -> lg n
        }
             1;

}

For each of the line I have inserted the answer I think would be a logical value to put e.g "-> 100". However I am not confident with the answer. These are the following questions that I would like to ask as well:

Does all while loop have a value of lg n?

If the doIt(n) method does not have a return statement, do we still add in part of calculation?

For the line with m <- (m+j)/2, the value I have inputted is lg n /2. Is that correct or is it some other value?

Whenever multiplying by 2 or dividing by 2 is it always lg 2? what if n is multiplied by 3?

Thank You

The while loop is executed $O(\log n)$ times (more precisely, $\Theta(\log n)$ times).

Yes. You account for every statement that is executed.

The line can $m \gets (m+j)/2$ can be executed in time $O(1)$, assuming that arithmetic operations take constant time. The overall time spent in one execution of the wile loop of the function doIt(n) is $O(\log n)$, since the number of its iterations is also $O(\log n)$ (and, more precisely, $\Theta(\log n)$).

This depends on the actual cost model you are using. Assuming that arithmetic operations take constant time, what you are probably thinking of is the number of divisions (resp. multiplications) by $2$ needed for $n$ to drop below (become larger than) some value $x < n$ (resp. $x>n$). If that's the case then the number of iterations is $O(\log n - \log x) \subseteq O(\log n)$ (resp. $O(\log x - \log n) \subseteq O(\log x)$.
Multiplying/dividing by any constant greater than $1$ does not change the asymptotic time complexity (recall that $\log_b a = \frac{\log_2 a}{\log_2 b}$, where $\log_2 b$ is a constant in this scenario).


Efficiently map different codes to rotation-different codes Let $\mathbb{F}^n_2$ denote the set of $n$-bit 0-1 strings. How to construct an efficiently computable function $f:\mathbb{F}^n_2\to \mathbb{F}^m_2 (m>n)$ satisfying that $\forall u\neq v$,$f(u)\neq f(v)$ and $f(u)$ is not a circular rotation of $f(v)$?

$m$ is expected to be as small as possible.

Thank you very much for your kindness.

Here's a more efficient way of doing it. Let's map all the strings of length $n$ into strings of length $n+O(\sqrt{n} \log n)$ with no consecutive string of $0$'s of length more than $\sqrt{n}$. We then add a string $1 0^{a}1$ at the end, where $a \geq \sqrt{n} + 1$. Our mapping isn't always going to give us the same length string, so $a$ can vary.

How do we do this encoding? We need a way of encoding long string of 0's. Let's do that by
taking a string of $0$'s of length at least $t$ and mapping it to a string of zeros of length $t$ followed by a number telling us how many zeros were in it.

$$
\begin{array}{lcl}
0^{\sqrt{n}} & \rightarrow & 0^{\sqrt{n}}10\ldots000 \\
0^{\sqrt{n}+1} & \rightarrow & 0^{\sqrt{n}}10\ldots001 \\
0^{\sqrt{n}+2} & \rightarrow & 0^{\sqrt{n}}10\ldots010 \\
0^{\sqrt{n} +3} & \rightarrow & 0^{\sqrt{n}}10\ldots011 \\
0^{\sqrt{n} +4} & \rightarrow & 0^{\sqrt{n}}10\ldots100 \\
\vdots &\rightarrow & \vdots
\end{array}
$$
Because we will never have a string of more than $n$ 0's, we can use the first $\lceil\log n \rceil$ bits after the string $0^{\sqrt{n}} 1$ to encode the length of the string of 0's. Thus, the most we can increase the length of our code by is a factor of $1 + \frac{\log n+2}{\sqrt{n}}$. After this expansion of the code, we need to add at least $\sqrt{n} + 1$ consecutive 0's. This lets us take $m = n + \sqrt{n}(\log n + 3)$.

I think you can probably get $m \approx n + \log n\,$ by using the ideas behind arithmetic codes, but I don't have time to work the details out right now. If somebody else wants to work them out and post an answer, please feel free to do so.


Analysis of a LALR shift-reduce conflict I have created an extremely simple byacc grammar (ok, it's not really that simple but I simplified purposefully to be a minimal complete verifiable example):

%token NEWLINE SPECIFIER
%token EQUALS STRING VAR

%start st

%%

st: toplevel;

toplevel:
| toplevel VAR EQUALS STRING NEWLINE
| toplevel list NEWLINE
;

list:
  maybe_specifier VAR
| list maybe_specifier VAR
;

maybe_specifier:
| SPECIFIER
;

However, it is warning about a shift-reduce conflict. If I remove maybe_specifier from the grammar entirely (so that variables cannot be prefixed by a specifier in a list), the conflict disappears. Similarly, if I remove the variable assignment from the grammar entirely, the conflict disappears too.

My questions are:

Where does this shift-reduce conflict come from? Is it an artifact of LALR? Or would it be there even with an LR(1) parser generator?
Does this shift-reduce conflict matter? Or is it always doing the right thing anyway by using shift instead of reduce?
Is there any way to modify the grammar to accept the same language without having the shift-reduce conflict, other than by prefixing VAR in assignment line by maybe_specifier and then checking whether the SPECIFIER was there in a semantic action, and failing if the SPECIFIER was present?

My current approach is to modify the assignment rule to initially accept a SPECIFIER in the form of maybe_specifier but then terminate with a parse error if the SPECIFIER was there. I'm wondering if there's a cleaner approach that would allow me to do the same without adding a semantic action.

This conflict arises because when the parser is at the beginning of a line and the lookahead is VAR, it can't tell whether or not to reduce an empty maybe_specifier. In this simple grammar, that decision could be resolved with one more lookahead token, making the grammar LR(2), but that might not be true in the original unsimplified version.

So the conflict is not an artefact of the LALR algorithm, and it is important to fix. (The yacc default resolution "choise shift over reduce" will make it impossible to parse lists which don't start with a SPECIFIER.)

A simple fix is to defer the parsing decision for the first entry in a list:

list:
  VAR
| SPECIFIER VAR
| list maybe_specifier VAR
;

Again, that might or might not be useful in the context of your full grammar.


How to write an OR constraint in MILP? I want to write a constraint with ORs in a MILP. In particular, the following:

$$x \ge c \lor x \le -c \lor x=0,$$

where $c$ is just a real number.

Can anyone give me some hints?

Tough. You are leaving linear programming.

Solve the problem without these equations and with no restriction for the sign of x. If by coincidence x matches one of the conditions, you are done. Otherwise you will need to solve the problem with one of these equations added.

Calculate how much changing x by eps changes the optimal solution. With that guess how much adding x=0, x>=c, or x<=-c would affect the optimal solution. Add the equation that seems to cause the least damage and solve with an optimal goal function G. Then try adding each of the other equations, with an additional restriction goal >= G.

You could have just tried adding each equation in turn and solving, but this way you might find quicker that one condition can’t lead to an optimal solution. For example if c=100 and your optimal solution was x=80, you can add x>=100, optimise , and you can likely show easy that x=0 or x<= -100 will lead to a worse outcome.


Randomized communication complexity of indexing The function $\mathrm{INDEX}:\{0,1\}^n\times\{1,\dots,n\}\to \{0,1\}$ is defined as

$$\mathrm{INDEX}(x,i)=x_i,$$
where $x=x_1\dots x_n$. I am looking for the randomized communication complexity of $\mathrm{INDEX}$ for an arbitrary number of rounds.

Somehow, I do not manage to find it in the literature.

The deterministic communication complexity is known to be $\Theta(\log n)$, while its one-way randomized communication complexity is $\Theta(n)$.

I guess the randomized communication complexity is still $\Theta(\log n)$, I was not able to find a lower bound.

Since this function its well-studied, it should be stated somewhere.

Thanks for your help.

It is known that the randomized communication complexity of inner product on $m$ bits is $\Omega(m)$. You can compute inner product using a protocol for the indexing function on $\{0,1\}^{2^m} \times [2^m]$ as follows: denoting Alice's input by $x \in \{0,1\}^m$ and Bob's by $y \in \{0,1\}^m$, Alice computes a new vector $X$ by $X_y = \mathsf{IP}(x,y)$, and the parties run the indexing protocol on the inputs $X$ and $y$. This gives an $\Omega(m) = \Omega(\log n)$ lower bound for indexing.


How to find n-1 complete matches for bipartite graphs that are related (speed-date)? How can one assign n people pairwise to n-1 tables, in a speed-date fashion, such that no two persons meet twice and each person is at each table exactly once? Does this problem have a name?

The problem in full

Given n people (n is even), assign them in pairs in n-1 rounds. Each round represent a list of n/2 pairs, each pair being two individuals that have not met earlier.

For each round, find a match between the n/2 pairs and n-1 tables, so that every pair are assigned a table. The tables are unique. Through all n-1 rounds, an individual should meet each other individual exactly once, and be at each table exactly once.

What have I tried?

Here is the naive bipartite matching algorithm I've created so far:

Create rounds using the round-robin tournament scheduling.
Represent each round as a bipartite graph, pairs vs tables.
For each round, find a match.

For each player, remove table matched in this round.

In pseudo:

n = 6
tables = [1, 2, 3, 4, 5]
players = [{'i': 1, 'tables': copy(tables)}, {'i': 2, 'tables': copy(tables), ...]
rounds = roundRobin(players)
# each round has a list of pairs
# each pair is two players
# [
#     [[1,6], [2,5], [3,4]],
#     [[1,2], [3,6], [4,5]],
#     ...
# ]
matches = []
# keep matches

for round in rounds:
    match = hopcroft_karp(round, tables)
    # pair 1 to table 1, ...
    # [ [1, 1], [2, 2], [3, 3] ]

    if len(match) !== len(round):
        # TODO: backtrack
    else:
        add match to matches
        for edge in match:
            pair = round[edge[0]]
            table = edge[1]
            removeTable(pair[0], table)
            removeTable(pair[1], table)

Example

For some n, there is no solution. For example n = 4. I'm unsure for which n the problem has solutions. Here is n = 4 as an example:

People: 1, 2, 3, 4
Tables: A, B, C

Round 1: A:1,2 - B:3,4
      In round 1, we can assign tables at random, because
      the problem is the same with renaming tables.
Round 2: C:1,3 - ?:4,2 <-- not possible
      4 has already been at table B.
      2 has already been at table A.
      Table C is taken by pair 1,3.
Round 3: ?:1,4 - ?:2,3 <-- same as round 2

Your problem seems to be the same as that of constructing a Room square. Let me quote from The existence of Room squares by Mullin and Wallis:

A Room square of side $2n+1$ is a $2n+1$ by $2n+1$ array of cells and a set $S$ of $2n+2$ objects called symbols which satisfy the following conditions:
(i) Every cell of the array is either empty or contains an unordered pair of distinct symbols from $S$.
(ii) Each symbol occurs in every row and column of the array.
(iii) Every unordered pair of symbols occurs precisely once in the array.

Mullin and Wallis state that a Room square of size $v$ exists for all odd positive $v$ except for $v=3,5$. This explains why your construction for $n=4$ (which corresponds to $v=3$) wasn't successful.
To construct a Room square, look into the article Construction of Room Squares by Stanton and Mullin.


Reflexive transitive closure = (zero or more) Kleene star? In Alloy Tutorial they denote some reflexive transitive closure with Kleene star saying that they admit zero or more elements at that position.

  // File system is connected
  fact {
    FSObject in Root.*contents
  }

  In Alloy, in can be read as "subset of" (among other things). The operator "*" denotes reflexive transitive closure. Thus, this fact says that the set of all file system objects is a subset of everything reachable from the Root by following the contents relation zero or more times.

Reflexive Transitive Closure *

  In Alloy, "*bar" denoted the reflexive transitive closure of bar. It is equavalent to (iden + ^bar) where ^ is the (non-reflexive) transitive closure operator.

Can you explain the closure and star operators such thut it becomes obvious that they are identical?

(Note: I'm not 100% sure about the Alloy syntax since I never used it -- what follows is accurate on the general principles but the syntax could be slightly different)

Basically, S.*bar means starting from S and using .bar any number $n\geq 0$ of times.

Instead, S.^bar means starting from S and using .bar any positive number $n > 0$ of times.

It is immediate to see that S.^bar is equivalent to S.bar.*bar since the latter denotes zero or more steps after a first step, hence one or more steps.

If the language allows S.iden to mean "zero steps from S", and + to denote union, then we can also write S.^bar as S.(iden + ^bar) which can be read as "zero steps or (one step or more)" which is the same thing as "zero or more steps".

In the underlying theory, one can define the reflexive and transitive closure of a relation $R \in \mathcal{P}(A\times A)$ as the smallest relation $R^* \in \mathcal{P}(A\times A)$ satisfying

$$
R^* = I_A \cup R \circ R^*
$$

where $I_A$ stands for the identity relation. The existence of the smallest $R^*$ is guaranteed by the Tarski fixed point theorem (on the complete lattice of the relations). According to the Kleene fixed point theorem (and a few minor simplifications) one can also write it as
$$
R^* = \bigcup_{n\geq 0} R^n
$$
where $R^n$ denoted the self-composition of $R$ for $n$ times.


Why updating only a part of all neural network weights does not work? I am having a problem with my program of deep neural network using Theano. In my deep neural network, I have several layers of neural network to predict an output given a certain input. Because of an issue when compiling theano, I have to debug my program step-by-step. Since Theano gives me an error when updating weights of some layers, I perform a check by calculating the derivatives of only the last layer (using tensor.grad if you know Theano). But if I do that then the network will not update properly and the cost does not decrease and the output is nowhere close to the true output. It seems like updating the weights of only the last layer does not seem to train the network to learn.

Is it mandatory to update all weights of all layers in a deep neural network to decrease the cost? What I understand is that if I fix the values of all weights except the weights of the last layer, it should still be able to predict correctly after many rounds of training (of course, the only layer that is learning is the last layer, but I accept that, I only needs the predicted values to be close to my true values while training).

I hope my explanation make sense to you. If you do not understand any part, I will gladly provide you more information.

If you're only changing the weights in the last layer, then effectively you have a neural network with a single layer, preceded by some preprocessing step. Single-layer neural networks (also known as perceptrons) aren't so powerful.

Why isn't the network learning anything?  It doesn't learn much because it can't -- a single-layer network can't learn complicated functions.


Beginner Question Concerning the Logic of a Very Simple Correctness Proof I'm trying to familiarize myself with correctness proofs and need some help. In the proof for SimpleSelect (P.25), why do we assume both $A'[i] < A'[k]$ and $1 \leq i \leq k$? I'm not quite sure why we do this, as the text states that because "of what it means for an algorithm to meet its specification, any proof of correctness will begin by assuming the precondition." However, isn't the precondition here simply the precondition of SimpleSelect as specified here (P.6)?

Both of the assumptions you mention are "local" in the sense that they are a subclaim in the proof and are not part of the conditions of the theorem. You can also see them as the definition of a local variable $i$, an equivalent formulation of the two assumptions would be

Let $i$ be such that $A'[i]<A'[k]$ and $1\leq i \leq n$.

Let $i$ be such that $1\leq i \leq k$.

The proof counts the number of values of $i$ for which these statements hold, which shows that the postcondition is satisfied.

I think part of your confusion follows from some implicit language in these paragraphs, so I will rewrite one of them in full to be more explicit. The first paragraph from the book reads:

Suppose $A'[i] < A'[k]$ for some $i$, $1 \leq i \leq n$. Then $i < k$, for if $k < i$, $A'[k] > A'[i]$ violates the postcondition of Sort. Hence, there are fewer than $k$ elements of $A'$ , and hence of $A$, with value less than $A' [k]$.

A more explicit phrasing is as follows:
Let $i$ be such that $A'[i]<A'[k]$ and $1\leq i \leq n$. If $k<i$, then $A'[i]<A'[k]$ contradicts with the postcondition of Sort, so $i\leq k$. If $i=k$, then $A'[i]=A'[k]$, which contradicts with our definition of $i$.
So, we have shown that if $A'[i]<A'[k]$ and $1\leq i \leq n$, then $i<k$. This means that the number of elements of $A'$ with value strictly less than $A'[k]$ is strictly fewer than $k$. Since $A$ is a permutation of $A'$, there are fewer than $k$ elements of $A$ strictly less than $A'[k]$. Since $A'[k]$ is the return value of the algorithm, the first part of the postcondition of Select is satisfied.
The overall structure of the second paragraph is similar, so you should be able to grasp it if you can understand the first.


How do you convert a regular expression to its disjunctive normal form? A regular expression $r$ is said to be in disjunctive normal form if it can be written in the form $r = r_1 +r_2 +\dots+r_n$ for some $n ≥ 1$, where none of the regular expressions $r_1, r_2, \dots, r_n$ contains the symbol $+$ (union).

For example, the regular expression $a^*b^* + (ab)^* + (c(acb)^*)^*$ is in disjunctive normal form.

The task is to prove that every regular language can be specified by a regular expression in disjunctive normal form. Considering that every regular language by default can be represented by a regular expression, the question now seems to simplify to proving that any regular expression can be converted to or expressed in disjunctive normal form. Any idea on how that is possible?

The proof is by structural induction. I will define an operator $T$ that takes an arbitrary regular expression, and outputs an equivalent regular expression in disjunctive normal form:

Base cases: $T[\epsilon] = \epsilon$, $T[\sigma] = \sigma$, $T[\emptyset] = \emptyset$.
If $r = s + t$, then we define $T[r] = T[s] + T[t]$.
If $r = st$, by induction we know that $T[s] = s_1 + \cdots + s_n$ and $T[t] = t_1 + \cdots + t_m$, where $+$ doesn't appear in any of the $s_i$ or $t_j$. We define $T[r] = \sum_{1 \leq i \leq n} \sum_{1 \leq j \leq m} s_i t_j$.
If $r = s^*$, by induction we know that $T[s] = s_1 + \cdots + s_n$. We define $T[r] = (s_1^* \cdots s_n^*)^*$.

It is routine to prove by structural induction that $T[r]$ is a regular expression in disjunctive normal form which is equivalent to $r$.


Is there any algorithm which takes regular expression as input and finds if the regular language which expression describes is infinite? Is there any algorithm which takes regular expression as input and finds if the regular language which expression describes is infinite?Does it have to do with pumping lemma?

Additionally,is there an algorithm which finds if a regular language of a regular expression is the empty set?

Thank you

Yes, there is such an algorithm, and (if I am not mistaken) you can actually use a recursive evaluation of regular expressions.

Recall that regular expressions are composed from $\varnothing$, $\varepsilon$ and $a$ (for $a$ in some alphabet) using the operations $\cdot$, $+$ and $*$ (concatenation, union and iteration).

Observe that a language can only be infinite if it is based on the iteration of any language that contains a string that is not empty ($\varepsilon$). Then such an iteration can be repeatedly concatenated and unioned with other languages.   The result will be infinite again, except in the case we concatenate with the empty set.

Now introduce language 'classes' NUL, ONE, FIN, and INF for the empty set, the empty string, any (finite) language that contains a string other than $\varepsilon$, and any infinite set.

Start by replacing in your regular expression any occurrence of $\varnothing$, $\varepsilon$ and $a$ by NUL, ONE and FIN respectively.

Now use a set of reductions (equalities) on the new expression, and repeat those:

NUL* = ONE* = ONE
NUL + FIN = ONE + FIN = FIN + FIN = FIN
NUL NUL = NUL ONE = NUL FIN = NUL INF = NUL
ONE FIN = FIN FIN =  FIN
ONE INF = FIN INF = INF INF = INF
FIN* = INF* = INF

And many more, try to find what is needed.

And it seems to solve the empty set problem at the same time?


What sorting algorithm should be used for this array? I am given an array {1, 2, 3, 5, 4, 6} and I am asked

  What sorting algorithm might you want to use to sort the given list, and why?

Initially I think using Bubble sort would be the best option due to it's best case linear ($O(n)$) complexity and due to the fact that you'd only need to use 1 swap. However, the more I look at the problem I am starting to think that Insertion Sort may also be efficient in this situation.

Insertion sort and Bubble sort both have the same best, average, and worst case time complexities as well as the same space complexities. Are neither one of these algorithms the proper one to be used on this array? If not, why not?

An inversion in a permutation $\pi(1),\ldots,\pi(n)$ is a pair of indices $i < j$ such that $\pi(j) < \pi(i)$. Denote the number of inversions by $I(\pi)$. In your example, $I(123546) = 1$. It is well-known that insertion sort runs in time $O(I + n)$ on a permutation of length $n$ having $I$ inversions. Due to this guarantee, insertion sort is asymptotically optimal when the number of inversions is small, $I = O(n)$.


Prove that $S_2$ is closed under union and complement I'm having trouble proving that $S_2$ is closed under union and complement, even though in this Wikipedia article it says that:

It is immediate from the definition that $S_2$ is closed under union and complement.

I think that my problem is due to the fact that $S_2$ is defined slightly differently in my assignment. Here's the definition I must work with:

$S_2$ is the complexity class of all languages $L$ for which there exists a polynomial bound verifier $V$ and a polynomial $p$ such that for all $x \in \{0,1\}^*$:
$x \in L \Rightarrow \exists y \in \{0,1\}^{p(|x|)}  \forall z \in \{0,1\}^{p(|x|)} : V(x,y,z)=1$
$x \notin L \Rightarrow \exists z \in \{0,1\}^{p(|x|)}  \forall y \in \{0,1\}^{p(|x|)} : V(x,y,z)=0$

Let's look first at union. Let $A,B \in S_2$. I thought of defining a new verifier $V_{A \cup B} = V_A \lor V_B$ which should return a correct answer. However, my problem is defining the new polynomial $p$. Let's say that the polynomials that exist for languages $A,B$ are $p_A,p_B$ and that $p_A < p_B$. Now let's look at some $x \in A \cup B$.
The problem is that if $x \in A$ all I know is that there exists a $y$ s.t. $|y|=p_A(|x|)$ and that if $x \in B$ there exists a $y$ s.t. $|y|=p_B(|x|)$. But how do I define a polynomial $q$ such that I can be sure that there exists a $y$ s.t. $|y|=q(|x|)$ for any general $x$?
As for the closure under complement, if $A \in S_2$, all I know is that if $x \in \overline A$, then $x \notin A$, therefore $\exists z \in \{0,1\}^{p(|x|)}  \forall y \in \{0,1\}^{p(|x|)} : V(x,y,z)=0$. However I do not see how we use this in order to conclude that $\exists y \in \{0,1\}^{p(|x|)}  \forall z \in \{0,1\}^{p(|x|)} : V(x,y,z)=1$.

As you mention in your post, you can define a new verifier $V=V_A \vee V_B$ however, you missed the point that the input of $V$ need not be the input of $V_A$ or $V_B$: it can be the concatenation of their inputs

So the new $V$ can be written as
$$ V(x, y_A\circ y_B, z_A \circ z_B )$$
where it "runs" $V_A(x,y_A,z_A)$ and $V_A(x,y_B,z_B)$ and decides accordingly.

It then immediately follows that $q = p_a +p_b +1$  (the +1 is just to separate the prefix from the suffix, you can ignore it).


Quickly identify changes in connectivity Given an undirected graph with at least one path connecting $u, v$, and a sequence of edges to be removed: $e_1, e_2, \dots$, I would like to quickly identify the point at which $u$ will be separated from $v$. Clearly this could be done by doing a full path search after each removed edge, but this is very expensive.
Is there a faster algorithm? (This is this question which asks about a related but more general and difficult situation, but it has gone unanswered.)

You can work your way backwards. Suppose the edges being removed are $e_1,\ldots,e_\ell$, and the rest of the edges form a set $E$. Start by determining the connected components induced by $E$, using a disjoint sets data structure. Now add the edges $e_\ell,\ldots,e_1$ in that order, updating the disjoint sets data structure, until $u$ and $v$ belong to the same connected component. The last edge encountered in this way is the one you seek.


How to compare n number of m-dimensional points among one another with minimum time complexity? Suppose there are four points (n = 4) which are four dimensional (m = 4) . Lets say these points are : A(4,1,1,1) , B(3,2,1,1) , C(2,3,3,3) , D(1,4,4,4). What is the best data structure to compare all points among one another based on their values in corresponding dimensions ? Aim is to have minimum time complexity . (Practically n >> m ). The mentioned comparison is carried out to check whether points are mutually non-dominated or not. Example :

A(4,1) and B(5,6) -> B dominates A since (5>4) and (6>1) . Therefore, A and B are not mutually non-dominated.
C(4,1) and D(2,3) -> D doesn't dominate C ,since (3>1) but (2<4) . Similarly C also doesn't dominate D ,since (4>2) but (1<3) . Therefore, C and D are mutually non-dominated.

(Note : In general, if (X>=Y) -> X dominates Y )

Goal is to check for non-dominance among all possible combinations of points from the given set of points with minimum time complexity . With four points A, B, C, D possible combinations are AB, AC, AD, BC, BD, CD . If ALL of these six combinations are mutually non-dominated , then it can be concluded that given set of points are mutually non-dominated, else dominated.

Input : Set of points, Task : Check for non-dominance among all possible combination of points from the given set of points , Output : If ALL combinations are mutually non-dominated , print ('set of points are mutually non-dominated') . Else print ('set of points are not mutually non-dominated') .

I have taken a 2-D array for this purpose . For n points which are m-dimensional , I have used a (n * m) matrix and compared each row with every other row to check for non-dominance among rows. Suppose if points are : A(4,1,1,1) , B(3,2,1,1) , C(2,3,3,3) , D(1,4,4,4) , then matrix is : x[4][4] = { {4,1,1,1}, {3,2,1,1}, {2,3,3,3}, {1,4,4,4} } . Here the time complexity is : O(m * n * n).

(Note :In this method , each row of matrix is representing one point )

Is there any better approach which results lesser time complexity ?

So you suggested the basic technique of checking all pairs which is $O(mn^2)$. Here are some things you can try first, at lower complexity, before falling back to an approach with a similar worst-case bound but likely better constants.

We represent each point $p_i = (x^i_1, \dots, x^i_m)$.

Then clearly there is a dominated pair if $\min_i \max_j x^i_j \leq \max_i \min_j x^i_j$. The time to evaluate this is $O(mn)$.

Next, we sort the points $m$ times, by each dimension. Let $r^i_j$ and $R^i_j$ be the indexes at which $p_i$ appears in each list (in range $[0,n)$), where the $r$ values have tie-breaks resolved down and $R$ values have tie-breaks resolved up, respectively. In other words, considering the values $3, 5, 5, 6$. Then the $r$ and $R$ values for the two points having $5$ would be $1$ and $2$. The time to evaluate this is $O(mn \log n)$, before we check conditions.

If $\min_i \max_j R^i_j \leq \max_i \min_j r^i_j$, then there is a dominated pair. The additional time to evaluate this is $O(mn)$ leaving the total time as $O(mn \log n)$.

Next, let $w_i = \sum_j r^i_j$ and $W_i = m(n-1) - \sum R^i_j$. Note that $w_i$ is an upper bound on the number of points that can't dominate $p_i$. Similarly, $W_i$ is an upper bound on the number of points that $p_i$ can't dominate. Thus, if $\min_i w_i < n - 1$ or $\min_i W_i < n - 1$, then there must be a dominated pair. The additional time to evaluate this is $O(mn)$ leaving the total time as $O(mn \log n)$.

Finally, as a fallback, for each point $p_i$ we know there are at most $\min_j R^i_j$ points which $p_i$ can dominate. Thus, knowing which list each $p_i$ obtained its minimum $R^i_j$ can give us a shorter list of points to check. The time here is still $O(mn^2)$ in the worst case, but the constant will be better than all pairs.


Unification Functions I need to apply the unification function to unify the following expression:

foo(X,X,Y) and foo(Z,p(Z),w)

So far, I've determined that I must substitute 'w's for occurances of 'Y', making

foo(X,X,w) and foo(Z,p(Z),w)

Then, I can saw X/Z (replaces 'Z' with 'X'), making:

foo(X,X,w) and foo(X,p(X),w)

Now all that's left is making p(X) equivalent to X

My question here is, is it allowed to replace this P(X) with X using the substitution X/p(X)? Or am I going about the question in the wrong pattern?

Thank you!

Rather than thinking about this in terms of substitutions, you might find it useful to think about this in terms of equalities that you can infer.

In the first step, you inferred that $w=Y$.

In the second step, you inferred that $X=p(Z)$.

In the third step, you inferred that $X=Z$.

It follows that you can infer $Z=p(Z)$.  So we know $X=Z=p(Z)$ and $w=Y$.

Of course, if you can infer that two things are equal, you can substitute one for the other.  But maybe it's easier to think about unification as being a way to keep track of which things are equal (which in turn helps you know which substitutions you can make).  Hope this helps make this kind of situation feel more intuitive.


Check whether an interval is contained in a union of intervals Initial Problem:

  Given an interval $[A, B]$ and a set of intervals $S = \{[S_{11},
S_{12}], [S_{21}, S_{22}], [S_{31}, S_{32}], \ldots, [S_{N1}, S_{N2}]\}$
  with $S_{11}\leq S_{21}\leq \cdots \leq S_{N1}$ output True if and only if
  $[A, B]$ is completely contained in the union of all intervals in $S$,
  and False otherwise.

What is the best-time-complexity algorithm we can do this? Surely, there is a way to do this in $O(N)$ naively but is there any technique we could use to, say, lower the complexity down to $O(\log N)$ or anything better than $O(N)$?

The problem requires $\Omega(n)$ time. Consider the interval $[A,B] = [0,N]$ and an algorithm for the problem. Whenever the algorithm queries $[S_{i1},S_{i2}]$, it gets the answer $[i-1,i]$. If the algorithm queries all intervals, then it knows that they cover $[A,B]$. Otherwise, the algorithm cannot tell. Indeed, suppose that it doesn't query $[S_{i1},S_{i2}]$, and that all other intervals are of the indicated form. If $[S_{i1},S_{i2}] = [i-1,i]$ then they cover $[A,B]$, but if $[S_{i1},S_{i2}] = [i-1/3,i-2/3]$ then they don't. Note that both inputs are legal (satisfy the constraint $S_{11} \leq S_{21} \leq \cdots \leq S_{n1}$).


Is there an efficient method to store large DAGs? I have a DAG representing strict partial order where each node is an assignment of variables $V$ to their values $v$. Each arc $(u,w)$ represents a change in one variable value such that $u\succ w$.

So if I have $n$ binary variables, I will end up with $2^n$ nodes which is exponential to the size of variables $n$. is there any method to store such DAG efficiently?

Try constructing a reduced ordered binary decision diagram (ROBDD) as described here.
The reducing algorithm removes redundant nodes, and reuses equal subtrees in the decision tree, such that every node is unique.
The memory complexity of a ROBDD is $\mathcal O({2^n \over n})$ as proved here.


What other involutions are there besides xor? There is a classic problem of finding the only number that occurs an odd number of times in a list. The solution is to xor everything and the result is the requested number.

The key properties used here are the involution of xor (i.e. a number's inverse is the same number) and the closure over integer range of the variable.

Now, are there any other operations that could be used for this? I could only find 1/x which, unfortunately, cannot be used due to precision erros.

Roll your own.

Take an arbitrary bijection $f$ from the integers to integers. This is a permutation of the integers.

Then, take the conjugate of XOR ($\oplus$):
$$
    g(x,y) = f^{-1}(f(x) \oplus f(y))
$$
We then have
$$
g(x,x) = f^{-1}(0)
$$
which now acts as the "new zero" (neutral element)
$$
g(x,f^{-1}(0)) = x
$$
We also have that $g$ is associative and commutative
$$
g(x,y) = g(y,z) \qquad
g(g(x,y),z) = g(x,g(y,z))
$$
So, we still have an abelian group where $x^{-1}=x$. The trick on arrays mentioned by the OP still works.


How to obtain the camera extrinsic matrix without using chessboard I'm working on a problem to find the camera position in the world system when each picture was shot.

I currently have several pictures taken from different angles, and for each picture there is only a black square on a white paper.

I have the actual size of the black square on the paper and the intrinsic matrix of the camera. And since the square is very easy to crop from each image, I can also obtain the perspective transformation matrix for each image. But I think to eventually find the camera position, the key is to get the extrinsic matrix of the camera. What I've researched is that we need to use a chessboard, but I wonder if I can continue my work without using that.

I think the answer is yes, it is possible to get the extrinsic matrix of hte camera with just a single square, though the error might be higher as there is less redundancy.  Let's look at how much information we obtain:

How many unknowns?  The extrinsic matrix has 5 real-valued parameters (the rotation matrix has 2 angles; the translation matrix has a 3D location).  In other words, there are 5 degrees of freedom or 5 unknowns.
How many equations?  We obtain 8 equations/constraints.  I am assuming we know the 3D location of each corner of the square (in world coordinates).  We also know the 2D location of each corner (in image coordinates).  The camera matrix maps each 3D point to the corresponding 2D point.  So, each point gives us 2 equations (from the known 2D image coordinates), and there are 4 corners, so we get 8 equations.

In short, we have 8 equations in 5 unknowns.  That's enough that it should be possible to recover the extrinsic matrix.  Of course, there's not a lot of redundancy here, so the error might be higher than if you used a chessboard.  A chessboard would provide a lot more equations (each corner inside the chessboard provides an additional point with a known 3D->2D mapping).

How would you recover it?  Follow the guidelines in https://ksimek.github.io/2015/03/29/QA-recovering-pose-of-calibrated-camera/.  In particular, you could solve for the 5 parameters of the extrinsic matrix using some optimization routine, such as gradient descent or L-BFGS.

Given some value for those 5 parameters, you can compute the camera matrix and map the 3D world coordinates of each corner to its corresponding 2D image coordinates; then you can compute the $L_2$ error (sum of squared error) between the inferred 2D coordinates and the known 2D coordinates from the picture.  This gives you an objective function that maps a value for the 5 parameters to an error term (which you want to minimize).  Next, you can apply any off-the-shelf optimization library to try to minimize this objective function.  This sounds pretty doable, with not too many lines of code to implement.


Reduce Subset-Sum to Sat Is there a reduction from SUBSET-SUM to SAT?
Just general SAT, not 3-SAT.
Also the given multiset S only has positive integers.
SUBSET-SUM is defined as follows:
Input: a multiset S = { x1 , ... , xn } of positive integers and a positive integer t
Output:
accept if there exists a sub-multiset { y1, …, ym } ⊆ S such that y1 + ··· + ym = t
reject otherwise
x1 , ... , xn and t are encoded in binary notation.
The boolean formula SUM should be used in the reduction.
Let a1···ak, b1···bk, c1···ck be k-bit integers.
SUM(a1, ... , ak, b1, ... , bk, c1, ... , ck) is true iff (a1···ak) + (b1···bk) = c1···ck
For example, if k = 3, sum(0, 1, 1, 1, 0, 0, 1, 1, 1) is true because 011 + 100 = 111.
Can this be done?
For example, what would the boolean formula produced by the reduction look like for
S = { 010, 011, 011, 100 }
t = 110

The Cook-Levin theorem demonstrates a reduction from SUBSET-SUM to SAT.
If you wanted a reduction from SAT to SUBSET-SUM, then yes, such a reduction exists; SUBSET-SUM is NP-complete, and thus the existence of such a reduction follows from the definition of NP-completeness.  You should be able to take any standard proof of NP-completeness for SUBSET-SUM and chain the reductions together to get the desired reduction.


What is the relation of complexity class $L^L$ to other complexity classes? What is the relation of complexity class $L^L$ to other complexity classes?

(Here $L^L$ is the complexity class of decision problems solvable by a TM in logspace with an oracle for a language in logspace.)

$L$ is self-low, i.e. $L^L=L$. The reason being that you can compute each oracle call yourself, using additional logarithmic space.


Show $B= \{z \mid (\exists x)\; P(x,z)\}$ is a recursive enumerable set Let $B = \{z \mid (\exists x)\; P(x,z)\}$ and $P$ be a computable predicate. Show $B$ is a recursive enumerable set.

My attempt

As $P$ is a computable predicate then there is a program that computes it, therefore $B= \{z \mid (\exists x)(\exists t)\;\text{STP}^{(1)}(x,z,t)\} \Rightarrow B= \{z \mid \Phi(x)\downarrow\} = W_z$ and so $B$ is a recursive enumerable set.

Further info

$\text{STP}^{(n)} (x_1, \ldots, x_n, y,t)$ is a predicate that is true if the program number $y$ halts after $t$ or fewer steps on inputs $x_1, \ldots, x_n$.

Note: please note this is the first time I ever try to solve this kind of exercises, so even if I got everything wrong and nothing makes sense, every nudge in the right direction is really welcome.

Hint, do you know the argument for the countability of the rational numbers?

Just enumerate every pair $a,b$ of natural numbers and output the $b$ if $P(a,b)$ is true.

Other way, can you construct a machine that given a $b$, answers YES if there is an $a$ such that $P(a,b)$ is true?


Preserving connectivity from a vertex by edges deletion Given a connected graph $G$ and a vertex $v$, is it polynomially solvable to find a maximal cardinality set of edges incident to $v$, which deletion (still) leaves vertex $v$ to be connected with all the other vertices in $G$?

Construct a DFS traversal tree, starting from $v$.

You can remove all edges of v that are not part of the tree.

The tree construction costs $O(|V|+|E|)$.

The identification of the edges that can be removed is $O(deg(v))$.


Are there any decision complexity classes which have no "complete" subclass? Are there any decision complexity classes, where the "-Hard" version of the class does not intersect with the original class?

Apart from the many answers from the Mathoverflow link commented above by Ariel, we have a very simple example as follows.

Under widely accepted conjecture that $\mathrm{P}\neq \mathrm{NP}$, we have that $\mathrm{NP}\setminus \mathrm{NP}$-$\mathrm{complete}$ does not have complete problem and therefore the "hard" part of it is well "above" it.

For the proof, use Ladner's result on $\mathrm{p}$-degree, for any two different $\mathrm{p}$-degrees $\mathrm{A}$ and $\mathrm{B}$, if $\mathrm{A}<_p\mathrm{B}$, then there must exist another $\mathrm{p}$-degree $\mathrm{C}$ in between: $\mathrm{A}<_p\mathrm{C}<_p\mathrm{B}$. So by removing $\mathrm{NP}$-$\mathrm{complete}$ from $\mathrm{NP}$, every $\mathrm{p}$-degree below the complete degree always has another non-complete degree above it.


How to solve recursion T(n)=T(n/2)+T(n/3)+n? How to solve recursion $T(n)=T(n/2)+T(n/3)+n$? I do not really know how to approach this kind of recurrence.

This is a straightforward application of the Akra-Bazzi theorem.

You can also show that $T(n) = \Theta(n)$ by induction. First, clearly $T(n) \geq n$. In the other direction, if we have shown that $T(m) \leq 6m$ for $m < n$, then
$$
T(n) \leq 6(n/2 + n/3) + n = 6n.
$$
Therefore as long as the base case holds, and if we ignore the fact that $n/2,n/3$ are not necessarily integers, we can prove inductively that $T(n) \leq 6n$.


How to generate random adjacency matrix with given number of components in graph I am building a graph package in C and a part of the work involves generating a random graph with a given number of components in the graph.

For example, if I wanted to generate a graph of 50 vertices and 5 components, then the module will take 50 and 5 as parameters and should be able to generate an adjacency matrix of the graph(for the time being I am implementing it using adjacency matrix only).
I have an idea that I can generate cliques of a different number of vertices and the number of cliques is exactly equal to the number of components. Then I can merge all the adjacency matrices corresponding to cliques to form the adjacency matrix of the graph.

Implementing this in C seems to be quite complicated, and I feel this is not an optimal solution as the graph will be dense every time and I can not achieve a sparse graph using this approach. Is there anything I am missing?

What you need is to take advantage of disjoint set, a very efficient data structure.

Here is the simple algorithm to generate a random graph of $n$ vertices and $m$ component.

MakeSet of size $n$.
Choose two random vertices that has not been connected by an edge.
Union these two vertices. That means adding the edge between them. Use an implementation of the union operation that tells you if two different components are unioned.
Stop if the number of components become $m$. Go back to step 2 otherwise.

There are existing implementations of disjoint set in C/C++, Java, Python, or just about every popular language.

You can implement step 2 in various ways.

You can use rejection sampling. Choose two random vertices. Repeat if the edge between them has been added.

This method is about the simplest to implement. It is efficient when the number of components is greater than a fixed proportion of the number of vertices. It takes little time if the number of vertices is not large.
You can also keep track of the degree of each vertex. Choose a vertex whose degree is not $n-1$. The choose an edge from that vertex.

You can vary step 3 as well. Step 3 above is aimed to produce a random graph with given number of components and the "minimal" number of edges.

One way to get random number of edges is to continue adding some random number of random edges after step 3 as long as no two different components become unioned/connected.
One way to get denser graphs is to not add the edge when it connects two different component with some probability $p$. The larger $p$ is, the more edges.

In the special case of one component (connected graph) and many vertices, you can also generate a random tree using Prüfer sequence, followed by adding some random edges.

As you have mentioned, you could also generate $m$ random connected graphs with given numbers of vertices, the joining them together. Each connected graph can be generated using either disjoint set or Prüfer sequence.

Note that for all above variations, the distribution of the generated graphs is probably different from each other. It is your task to choose an implementation whose randomness/biasness is what you want. Or roughly.


What is an addressable cell size? This question started with a quiz question from my university:
Consider a big-endian computer system with an addressable cell size of one byte. The values in memory cells 372 to 375 are shown in the table below. What 16-bit two's complement value (expressed as a decimal number) is stored at address 374?

Address    Value
372        0xC5
372        0x5E
374        0x7F
375        0x23

One thing I'm not clear about is what exactly does "addressable cell size of one byte" mean?

Addressable cell size of one byte, in this context, means that every cell in memory contains one byte. Variables which take up more than one byte are spread across several contiguous cells.


How to show that this variation of the algorithm (that runs until it finds a solution) still has linear expected running time? In the last section of chapter 3 (page 57) in Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Mitzenmacher and Upfal, a randomized algorithm is discussed for finding the median of a set $S$ of distinct elements in $O(n)$ time. The algorithm discussed is a Monte Carlo algorithm. As such if we would like to run this variation of algorithm till we find a solution, how do we show that it still has a linear running time?

The Algorithm (source, starts on slide 66, page 53):

  Input: A set $S$ of $n$ elements over a totally ordered
  universe$^{***}$.

  Output: The median of set $S$, denoted by $m$.

  Pick a (multi-)set $R$ of $\lceil n^\frac{3}{4} \rceil$ elements in $S$ chosen independently and uniformly at random with
  replacement.
  Sort the set $R$.
  Let $d$ be the $(\lfloor \frac{1}{2} n^\frac{3}{4} - \sqrt{n} \rfloor)$-th  smallest element in sorted set $R$.
  Let $d$ be the $(\lceil \frac{1}{2} n^\frac{3}{4} + \sqrt{n} \rceil)$-th  smallest element in sorted set $R$.
  By comparing every element in $S$ to $d$ and $u$, compute the set: $$C = \left\{ x \in S : d \leq x \leq u \right\}$$ and the numbers
  $$\ell_d = |\{x \in S : x  < d\}|$$ and the numbers $$\ell_u = |\{x
 \in S : x > u\}|$$
  If $\ell_d > \frac{n}{2}$ or $\ell_u > \frac{n}{2}$ then $FAIL$.
  If $|C| \leq 4n^\frac{3}{4}$ then sort the set $C$, otherwise $FAIL$.
  Output the $(\lfloor \frac{n}{2} \rfloor - \ell_d + 1)$th element in the sorted order of $C$.

I'm assuming you're referring to this as your source.

Short answer: The algorithm terminates in linear time. This does not mean it identifies a median in linear time.

The text first proves, by Theorem 3.9 on page 54, that the algorithm terminates in linear time.

Then it proves, by Theorem 3.13 on page 57, that the probability of failure is bounded by $n^{-1/4}$.

Then the text mentions (page 57):

  By repeating Algorithm 3.1 until it succeeds in finding the median, we can obtain an iterative algorithm that never fails but has a random running time. The samples taken in successive runs of the algorithm are independent, so the success of each run is independent of other runs, and hence the number of runs until success is achieved is a geometric random variable. As an exercise, you may wish to show that this variation of
  the algorithm (that runs until it finds a solution) still has linear expected running time.

The algorithm merely terminates in linear time, making it a Monte Carlo Algorithm. Although by successive runs and a bound on the probability of failure, we can guarantee a success at some point, making it a Las Vegas Algorithm. This successive trial algorithm is what you would attempt to show has an expected linear running time, by working on the geometric random variable represented by $k$ successive trials with bounded failure probability $n^{-1/4}$.


Randomly Choosing a N-Bit Prime I've been studying some number theory, and I came across this problem:

  Lagrange’s prime number theorem states that as N increases, the number of primes less than $N$ is $Θ(N/ log(N))$.

  Consider the following algorithm to choose a random n-bit prime:

  1) Pick a random n-bit number $k$.

  2) Run a primality test on $k.$

  3) If it passes the test, output $k$; else repeat the process.

  Show that this algorithm will sample on average $O(n)$ random numbers before hitting a prime.

I'm guessing I need to approach this probabilistically. Let $p$ be the probability that we randomly choose a prime. Let $E$ be the expected number of random numbers to choose before hitting a prime. Then, I need to express $E$ in terms of $p$, and show that it is less than or equal to $n$, right? Since, if we sample on average $O(n)$ numbers, then the expectation $E$ should be $\le n$.

But I'm a bit stuck on how to go about doing this. Is each event of choosing a random number binomial? Either we choose a prime or we don't, and each event is independent. But the expectation of a binomial RV is $np$, which is clearly not $\le n$.

I feel like I'm going about this all wrong. What am I missing here? Am I even on the right track? Thanks for your help.

Actually you should be thinking about a geometric random variable, not a binomial RV, since you're interested in the number of times that you have to sample before you hit a prime. And each sampling event is actually a Bernoulli trial (with probability of choosing a prime $p = \Theta(1/\log {2^n}$), where $n$ is the number of bits).

And for showing that the expected value is $O(n)$, you don't need to show that it's less than $n$. You actually need to show that there are some constants $k$ and $N$ such that the expected value is less than $kn$ for all $n \ge N$.

But besides that, you're on the right track.


If a poly-time solution exists for an NP-Complete (Decision) problem, then there exists a poly-time solution for the NP-hard (Optimization) flavor? This question boils down to: If a polynomial time solution exists for a decision problem, is there also a polynomial time solution for the same problems optimization flavor?
Let's take the Traveling Salesman Problem for example:

TSP Decision Problem (NP-Complete):
Input: Graph G, Budget b
Output: Does a route exist in G with a distance of at most b? (true/false)

TSP Optimization Problem (NP-Hard):
Input: Graph G
Output: What route in G has the shortest distance?

If one could find a polynomial time solution for the TSP Decision Problem wouldn't they also have a polynomial time solution for the TSP Optimization Problem?

Why? Binary search.

You can run your polynomial time solution for the TSP Decision Problem on G over and over with an input for b that increases, e.g. {1, 2, 4, 8, 16, 32, 64, 128, 256, ...}, until the algorithm returns false. Then you decrease b and slowly hone in on the correct answer.
Is this logic correct?

In this particular example, the following works:
Let $A$ be the algorithm for deciding whether some graph $G$ has a TSP-route has a cost of at most $b$.
We start by finding the optimal $b^\ast$ using $A$ and binary search on an appropriate range (say $[0, \sum_{e \in E(G)} w(e)]$) in polynomial time.
Following this, we start modifying the instance graph $G$ by setting edge weights to some large value so they will never be picked (e.g. $1 + b^\ast$) in a route of optimal cost $b^\ast$ and using $A$, we check whether the resulting graph still has a route of cost $b^\ast$.
If that is the case, we keep the modification and otherwise we undo it.
However, we now know that any such route (in the modified graph) must include the edge we messed with, so we store that.
Successively applying this to all edges we will find at least one such edge per pass over $E(G)$ and after at most $|V(G)|$ passes, we will have found a TSP-route of cost $b^\ast$ consisting of the edges we stored.
Hence we call $A$ an polynomial ($O(|V(G)| \cdot |E(G)|)$, or if you want $O(|V(G)|^3$) amount of times (in the second step, the first one also takes polynomially many) and all of our other operations can also be easily done in polynomial time.
Therefore, we can solve the optimization problem in polynomial time if we have a polynomial-time algorithm for the decision variant.
This approach also works for other problems (with slight variations for the second part); in fact I am not aware of a problem where this general strategy fails. I am actually pretty sure that one can use it to recover an accepting path of a polynomially-bounded NTM which can then be used to solve optimization variants of all $\mathsf{NP}$-complete problems.


Accurate way to compute the sum of exponentials In my work, I had to essentially compute the following quantity.

Given a sequence of positive floating point numbers $\{a_i\}_{i=1}^n$, such that

$$6000 \leq a_i \leq 7000$$

I needed to compute the following quantity (for some $n>1$, but for now can assume $n=1000$):

$$\log_2\left(\frac{\sum_{i=1}^n 2^{a_i}}{n}\right)$$

Direct computation is infeasible as the exponents are too large. So I rewrote the above expression as
$$a_1 + \log\left(\frac{1+\sum_{i=2}^n 2^{a_i-a_1}}{n}\right)$$

This also seemed a bit daunting but was better than what I had. My question was, is there a better way/algorithm to compute the above quantity? I appreciate any help on this.

The following observation might help:

$$\frac{\sum_{i=1}^n a_i}{n}\leq \log_2\left(\frac{\sum_{i=1}^n 2^{a_i}}{n}\right)\leq \max_{1 \leq i \leq n} a_i$$

Let $a = \max_i a_i$. Then your expression is equal to
$$
a + \log_2 \frac{\sum_i 2^{a_i-a}}{n},
$$
and this should be a very good approximation (this is "renormalization"). Don't forget to add the numbers in decreasing order of magnitude (that is, sort the $a_i$'s so that they are in decreasing order).


Bare Metal Operating Systems in High Performance Computing Few years back, I stumbled across Return Infinity - the OS framework designed around flat, 64bit memory model, with minimal MMU / VM overhead, etc.

I'm wondering if there are any public benchmarks or success stories of that approach - I'm eyeing it as something to practice doing low latency / high performance computing systems.

The theoretical advantages are substantial, if you're aiming to build a specific-purpose computer system (think bare redis / memcache, fft, transcoding, scientific computing etc).

The Return Infinity site you linked claims that BareMetal is an Exokernel.

Exokernel was an MIT research project from the mid to late 1990s which is still widely studied.  The philosophy behind Exokernels was that they would provide just mechanism and all policy would move to user-level libraries.  In later papers they more specifically said that the kernel provides protection and the libraries provide management.  The idea was to avoid expensive abstraction layers that are actually unneeded by certain applications.

In hindsight, it is probably not unfair to claim that the main achievement of the Exokernel research project was to invent a number of very clever techniques to make a microkernel OS perform better than a monolithic OS in some cases.  The key, I think, was finding ways to avoid kernel-boundary crossing costs.  One way they did this was through judicious and careful mapping of kernel data structures into an application's memory space.  This allows large amount of data to be transferred across the kernel/user boundary with fewer system calls and address space changes.  They also came up with several techniques for describing network and file system policies with tiny languages that could be easily checked and safely checked inside the kernel.  (So the core filesystem and network handling in Exokernel is actually done inside the kernel, rather than from a user-level service across an isolation boundary like it might be in a naive microkernel.)

The canonical paper on Exokernels is (IMHO) one of the best systems experience papers I've ever read.  It's been quite a while since I read it, but I recall it as being quite honest about both strengths and weaknesses of the approach.

Kaashoek, M. Frans; Engler, Dawson R.; Ganger, Gregory R.; Briceño, Héctor M.; Hunt, Russell; Mazières, David; Pinckney, Thomas; Grimm, Robert; Jannotti, John; Mackenzie, Kenneth: Application Performance and Flexibility on Exokernel Systems, Proceedings ACM Symposium on Operating Systems Principles, (SOSP-15):251-266, 1995.  (That's a Citeseer link and the Citeseer server is often down, so here also is the ACM link (paywalled).

The wikipedia article on Exokernels is not terrible, and gives a reference to at least one other (later) research project, Nemesis from Cambridge University.  Another efficient microkernel project that was being worked on around the same time as Exokernel was the L4 microkernel by Jochen Liedtke.


Time complexity of linear iteration bounded by logarithmic iteration? I was wondering about the time complexity of something like the following loop (where work() is O(1)):

for (i = 0 to N; i = i * 2) do
    for(j = 0 to i; j = j + 1) do
        work()
    end
end

The outer loop takes $\lg(N)$ steps, and the inner loop takes (on the final iteration) $N$ steps. So, a simple bound would be $O(N\lg(N))$. However, the inner loop doesn't fully reach $N$ until the last iteration, so I was wondering if the bound could be narrowed any further.

Derp, nevermind. I observed that on the last iteration, the inner loop takes $N$ steps. On the previous iteration, the inner loop would take $\frac{N}{2}$ steps. Overall, this would take $N, \frac{N}{2}, \frac{N}{4}, \frac{N}{8},...$ steps, which has a geometric sum to $2N$ steps. Therefore, the loop is $O(N)$.


Lambda Calculus Reduction Examples I'm still trying to get the hang of lambda calculus:
I completed simplified some of these already but am lost on the last two. I did so far:
\begin{align*}
    (\lambda x.x)y &\to y\\
    (\lambda x.y)x &\to x
\end{align*}

However, I'm not sure how to simplify these two:

\begin{gather*}
(\lambda x.x y)(\lambda y.y z)\\
(\lambda x.x y)(\lambda a.a b) p
\end{gather*}
They are a little bit similar, but I'm not sure how to simplify these expressions.

Just follow the rules of $\beta$-reduction and remember that function application associates to the left, i.e. $f g h$ is just syntactic sugar for $(f g) h$.

I'll show the steps for $(\lambda x.x y)(\lambda y.y z)$.

Strip off $\lambda$ from $(\lambda x.x y)$. You get the abstraction body $x\ y$, where $x$ is free now.
Substitute the argument $(\lambda y.y z)$ for $x$ into $x\ y$: $(\lambda y.y z)$ y. Notice that I didn't do anything with $y$ during this step.
Observe that the current $\lambda$-term is an application that can be reduced further. Again stripping off $\lambda$ we get $y\ z$ and substituting $y$ for $y$ results in the same term $y\ z$.

Here is the sequence of $\beta$-reductions without the intermediate steps:
$$(\lambda x.x\ y)(\lambda y.y\ z) \rightarrow_\beta (\lambda y.y\ z) y \rightarrow_\beta y\ z.$$

The second problem can be dealt with in the same way.


Is w ∈ L(M ) ⟹ ww ∈ L(M) co-semi-decidable? Consider the following langugage:

$\qquad L = \{ \langle M \rangle \mid M \text{ TM}, w \in L(M) \implies ww \in L(M)\}$.

I've been asked to decide whether this language is in R/RE/CO-RE. I've proved that the language doesn't belong to R and RE using Rice theorem, but I can't find a formal proof for CO-RE. Any suggestions?

You can show that this language $L$ is not co-RE in the following way:

Assume $L$ was co-RE, that is you have a semi-algorithm $A$ to decide given an input machine $M$ whether there exists a word $w\in L(M)$ such that $ww\notin L(M)$.

We show that we can build a semi-algorithm to decide the complement of the halting problem (on empty input), which is impossible.

The algorithm goes like this, on input $M$:

Build a machine $M'$ that

simulates $M(\varepsilon)$ on input $00$ and accepts if $M$ halts,
accepts on input $0$,
and accepts on all other inputs.

Run algorithm $A$ on $M'$.

Now $A(M')$ will answer yes iff $M'$ accepts $0$ but rejects $00$, meaning iff $M$ does not halt on empty input. Hence we have constructed an algorithm that semi-decides the complement of the Halting problem, which is a contradiction (it is not possible).


Drawing a DPDA for the language $L=\{w\in\{a,b\}^*|n_a(w)=n_b(w)\}$ in Sipser's format As I know $L=\{w\in\{a,b\}^*\mid n_a(w)=n_b(w)\}$ is a deterministic context free language. I have drawn a push dawn automata for this language in the format of Sipser as the following

However, as you may know, in Sipser's format, the transition
$$\varepsilon,$;\varepsilon$$
means that "don't read any thing from the input" and it doesn't mean "read $\varepsilon$ from the input". In Sipser's format this is a non-deterministic push down automata, since in deterministic one, we have that if there is a transition
$$\varepsilon,$;\varepsilon$$
outgoing from the state $q_1$ then it must not be an outgoing transition
$$a,$;a$ $$
from that state.
Could you please help me to draw a DPDA for that language in Sipser's format?

I myself have found that DPDA as follows:


Algorithm to compute a recursive function on a given set I am working on a property of a given set of natural numbers and it seems difficult to compute. There is a function 'fun' which takes two inputs, one is the cardinal value and another is the set. If the set is empty then fun should return 0 because fun depends on the product of the set and fun on all subsets of the complement set.

For clarification here is an example:

S is a set given S={1,2,3,4}. The function fun(2,S) is defined as

fun(2,S)=prod({1,2})*[fun(1,{3}) + fun(1,{4}) + fun(2,{3,4})] +
         prod({1,3})*[fun(1,{2}) + fun(1,{4}) + fun(2,{2,4})] +
         prod({1,4})*[fun(1,{3}) + fun(1,{2}) + fun(2,{2,3})] +
         prod({2,3})*[fun(1,{4}) + fun(1,{1}) + fun(2,{1,4})] +
         prod({2,4})*[fun(1,{1}) + fun(1,{3}) + fun(2,{3,1})] +
         prod({3,4})*[fun(1,{1}) + fun(1,{2}) + fun(2,{1,2})]

prod is defined as the product of all elements in a set, for example

prod({1,2})=2;
prod({3,2})=6;

I am trying to write the pseudo code  for this problem using recursive method but it's not working. The base case is the cardinal value should be more than zero that means there should be at least one element in the set other wise prod will be zero and fun will return zero.

Pseudo code:

fun(i,S)
if |S|=1 && i!=0
   return prod(S)
else if i==0
   return 0
else
  prod(subset s', s' is a subset of S and |s'|=i)*(sum over fun((for i=1 to m),{S-s'}), m=|S-s'|) //I don't know how to write code for this part and need help.
end if
end fun

prod(s)
if |s|=0
  return 1
else
  n=|s|
end if
temp=1
for i=1 to n
    temp *=s(i) //s(1) is the 1st element of set s
end for
return temp
end prod

Update:I tried to form a mathematical expression of the function fun
$fun(m,s)=\sum_{\sigma_{p}\subset s;|\sigma_p|=m}\left [\prod_{i}i\in \sigma_p \sum_{j=1}^{|s-\sigma_p|}\sum_{\gamma_p\subset (s-\sigma_p);|\gamma_p|=j}fun(j,\gamma_p)\right ]$

Where $|s|\geq 1$ and $m\geq 1$

$fun(m,s)=0$ if $s$ is a null set.

You haven't told us what the function is, so we can't give you an algorithm.

However, here's what I can say.  There are two general techniques that are often applicable to this setting:

Use dynamic programming (or memoization).  This will avoid you having to evaluate fun(k,S) more than once for any pair (k,S).
Look for mathematical identities that give you different ways to express your function.  Sometimes you can find different ways to express your function (e.g., by factoring out common terms or somesuch); if so, look for these, and see if any of them leads to a more efficient algorithm than the others.


what is actually a circular array and representation There are two ways to implement a circular array either take a new array of size 2N where N is the size of the initial array and copy initial array twice into that new array

array = [1,2,3,4,5]
new_array = [1,2,3,4,5,1,2,3,4,5]

Or we can use (i % N) where N is the size of the array, i is the index of that element

for(var i = 0; i < N + i; i++)
{
    console.log(arr[i%N])
}

What does exactly circular array mean? Is a normal array while representing?

Circular array is just a fixed size array. We call it circular just because we define the operations on the array in such a manner that its limited size can be utilized again and again and it apparently appears that we are traversing the array in clockwise or anti-clockwise way.

The best example for understanding the circular array is a Queue. We can implement Queue with the help of a circular array. In a Queue we insert at the end and delete from the front.

Suppose you have an array of size 5. Let say we implement Queue using this array. We will have two pointers - one for the front of Queue and one for the rear of Queue. Initially front and rear both will point at index 1. We may do let's say 3 insertions in the beginning. Rear pointer would point at index 3 and front would point index 1 at this moment (consider 1-based indexing).

Now let say we make 2 deletions and now front is 3 and rear is 3. At this moment we have 2 array positions vacant in the front of array. We can use this space again rather than reallocating an array once rear reaches the end of the array. What we can do to utilize these spaces again, is to introduce the circularity, which when rear or front reaches the end of the array re-indexes the rear to 1th index. Since we have changed the index from last index to the first index, we say that the array is circular (apparently in a clockwise manner).

The idea to re-allocate an array and copy the original array twice is totally wrong. The % operation lets you re-index the pointer once you have reached the end of array (e.g. 6%5 = 1). The approach with the mod operation is the correct approach to implement a circular array.

EDIT

I have added an image which will help you:


How to prove an polynomial run time is faster than exponential using definition of big O This is for homework so feel free to not give me an answer but steer me in the right direction.

The problem states:

  Prove that $n^{1000000} = O(1.000001^n)$ using the formal definition of Big-O.

The definition of Big-O is:

$\hspace{2cm}T(n)=O(f(n)):\,\exists\;c\gt0\;$ and $\;n_0\ge0,\;$ such that $\;T(n)\le c\cdot f(n)$

Now, I know that there is also the definition that

$\hspace{4cm}$For every $\;r\gt0\;$ and $\;d\gt0,\; n^d = O(r^n)$

But how exactly am I supposed to prove this without using induction or a limit equation? Any guidance on where to start?

This is what I have so far:

$\hspace{7.6cm}\frac{T(n)}{f(n)}\le c$

$\hspace{6.8cm}\frac{n^{1000000}}{1.000001^n}\le c$

$\hspace{6cm}\frac{1.000001^{1000000n}}{1.000001^n}\gt\frac{n^{1000000}}{1.000001^n}$

EDIT: I continued simplifying.

$\hspace{5.4cm}1.000001^{999999n}\gt\frac{n^{1000000}}{1.000001^n}$

Do I stop here?

$\hspace{5.3cm}1.000001^{1000000n}\gt n^{1000000}$

$\hspace{3.4cm}1000000n\cdot log(1.000001)\gt 1000000\cdot log(n)$

$\hspace{5.8cm}log(1.000001)\gt \frac{1}{n}\cdot log(n)$

$\hspace{6.8cm}1.000001\gt n^{1/n}$

What would the above even tell me?

In order to prove that $f(n) = o(g(n))$ (and so $f(n) = O(g(n))$) for two positive functions $f(n),g(n)$, it is enough to prove that
$$
\lim_{n\to\infty} \frac{f(n)}{g(n)} = 0.
$$
In your case, you can use L'Hôpital's rule, together with induction on $k$. We will show that for all integer $k \geq 0$ and all $c > 1$,
$$
\lim_{n\to\infty} \frac{n^k}{c^n} = 0.
$$
This is clear for $k = 0$. Given that it holds for $k-1$, it holds for $k$ since
$$
\lim_{n\to\infty} \frac{n^k}{c^n} =
\lim_{n\to\infty} \frac{k}{\ln c} \frac{n^{k-1}}{c^n} = 0,
$$
by the induction hypothesis.

If $k$ is not integral, the result still holds, since $n^k \leq n^{\lceil k \rceil}$.


optimizing for loops Disclaimer: I'm not a compiler expert.  I'm simply curious and come seeking enlightenment.
I've seen people claim that -- for efficiency -- for loops should generally use a zero comparison for termination.  So rather than:
void blink1(int n) {
    for (int i=0; i<n; i++) {
        blink_led();
    }
}

you should write:
void blink2(int n) {
    for (int i=n; i>0; i--) {
        blink_led();
    }
}

I thought that was a little silly: why put the burden on the human if a compiler could interpret both cases as "blink_led() n times"?
But using Mr. Godbolt's Compiler Explorer, I now think I'm wrong.  For all the compilers I tried, the "compare against zero" always produced a shorter loop.  For example, x86-64 gcc 10.2 with -O3 optimization produced the following inner loops:
blink1:
    ...
.L3:
        xor     eax, eax
        add     ebx, 1
        call    blink_led
        cmp     ebp, ebx
        jne     .L3

vs
blink2:
    ...
.L12:
        xor     eax, eax
        call    blink_led
        sub     ebx, 1
        jne     .L12

So here's the question
This seems like such a common case.
Why can't (or why doesn't) the compiler notice that the effect of the for loop is simply "do this thing N times" -- whether counting up or counting down -- and optimize for that?

What you read is total nonsense, except for the most primitive of compilers. First, comparison with an integer is as fast, possibly even faster than comparison with a constant. Second, a good optimising compiler will take a loop written using some common pattern and turn it into the best possible code; it may not recognise your obfuscated pattern and produce less good code for it.
And lastly, you shouldn’t replace readable with unreadable code unless there is an actual need for it. If you spend an hour making the change, it needs to produce 20 hours saved CPU time at least. When you are at that level, better algorithms are very likely to give better savings.


How would you prove a family of functions is universal? A set of functions from a universe U of keys to n buckets is universal if for every pair of keys in U, say x and y, such that x != y, the probability of h(x) = h(y) is less than or equal to 1/n, for a random function h in the set of functions.

Say you're given a prime number p, and a random integer n, such that p is greater than or equal to n. Say we want to look at the family of functions where we pick a random integer i, and define each function hi = ((i * x) mod p) mod n. The input can be any integer from 0 to p-1, and the the output can be any integer from 0 to n - 1.

How would you prove that this family of functions is universal. Or similarly, if you pick an arbitrary p and n, how would you come up with a counter example?

A good approach is to simultaneously try to prove it, and try to disprove it.

To try to prove it: look at what the definition says, plug in the definition of the hash function, and see what number-theoretic fact needs to be true.  Can you find any proof for this number-theoretic fact?

To try to disprove it: look for a counterexample.  When looking for a counterexample, I suggest starting with the smallest parameters you can, to make manual calculations tractable.  In this case, you might start with prime $p=3$ and number $n=2$; I think that is the smallest possible parameter setting that meets your requirement.  Now, calculate the probabilities explicitly and see if it meets the definition.  (The numbers are so small you should be able to calculate that explicitly by just enumerating all cases.)  What do you get?

If you try this, I think you'll be able to answer your own question.  If you're still stuck, edit the question to show what you tried along each of these two directions and where you got stuck.


Asymptotic complexity of function with two Input variables Suppose I have a function with two input below.

$f(m,n) = \log {n^m} + 100n \log \log {m^5} + 150m + 4n^2 + 1000$.

Is it safe to say that $f(m,n)$ is $\mathcal{O}(m \log n)$, or is it $\mathcal{O}(n^2)$ instead? I think the first one is more representative as it includes the variable $m$. But that may not be the case if $n$ is relatively very larger than $m$.

No, it's not safe to say either.  The intuition: When $n$ is really large, $f(m,n)$ grows faster than $O(m \log n)$.  When $m$ is really large, $f(m,n)$ grows faster than $O(n^2)$.

Instead, what you can say is that $f(m,n)$ is $O(m \log n + n^2 + n \log \log m)$.  Why?

$$\begin{align*}
f(m,n) &= \log {n^m} + 100n \log \log {m^5} + 150m + 4n^2 + 1000\\
  &=m \log n + 100n\log \log m + 100n\log 5 + 150m + 4n^2 + 1000\\
  &=O(m \log n) + O(n \log \log m) + O(n) + O(m) + O(n^2) + O(1)\\
  &=O(m \log n) + O(n \log \log m) + O(n^2) + O(m \log n) + O(n^2) + O(1)\\
  &=O(m \log n + n \log \log m + n^2).
\end{align*}$$

If $n \log \log m = O(m \log n + n^2)$ (I'm not sure if this is true), then you could simplify this to $O(m \log n + n^2)$.


Parallelising random reads seems to work well — why? Consider the following very simple computer program:

for i = 1 to n:
    y[i] = x[p[i]]

Here $x$ and $y$ are $n$-element arrays of bytes, and $p$ is an $n$-element array of words. Here $n$ is large, e.g., $n = 2^{31}$ (so that only a negligible fraction of the data fits in any kind of cache memory).

Assume that $p$ consists of random numbers, uniformly distributed between $1$ and $n$.

From the perspective of modern hardware, this should mean the following:

reading $p[i]$ is cheap (sequential read)
reading $x[p[i]]$ is very expensive (random reads; almost all reads are cache misses; we will have to fetch each individual byte from the main memory)
writing $y[i]$ is cheap (sequential write).

And this is indeed what I am observing. The program is very slow in comparison with a program that does only sequential reads and writes. Great.

Now comes the question: how well does this program parallelise on modern multi-core platforms?

My hypothesis was that this program does not parallelise well. After all, the bottleneck is the main memory. A single core is already wasting most of its time just waiting for some data from the main memory.

However, this was not what I observed when I started experimenting with some algorithms where the bottleneck was this kind of operation!

I simply replaced the naive for-loop with an OpenMP parallel for-loop (in essence, it will just split the range $[1,n]$ to smaller parts and run these parts on different CPU cores in parallel).

On low-end computers, speedups were indeed minor. But on higher-end platforms I was surprised that I was getting excellent near-linear speedups. Some concrete examples (the exact timings may be a bit off, there is a lot of random variation; these were just quick experiments):

2 x 4-core Xeon (in total 8 cores): factor 5-8 speedups in comparison to single-threaded version.
2 x 6-core Xeon (in total 12 cores): factor 8-14 speedups in comparison to single-threaded version.

Now this was totally unexpected. Questions:

Precisely why does this kind of program parallelise so well? What happens in the hardware? (My current guess is something along these lines: the random reads from different thread are "pipelined" and the average rate of getting answers to these is much higher than in the case of a single thread.)
Is it necessary to use multiple threads and multiple cores to obtain any speedups? If some kind of pipelining indeed takes place in the interface between the main memory and the CPU, couldn't a single-threaded application let the main memory know that it will soon need $x[p[i]]$, $x[p[i+1]]$, ... and the computer could start fetching the relevant cache lines from the main memory? If this is possible in principle, how do I achieve it in practice?
What is the right theoretical model that we could use to analyse this kind of programs (and make correct predictions of the performance)?

Edit: There is now some source code and benchmark results available here: https://github.com/suomela/parallel-random-read

Some examples of ballpark figures ($n = 2^{32}$):

approx. 42 ns per iteration (random read) with a single thread
approx. 5 ns per iteration (random read) with 12 cores.

Forget for a moment all of the issues related to the access to main memory and level 3 cache. From a parallel perspective, ignoring these issues, the program parallelize perfectly when using $p$ processors (or cores), owing to the fact that, once you partition the work to be done through domain decomposition, each core must process either $\left\lfloor {\frac{n}{p}} \right\rfloor$ or $\left\lceil {\frac{n}{p}} \right\rceil$ elements and there is no communication and/or synchronization overhead since there is no functional dependence among the processors. Therefore, ignoring memory issues you expect a speedup equal to $p$.

Now, let's take into account the memory issues. The super-linear speedup you actually observed on your high-end Xeon based node is justified as follows.

A parallel system might exhibit such behaviour if its memory is hierarchical and if access time increases (in discrete steps) with the memory used by the program. In this case the effective computation speed could be slower on a serial processor than on a parallel computer using similar processors. This is because a sequential algorithm using $n$ bytes of memory will use only $n/p$ bytes on each processor of a $p$ processor parallel system, while
cache and virtual memory effects could instead reduce the serial processor’s effective computation rate.

For $n = 2^{31}$ bytes, we need 2048 Mbytes of memory. But, when using 12 cores as in your last example, every core needs to deal with only 2048/12 Mbytes of data, which is about 170 Mbytes. High-end Xeon processors are equipped with a cache level 3 whose size ranges from 15 to 30 Mbytes of size. Clearly, with this huge cache size the cache hit ratio is high, and this explains the good or even super-linear speedup-observed.

Regarding your second question, current architectures already prefetch data by evicting cache lines and replacing them as required to exploit temporal and spacial locality of data. But this will not be enough for a single core processing 2048 Mbytes of data. If you restrict $n$ to about 170 Mbytes, then you should see on a single core more or less the same performances, since you are now running under (more or less, not exactly) the same conditions.

Finally, besides QSM (Queueing Shared Memory), I am not aware of any other theoretical parallel model taking into account at the same level the contention for access to shared memory (in your case, when using OpenMP the main memory is shared among the cores, and the cache is always shared as well among the cores). Anyway, even though the model is interesting, it did not obtain great success.


Which all nodes will qualify as an ancestor? I was going through the fundamentals of tree structure and the definition for ancestor is as follows:

  A node u is an ancestor of v if there is a path from u to v.

Consider the node 11. Is node 2 (not the root, the other one on the left) an ancestor of node 11? It is strictly not a grandparent of 11, however, there does exist a path between these nodes. This is confusing to me, because this would also imply that the sibling nodes (5) of 11 would qualify as an ancestor.

The root-2 is an ancestor of 11 (it's the great-grandparent) but you're asking about the 2 on the left, which is not an ancestor. There is no directed path from that node to 11 since the left-2 has no outgoing edges. Paths must respect the direction of the edges.  Siblings are not ancestors for the same reason.

(Sometimes, we want to talk about a path that ignores the edge directions. These are usually referred to as something like "paths in the underlying undirected graph".)


How to prove the set of powers of 2 in ternary representation to be non-regular using pumping lemma? Given the set of natural numbers, $S = \{2^i|i\in\mathbb{N}\}$ let $L$ be the language defined as the ternary representation of all numbers in $S$. How can you prove that this is not a regular language using the pumping lemma?

I cannot seem to find any sort of pattern for ternary representations of $S$, and so I'm finding it really difficult to prove this using the pumping lemma.

I tried to make a few strings in $L$ and got $\{1, 11, 22, 121, 1012, 2101, \dots\}$ but cannot find any sort of pattern that leads to using the pumping lemma. So, how would you prove that this is not a regular language using the pumping lmma? Thanks in advance.

This answer is a simpler version of Colin McQuillan's answer to the same question.

Suppose the language is regular. The pumping lemma gives strings $u,v,w$ such that every string $x_n=u v^n w$ is
a power of $2$.

Interpreting these strings as numbers and writing $d$ and $e$ for the lengths of $v$ and $w$ respectively, we have
$$
x_n = u 3^{dn+e} + v 3^{d(n-1)+e} + v 3^{d(n-2)+e} + \dots + v 3^e + w.$$
So,
$$x_{n+1}-3^dx_n = v3^e + w - 3^dw.$$

Note that the right-hand side is a constant as $n$ goes to infinity. Letting $c$ be the right-hand side, we have
$$\frac{x_{n+1}}{x_n} - 3^d= \frac{c}{x_n}.$$

Since $x_{n+1}$ is a bigger power of 2 than $x_n$, $\dfrac{x_{n+1}}{x_n}$ is always an integer. That means the right-hand side is always an integer as well. Since $\dfrac c{x_n}$ goes to $0$ as $n$ goes to infinity, it must become 0 eventually.

Well, when it does become 0, we have $\dfrac{x_{n+1}}{x_n}=3^d$, which cannot happen since the left-hand side, a power of 2 that is greater than 1, can never be a power of 3.

Here is an easy exercise.

Exercise. Check that the above proof works the same if you replace 3 by any positive integer that is not a power of 2.