Representing a sentence using propositional logic I am confused regarding a propositional logic representation of a sentence.

Please note that this sentence is not realistic:

"A person who is male (M) is smart (S) if he is tall (T), but otherwise is not smart."

Which of the following propositional logic formulas correctly represents the above:

(a) $(M \wedge S) \iff T$

(b) $M \Rightarrow (S \iff T)$

Note that $\Rightarrow$ and $\iff$ represents "only if/implies" and "iff and only if," respectively.

The solution to the problem is (b)

The solution claims that (a) is NOT an option because it asserts, among other things, that all tall people are male, which is not what is asserted. This makes sense to me, I think (not confident, but this is not the main point of this post).

The solution claims that (b) IS a correct representation because it is saying that if a person is male, then they are smart IF AND ONLY IF they are tall. I don't understand that, and based on my current understanding, I don't agree with this because the "IFF" part is saying that if the person is tall, then they are smart, and that is not what the problem statement said. The problem statement only states that a person who is male is smart if he is tall.

So I feel like (b) is not correct, but if you swap out the $\iff$ for $\Rightarrow$ then it becomes correct.

Am I misunderstanding something here?

The sentence says that a male "is smart (S) if he is tall (S)", that gives $T \Rightarrow S$, but it also says "but otherwise is not smart", which gives $\neg T \Rightarrow \neg S$, and this is equivalent to $S \Rightarrow T$ by contraposition. Thus together this gives $S \iff T$ under the condition $M$. Therefore (b) is correct.


Assigning all nodes in a tree a parent and children If one was given a tree in the form of a list of $A,B$ (not implying which one is the parent) pairs implying that node $A$ and $B$ were connected by an edge, how could a root node be determined and each node be assigned children and a parent such that by recursing up through its parent, its parents parent and so on the eventually one will eventually hit the root  e.g.

Could be represented as
4,1 4,2 4,3 4,5 6,5

and a possible solution could be

1: parent:4, children: None
 2: parent:4, children: None
 3: parent:4, children: None
 4: parent:None, children:1,2,3,5
 5: parent:4, children: 6
 6: parent:5, children: None

where 4 is the root.

The tree in your diagram is undirected. Undirected trees don't have a uniquely determined root because the edge $xy$ just means that nodes $x$ and $y$ are related: it doesn't specify that one is the parent of the other.

If you're told to make a particular node the root, you can do so by directing all of the edges away from the root, which you can do by depth-first search (or breadth-first search, or any other enumeration procedure).

Conversely, if the edges are directed, so $xy$ means "$x$ is the parent of $y$" (or vice-versa, if you want to adopt the opposite convention), then you can find the root by starting at any node and navigating to the parent until you find a node without a parent. Since the root is the unique node without a parent, you're done.  You might also want to check that the graph really is a tree, i.e., that it is connected and acyclic.


Given regular language $L$, is $L_1 = \{ w \mid \text{each prefix of } w \text{ of odd length} \in L \}$ regular? I was given a question and don't really know to solve it.

  Given a regular language $L$, is the following language also regular?
   $$L_1 = \{ w \mid \text{each prefix of } w \text{ of odd length is in $L$} \}.$$

I think that $L_1$ should be regular, but I don't have a clue how to prove it.

Thank you for any input.

Try constructing an NFA for $\hat L:=\{w|$ there is an odd length prefix of $w$ that is $\notin L\}$, given a DFA for $\overline L$, and then show $L_1=\overline {\hat L} $.

If I'm not mistaken, this should work out.


Given N vertices and M edges find if two nodes are in the same connected component? Given a set of $n$ people and $m$ friendship relations between those people (relation is between two persons) we need to suggest a data structure that supports the division of those people into maximum groups such that if 2 people are connected, they belong to the same group.

Asking $k$ queries, where each query is asking if $(i,j)$ are 2 people are in the same group, what data structure can have a total running time of $O(m+n+k)$?

For example:

$n = \{1,2,3,4\}$

$m = \{(1,2) , (2,3)\}$
(person 4 has no friends)

So the above relations will form 2 groups:
$\{1,2,3\} ,\{4\}$

I thought about taking an Undirected graph and checking if two vertices are in the same connected component. The problem is that I do $k$ checks. And I need to find a way such that a check will be $O(1)$.

The problem is that you want to do a graph traversal every check : that is way too often.

Do a graph traversal to find the connected component of each vertex (e.g. give them a number). This takes $O(m+n)$ time. Store these numbers in an array indexed by the vertices, let's call it $A$. Then check if two vertices $i$ and $j$ are in the same connected component in $O(1)$ time by checking whether $A[i] = A[j]$.


If $A$ is context-free then $A^*$ is regular I am currently studying for my exam and I am having trouble to solve this question:

Right or wrong: If $A$ is context-free then $A^*$ is regular.

I think it's wrong because if $A$ is context-free it means that $A$ can be a non-regular language. And the non-regular languages are not closed under the Kleene star operation (at least I think so). I am not sure how write this in a more formal way.
Maybe like this?
Let $A=\{a^nb^n \mid n \in \mathbb{N}\}$. Then we know that $A$ is non-regular and context-free. However, I'm not sure what $A^*$ is.

Let $A=\{a^nb^n \mid n \in \mathbb{N}\}$. Then we know that $A$ is non-regular and context-free. Also we can see that $A^*\cap a^*b^*=A$. Since $a^*b^*$ is a regular expression, we do know that it is regular. Lets assume that A* is regular.
The regular languagues are closed unter intersection. Therefore $A^*\cap a^*b^*$ must be also regular(because we assume that $A^*$ is regular). This would implicate that A is regular because  $A^*\cap a^*b^*=A$. This is a contradiction because we know that A is not regular. Therefore A* cant be regular.
$q.e.d$


Modelling of minimal NOR-circuit problem with CP I'm currently working on a Constraint Programming problem which I find difficult to model.

Here 's the definition of the problem :

" Given a specification of a Boolean function f(x1, ..., xn) in the form of a truth table, to find a NOR-circuit (meaning only NOR gates) satisfying the specification that minimizes depth (and, in case of a tie in depth, with minimum size).
In order to simplify the problem, several assumptions are made:

• Only NOR gates with 2 inputs and 1 output can be used: more general
NOR gates with more inputs are not allowed (i.e., the fan-in of NOR
gates is always 2).

• The output of a NOR gate can only be the input of a single gate:
outputs cannot be reused as inputs of more than one gate (i.e., the
fan-out of NOR gates is always 1).

• In addition to the input signals of the Boolean function to be implemented, constant 0 signals can also be used as inputs of NOR gates.
Constant 0 signals as well as input signals can be used as many times
as needed as inputs of NOR gates. On the other hand, the circuit does
not need to use all input signals. Similarly, the constant 0 signal does
not have to be used if it is not needed."

Source : https://www.cs.upc.edu/~erodri/webpage/cps/projects/Q2-16-17/proj.pdf

Since this is the first time that I'm confronted to this kind of problem, I'm having difficulties finding "good" decision variables. Maybe I'm missing something trivial ...

Do you have any idea/hint on how to model this problem ?

This is a logic synthesis problem.  Specifically, without the "fan-out of 1" limitation, this looks like the circuit minimization problem.  Circuit minimization is $\Sigma_2^P$-complete, so you should not expect any efficient algorithm for it.  There are many algorithms in the literature that you can explore, including Karnaugh Maps, Quine-McCluskey, Espresso, and others.  I wouldn't consider constraint programming the obvious first way to approach this problem.

If you have a requirement to use constraint programming for some homework exercise, well, you should do  your own exercise, but here is a hint: you should be able to tell whether there exists a circuit of depth $d$ and width $w$ by building a $d \times w$ grid of NOR gates, then using decision variables to represent which edges are used to connect these gates.  How could you use that to solve the original problem?

Limiting fan-out to 1 seems unrealistic, as gnasher729 explains.


Overlapping between two intervals: reasoning / algorithm to find the set of disjoint and overlapping intervals Consider the positive integers {1, 2, 3, 4, ...} and the corresponding Integer Number Line.

Suppose we have four integer numbers, A, B, C and D.

For example:

_________________A___________________________B__________________
___________________________C__________D_________________________

or

_________________A___________________________B__________________
___________________________C____________________________D_______

Consider the notation AB as the set of all consecutive numbers A, ...., B, and the interval CD as the set of all consecutive numbers C, ..., D.

I would like to know a simple yet abstract and generalizaed resoning (mathematical demonstration would be really apreciated) that we can apply if we want to find all intervals consisting of the "disjoint" numbers and the "overlapping" numbers between both set of numbers, AB and CD.

Example 1: If AB = {2, 3, 4, 5, 6, 7, 8, 9} and CD = {4, 5, 6, 7}, we have the following subsets for each set AB and CD:

for AB: {2, 3}, {4, 5, 6, 7} and {8, 9}
for CD: {4, 5, 6, 7}

Example 2: If AB = {2, 3, 4, 5, 6, 7, 8, 9} and CD = {4, 5, 6, 7, 8, 9, 10, 11, 12}, we have the following subsets for each set AB and CD:

for AB: {2, 3}, {4, 5, 6, 7, 8, 9}
for CD: {4, 5, 6, 7, 8, 9} and {10, 11, 12}

But, which one would be a great and yet simple reasoning behind disjoint and overlapping sets of numbers between two given set of integer numbers?

Thanks very much for any clue!!

For two integers $A$ and $B$ where $A\le B$, let $[A,B)$ denote the half-closed half-open interval that consists of the numbers $A, A+1, \cdots, B-1$. In particular, if $A<B$, then there are $B-A$ numbers in $[A,B)$. If $A=B$, then there is no numbers in $[A,B)$. For example,

$[0,1)$ means the number 0.
Both $[0,0)$ and $[3, 3)$ mean no numbers.
$[5,11)$ means the numbers $5,6,7,8,9,10.$
To denote the numbers $-2, -1, 0, 1, 2$, we can use $[-2, 3)$.

A nice property of half-closed half-open interval: If $L\le M \le R$, then $[L,R) = [L,M) \sqcup [M,R)$.

Proof: I am afraid it is obvious by definition. Done.

Suppose we are given $[A, B)$ and $[C, D)$, where $A\lt B$ and $C\lt D$. Then $[A,B)$ overlaps $[C,D)$ if and only $\max(A,C)\lt \min(B,D)$.

Proof:

"$\Rightarrow$": Let $n$ be a number in both $[A,B)$ and $[C,D)$, i.e.,
$A\le n\lt B$ and $C\le n \lt D$. Then $\max(A,C)\le n\lt \min(B,D)$.

"$\Leftarrow$": $A\le \max(A,C)\lt \min(B,D)\le B$, i.e., $\max(A,C)\in [A,B)$. Similarly, $\max(A,C)\in [C,D)$. So $[A,B)$ overlaps $[C,D)$.

Done.

Suppose $[A,C)$ and $[B,D)$ overlap. Then we have the following set decompositions.

$[A,B) = [A, \max(A,C))\sqcup[\max(A,C), \min(B,D)]\sqcup[\min(B,D), B)$
$[C,D) = [C, \max(A,C))\sqcup[\max(A,C), \min(B,D)]\sqcup[\min(B,D), D)$

Proof:

We have $A\le \max(A,C) \le \min(B,D)\le B$. So,

$$\begin{align}
[A,B) &= [A, \max(A,C))\sqcup[\max(A,C),B)\\
&= [A, \max(A,C))\sqcup[\max(A,C), \min(B,D)]\sqcup[\min(B,D), B).
\end{align}$$

Example 1: If $I = \{2, 3, 4, 5, 6, 7, 8, 9\}$ and $J = \{4, 5, 6, 7\}$, then $I=[2,10)$ and $J=[4,8)$. We have the following set decompositions.

$[2,10) = [2, 4)\sqcup [4, 8) \sqcup [8,10)$.
$[4,8) = [4, 4)\sqcup [4, 8) \sqcup [8,8) = [4,8)$.

Example 2: If $I = {2, 3, 4, 5, 6, 7, 8, 9}$ and $J = {4, 5, 6, 7, 8, 9, 10, 11, 12}$, then $I=[2,10)$ and $J=[4,13)$. We have the following set decompositions.

$[2,10) = [2, 4)\sqcup [4, 10) \sqcup [10,10)= [2, 4)\sqcup [4, 10)$.
$[4,13) = [4, 4)\sqcup [4, 10) \sqcup [10,13)= [4, 10) \sqcup [10,13)$.

The above examples should indicate clearly enough the algorithm that decomposes two overlapping intervals into disjoint intervals.


Task scheduling algorithm that limits concurrency My prof introduced us an algorithm with semaphores that was used to solve the "dining philosophers" problem.
The algo is ok, apart from that it limits concurrency.

What does mean that it "limits concurrency" and why this happens ?

You (or the algo) probably assigns a constant amount of time slice per process. Since amount is constant, as with number of process increases this effectively hinders concurrency. If this is the case, you need a fair scheduler type algorithm. Check on different algo's on a linux kernel may have.


Bubble sort: how to calculate amount of comparisons and swaps For a given sequence 1, N ,2 ,N −1 ,3, N −2, ... I want to calculate the number of comparisons and swaps for bubble sort. How can I accomplish that using $\theta ()$ notation? I would know how to do it for any sequence, but not for a given one.

Number of swaps: The number of swaps in Bubble sort is exactly the number of inverted pairs, i.e. the number of pairs $(i,j):i < j\wedge s[i]>s[j]$. This number of pairs should be $(n/2-1)+(n/2-2) + ... + 1$ which is of the order of $n^2$.

Number of comparisons: This is of the order of $n$ times the number of passes through the list, which is of the order of $n$, as the element N needs to get to the end.

Therefore you have $\Theta(n^2)$ comparisons and swaps.


Why can't we find shortest paths with negative weights by just adding a constant so that all weights are positive? I'm currently reading introduction to algorithms and came by Johnson’s algorithm that depends on making sure that all paths are positive.

the algo depends on finding a new weight function (w') that is positive for all edges and keeps the correctness of the shortest paths relations.

It does so by calculating h(s), h(d) values to be added to the w original value.

My question is, why not just find the smallest w in the graph and add it to all edges ? this will satisfy both conditions and will require less calculation.

Adding a weight to every edge adds more weight to long paths than short paths. (Long in the sense of having many edges.)

For example, suppose the lowest-cost edge has weight $-2$ and there are two paths from $a$ to $b$: a single edge of weight $3$ and a path with two edges, each of weight $1$.  The two-edge path has the lowest weight.  However, if you add $2$ to every edge, the one-edge path has weight $5$ but the two-edge path now has weight $6$, so you get the wrong answer.


How to prove that a language is not recursively enumerable How does one prove that some arbitrary language $L$ is not recursively enumerable?

I know I can prove that the language $L$ is recursively enumerable by constructing a Turing machine $M$ that accepts all words in the language (and the language would be even recursive if $M$ halts on all inputs).

But it is not clear to me how to prove that language in not RE. I was thinking about showing the fact, that such TM could not be constructed for a given language, but proving non-existence is always difficult.

Here are two methods.
Consider the complement
Theorem. If a language $L$ and its complement are both RE, they are both recursive.
Proof. Decide whether $w\in L$ by enumerating $L$ and its complement in parallel and accept/reject as soon as $w$ appears in one of the enumerations. $\Box$
So, if you can prove that $L$ is not recursive but its complement is RE, then $L$ is not RE.
Halting problems
Theorem. Let $\mathcal{M}$ be the class of Turing machines equipped with an oracle for the ordinary Turing machine halting problem. The halting problem for $\mathcal{M}$ is not RE.
Proof. Essentially the same as the proof that the ordinary Turing machine halting problem is not recursive. $\Box$
So, if you can reduce the halting problem for $\mathcal{M}$ to your problem, your problem is not RE.


If $\mathbf{P} = \mathbf{NP}$, then is $\mathbf{L} = \mathbf{NL}$? If $\mathbf{P} = \mathbf{NP}$, then is $\mathbf{L} = \mathbf{NL}$? I am asking this question because, for other non-deterministic classes, it seems $\mathbf{P} = \mathbf{NP}$ always establishes that they are equal to their deterministic counterparts.

This is an open research question. At our current state of knowledge, knowing $\mathbf{P}=\mathbf{NP}$ would neither imply $\mathbf{L}=\mathbf{NL}$ nor $\mathbf{L}\neq\mathbf{NL}$. And, conversely, knowing $\mathbf{L}=\mathbf{NL}$ or $\mathbf{L}\neq\mathbf{NL}$ wouldn't imply anything about the $\mathbf{P}$ vs $\mathbf{NP}$ question.  (But it's possible that the proof of $\mathbf{L}$ vs $\mathbf{NL}$ would tell us something about $\mathbf{P}$ vs $\mathbf{NP}$ or vice-versa.)

We know $\mathbf{L}\subseteq \mathbf{NL} \subseteq \mathbf{P} \subseteq \mathbf{NP} \subseteq \mathbf{PSPACE} = \mathbf{NPSPACE}$, where the equality follows from Savitch's theorem.  The nondeterministic version of the space hierarchy theorem says that $\mathbf{NL}\neq \mathbf{NPSPACE}$ so we know that at least one of the set inclusions must be strict. We kinda think they're all strict but our current knowledge doesn't rule out any subset of them, as long as it includes at least one between $\mathbf{NL}$ and $\mathbf{PSPACE}$.


Reduction from max-cut to min-cut Algorithms for the finding of an MST in a graph can be applied for both maximum and minimum spanning trees.

It is well known, however, that the finding of a max-cut in a graph is an NP-hard problem while the min-cut problem can be easily solved in polynomial time.

Why aren't the two equivalent?

What is the restriction that I’m missing here?

Thanks!

Some intuition involves the notion of a convex function. You can look up the formal definition, or consider the quintessential example of a convex function, namely $x^2$. Minimizing a convex function is easy, since there is a unique minimum, and moreover if you start anywhere and keep going done, you will eventually reach the minimum. Maximizing a convex function is a different thing. Suppose for example that you want to maximize $x^2$ under the constraint $x \in [\alpha,\beta]$. In order to do that, you need to compute the function at both endpoints $\alpha,\beta$ and choose the maximum. Now imagine that you function is multivariate and has lots of inputs. Minimizing is still easy - there is a unique minimum that can be reached by descent - but maximizing is problematic, since there are many potential maxima.

MAX-CUT and MIN-CUT are related to the cut function, which gets as input a cut, and outputs the number of edges cut. This is a set function rather than a function on $\mathbb{R}^n$, but it has the property of submodularity, which is a form of convexity for set functions. Indeed, in general one can minimize submodular functions, but maximizing them is NP-hard.


Common subgraph isomorphism with K vertex I'm looking for subgraph isomorphism of at least K vertex between Graph A and B.
I only can come up with the dumbest algorithm, which is:

Compute all combination of vertices with length K of Graph A.
Run subgraph isomorphism test for every combination vertices against Graph B, probably using VF2 algorithm.

Upon researching I found Maximum Common Subgraph. On one paragraph, there is

  The associated decision problem, i.e., given G1, G2 and an integer k, deciding whether G1 contains a subgraph of at least k vertices isomorphic to a subgraph of G2 is NP-complete.

This "associated decision problem" is exactly what I'm looking for. But I can't look further than this Wikipedia article to learn about it. Can anybody point me to related paper or text about this problem? Or even better, slightly explain to me how solution of the problem might works compared to my dumb algorithm.

My sincerest thank to you all.

The fact that the Maximum Common Subgraph is NP-complete suggests that your "dumb" algorithm is about as good as it gets. You certainly cannot expect a polynomial time solution.

There are a few approaches you could try, depending on the exact context you are working in, the details of which are more than can reasonably be reproduced here, but a good starting point would be Abu-Khzam et al.'s paper "The Maximum Common Subgraph Problem: Faster Solutions via Vertex Cover" (In Proceedings of AICCSA 2007, pp. 367-373). This describes a variety of exact approaches which exploit different properties of the input.


Is emptiness of the intersection of the languages of two TMs decidable? Let

$\qquad \mathrm{DISJOINT} = \{ \langle M_1,M_2 \rangle : M_1, M_2 \text{ are TMs and } L(M_1) \cap L(M_2) = \emptyset\}$.

How do I know if this language is decidable or not? And How do I prove my answer?

Assuming you have a decider $R$ for DISJOINT, you could use this to make a decider D for $E_\text{TM} = \{\langle M\rangle\mid L(M)=\emptyset\}$ as follows:

D(<M>) =
   return R(<M>, <A>)

where $A$ was a TM, selected in such a way that $\langle M\rangle\in E_\text{TM}$ if and only if $(\langle M\rangle, \langle A\rangle)\in\text{ DISJOINT}$. All that's left for you is to find the $A$ and show that it satisfies the needed conditions. (There are a couple of ways to make this choice.)


Troubles understanding this Interval Scheduling question Can someone explain how to prove what this question is asking? I'm terrible at proofs and the fact that I don't even understand the hint is very troubling. This is a homework question.

Consider the Interval Scheduling problem. We have seen that the “earliest deadline-first” greedy algorithm finds an optimal set of jobs.

Consider now the “shortest-job-first” greedy
algorithm, which initially sorts the jobs by increasing duration — i.e., so that f(1)−s(1) ≤ f(2)−s(2) ≤
. . . ≤ f(n)−s(n). It then considers the jobs in this order; each job considered is added to a set A (initially
empty) if it does not conflict with any job currently in A. Thus, at the end, the algorithm has produced a
set of non-conflicting jobs A. (In contrast, the “earliest-finish-time-first” algorithm initially sorts the jobs
by increasing finish time — i.e., so that f(1) ≤ f(2) ≤ . . . ≤ f(n). Other than the initial sorting of jobs,
the two algorithms are the same.)
We have seen that the “shortest-job-first” greedy algorithm does not necessarily produce an optimal
set of jobs.

In this problem you must prove that it produces a set of feasible jobs whose size is at least
half the size of an optimal set. Thus, in some sense, the set of jobs produced by this algorithm is not too
bad compared to the optimum. (Contrast this to the “earliest-start-time-first” algorithm, which produces
a set of jobs whose size can be an arbitrarily small fraction of the optimal.)
More precisely, let m be the size of an optimal set of jobs, and let A be the set of jobs computed by
the shortest-job first greedy algorithm. Prove that |A| ≥ m/2.

Hint. Let B be any optimal set of jobs and j be any job in A. What is the maximum number jobs in B
with which j conflicts?

You'll want to start by answering the question in the hint, and then make another argument to obtain the final result.

The hint is saying that for any job $j \in A$, there is a fixed upper bound on the number of intervals in $B$ with which $j$ overlaps. Think about what happens if $j$ intersects with three or more intervals in $B$. Would this be possible using the Shortest-Job-First algorithm?

Let the upper bound you obtain from the hint be $k$. Then, you can make the following argument (presented informally, as it is just a hint). Using our result above, we can state that in the worst case, we have each $j \in A$ overlapping with a subset of $k$ distinct jobs of $B$, where these subsets of $k$ jobs are pairwise disjoint. This gives you an upper bound on $|B|$ in terms of $|A|$.

Can you take it from here?


In SAT, do we require an assignment for arbitrary variables? I am reading about the Satisfiability Problem, in page (5) the author gives the following example :

$(P \lor Q \lor R) \wedge
(\bar{P} \lor Q \lor \bar{R}) \wedge
(P \lor \bar{Q} \lor S) \wedge
(\bar{P} \lor \bar{R} \lor \bar{S})$

A satisfying assignement is $: P,Q,\bar{R},\bar{S}$.

A different assignments is $P,\bar{R}$ to satisfy the four caluses. This means that $Q,S$ can be set arbitrarily to $True$ or $False$.

Do we require an assignment for all variables or we only reqiure to set variables that satisfy the input (i.e. $P,\bar{R}$ discluding $Q,S$) ?

Does that mean that the satisfying assignment of $P,\bar{R}$ is more efficient than $P,Q,\bar{R},\bar{S}$ given that it uses less variables ? Is there any resources to read about it ?

Also, given that $P,\bar{R}$ satisfy the input, does that mean that we can disclude $Q,S$ from the original Boolean Formula ?

If the truth value of a formula is determined by setting only a subset of the variables, an author might skip describing the remaining truth values. However, by definition, a truth assignment gives a value to every variable.


Proving $L = \{ w : w \neq w^R \}$ over $\Sigma = \{0,1\}$ is CFL I'm trying to prove $L = \{ w : w \neq w^R \}$ over $\Sigma = \{0,1\}$ is CFL.

Define $G = ({S,T}, \Sigma, R, S)$ where $R = S \to 0S0|1S1|0T1|1T0, \; T \to 0T|1T|\varepsilon$.
Now I want to show that $\mathcal{L}(G) = L$.
One direction is fine, where given $w\in \mathcal{L}(G)$, it must've deduced using $S \to 1T0|0T1$, and therefore $w \neq w^R$.

But given $w \in L$, all I know is $w \neq w^R$. How can I prove $w\in \mathcal{L}(G)$?

Use induction.

For instance:

Define $\mathcal{L}_i(G) = \{ w \in \mathcal{L}(G) \mid |w| = i \}$ for $i \in \{ 0, 1, 2, \ldots \}$.
Prove that for all $w$ and $i > 1$, $w \in \mathcal{L}_i(G)$ if and only if $\exists x \in \Sigma, v \in \mathcal{L}_{i-2}(G) : xvx = w$.


What is Pumping length for Union of Regular languages? This is an exam question.
For E = {a,b}. let us consider the regular language
$L= \{x|x = a^{2+3k} or x=b^{10+12k}, k >= 0\}$
Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for L?
A)3
B)9
C)5
D)24
Ans is 24.
As per me pumping length is the length which gets actually repeated.
So, basically it's the length of y as per pumping lemma statement.
Now, for the first regular language, $a^{2+3k}$
How I visualized?
There would be sure 2 states which accept min 2 'a' ( since k>=0).
Now, then I have $a^{3k}$
Means, which should definitely have a loop of length 3.
So, I choose x=2 (first 2 states) y=3 (the repeating part) and z=0.
So this first language must have atleast 3 as the pumping length.
And in similar lines the other must have. Atleast 12 as pumping length.
(X=10, y=12, z=0)
And that's why as per me 24 is right.
(Still sketchy at concluding)
Plz tell me if my understanding of Pumping length is right?
If no plz try suggesting some links/references.
If yes then have I applied the Concept right?

A pumping length is a positive integer $p$ such that any string of $L$ of length at least $p$ can be decomposed in the form $xyz$ with $|xy|\leq p$, $|y|>0$ and for all $n\geq0$ the words $xy^nz$ are in $L$.
Assume that $p<12$. Then the word $b^{10+12}$ should be able to be decomposed as above. We cannot take $y$ with $1\leq|y|\leq p <12$. Otherwise $xz=xy^0z$ wouldn't be in $L$.
We can take $p=12$ or larger.
If $10+12k=|b^{10+12k}|\geq p\geq 12$ then $k\geq1$ and we can decompose $b^{10+12k}$ as $xyz$, with $x=\epsilon$, $y=b^{12}$ and $z=b^{10+12(k-1)}$. Then $|xy|=12\leq p$ and for all $n\geq0$ we have $xy^nz=b^0b^{12n}b^{10+12(k-1)}=b^{10+12(n+k-1)}$ in $L$, since $n+k-1\geq k-1\geq0$
If $2+3k=|a^{2+3k}|\geq p\geq 12$, then $k\geq4$. We can decompose $a^{2+3k}$ as $xyz$ with $x=\epsilon$, $y=a^3$ and $z=a^{2+3(k-1)}$. We have that $|xy|=3\leq p=12$, $|y|=3\geq1$ and for all $n\geq0$ we have $xy^nz=a^0a^{3n}a^{2+3(k-1)}=a^{2+3(n+k-1)}$ in $L$, since $n+k-1\geq k-1\geq0$.
So, the minimum pumping length of $L$ seems to be $12$. Any larger value would also work in this case.


Comparison of $(\log^* n)!$ and $(n\log n)^b$ How can I compare $(\log^*n)!$ with $(n\log n)^b$?
I know that $n^b<n!$.

For sufficiently large values of $n$, and $b>0$:
$$
( \log^*n )! < ( \log \log n )! < (\log \log n)^{\log \log n} = 2^{(\log\log n) \log \log \log n} \in o(2^{b \log n}) \subset o( (n \log n)^b ).
$$


Does it hold that $F \equiv \sigma(F)$ for a CNF formula $F$ and a permutation $\sigma$ s.t. $F \vDash \sigma(F)$? Suppose we have a CNF formula $F$ and a permutation $\sigma$ of its literals such that for any literal $x, \sigma(\neg x)=\neg \sigma(x)$ and $F \vDash \sigma(F)$.

Does it hold that $F \equiv \sigma(F)$?

It is the case when $\sigma$ is a syntactic or even a semantic symmetry of $F$ but I don't know if it hold for any permutation that respects the hypothesis above.

The crucial observation is that if $A \vDash B$ then also $\sigma(A) \vDash \sigma(B)$. This follows since all $\sigma$ does is rename variables and flip some variables. For example, if $\sigma(x) = \lnot y$, $\sigma(y) = z$, and $\sigma(z) = x$, then $A(x,y,z) \vDash B(x,y,z)$ implies also $A(\lnot y, z, x) \vDash B(\lnot y, z, x)$.

Let $G$ be the set of all permutations of literals satisfying your condition. I claim that $G$ forms a group with respect to composition. Since $G$ is finite and composition is associative, it suffices to check that it is closed under composition. Indeed, if $\sigma(\lnot x) = \lnot \sigma(x)$ and $\tau(\lnot x) = \lnot \tau(x)$ then $\sigma(\tau(\lnot x)) = \sigma(\lnot\tau(x)) = \lnot\sigma(\tau(x))$.

Since $G$ is a group, $\sigma^{|G|}$ is the identity. If $F \vDash \sigma(F)$ then, applying $\sigma$ on both sides, we get $\sigma(F) \vDash \sigma^2(F)$. More generally, we get $\sigma^n(F) \vDash \sigma^{n+1}(F)$, and so $\sigma^n(F) \vDash \sigma^m(F)$ whenever $m \geq n$. In particular, choosing $n = 1$ and $m = |G|$, we obtain $\sigma(F) \vDash F$.

The group $G$ is known as the signed symmetric group, denoted $B_n$, where $n$ is the number of variables.


Why can Multilayer neural networks solve non-linear problems I understand what a multilayer neural network is, but what about them allows them to solve non-linear problems unlike perceptrons? Is it the fact that they can extend to any number of outputs/hidden layers? Or is it another feature?

A single-layer network is already nonlinear, but it's only a limited kind of nonlinearity.

Yes, the ability to have multiple layers and multiple hidden nodes is what allows multi-layer neural networks to express any function.

Let me give you an analogy that provides intuition but shouldn't be taken too seriously.  A single NAND gate can compute only a single, simple function.  However, when you consider circuits containing NAND gates, they can express any boolean function: the ability to have multiple layers of NAND gates, and multiple intermediate gates in the middle, allows you to express any boolean function.  Something vaguely similar happens with multi-layer neural networks: each individual unit provides a limited amount of nonlinearity, like a NAND gate, and the ability to compose them is what lets you express more complex nonlinear functions.


Most efficient know way to match orders Consider two 2D-Array $B_{ij} $ (the buy array) and $S_{ij}$ (the sell array) where each $i^{th}$ element is associated with an array of floating-point values and each of the floating point value, in turn, is associated with an array of integers.

For example

B = [
  0001 => [ 32.5 => {10, 15, 20},
            45.2 => {48, 16, 19},
            ...,
            k1
          ],
  0002 => [ 35.6 => {17, 35, 89},
            68.7 => {18, 43, 74},
            ...,
            k2
          ]
]

and similiarly for the sell array.

This is akin to an order association system of a stock/commodity exchange

BuyOrderBook = [
                 CompanyName => [
                                 Price1 => [Qty1, Qty2...],
                                 Price2 => [Qty1, Qty2...]
                                ]
                 SecondCompany = [...]
               ]

What is the fastest way known to solve the following problem:

  Input: Buy array $B$, Sell array $S$
  Problem: Decide wether there are $(c_1 \Rightarrow p_1 \Rightarrow q_1) \in B$ and $(c_2 \Rightarrow p_2 \Rightarrow q_2) \in S$ with $q_1, q_2 > 0$ and $p_2 \geq p_1$.

In short, what is the fatest way of matching orders for an exchange?

Update in response to comments

Lets say, MSFT has 25 shares @ \$60 to be sold and there is buyer who is willing to offer \$61 for 10 shares of MSFT. Then the buyer gets 10 shares @ \$60 and the buy order book becomes empty while the sell order book now is updated with new quantity - 15 shares @ \$60.

Now take the reverse case, MSFT has 25 shares @ \$60 to be bought and there is seller who is willing to receive \$61 for 10 shares of MSFT. Then the trade will not be executed because seller is demanding a minimum of \$61 and the buyer is offering a maximum of \$60. The orders are now stored and await until new orders are received.

(This is the limit order principle, where the seller specifies minimum price at which he is willing to sell at and buyer specifies maximum price at which he is willing to buy).

Post execution, the sell order book will be (25-10)=15@86.5 while buy order book will be empty (10-10)=0.

Maintain your buy-order book as an array of companies.
For each company, keep a priority queue of prices (max for buy and min for sell).
For each price, keep a queue of orders.

To check for matching orders, for each company, call find-min() and find-max() on the company in the sell array and buy array to find the best buy/sell prices. If max > min, then try to fulfill the order. To fulfill the order, pull elements off of your buy and sell queues for that company and price, until one of your price queues is empty. When the price queue is empty, delete the corresponding element from its priority queue, and perform the check again.

This strategy costs constant time per order, and $O(\log p_i)$ per price change, where $p_i$ is the number of prices for company $i$.


Search Algorithm with two areas of solutions I need some help with a problem. I have currently an algorithm. This algorithm gives me a true or false for a variable which I need to iterate( e. g. From 0 to 100} . Till now I solved it with a brute force method. So I just enhance the variable by a factor, enter the variable to the algorithm till I get a true.
This really needs a lot of run time. Then I switched to the bisection method. Here I had the problem that sometimes the function is true for some values and then switches again to false. This means if the area is before the half of the interval, the bisection method can not find the area before because the bisection method doesn't get the true in therefore took the second half of the interval.

My question is now: does sb has an idea how I could fix that? Are there any search algorithms which are exactly for that problem?

With no other given assumptions, it is a linear solution in the most optimal scenario.
One can have better solution (binary search) in problems where all the values after first true are true. But if there is only one element, it is a O(n) solution.


Satisfying assignments, twice-3SAT NP complete I wanted to solve the following problem about 3SAT . The question is
1. to show if the problem is NP-complete and
2. whether the problem has two different satisfying assignments.

"TWICE-3SAT Input: A propositional formula ϕ in conjunctive normal form, such that each clause consists of exactly three literals (as in 3SAT). Question: Does ϕ have at least two different satisfying assignments?"

I understand that we have to use reduction of a known NP-complete problem (such as an independent set) to the problem asked. But I can't go further. I would appreciate your help. I have been working on this for almost a week but I cannot go further.

Hints:

Showing that the problem is NP is easy.
To show that it is NP-hard, show first that TWICE-SAT is NP-hard (see next step).
In order to show that TWICE-SAT is NP-hard, reduce from SAT. The idea is to add a "dummy" satisfying assignment, which is always going to be satisfying; any satisfying assignment of the original SAT instance will translate to a (different) satisfying assignment of the new instance.
Either reduce TWICE-SAT to TWICE-3SAT, or use insights from your proof in step 3 to prove that TWICE-3SAT is NP-hard.


Complexity of computing the antiderivative of a given function Disclaimer: I don't know much computational complexity theory. I am nevertheless curious.

If function $f(x)$ has a certain level of computational complexity (which I actually don't know how to measure), what can we then say about the computational complexity of the following indefinite integral?

$$\int f(x) \, \mathrm d x$$

For example, can we say something about how long it takes to approximate the integral of $f$ within an error of $\epsilon$, given that we know how long it takes to compute $f$ within an error of $\epsilon$?

Kawamura, in his paper Lipschitz Continuous Ordinary Differential Equations
are Polynomial-Space Complete, mentions a classical result of Friedman (Theorem 3.4) which implies that computing the integral of an easy function could be a hard task (check the paper for the exact definitions), essentially since integration is like summing over many different values.

The result mentioned above is in the framework of computable analysis. The answer could be different in other models of computation. See Real-number Computability from the Perspective of Computer Assisted Proofs in Analysis for a recent survey of models of computation on real numbers.


Is the bitwise-xor of a Uniform bit string and a non_uniform bit string Uniform? Having two bit strings $x,y \in \left\{0,1\right\}^n$, where $x$ is selected following a uniform distribution but $y$ is not.

Is $z = x \oplus y$ uniform?

Yes, if $x$ and $y$ are chosen independently of each other.

One way to quickly see this is to note that the map $x \mapsto x \oplus y,$ for some constant $y,$ is a permutation of $\{0,1\}^n.$  This means that if $x$ is uniformly distributed over $\{0,1\}^n$ and $y$ is constant, then $x \oplus y$ is also uniformly distributed.  And since $x \oplus y$ is uniformly distributed for every constant $y,$ it follows that, if we make $y$ itself a random variable (independent of $x$), then the distribution of $x \oplus y$ will be a mixture of uniform distributions, and thus uniform.

Or we can just do the math:

$$\begin{aligned} {\rm P}(x \oplus y = a)
&= \sum_{b \in \{0,1\}^n} {\rm P}(x \oplus y = a \land y = b) \\
&= \sum_{b \in \{0,1\}^n} {\rm P}(x = a \oplus b \land y = b) \\
&= \sum_{b \in \{0,1\}^n} {\rm P}(x = a \oplus b)\ {\rm P}(y = b) & (x \perp y) \\
&= \sum_{b \in \{0,1\}^n} \frac1{2^n}\ {\rm P}(y = b) & (x \sim \mathcal U\{0,1\}^n) \\
&= \frac1{2^n} \sum_{b \in \{0,1\}^n} {\rm P}(y = b) \\
&= \frac1{2^n}.
\end{aligned}$$

However, the assumption of independence is absolutely necessary here — without it, it's easy to come up with counterexamples, such as letting $x$ be uniformly distributed over $\{0,1\}^n$ and letting $y = x,$ which of course implies that $x \oplus y = 0^n.$


Finding independent set of size n in an undirected graph Is there an algorithm that, given an undirected graph, finds an independent set of size n (where n is less than or equal to the total number of vertices)?

(Note: for the sake of standardization, I'm using $n$ for the number of vertices in the graph, and $k$ for the number you want in your independent set.)

The problem of whether such a set even exists is actually NP-complete, by reduction from the clique problem (since an independent set is a clique in the complement of the graph). So unless P=NP, you're not going to get any better than exponential time. This limits you to rather small graphs in practice.

The easiest algorithm for this is simple brute force: run through all sets of $k$ distinct vertices, and check whether each one is independent. If it is, return it. As expected for brute force, this runs in $O(n^2 2^n)$. An improvement was found by Xiao and Nagamochi in 2017, which brings this down to about $O(1.2^n)$. (Unfortunately, I don't have access to their paper, so I can't summarize their algorithm here.)


Smallest NFA accepting concatenations of two words of the length $k$ which are different at all positions Let $k\in \mathbb N$

I'm looking for a small NFA build for the language of concatenation of two words of the length $k$ which are index-wise different, i.e. $$L_k=\{u\cdot v \in \Sigma^* : |u|=|v|=k\wedge \forall i, u_i\neq v_i\}$$

Notice that since $k$ is fixed, $|L_k|=(|\Sigma|\cdot(|\Sigma|-1))^k$, and is regular as a finite language.

$%$

The trivial DFA for the language contains $k$$|\Sigma| \choose k$$+1$ states and just "remembers" which letters it have seen during the first $k$ letters, however if $k=o(|\Sigma|)$, we can create a significantly smaller NFA.

$%$

A "simple" NFA for it would be of size $O^*(2^{2k})$ (more precisely, $O(k^2 \log |\Sigma| 2^{2k+O(\log^2 k)})$ ):

$%$

Take a $(|\Sigma|,2k)$-universal set (i.e. a set of vectors $\mathcal V\subseteq \{0,1\}^{|\Sigma|}$ such that for every vector $u\in \{0,1\}^2k$ and a $2k$ indices, there exists a vector $v\in \mathcal V$ such that $v_{|I}=u$, i.e. if we look only at these $k$ indices in $v$ we find $u$). Such families of size $O^*(2^{2k})$ are known.

We think of each vector $v$ as a function $\Sigma\to \{0,1\}$, where $v(\sigma_i)=1⟺v_i=1$.

$%$

Create an NFA as follows:

From the starting state $q_0$ create an $\epsilon$-transition to a new state for any $v\in \mathcal V$. Denote this state by $q_v$.
From each $q_v$ build a path of states which accepts all words whose first $k$ letters are mapped by $v$ to 0, and the later $k$ letters are mapped by $v$ to 1.

$%$

Basically, the idea is that the universal set allowes us to partition the letters which are allowed to appear in the first $k$ symbols from the rest, and we get every word in the language since there has to be a corresponding vector $v\in \mathcal V$ which partitions it right.

So the questions are:

  What is the size of the smallest NFA for $L$?

  Is this construction optimal?

  What lower bound we can prove for such automaton size?

Update: this doesn't answer the question that the original poster was looking for, and doesn't help with  the general case where $|\Sigma|>2$, so the question remains open.

Here is a simpler construction, showing that in the case where $\Sigma=\{0,1\}$, $O(k \cdot 2^{2k})$ states suffice, and in fact you can recognize the language with a DFA with that many states.

Let's start by looking at the complement language:

$$\overline{L_k} = \{u \cdot v \in \Sigma^* : |u| = |v| = k, \exists i . u_i = v_i\}.$$

Notice that this can be recognized by a NFA with $2k^2 |\Sigma|$ states.  The NFA first guesses $i$ and a symbol $x$, then accepts all strings $u \cdot v$ where $u_i = v_i = x$.

Convert this to a DFA using the standard subset construction.  We get a DFA with $\le 2^{|\Sigma| k + 1} k$ states.  Now we can compute its complement, which is another DFA with the same number of states that recognizes $L_k$.  Since it is a DFA, it is in turn automatically a NFA, too.

This beats your construction for the case where $|\Sigma|=2$, but otherwise leads a NFA that's larger than your scheme.  However, I thought it might be of interest, both because it is so simple, and because it in fact provides a DFA (not just a NFA) to recognize your language $L_k$.


Logic behind O(n) solution for 'Maximum length sub-array having given sum' I am unable to understand the logic behind O(n) solution of this classical problem- Maximum length sub-array having given sum (negative numbers included),

I read that it can be solved in O(n) time complexity and O(n) space complexity, but the logic behind it is still unclear to me. I have read this solution:

Initialize sum = 0 and maxLen = 0.
Create a hash table having (sum, index) tuples.
For i = 0 to n - 1, perform the following steps:

Accumulate arr[i] to sum.
If sum == k, update maxLen = i + 1.
Check whether sum is present in the hash table or not. If not present, then add it to the hash table as (sum, i) pair.
Check if (sum - k) is present in the hash table or not. If present, then obtain index of (sum - k) from the hash table as index. Now check if maxLen < (i - index), then update maxLen = (i - index).
Return maxLen.

Examples:

Input : arr[] = { 10, 5, 2, 7, 1, 9 }, k = 15
Output : 4
 The sub-array is {5, 2, 7, 1}.

Input : arr[] = {-5, 8, -14, 2, 4, 12}, k = -5
Output : 5

Taken from this link: https://www.geeksforgeeks.org/longest-sub-array-sum-k/

Could someone please elaborate on the solution provided for this problem?

This is an example of a dynamic algorithm. I will adapt the algorithm in the link, as I don't think that it is written in the most helpful way.

Initialise sum = 0 and maxLen = 0.
Create a hash table having (sum, index) tuples.
For i = 0 to n-1, perform the following steps:

Set sum = sum + arr[i].
If sum == k, update maxLen = i+1, continue from here to next iteration.
Check whether sum is present in the hash table or not. If not present, then add it to the hash table as (sum, i) pair.
Check if (sum-k) is present in the hash table or not. If present, then obtain (sum-k, index) from the hash table. If maxLen < (i-index), then update maxLen = (i-index).
Return maxLen.

If sum == k at case 3.3, then we know that the sub-array [a[0],...,a[i]] is the maximum-length sub-array whose sum is k. Otherwise, we continue to 3.3. If there was no sub-array until now whose sum we equal to the current sum, then we add (sum, i) to the hash table. The reason we don't overwrite existing entries will become apparent at the end.

We now continue to 3.4. If we came across a sub-array S whose sum was sum - k, then there must be pair of the form (sum - k, index) in the hash table. S is therefore the sub-array of the form [a[0], ..., a[index]].

We obtain a new sub-array [a[index + 1], ..., a[i]] whose sum is k and whose length is i - index as follows: Remove all elements in S from the sub-array [a[0], ..., a[i]]. Its sum must be sum - (sum - k) = k. Now the question is whether the length of the new sub-array i - index > maxLen. If it is, set maxLen = i - index.

Now we can see why we didn't update existing entries in 3.3. We do not want to add larger arrays (greater index) for a given sum. This would have made i - index smaller.

This is a polynomial-time algorithm, as we look at each element exactly once, and the hash table accesses are also constant time.


Given a binary min-heap, getting a sorted array of the $\log n$ smallest elements Let's say we have a binary min-heap of size $n$, and we want to get an array of the smallest $\log n$ values in the heap, sorted. What is the best complexity that we can get and how do we implement it?

The simplest solution would be using $\text{Get-Min, Delete-Min}$, $\log n$ times, and that would be of time complexity of $O(\log ^2 n)$.

I've been told that this problem can be solved in time complexity of $O(\log n \log \log n)$, but I couldn't figure out an algorithm that reaches that time complexity.

Consider another min-priority queue $q$. The result will be in array $a$.

Push the top of the heap into $q$.
For $i$ from $1$ to $\log n$:

Set $a_i = \text{pop}(q)$.
Push the two sons of $a_i$ in the heap into $q$.

$q$ may be implemented with a min-heap of size  $O(\log n)$, so the overall complexity is $O(\log n \log \log n)$.


Find a subset in constant many queries Black box of $f(x)$ means I can evaluate the polynomial $f(x)$ at any point.

Input: A black box of monic polynomial $f(x) \in\mathbb{S}[x]$ of degree $d$.
Question : $\mathbb{S} \subseteq \mathbb{Z}$, unbounded from both sides

Here $\mathbb{S} \subseteq \mathbb{Z} $ is an interval unbounded from both sides. For example interval $(-b,\infty]$, where $b$ is any fixed value and this interval is bounded from left side. I am allowed to make only constant many queries to oracle. I want to find such an subset $\mathbb{S}$.

Unbounded interval: An interval is said to be left-bounded or right-bounded if there is some real number that is, respectively, smaller than or larger than all its elements. An interval is said to be bounded if it is both left- and right-bounded; and is said to be unbounded otherwise

Please give a reference to material also if possible. If anything is not clear please ask in the comments I will try clear it.

Motivation : Find a polynomial in two or three queries

If you don't know any bounds on the coefficients beforehand, then you cannot give them any bound without $d$ queries. Suppose you have made queries of $f(x)$ on $x=x_1,\ldots,x_{d-1}$, and claim that the coefficients of $f(x)$ are all at least $-b$. However, a different monic polynomial $f(x)-N(x-x_1)\cdots(x-x_{d-1})$ has the same evaluation on all the $d-1$ queries, and when $N$ is large enough the coefficient of $x^{d-1}$ in this polynomial must be smaller than $-b$, leading to a contradiction.


books on algorithms for beginners in Ruby or Python or C. Not too math heavy I am currently at student at Turing and I would like to learn more about algorithmic design while studying programming. Our school mainly deals more with web software, Ruby, and Rails, but I would like to gain an education in algorithms and data structure while here.

Do you have any books for beginners on algorithms or data structure? I only know Ruby and a little Python. Is there anything that you recommend that isn't the CLRS book... it's a tad over my head right now.

How much mathematics do I need to know? My guess is that I also need a book on discrete mathematics?

To be honest, it doesn't really matter what languages you use to learn an algorithm (it's only the syntax that changes, the logic is the same).

However, if you want a Python specific one check out:

Python Algorithms: Mastering Basic Algorithms in the Python Language

A more generic one is by the O'Reilly series (they make wonderful books!):

Algorithms in a Nutshell

There are also a number of youtube tutorials, so check out this, although it is in Java, it is very good!


Time complexity - Algorithm to find the lowest common ancestor of all deepest leaves This is the problem statement I came across today.

Given a binary tree, find the lowest common ancestor of all deepest leaves.

I came up with a correct algorithm, but I would like to confirm the running time of this approach.

The algorithm is as follows:

Traverse the tree and find the deepest level of the tree, dmax.
Traverse the tree and find all leaves at depth dmax.
Given that LCA(A,B,C) = LCA(LCA(A,B),C), traverse all nodes found at step 2 and calculate LCA.

The subroutine for LCA(A,B) is simple. Starting at A, go all the way up to the root and store each visited node in a hashset. Then, starting at B, go up until you find a node which is contained in the hashset.

I know the first two steps of the algorithm are both O(n), where n corresponds to the number of nodes in the tree. However, I am uncertain about the last step.

LCA(A,B) subroutine has a linear complexity. But how many nodes, in the worst scenario, can be found at step 2?.

Intuitively, I would argue that it has to be far less than n nodes.

As @Rick Decker explained, you could have $n/2$ leaves at the max depth in the one case. In this case, step 3 is $O(n\log n)$. This post shows the worst case. Consider a tree $T$ consists of a chain of $n/2$ nodes where the remaining $n/2$ nodes are attached as a balanced tree at the bottom of the chain. This gives every leaf depth $n/2+\log_2(n)=\Theta(n)$ With $n/4$ leaves at depth $\Theta(n)$ we have $\Theta(n^2)$ runtime for step 3 in this case. This is asymptotically the worst case since we have $n$ nodes at max depth $n$.

There's a better way to do this. Lets define a function $f$

$
f(v) =  \begin{cases}
v & \text{if}\quad \texttt{height}(v.left) = \texttt{height}(v.right) \\
f(v.left) & \text{if}\quad \texttt{height}(v.left) > \texttt{height}(v.right) \\
f(v.right) & \text{if}\quad \texttt{height}(v.left) < \texttt{height}(v.right)
\end{cases}
$

If the heights of the children of a node $v$ are the same, then clearly $v$ is the LCA of the deepest nodes of the subtree rooted at $v$. If the left subtree is taller, then we want the LCA of the deepest nodes of the subtree rooted at $v.left$, since they are deeper than the deepest nodes in the subtree rooted at $v.right$. The same logic follows for $v.right$ when it is taller.

The values for $\texttt{height}$ and $f(v)$ can be computed in a post-order traversal of $T$ in linear time.

Calling $f(root)$ should return the LCA of the deepest nodes in the tree.


Why do admissible functions allow $A^*$ to retain correct shortest path computations? I was reading about how to use $A^*$ and was told that:

  A heuristic is admissible if $h(u) \leq \delta(u,t)$, where $\delta(u,t)$ function indicates that the shortest path from $u$ to $t$.

I was wondering why such a condition guarantees that the shortest paths can still be computed.

Its clear to me if the heuristic is defined as with the help of a potential function $\lambda(u)$:

$$ h(u) = \lambda(u) - \lambda(s) $$

and the new weights are defined as (i.e. the potential function is feasible):

$$ w^*(u,v) = w(u,v) + h(u) = w(u,v) + \lambda(u) - \lambda(s) $$

then if we have $w^*(u,v) \geq 0$ with that heuristic then its clear that shortest paths are retained (because of telescoping series).

However, otherwise, I can't see why admissible function would retain shortest paths or what the motivation is to use admissible function with the property $h(u) \leq \delta(u,t)$. Why is that?

Usually heuristics tilt search algorithms to better paths, how do admissible function attain this?

Look at it this way:

The heuristic function lets us avoid exploring subpaths that we know are too long.

Suppose we're trying to get from $u$ to $t$. We're running our search, and the best path from $u$ to $t$ so far has length $UB$. We know it takes at most $UB$ to get to $t$.

Now, we see a vertex $v$. If we've found $v$, then we know the exact shortest path from $u$ to $v$. Call this $k$.

We want to know if we should bother looking at the shortest path from $v$ to $t$. So we ask, can it possibly be better than our best so far? So, we check our heuristic. We know that the distance from $v$ to $t$ is at least $h(v,t)$.
So if $k + h(v,t) > UB$, then we don't need to even bother expanding $v$, since there's no way it will be better than existing paths to the goal.

This is only safe if $h$ is admissible. But note also that, the larger $h$ is, the more paths we will be able to eliminate. So we have "Price is Right" rules: our goal is always to get $h$ as close to the actual distance function as we can, but we are never allowed to go over.

Dijkstra's is just A* with the heruistic of $h(x,y) = 0$: we ignore vertices if the distance to them from the start is farther than the best distance to the end so far. But we can do a lot better than this if we have a lower-bound on the distance between two vertices, since we can eliminate even more paths.

A common heuristic in a path-finding graph is to use euclidean distance: the shortest road between two points is never shorter than the distance between those two points.
Then, our heuristic lets our algorithm eliminate nodes which are close to the initial node if they take us too far away from the final node.

If you're trying to get from Seattle to New York, Dijkstra's might try to go through Portland, because it's close to Seattle. But A* with a Euclidean heuristic sees that this takes you out of your way too much, and can avoid this path.


How do you find a hash function that respects a custom equality function? I've been tasked with hashing arbitrary types in C++, with the caveat that A == B implies hash(A) == hash(B) even if equality of A and B is determined by a custom equality function ==.

For simplicity we can assume that == is an equivalence relation.

For example, the expected behavior of the hash function on std::vectors is as follows:

Given

using namespace std;
vector A = vector();
vector B = vector();

A == B will be true because == is overloaded for std::vector to mean equality of the underlying data. Correspondingly, hash(A) == hash(B) should also be true.

I can't simply hash the addresses of A,Bas integers because A == B but hash(&A) != hash(&B) in general.

I've thought of one solution, but I wonder if its optimal. It seems terribly inefficient. The solution is to build the hash function as new values are hashed:

using namespace std;

<template class Key>
class Hasher{

    public:

       unordered_map<pair<Key,Integer>> hashedKeys;
       int max_hash

       Hasher(int max_hash){
          this->max_hash = max_hash;
       }

       int hash(Key key){

          // If key has already been hashed, used that hash_value
          if ( hashedKeys.count(key) == 1){
               return hashedKeys[key];
          }

          // For pairs of saved (Key key, int hash_value)
          for(unordered_map<Key,Integer>::iterator it=hashedKeys.begin(); it!=hashedKeys.end(); it++;){

             // If an equal key has been inserted, just use its hash_value
             if(key == *it){
                hashedKeys.insert(key, *it.second);
                return *it.second; //use hash value of equal Key
             }
          }

          // If no other Keys equal this one, randomly hash it, and save
          int hash_value = rand() % max_hash;
          hashedKeys.insert(key, hash_value);
          return hash_value;

       }
}

I could do some extra bookkeeping to ensure that inequivalent Keys are less likely to be mapped to the same hash by the random assignment, but that's largely besides the point.

Ignoring collision resolution, hashing a new value is O(hashedKeys.size()),  while hashing a previous hashed value is O(1)
We also require O(n) additional space to store the computed hash values, where most hash functions require O(1).

In a situation where a cache is large and new keys are constantly being inserted, the O(n) search is incredibly inefficient, so I'd prefer another approach if possible, or a proof that improvement is impossible.

Take the class ParityInteger:

class ParityInteger{
   public:
      int number;

      ParityInteger(int n){
         number = n;
      }

      bool operator==(const ParityInteger& other){
         return (number % 2) == (other.number % 2);
      }
}

The ideal hash for such a class is:

int hash(ParityInteger n){
   return n%2;
}

which basically assigns a ParityInteger to a representative of its equivalence class.

Besides my method in the class Hasher, is there any better way to automatically find a function which assigns equivalent members of an arbitrary type to the same integer, without being trivial?

Given a computable equivalence relation == for some type, is there an algorithm to compute a nontrivial function hash such that == is a congruence relation wrt hash.

EDIT:
It seems that the naive Hasher algorithm I put forward is essentially optimal assuming you treat == as a blackbox:
https://cstheory.stackexchange.com/questions/33223/on-partitioning-a-collection-into-equivalence-classes

The way I can think of to do this is by some sort of normalization: that is, you need to find a function $f$ such that, if $\equiv$ is your custom equality and $==$ is the normal C++ (or whatever language you use) equality, for all $x,y$, we have $x \equiv y$ if and only if $f(x)==f(y)$. We call $f(x)$ the normal form of $x$.

Then, the trick is, instead of computing hashes, you compute hashes of normal forms.

Hash functions are specifically designed to produce large changes in output for small changes in input: that's what makes them well suited to hashtables and cryptography. So there's not likely a way to make a hash function that is invariant over some custom equality, except to have it compute on normal forms.

What you've described might work from a correctness point of view, but there are a few things to consider:

It is not hashing. That is, a hash is essentially a function that takes some variable-sized data and produces a fixed size output (in your case, an int). You haven't designed a function at all, you've just defined a way to assign random identifiers to input.
You lose all the advantages of hashing. One main use case of hashing is quickly comparing two things.

If you hash a bunch of things ahead of time, then you very quickly check that any of those two things are for sure different, and if their hashes are the same, you know with high probability that they are actually the same. With your version, you get fast comparison, but to compute all your hashes you'll have already compared all $n^2$ unhashed pairs at least once, so you will never save work.

The other thing hashes are useful for is indexing complex data in a data structure. That is, you convert your key into a hash, and each time you do a key lookup, you compute the hash and use it to find the key in a data structure, possibly a tree or hashtable. With yours, you end up doing $n$ comparisons each time you lookup the hash key, which means you'd be better to just use an unordered list as your data structure and search through it each time, comparing each element to the key you're looking for.

Using unique identifiers instead of hashes is a fine way to index data, but then you definitely do NOT want to generate random identifiers, since there's still a risk of a collision. Usually you'd just keep a counter and generate one plus the last identifier each time you allocate a new one.


Decidability of the halting problem on real-life finite computers given unlimited input It has been my understanding that, technically, our computers are Finite State Machines.  And, since FSMs halt when they run out of input, the halting problem is technically solvable.  At some point, we must reach an identical state without consuming input if there is an infinite loop.

I also understand that doing this in practice would take far, far, far too long to be useful.  Thus, I have read over and over that, yes, technically the halting problem is solvable for real computers, but it doesn't matter, because we can't do it in practice.

However, in a real computer, while we have a finite (vast) set of states, isn't it the case that we don't have finite input?  Input can easily be generated from non-cyclical random events, such as random radioactive decay, or the motion of water in a stream.  Doesn't this mean that, in fact, our computers are not truly Finite State Machines, and that the Halting Problem is not merely practically unsolvable, but genuinely unsolvable?

The halting problem can be stated as follows:

  Given a program P and an input x, does P halt when run on x?

Here both P and x are finite. In some cases (for example, in program verification) we might also be interested in infinite input which is eventually periodic, or at the very least, has an effective finite description (i.e., it is given by some algorithm). Assuming that this algorithm is also executed on a real machine (otherwise it is "cheating"), the entire setup can be folded to a program running on a real machine, and so the property of having a finite number of states is recovered.


Computing the size of an m-associative cache I am trying to answer this question:

Consider a computer with a byte-addressable memory. A 40-bit memory address is divided as follows for cache processing. First, the 8 low-order bits are chopped off to expose the cache-line number. Second, the next 17 low-order bits are inspected to get the cache-container index.  Third, the remaining 15 bits are used as the cache tag. Hint: What do the direct-mapped and set-associative placement formulas have in common?

What is the cache size in bytes?

I've figured out that the cache line size is 2^8 bytes and that there are thus 2^32 cache lines in memory.
Furthermore I know that there are 2^17 cache sets in the cache.
To compute the capacity of the cache, I am using the equation

capacity = line size x #of sets x associativity

However, even using the tag field, I can't see how I can find the associativity of the cache here.

I'm not sure if the first question is actually a question or a Hint. Anyway cache size can be calculated as follows.

Memory is byte addressable.
Masking off 8 bits for cache line, that means, cache line in 2 ^ 8 bytes.
Using 17 bits for TAG indexing, that is 2^17 cache entries.
Therefore, you have 2^8*2^17 bytes in the cache. That is 2^25 = 2^5*2^20 = 32 MB.


Count all pairs of x,y such as x + y = c && x XOR y = d Given two decimals $c$ and $d$;  $1 \le c,d \le 10^{12}$. Count all pairs of $x$ and $y$ that satisfy the following statements:
  $$
x+y = c\\
x \text{ XOR } y = d
$$

Killed already a day still can't solve that task in 2s. Even with optimizations brute-force algorithm doesn't terminate when $c$ and $d$ closer to upper bound.

UPDATE
Took a while to figure, here is solution:

void solve( Scanner in, PrintWriter out ) {
    long sum = in.nextLong();
    long xor = in.nextLong();

    long andMask = andMask( sum, xor );
    if( andMask == -1 ) {
        out.print( 0 );
        return;
    }

    long sample = sample( sum, andMask );
    if( sample == -1 ) {
        out.print( 0 );
        return;
    }

    out.print( combinations( sample, andMask ) );

}

long andMask( long sum, long xor ) {
    if( ( sum - xor ) % 2 != 0 ) return -1;
    return ( sum - xor ) / 2;
}

long sample( long sum, long andMask ) {
    if( ( ( sum - andMask ) & andMask ) != andMask ) return -1;
    return sum - andMask;
}

long combinations( long sample, long andMask ) {
    long combinations = 1;
    int major = major( sample );
    for( int i = 0; i < major; i++ ) {
        if( bitValue( sample, i ) == 1 && bitValue( andMask, i ) != 1 ) {
            combinations *= 2;
        }
    }

    if( andMask == 0 ) {
        combinations -= 2;
    }
    return combinations;
}

int major( long sum ) {
    int major = 0;
    while( sum > 0 ) {
        major++;
        sum = sum >> 1;
    }
    return major;
}

int bitValue( long value, int bit ) {
    return ( int ) ( value >> bit & 1 );
}

Hint: $x+y=(x \text{ XOR } y)+2(x \text{ AND } y)$.


Call by need compared to pass by function SML uses pass‑by‑value, Haskell uses call‑by‑need. Unless I'm wrong (the purpose of this question), one can do call‑by‑need with SML, passing a function instead of a value; a function to be later evaluated when needed.

Adapting a classical example:

(* This will print `0` *)

fun pass_by_function (cond, a1, a2) =
   if cond then a1
   else a2

val e1 = fn () => 1 * 0
val e2 = fn () => 1 div 0

val _ = print (Int.toString (pass_by_function (true, e1, e2) ()))

(* This will fail with a divide error *)

fun pass_by_value (cond, a1, a2) =
   if cond then a1
   else a2

val _ = print (Int.toString (pass_by_value (true, 1 * 0, 1 div 0)))

It's a big matter for Haskell to be call‑by‑need. I'm just wondering if there is something else or if it's just, say “syntactic sugar”, compared to the way it needs to be done with SML.

Is this just a different way to write the same or is there a semantic difference I'm not aware of? Passing a function, is it indeed always the same as call‑by‑need? If not, when and how does it differs?

Call-by-need is more than call-by-name.  Call-by-name is syntactic sugar for wrapping a closure (thunk) around each argument and then passing the pointer to the closure.  Your example shows what call-by-name turns into under the covers.

Call-by-need goes one step further by memoizing.  If an argument is used twice in a function then the thunk corresponding to that argument is only evaluated once, the result is stored, and then on the second (and after) use of that argument the stored value is returned instead of paying the cost of reevaluating the function.

This only works because Haskell is pure functional.  That means that every function call always returns the same result for the same inputs.  With a language with any mutation you can't make this guarantee, so it is much harder to do call-by-need automatically.  SML allows mutation.


1/2 Approximation to MAX-DICUT by rounding a linear program Consider a graph $G=(V, A, w)$, where each arc $(u,v)\in A$ has a non negative weight $w_{u,v} \in \mathbb{R}^+$, partition $V$ into $U$ and $W$, $W=V-U$ such that $\sum_{(i,j)\in A} w_{i,j}z_{i,j}$ where $z_{i,j} = [[i\in U \land j \in W]]$.
By getting a randomized cut we have a 1/4 approximation:
\begin{align}
\mathbb{E}\left[\sum_{(i,j)\in A} w_{i,j} z_{i,j}\right] = \sum_{(i,j)\in A}w_{i,j}\mathbb{E}\left[z_{i,j}\right] = \sum_{(i,j)\in A}w_{i,j} \Pr(i\in U \text{ and } j\in W) \geq \frac{1}{4} OPT
\end{align}
We can instead solve an integer program to get an exact solution. Consider a randomized algorithm that solves the linear relaxation of the integer program below and puts each vertex $i$ in $U$ with probability $1/4+x_i/2$.
\begin{align}
\text{maximize } &\sum_{(i,j)\in A} w_{i,j} z_{i,j}\\
\text{subject to }& z_{i,j} \leq x_{i} &\ \forall (i,j) \in A\\
& z_{i,j} \leq 1- x_{j}                &\forall (i,j) \in A\\
& x_{i}\in\left\{0,1\right\}  &\forall i \in V\\
& 0\leq z_{i,j} \leq 1 &\forall (i,j) \in A\\
\end{align}
We can relax the integer program to a linear program by relaxing $ x_{i}\in\left\{0,1\right\}$ to $ x_{i}\in[0,1]$ for all $ i \in V$.
\begin{align}
\mathbb{E}\left[\sum_{(i,j)\in A} w_{i,j} z_{i,j}\right] = \sum_{(i,j)\in A}w_{i,j}\mathbb{E}\left[z_{i,j}\right] = \sum_{(i,j)\in A}w_{i,j} \Pr(i\in U \text{ and } j\in W) = \sum_{(i,j)\in A}w_{i,j}(\frac{1}{4}+\frac{x_i}{2})\left[1-(\frac{1}{4}+\frac{x_j}{2})\right]
\end{align}
I have trouble however going further and showing that this is a 1/2 approximation though.

The constraints force $z_{ij} = \min(x_i,1-x_j)$. Therefore you have to show that
$$
\left(\frac{1}{4} + \frac{x_i}{2}\right) \left(\frac{1}{4} + \frac{1-x_j}{2}\right) \geq \frac{1}{2} \min(x_i,1-x_j).
$$
By symmetry, we can assume that $x_i \leq 1 - x_j$, and so we have to show that
$$
\left(\frac{1}{4} + \frac{x_i}{2}\right)^2 \geq \frac{x_i}{2}.
$$
You can check that this holds for all $x_i$. Equality holds when $x_i = 1-x_j = 1/2$, showing that the approximation ratio $1/2$ is tight (for the analysis).


Solving a peculiar recurence relation Given recurrence:

  $T(n) = T(n^{\frac{1}{a}}) + 1$ where $a,b = \omega(1)$ and $T(b) = 1$

The way I solved is like this (using change of variables method, as mentioned in CLRS):

Let $n = 2^k$

$T(2^k) = T(2^{\frac{k}{a}}) + 1$

Put $S(k) = T(2^k)$ which gives $S(\frac{k}{a}) = T(2^{\frac{k}{a}})$

$S(k) = S(\frac{k}{a}) + 1$

Now applying Master's Theorem,

$S(k) = \Theta(log_2(k))$

$T(2^k) = \Theta(log_2(k))$

$T(n) = \Theta(log_2log_2(n))$

I believe my method is incorrect because $a = \omega(1)$ doesn't necessarily mean that $a$ is a constant (or is it ?) and hence Master's Theorem is not applicable. Following the same line of reasoning, this also means that $b$ may not be a constant, but that would make "$T(b) = 1$" condition meaningless. Can anyone help clear out my misconceptions (if any) ?

Thanks

In my opinion the problem statement seems poorly posed.  It's not clear what is meant by the problem statement.

Normally, if we write $a$ or $b$ the assumption is that they are a constant: they do not depend on $n$.  If they are intended to be a function of $n$, then they should be written as $a(n)$ or $b(n)$.  Since that wasn't done, the only assumption I can see that makes sense is to assume they are constants.  But then if they are constants, then writing $a,b = \omega(1)$ doesn't seem to me to make sense.

So, I suggest you go talk to your instructor to ask them what they had in mind and how one should interpret the question.  We can't solve the question until we know what the question is asking.

Basically, I am validating that the confusion you are having seems reasonable: it seems reasonable to me to be confused about that, as I find the problem statement confusing.


Need help about solving a recurrence relation I have a recurrence relation which is like the following:

$T(n) = 2T(\frac{n}{2}) + \log_{2}n$

I am using recursion tree method to solve this. And at the end, i came up with the following equation:

$T(n)=(2\log_{2}n)(n-1)-(1\times 2 + 2\times 2^{2} + \ldots + k\times2^{k})$ where $k=\log_{2}n$

I am trying to find a theta notation for this equation. But i cannot find a closed formula for the sum $(1\times 2 + 2\times 2^{2} + \ldots + k\times2^{k})$. How can I find a big theta notation for $T(n)$?

For $\sum_{0 \le r \le k} r \cdot 2^r$, start with:
$$
\frac{1 - z^{k + 1}}{1 - z} = \sum_{0 \le r \le k} z^r
$$
As this is a polynomial, the following mangling doesn't need any justification:
$$
z \frac{d}{dz} \frac{1 - z^{k + 1}}{1 - z} = \sum_{0 \le r \le k} r z^r
$$
Doing the operations indicated:
$$
\sum_{0 \le r \le k} r z^r = \frac{z^k (k z^2 - (k + 1) z) + z}{(1 - z)^2}
$$
Finally:
$$
\sum_{0 \le r \le k} r 2^r = (2 k - 2) 2^k + 2 = \Theta(k 2^k) = \Theta(n \log n)
$$


Do comparison sorts have to start at the beginning of the input? Say I had an input $\langle3,17,15,9,1\rangle$, could I for example begin by comparing 1 with 3 so that 1 appeared at the start of the sorted sequence straight away or would I first have to compare 3 and 17 and then continue working from left to right with consecutive numbers? If the latter is correct, do I then have to keep returning to the start to continue comparing elements until I reach the fully sorted array? If this is the case, how is it possible to sort the input in $n-1$ (4) steps?

You can make the comparisons in any order you want. If there was only one possible sequence of comparisons, there'd be only one possible sorting algorithm!

But note that, to specify an algorithm, you have to specify it in terms of operations that your model of computation supports. For example, althouh you as an intelligent human can say "compare 1 with 3", to specify an algorithm, you'd need to be able to describe how to choose the elements to be compared next. Of course, you could try to say "compare the smallest with the second-smallest" but, then, you'd have to give an algorithm for finding those two elements which would, itself, probably use further comparisons.  And, of course, if you already knew which were the smallest two, you wouldn't need to compare them anyway.


Listing all possible train routes I'm interested whether there is the standard solution to the following problem.
Some number of train routes is given:

Route1: First City -> Next City -> ... -> Last City

Route2: ...

...

We need to list all possible ways to get from one given city to the other with possible transfers but without visiting any city more than once. So, for example, if we're given

R1: A -> B -> C

R2: B -> D -> E

R3: C -> D -> A

R4: C -> E -> F

than the routes from A to E are the following:

A -> [R1] -> B -> [R2] -> E

A -> [R1] -> C -> [R4] -> E

I hope i've managed to explain properly. And thank you very much in advance for any tips.

Based on your comments, I'm assuming that if the problem asked to find all paths between $A$ and $B$ on a directed graph, you'd have no problem.  So the only hurdle is how to deal with the extra route information.
Here's an outline of the most obvious approach that I can see:

Convert the given set of routes to an adjacency matrix. Since each edge $(A,B)$ belongs to some route $R$, store that route in the corresponding entry for $(A,B)$ in the matrix.
Run your algorithm to find all paths between your start and goal nodes.
Convert the output of your algorithm to the desired form by collapsing all consecutive edges that belong to the same route into one edge.


Can a Turing Machine decide only non-regular languages? I have an assignment where i need to create a Turing machine that decides an infinite language $L\subset \{0,1\}^*$ for which all $L'\subseteq L$, if $|L'|=\infty$, then $L'$ is not a regular language.

I think this is not possible due to Rice's Theorem. It's not possible to tell for a Turing Machine if a language is regular or not.

Moreover, on any given input, the machine can loop so it cannot decide an infinite language $L$.

Is this the right answer? It seems too easy to be the answer... Any input would be appreciable. Thanks in advance.

@Karolis Juodele already gave the answer, and your answer is also correct.

Another thing to keep in mind is although infinite languages can be undecidable, some of them are regular.. ex. $\{0\}^* \subset \{0,1\}^*$ is an infinite language but is regular (you can construct a FSM, with a single state, that accepts it).

Basically any undecidable language is infinite, but any infinite language is not necessarily undecidable.

Also, for a language like $L = \{w \mid m \text{ halts on the input } w\}$, there exists a Turing Machine for which $L$ is undecidable.


Comparing dual of a canonical primal program - Directly and by dual of the standard program I have it as a homework question to compare dual programs in the following way:

Take a canonical program and write its dual
Take the same canonical program, write it as a standard program, take the dual of the latter, then write it as a canonical program.

In the following image, option 1 is starting with the upper left square and going right, and option two is (starting with the same place and) going down and then right and then up.

I have tried to do this, both in general and both by example, but I'm getting something strange: First I add slack variables to move from inequalities to equality, and I add the constraint that all slack variables are positive.

Then I write the dual of that program, the inequality look like $[A|I]^Ty\leq [c|0]$

(here $[A|I]$ denotes a block matrix) which gives two sets of inequalities: one is $A^Ty\leq c$ and the other is $Iy\leq 0$. Which is almost like the CD form in the picture - but I got $y\leq 0$ instead of $y\geq 0$.

Why do I get a different result ? I guess I have some error and that I should actually get $y\geq 0$, but I checked multiple times and I don't see any errors.

Since $Ax\ge b$, you should make $Ax$ smaller to get equality. Slack variables are also non-negative, so the coefficients should be $-1$. It's $[A|-I]$ instead of $[A|I]$.


Maximum-cardinality matching in unbalanced bipartite graphs Let $G = (X+Y, E)$ be a bipartite graph, and suppose we want to find a maximum-cardinality matching in $G$.
The Hopcroft-Karp algorithm runs in time $O(|E|\sqrt{|V|})$, where here $|V| = |X|+|Y|$. So if the graph is unbalanced and $|X|<|Y|$, the run-time is $O(|E|\sqrt{|Y|})$.

Is there an algorithm that attains a better worst-case runtime complexity for the case of an unbalanced bipartite graph, where $|X| \in o(|Y|)$? In particular, if $|X|$ is constant, is it possible to get run-time $O(|E|)$?

I just found the answer myself. In this paper:

  Lyle Ramshaw, Robert E. Tarjan (2012). "On minimum-cost assignments in unbalanced bipartite graphs". Technical reports, HP research labs.

in section 5, the authors show that the Hopcroft-Karp algorithm in fact solves the following problem: given an integer $s$, find matchings with $1,\ldots,s$ edges. The run-time is $O(|E|\sqrt{s})$. In particular, if $|X|<|Y|$, we can take $s=|X|$ and the run-time is $O(|E|\sqrt{|X|})$.


Cannot find paper: All k nearest neighbors search in N*log(N) using distance indices for log(N) support points I remember reading a paper about finding k nearest neighbors for all N multi-dimensional objects in the set.

I've tries to find it again many times, but have failed so far.

The algorithm was as follows:

Each object is assigned a sorted queue of nears neighbors (maximum size is k). Let's assume that $k < log(N)$
Each time you calculate $distance(A, B)$ try to add A into B's neighbor list and vise versa.
Choose $log(N)$ support objects (say, first $log(N)$ objects out of $N$). (Or maybe that was $sqrt(N)$)
For each support, build the distance-based index containing all N objects
After the index construction, every object has a candidate list of k nearest neighbors. All real nearest neighbors are not further than the furthest neighbor in the candidate list - candidate neighbor radius.
For each point we use triangle inequality and current neighbor radius to constrain the distances between a candidate point and the support points: $|dist(candidate_i, support_j) - dist(point, support_j)| <= radius$. We efficiently extract the candidates that fall in radius-based ranges for all support points.
We calculate the distances for those candidates and update the nearest-neighbor lists for both the current point and the candidate points.
As we process more points, the neighbor lists become "tighter" - the radius, the distance to the furthest neighbor decreases with each update of the list.
Tighter constraints mean that the candidate lists become smaller and smaller after each processed point and leading to total run time of $N*log(N)$.

So, why do I need the paper again? First of all, several people have asked me for it and I was surprised I cannot find it again.
More importantly, it did not work well for me. This might be caused by a bad choice of the support objects. I remember nothing about the selection process.

Found the paper finally. Not sure I've read exactly the same paper (maybe I read some SO or SE answer or some other paper that inspired/was inspired by this paper). Nethertheless, the algorithm is exactly the same.

A Fast Algorithm for the All k Nearest Neighbors Problem in General Metric Spaces by Edgar Chávez and Karina Figueroa and Gonzalo Navarro. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.9299 http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=A580FE7BF3251BC23DB793E3B1DFDF64?doi=10.1.1.21.9299&rep=rep1&type=pdf


Maintaining a sorted moving window I have an array of length $n$ representing a time series of data. I want to implement a moving (sliding) window of length $k < n$ and calculate things like sliding median, sliding quantile, sliding trimmed mean, etc. Each of these requires the data to be sorted prior to calculating the statistic of interest.

Therefore I need a data structure which has the following 2 properties:

It must easily allow a new sample to be added and the oldest sample to be deleted as the window slides along the time series.
When a new sample is added, it should efficiently insert the sample into a sorted position in the data structure, so that things like the median and trimmed mean can easily be computed.

For #1, I am currently using a ring (circular) buffer of length $k$. This makes it easy to add new samples and overwrite old samples in $O(1)$ time simply by updating the head and tail pointers of the buffer.

For #2, I had thought to keep a separate array called perm to keep track of the permutation of the ring buffer entries needed to sort them. In other words, if array is the ring buffer array with head and tail pointers, then array[(head + perm[i]) % k] is the sorted array for i = 0,...,k-1. I tried using an Insertion Sort algorithm to update the perm array each time a new sample is added to the sliding window. The code for this is below.

/* sort ringbuf entries with insertion sort algorithm */
void
ringbuf_isort(const ringbuf *rbuf, int *perm)
{
  const int n = ringbuf_n(rbuf);
  int i, j;

  for (i = 1; i < n; i++)
    {
      int id = perm[i];
      double v = rbuf->array[(rbuf->head + id) % rbuf->size];

      for (j = i; j > 0; j--)
        {
          if (rbuf->array[(rbuf->head + perm[j-1]) % rbuf->size] < v)
            break;

          perm[j] = perm[j-1];
        }

      perm[j] = id;
    }
}

This code works correctly and sorts the ring buffer entires, however it is far too slow. I have tracked the slowdown to the modular arithmetic (rbuf->head + id) % rbuf->size in each loop iteration. This can be moderately improved by doing a comparison of id < head ? head + id : head + id - size, but this is still too slow.

In fact I have found it is faster to simply copy the ring buffer entries to a linear array and use a quicksort algorithm than using the above code.

Can anyone suggest a data structure which will solve the sorting problem and still be fast?

If you use augmented AVL (or any self-balancing tree like RB) tree with additional pointers for quantiles then maintaining median and quantiles work in logarithmic time. Inorder traversal is always sorted so if juggling with pointers is not good option for you, maintain tree, with one insert and delete per move and caclulated statistics during inorder traversal.

It is good to keep online algorithms whenever possible, keeping say mean or variance as accumulators, not recalculating all the time.

I have similar need, only maintaining median, mean, standard deviation and kurtosis. Here I keep threaded AVL tree with additional online version of statistics, moving median pointer on insert/delete.


SAT satisfaction with 10 variables I am trying to prove that the next problem is NPC:
$$
A = \{ \langle\phi\rangle \ \big| \ \phi \ \text{is CNF and has sat. assignment where exactly 10 vars are TRUE}  \}
$$
I am trying to find polynomial mapping reduction from SAT but I can't find a way to force exactly 10 variables to get TRUE assignment.
My idea was to create new formula, with 10 clauses, each clause is the intersection of a new variable $x_i$ with the old formula, but I don't see how my idea helpful.
I would appreciate help.

The problem you mentioned is in $P$ so it is not NP-complete. We know that $|\phi| = n$ so the number of variables is less than $n$ and we know that members of $A$ exactly have 10 True assignments. So by a brute force algorithm check every possible assignment to variables. Choose 10 variables from n, $(^{n}_{10})$ and set them to $True$ and set other variables to $False$ and check if this is a satisfying assignment. The run time of this algorithm is $(^{n}_{10})*n = O(n^{11})$.


Which Graph Algorithm should I use to find all possible groups in a graph? I have the following situation:

(Alex, Bob)

(Alex, Charlie)

(Debra, Erika)

Imagine that each row in the list represents a friendship. Alex is friends with Bob. Alex is friends with Charlie. And Debra is friends with Erika.

I would like to figure out how many independent friends groups there are. So if someone is a friend of a friend (or a friend of a friend to the nth degree), they would belog to the same group. In other words how many groups are there, that do not overlap eachother.

From the list above I would expect 2 groups:

(Alex, Bob, Charlie)

(Debra, Erika)

Which algorithm should I use to calculate these groups, from the list provided above?

Note: In the actual case the number of friendships is in the tens of millions, so I am looking for the most efficient solution.

These are called the connected components of the graph.

For most purposes, any graph traversal algorithm will suffice for finding the connected components. However, if you have a really big graph, see this question on Stack Overflow for practical considerations.


What is a dominator node and a dominator tree? I tried reading the wikipedia about Dominator (graph theory), which gives the following definition of a dominator node:

a node d dominates a node n if every path from the entry node to n
must go through d.

I need to understand the concept of a dominator node but I do not need to go deep into graphs, so I'm trying to make sense of these definitions. I'm trying to look in the images on the article:
This is a graph:

This should be a dominator tree for the graph above:

Based on the definition above, I think
node 2 dominates node 3 because every path from 3 must go through 2. Why? To go from 3 to itself I must pass to 2. That's why 2 goes to 3 in the dominator tree.
Am I thinking right?
Can I know also why this is useful in compilers?

The reason you give is not exactly right; the definition of a dominator node works from a starting node ($1$ in the example). The only way to reach $3$ from $1$ is to go through $2$ as it is the sole successor node of $1$ in the given graph. Hence $2$ dominates $3$. For the same reason, the nodes $4$ through $6$ are also dominated by $2$ and further, $2$ is the immediate dominator of these nodes (as $1$ dominates $2$) and these nodes are also not dominated by any other nodes than $1$ and $2$:

$3, 4$ and $6$ can be immediately reached from $1$ via $2$.
$5$ can be reached from $2$ either via $3$ or $4$ and thus the only common nodes in these paths to $5$ are $1$ and $2$.

As for applying these concepts to compilers, consider a block-level control flow graph (or CFG for brevity) of a program.
If some block $B$ dominates a block $B'$ in the CFG, then $B$ must have been executed by the time the program reaches $B'$.
This knowledge can be used to remove redundant pieces of code:
Consider the program
a = (something)
b = True

if a == True:
   b = True
else:
   b = False

Here, the block consisting of the first two lines dominates the if-block as well as the else-block.
Hence we know that by the time we jump to the if-block where we would set b to True, it is already set to True by the fist block and thus the compiler could optimize the code by deleting the assignment in the if-block.
You can also detect loops in the code by analyzing if the CFG has edges of the form $B' \to B$ where again $B$ dominates $B'$. Such a path indicates the existence of a loop where $B$ would then represent the loop header while $B'$ is (the last) part of the loop body.


Create cfg and npda/pda for Language {ww} I've been trying to make a CFG, and npda/pda for this language (to construct an npda for accepting the language):

L(M)={ww:w∈{a,b}∗,|w| is even}.

i had already solved the reverse of the language (like this):

L′={wwR:w∈{a,b}∗},

Please check this snapshot to know what i am asking to do ! (L') : http://i921.photobucket.com/albums/ad53/Johann_1990/IMG_20150117_132616.jpg

but is there is a way to solve this L(M)={ww:w∈{a,b}∗,|w| is even}?

For example, abaaba∈L with w=aba.

Note that I'm not asking to prove by conduction or anything else.

Short answer: $L$ is not context-free, so there is no CFG/PDA.


In-place matrix transposition using rotations Some time ago I invented an algorithm for in-place matrix transposition using rotations.

A matrix of size N×M is represented as a one-dimensional array of size N*M, which is also the future storage for the corresponding transposed M×N matrix.

The algorithm moves an element to its proper position in the representation for the transposed matrix rotating the sub-array of the array 1 element right, starting at the correct and ending at the current position of the element.

Let matrix be the array of size N*M, where N and M are the number of rows and columns in the original matrix (and the number of columns and rows in the transposed). Array indices are from 0 to N*M-1.

Let dst be the proper position for the element in the array for the transposed matrix, src — its current position, src_inc is the value addet to src to point to the "current position" of the next element to be moved. The algorithm starts with dst = 1, src_inc = M and src = dst + src_inc - 1 (which is equal to M) (The element at the 0-th position is already in its right place). After the first rotation, we increment dst by 1 and src by src_inc (which is M) until dst points to an element which should not be moved. This happens when (dst + 1) % N is 0. In this case we skip the element (incrementing dst again), decrease src_inc by one and restore the initial relation between src and dst — src = dst + src_inc - 1.

Let me, instead of writing a pseudo-code, show the C++ code and add a state of the array before each rotation (plus the final result)

#include <algorithm>

template<typename T>
void inplace_transpose_using_rotations(T* matrix, int N, int M)
{
    int dst = 1;
    int src_inc = M;
    int src = dst + src_inc - 1;

    while (src < N*M && dst < src)
    {
        std::rotate(matrix + dst, matrix + src, matrix + src + 1); // rotate right for 1 position
        if ((dst + 1) % N != 0) {
            dst += 1;
            src += src_inc;
        } else {
            dst += 2;
            src_inc -= 1;
            src = dst + src_inc - 1;
        }
    }
}

(https://wandbox.org/permlink/XAWE1Fn64SxvEvth)

Original 3×5 matrix:

11 12 13 14 15
21 22 23 24 25
31 32 33 34 35

The trace (the first row is indices, the matrix is represented linearly, dst and src to the right are shown before the rotation, the result of the rotation is on the next line):

00 01 02 03 04 05 06 07 08 09 10 11 12 13 14
11 12 13 14 15 21 22 23 24 25 31 32 33 34 35 | dst = 01, src = 05
11 21 12 13 14 15 22 23 24 25 31 32 33 34 35 | dst = 02, src = 10
11 21 31 12 13 14 15 22 23 24 25 32 33 34 35 | dst = 04, src = 07
11 21 31 12 22 13 14 15 23 24 25 32 33 34 35 | dst = 05, src = 11
11 21 31 12 22 32 13 14 15 23 24 25 33 34 35 | dst = 07, src = 09
11 21 31 12 22 32 13 23 14 15 24 25 33 34 35 | dst = 08, src = 12
11 21 31 12 22 32 13 23 33 14 15 24 25 34 35 | dst = 10, src = 11
11 21 31 12 22 32 13 23 33 14 24 15 25 34 35 | dst = 11, src = 13
11 21 31 12 22 32 13 23 33 14 24 34 15 25 35 | final array

(the code producing the trace https://wandbox.org/permlink/3nhlwYoSz5GnWuUP)

And transposed matrix (reinterpretation of the array as a representation for a 5×3 matrix):

11 21 31
12 22 32
13 23 33
14 24 34
15 25 35

The algorithm is not optimal, it does  swaps (assuming the rotation is implemented as a chain of swaps), but it is short and seems to work.

However, I couldn't prove why it should work. I was just curious to try to transpose a matrix using rotations instead of chain of swaps following cycles and discovered that there is a relatively simple law how to select the next sub-array for rotation. Is this algorithm published anywhere?

After the array is rotated with dst == N - 1 (so the condition (dst + 1) % N == 0 is about to fire), the tail of the array starting from index N looks like a representation of a N×(M-1) matrix with the values of the original matrix without the first column:

11 21 31 12 13 14 15 22 23 24 25 32 33 34 35
         ^ starting from here

looks like a representation of the

12 13 14 15
22 23 24 25
32 33 34 35

matrix

which immediately suggests how to simplify the algorithm:

template<typename T>
void inplace_transpose_using_rotations(T* matrix, int N, int M)
{
    if (N == 1 || M == 1)
        return;

    for (int dst = 1; dst != N; dst++)
        std::rotate(matrix + dst, matrix + dst * M, matrix + dst * M + 1);

    inplace_transpose_using_rotations(matrix + N, N, M - 1);
}

This explains how the algorithm works: rotations move first elements of each row into their proper position in the transposed matrix and at the same time shift the other elements to the right forming a representation of a smaller N×(M-1) matrix in the right side of the array. Then this smaller matrix is transposed, until we get a N×1 matrix.


Finding size of cache in blocks Let's say I have a 64 kB Cache provided (i,e 2^18) which is direct mapped and block size is 16 byte = 2^5

Now, in the solution it says
m=size of cache in blocks = 4096 = 2^12. This hasn't been provided in the question. So, how do we assume / derive size of cache in blocks was 2^12.

If this is a static value, then does that changes if block size is increased to 32 bytes?

The size of the cache in blocks is just the size of the cache in bytes divided by the size of a block in bytes.  However, both the figures you give are wrong: 64 kB is 2^16 bytes, and 16 bytes is 2^4 bytes.  Dividing we get 2^12.


Sorting n elements in worst case of $\sqrt{n}\log n$ Can $n$ elements be sorted in a worst case time of $\sqrt{n}\log n$? Why or why not?
I've seen algorithms being sorted in the worst case of $n\log n$, so why can they be or cannot be sorted in $\sqrt{n}\log n$?

This is impossible. You cannot sort $n$ elements without examining each element at least once, which takes at least $n$ operations.

$n=\sqrt{n}\cdot\sqrt{n}\ge\sqrt{n}\cdot\log{n}$ for all $n>1$, assuming the logarithmic base is at least 2. (Of course, if you assume something completely asinine like $\log_{1.000001}n$, it would be technically possible for some values of $n$.)