3-CNF to "independent form" Is it possible to convert all logical formulae into a form such that each variable ends up in exactly 1 "factor" of the and operation? ($\wedge$). Any combination of operations is allowed, though the fewer operations used the better.

$$ \left((a \rightarrow b ) \downarrow b \right) \wedge \left(c \vee d\right) \wedge \left( \left(e \leftarrow f\right) \vee f \right) \tag{IND} $$

This would be valid because all instances of each variable exist in only 1 of the "factors" even if it appears in that factor multiple times.

$$\left((a \rightarrow b ) \downarrow b \right) \wedge \left(a \vee b\right) $$
This would be invalid because the $a$ (or the $b$) appears in multiple AND "factors"

I have called this (IND) because each of the factors is independent of each other. I'm mainly interested in a way to convert 3-CNF to (IND), if it is possible.

Edit for clarification:

Consider $\left( a \vee b \vee c\right) \wedge \left(a \vee d \vee e \right)$. The $a$ appears on both sides of the $\wedge$ I would like to convert it into format: $ f(a,b,c) \wedge g(d,e)$ where $f(a,b,c)$ and $g(d,e)$ can use any operations.

Similarly

Given $\left( a \vee b \vee c\right) \wedge \left(a \vee b \vee d \right)$ I would like the $a$ and $b$ to be on the same side of the $\wedge$. It doesn't matter how they are separated, or if any of the other variables move. All that matters is that each instance of a variable appears in only 1 "factor"

$\underbrace{\left( a \vee b \vee c\right)}_{factor} \wedge \underbrace{\left(d \vee e \vee f \right)}_{factor} \wedge \underbrace{\left(g \vee h \vee i \right)}_{factor}$

Is it possible to convert all logical formulae into a form such that each variable ends up in exactly 1 "factor" of the and operation? ($\land$)

In general, it is impossible to separate variables in that way. Consider the formula $a \leftrightarrow b$, and assume it can be written in the form $f(a) \land g(b)$.

Up to logical equivalence, $f(a)$ must be either $a$ or $\lnot a$. Ditto for $g(b)$. We therefore have that $f(a) \land g(b)$ must be one of these formulas:

$$
a\land b \qquad
a\land \lnot b \qquad
\lnot a\land b \qquad
\lnot a\land \lnot b \qquad
$$

However, none of the above ones is equivalent to $a \leftrightarrow b$.

(Well, to be pedantic, $f(a)$ and $g(b)$ could also be the constantly true or constantly false function. Those choices won't work either, obviously.)


Estimating size of state space search problem Im currently enrolled in an AI course and we are starting with state space search problems. My professor always seems to ask, given a certain problem, what is the estimate size of the state space? It's been 3 years since ive taken a course in discrete math which is the type of question I am asking.

How can I use things like branch factor and depth to estimate state space?

So lets take an 8 queens problem. Intially the size of state is 64C8 where 64 is the number of squares in a chess board and 8 is the number of queens that can be placed.
Now lets say, you can only put one queen in each column so that's only 8 squares available. This reduces the branching factor from 64 to 8. Now the size of state is 8C8 only.
Now lets say, you can only use 2 queens instead of 8. This reduced the depth from 8 to 2. So in this case instead of being 8 queens , now it's going to be a 2 queens problem. So that changes the size of state from 8C8 to 8C2. Cheers man.


How to show that this algorithm for evaluating polynomials works? I'm having trouble showing how to solve this problem in particular the part where it asks "To Show that the following pseudo-code fragment finds the value of the polynomial..."

How do I exactly show that? I don't understand what that would entail and my professor isn't exactly that helpful he says to prove it for all $n$, but I don't understand how to show that mathematically through programming. He says not just to give a particular example, but rather show it works for all polynomials.

The whole question is this:

  It is required to find the value of the polynomial $$P(x)=\displaystyle\sum_{k=0}^n a_k x^k$$

  Show that the following pseudo-code fragment finds the value of the polynomial, given the coefficients $a_0,a_1,a_2,...a_n$ for a value of $x$.

y = 0;
i = n;
while (i >= 0) {
   y = a[i] + x * y;
   i = i - 1;
}

I suggest you use proof by induction, on the number of iterations of the loop.

In particular, find a loop invariant: an equation that relates the value of y, i, and $a_0,a_1,\dots,a_n$, and that always holds each time you reach the head of the loop.

Then, prove that your loop invariant is indeed an invariant, using proof by induction.


Exactly what is the difference between Finite Automata and Transition Graphs? I haven't found a good enough answer by googling. Here's what i know:

TG's can have more than one initial state
In TG's, Edges/transitions can be labelled with strings
In TG's, it is not necessary to show transitions for all letters

Notes:

I am talking about plain TG's, not GTG's and DFA's only not NFA
Only thing i know about NFA's is that each a state can have multiple transitions for the same letter, so please keep that in mind if hte answer invloves NFA's
Links would be appreciated.

Your nomenclature is highly nonstandard. It seems that "finite automata" are what are usually known as DFAs, whereas "transition graphs" are a special case of GNFAs in which the only regular expressions allowed are words; alternatively, they are like $\epsilon$-NFAs, only transitions can be marked by arbitrary words (rather than just words of length at most 1).

There are two differences between your FAs and your TGs:

FAs are deterministic: at each point in time, there is exactly one choice of which state to go to next. There is no such restriction on TGs. Moreover, whereas FAs have a unique initial state, TGs have an arbitrary number of initial states.
Transitions in FAs are labeled by symbols. In contrast, transitions in TGs are labeled by words.

These are exactly the differences that you listed.


Finding infeasible sets of constraints (CSP) Given a set of constraints, I want to check whether the constraints are feasible. What I am trying now, is to feed the constraints to a solver and check if the solver returns infeasible. I am using both CSP solvers and optimzation (such as MILP) solvers (in the latter case, I set a dummy objective function, e.g., maximize a constant).

This works, so I can check if a given set of constraints is feasible. However, now I am looking for a more general problem: How many set of constraints are infeasible. One way to do this is to generate all sets of constraints separately, and then feed each of them individually to the solver. Alternately, I can ask the solver to enumerate all solutions, then check which ones do not appear in. Both becomes impractical in my case, as the search space is too big to exhaustively enumerate.

  The question is, is there any practical way to find the sets of constraints which are infeasible by using standard CSP/optimization solvers?

Since the question is too broad, let me give a more specific example. Assume, we have 4 binary variables, $x_0$, $x_{1}$ and $y_0$, $y_{3}$. There are certain constraints (say, $x_0+x_1 = 1$, $x_0+y_0=1$, $y_1=1$) which are satisfied only for $(x_0, x_1, y_0, y_1) = (0, 1, 1, 1), (1,0,0,1)$; hence the rest 14 quadruples are infeasible (which I am interested in). In the first method, I am generating all 16 constraints and checking which ones are infeasible. In the second, I am asking the solver for all solutions and taking those 14's which are not present in the solution. In my case, the number of variables are too large (say, $x_0, \ldots, x_{127}$ and $y_0, \ldots, y_{127}$), so no method will work in practice.

Modern CSP solvers can check for feasibility for thousands of variables. What I am looking for is kind of the opposite direction: Can it look for non-feasibility?

If your system of constraints is expressed as a SAT instance, then this is known as the MAX-SAT problem.  MAX-SAT is harder than SAT, but there are standard algorithms.  The case of other discrete constraints can be reduced to Weighted MAX-SAT.


How can I prove that there is a decidable language which is not in P? Generally, I want to use the diagonal argument to prove it. I tried to define a language $A$ which is constructed by a Turing machine $D$:

It will only take a input which has a form of a Turing machine $\langle M\rangle$ (the description of $M$) and simulate $M$ on $\langle M\rangle$. If it halts in polytime and accept, reject. If it halts in polytime and reject, accept.

If $A$ is in P, there must exist a Turing machine $M'$ that decides it in polytime. However, if I run $D$ on the input $\langle M'\rangle$, the result will be converse to the simulation. Contradiction! So $A$ should not be in P.

The problem is that I don't know whether a turing machine will halt in polytime or not. Polytime can be $n^2$, $n^3$, $n^4$, ...

Unfortunately, this doesn't work at all. What you're proposing to do is to simulate a Turing machine on some input, and ask whether it accepts/rejects that input in polynomial time, and that question is not well-formed.

"Polynomial time" is the class P of Turing machines $M$ that have the following property: there is are constants $c$ and $k$ such that, for every input of length $n$, $M$ halts in at most $cn^k$ steps. Notice that this property talks about all inputs, so you can't test it just by looking at one input.

Indeed, it doesn't make sense to ask if a particular input is "accepted in polynomial time." Let the input have length $n$ and suppose that the Turing machine takes $t$ steps to accept it.  We can always find constants such that $t\leq cn^k$. For example, we could take $c=t$ and $k=0$.

You need to look at the time hierarchy theorem which says, loosely, that Turing machines with longer running time can decide more languages than Turing machines with shorter running times. Its proof does indeed use diagonalization, so you started with the right idea.


VC dimension of only the rim of a unit disk Suppose we have an origin centered circle, ie $x^2 + y^2 =1$, so it's in $\mathbb{R}^2$ (2D). It will be classified as 1 if it lies only on this arc, and will be labeled 0 otherwise. What is the VC dimension?

I think the answer is 2. Any two points can be shattered $(++, -+, +-, --)$. But if we have three points $\{(x_1,y_1),\dots,(x_3,y_3)\}$ that all have the label 1, with radius $r_1 = r_2 = 1$, and $r_3 = 0$, it is impossible to shatter them. Is my intuition correct?

Or can I construct the sample points to my liking (to get the maximum VC dim) so that only the positive labels will be on the rim (have some combination of $x_i^2 + y_i^2 = 1$), and have 0 labels to not lie on the rim, therefore have infinite VC dimension?

Let us prove the following general result:

  Let $\mathcal F$ be a class of functions from $\mathcal X$ to $\{0,1\}$. If $\mathcal F$ has VC dimension $d$ then $|\mathcal F| \geq 2^d$.

Indeed, if $\mathcal F$ has VC dimension $d$ then $\mathcal F$ shatters some set $S \subseteq \mathcal X$ of size $d$. This means that for any function $\phi\colon S \to \{0,1\}$ we can find a function $f_\phi \in \mathcal{F}$ that agrees with $\phi$ on $S$. Note that if $\phi \neq \psi$ then $f_\phi \neq f_\psi$. Since there are $2^d$ different functions from $S$ to $\{0,1\}$, we conclude that $\mathcal F$ must contain at least $2^d$ functions. $\square$

In particular, the VC dimension of a class of functions containing a single function is zero.


Valid-invalid bit in a process page table Valid-invalid bit is used to indicate whether a page in a process’s page table is valid or not. Why is it needed?

Does that mean that each page table has a certain minimum size, i.e. it can accommodate minimum of n references to pages and if the number of pages being referenced by the process is less than n, then this bit is required to tell that only few entries are valid in the page table?

If the page table is built and populated dynamically, then the page table will only have as many entries as needed by process and there will no need for this bit, as all entries will be valid.

Other tags are page-table, valid-invalid bit

Typically the page table is a tree of fixed size pages.  So each node of the page table contains a fixed number of entries.  Here's the picture of a 32-bit x86 multi-level page table from Wikipedia:

Each page on x86 is $2^{12}=4096$ bytes. Each page table entry is 4 bytes = 32 bits, and contains a pointer to the beginning of another page.  Each page table page contains exactly $2^{10}=1024$ page table entries.  Since the pages are aligned we know that the bottom 12 bits of the pointer would all be zeros, so we use those bits for status bits (including the invalid bit).  The invalid bit is necessary if you want to make the table sparse in any way.


How to calculate the size of a page in a two level paging CPU? I am having difficulties with understanding the concept of paging.

As a result I've got no idea how I can solve the following exercise - I'm lacking one more equation to solve it.

I've read a lot about paging and watched a few tutorials, but I still cannot solve paging problems easily. I'll provide some of the resources I learnt from at the bottom of this question.

Background:

The CPU has two level paging and the logical and physical addresses are of $34$ bits size each.

The sizes of the page table directory, the table directory and the page are equal.

The logical address $(12345678)_{16}$ has been translated to the $(ba9678)_{16}$ physical address.

What's the size of a single page?

My attempt:

The logical address can be decoded to:
$$(00\ 0001\ 0010\ 0011\ 0100\ 0101\ 0110\ 0111\ 1000)_2$$
The physical address can be decoded to:
$$(00\ 0000\ 0000\ 1011\ 1010\ 1001\ 0110\ 0111\ 1000)_2$$
So, as you can see, they share the last $14$ bits.
Hence, the number of bits representing offset is $\leq 14$.
The physical address looks like this:

+-----------+-----------+--------+
+-page-size-+-page-size-+-offset-+
+-----------+-----------+--------+

because page size = page table size = table directory size.
Therefore, we get the following equation:
$$
2\times \text{page size} + \text{offset} = 34
$$
However it is not sufficient to tell what is the page size. I'm stuck.

Resources:

Segmentation and paging
Wikipedia (discouraged)
Video tutorial by Anshul Agarwal: part 1, 2, 3, 4 and 5.

The thorough solution:

The virtual address looks like this:

+-------------+------------+--------+
+ table index + page index + offset +
+-------------+------------+--------+

where:

table index is the index length of an entry in the page table directory. I'll call it $i_t$.
page index is the index length of an entry in the page table. I'll call it $i_p$.

So we have such an equation now:
$$
i_t+i_p+o=32
$$
where $o$ represents bits that we need for offset.

From the decoded addresses we know that offset cannot be greater than $14$, so:
$$
o \leq 14
$$
We know that an entry in both page tables and page tables directories needs $i_t + b_d$ of bits where $b_d$ is the number of bits for accounting information (such as dirty bits, protection bits and so on). So, $b_d$ are accounting bits in the page table directory and $b_t$ are are accounting bits in page table.

So, if $\text{page size} = 2^\text{offset}$ then $\text{page table size} = 2^\text{offset}$ and $\text{page table directory size} = 2^\text{offset}$:
$$
\begin{cases}
i_t+b_d = o\\
i_s+b_t = o\\
\end{cases}
$$
We can say thatSince $\text{page table size} = \text{page table directory size}$ then $i:= i_t = i_s$ and $b :=b_d=b_t$, so we end up with a system of equations like this:
$$
\begin{cases}
i_t+b_d = o\\
i_s+b_t = o\\
i_t+i_p+o=32
\end{cases}
$$
$$
o-b_d+o-b_t+o=32\\
$$
and finally because of $b :=b_d=b_t$:
$$
3o-2b=32\\
$$
Now we will test different values of $o$ (I'll not test odd $o$'s because $o$ must be dividable by $2$):

when $o=14$:
$$
42-32=2b=10\\
\implies b=5\\
\implies i = 14-5=11\\
\implies i_t+i_s+o=11+11+14=36 \neq 32
$$
when $o=12$:
$$
36-32=2b=4\\
\implies b=2\\
\implies i = 12-2=10\\
\implies i_t+i_s+o=10+10+12=32 = 32
$$
which seems to be the answer. Let's just make sure there are no other possibilities.
when $o=10$:
$$
30-32=2b=-2\\
\implies b=-1\\
$$
which cannot be true - you obviously cannot have a negative number of bits.

Therefore, the size of a page is equal $2^o=2^{12}$.


Partitions of a directed graph - common prey and common enemy partitions Let $D=(V,E)$ be a finite directed graph with no isolated nodes(from every node there is at least one edge entering and one exiting). For $v \in V$ define the following sets: $$v^+= \left\{w \in V|(v,w)\in E \right\}, v^-= \left\{w \in V|(w,v)\in E \right\}$$

For some $S \subseteq V$ we have, $S^+= \bigcup_{v \in S} v^+, S^-= \bigcup_{v \in S} v^-$.

Now define two related graphs, $G_{cp}=(V,E_{cp}),G_{ce}=(V,E_{ce})$ such that for two distinct nodes $v,w \in V$ we have $vw \in E_{cp}$ iff $v^+ \cap w^+ \neq \emptyset$ (we identify this by condition $C(p)$,  and $vw \in E_{ce}$ iff  $v^- \cap w^- \neq \emptyset$ (condition $C'(p)$ (The notations cp and ce come from "common prey" and "common enemy" )

Let $B_1,B_2,...,B_p$ be the sets of nodes of the connected components of $G_{cp}$ and $A_1,A_2,...,A_k$ be the set of connected components of $G_{ce}$. Obviously those sets are two partitions of $V$

Prove that $(B^+_1,B^+_2,...,B^+_p)$ and $(A^-_1,A^-_2,...,A^-_k)$ represent partitions of $V$. Also prove that $p=k$ (that is both graphs have the same number of connected components).

To prove the first part I thought about taking some arbitrary $v \in V$ and than proving that $v$ is in $(B^+_1,B^+_2,...,B^+_p)$. Then a proof by contradiction may be required to complete the first part, but I can't quite seem to make the connection. I don't even know how to start proving $p=k$. Could you help, give me some hints that I miss or something?

UPDATE

So, after some research, it seems that $G_{cp}$ is a competition graph.

Let $p = p_1,\ldots,p_n$ be a sequence of vertices. We say that this is a +path from $p_1$ to $p_n$ if $n$ is even and $(p_1,p_2),(p_3,p_2),(p_3,p_4),(p_5,p_4),\ldots,(p_{n-1},p_{n-2}),(p_{n-1},p_n)$ are all directed edges. In other words, a +path is one that alternates taking the edges in the "correct" and "wrong" ways, starting with a "correct" and ending with a "wrong". A -path is defined analogously with the directions reversed.

Say that two vertices $p,q$ are +equivalent if there is a +-path from $p$ to $q$. I claim that this is an equivalence relation. Indeed:

The empty +path connects a vertex with itself.
The reverse of a +path from $p$ to $q$ is a +path from $q$ to $p$.
The concatenation of a +path from $p$ to $q$ and a +path from $q$ to $r$ is a +path from $p$ to $r$.

The equivalence classes of this relation are $B_1,\ldots,B_p$. If $x \in B_i$ and $y \in B_j$ have a common out-neighbor $z$ then $x,z,y$ is a +path from $x$ to $z$, so $i = j$. This shows that the $B_i^+$ are distinct, and because every vertex has an incoming edge, they form a partition of the vertex set.

We can similarly define -equivalence, whose equivalence classes are $A_1,\ldots,A_k$, and show that the $A_j^-$ partition the vertex set (since every vertex has an outgoing edge).

Take any $x,y \in B_i^+$, say $(z,x),(w,y)$ are edges for $z,w \in B_i$ (possibly $z = w$) and there is a +path $\alpha$ from $z$ to $w$. It's not hard to check that $x,\alpha,y$ is a -path from $x$ to $y$. Conversely, suppose that $x \in B_i^+$ and $y \in B_j^+$, say $(z,x),(w,y)$ are edges for $z \in B_i, w \in B_j$. If there is a -path $\beta$ from $x$ to $y$ then $z,\beta,w$ is a +path from $z$ to $w$, so that $i = j$. We conclude that $\{B_1^+,\ldots,B_p^+\} = \{A_1,\ldots,A_k\}$, so $p = k$. Similarly $\{A_1^-,\ldots,A_k^-\} = \{B_1,\ldots,B_p\}$.


radix-sort with different bases So i understand how to use radix-sort in base 10 and utilize mod 10 to go through the numbers. But not sure about 2,8 or 16.

Does it follow the same idea? and i read somewhere that i need to pass the base number to the radix function but not sure why would that be needed? because if i have for example:

int arr[] = {0xAA, 0x2D , 0x4B, 0x5A, 0x322, 0x24, 0x2, 0x42};

it works perfectly. So not sure why i need to pass the base to the function.

Radix sort splits data into own digits of given size, you may choose the base in which data would be treated. If you have 64bit integer you may choose size of radix to be any number, say 2 bits, 4bits, 21bits, 32bits etc., but since computer stores digits as binary numbers it makes more sense to stick with power of two.
Also, you would like to omit modulo operator and use bit masks for efficiency purposes, which is not possible for other numbers.

You haven't described your code, but if it assumes 10 as default base, it is perfectly good, your code is in hexadecimal representation, which gets stored as binary and then treated as decimal based number for sorting. This doesn't change your code, just language feature to provide numbers like that (you can input octal number using 0 in front, say 056, but it will not change running time, but changing radix will).


Woman optimal Gale Shapley Stable Matching I am learning about Gale Shapley Algorithm now, and I understand that it is Man Optimal and that all possible executions will yield a stable matching where each man gets the best partner that he can have. I was thinking is it possible to have a woman optimal solution with a guaranteed stable matching? Let's say each woman has a different man as her most preferred partner. Then can we say that we can ensure stable matching by simply assigning the most preferred man to each woman?

I am having problem understanding that, since by definition the matching is stable if no man or woman prefer another to their current situation. Wouldn't it give as stable matching if each woman has the most preferred man, considering they all unique?

Yes, of course you can switch the roles of men and women in the algorithm and you'll get a woman-optimal solution. It's just convention that we call one side of the graph "men" and the other side "women" but the algorithm itself doesn't care what names we use. We could just as well call them "horse" and "blueberry".


How to get this upper bound on worst-case heaps? I've seen answers on the subjects, however I still don't get such answers. In the Cormen book (Introduction to algorithms) it is explained that the worst case for a $Max-Heapify$ call happens when the last level is "half full", in this case the worst case cost is modeled by the inequality:

$$
T\left(n\right) \leq T\left( \frac{2n}{3} \right) + \Theta(1)
$$

I understand the equality (i.e. what it is modeling) but I don't understand how the worst case is built, I've tried to imagine an heap where the left subtree of the root is full up to level $h$ while the right one has (for example) just one node at level $h$, and with this example I can't see why the worst case modeling doesn't work, why such case would not represent an instance of the worst case?

The second question is that I don't understand why the number of nodes at height $h$ are at most $\lceil \frac{n}{2^{h+1}} \rceil$. There are proofs but I can't understand the motivation.

Update:

Trying to explain in more detail what I don't understand. As far as I know/remember for given $n$ that somehow measures how large is the input of an algorithm the worst case analysis is "choose among all the possible instances of size $n$ the one that would give you the worst case execution cost"

Following this direction, to me is not particular clear how for given $n$ we can be sure that the left subtree has $\frac{2n}{3}$ nodes, it is ok when the value $n$ is such that the distribution of nodes is such that half of the last level is full, while the other one is empty. In the proof for cost bounding I would differently.

I would distinguish two cases :

The tree has height $h$ and is complete, i.e. the total number of nodes is $2^{h+1} - 1$, I would also explain that it is possible to build in such case an heap such that starting from the root key it is possible to push down such key until it reach a leaf, how much is the cost in such case? it is exactly $h = ln_2(n+1) - 1 = O(ln \;n)$.
The tree has height $h$ but it is not complete, given the heap structure the left-most leaf is at height $h$. As done in point 1 I would explain it is possible to build a tree such that the root would be pushed down always in the left branch. How much is the cost in this case? Given that $n > 2^{h} - 1$ we have that $h < ln_2(n+1) = O(ln(n))$.

I don't think is difficult to build a particular example for both 1. and 2.
I also don't really see the point of "completing a tree" for computing the worst case cost, I can understand this operation can make the analysis easier, but for what I know about worst case analysis (assuming it is correct) it doesn't sounds correct to me.

In Heap sort we use a data structure which is a binary tree, and it is nearly complete. So, height is bounded by
 where n is the no. of nodes. In comparison to root, height of left and right subtree can differ by 1 at max.

Now, Imagine a tree T, and also assume left subtree height = h+1 and right subtree height = h

What is worst case in max_heapify() ? Worst case is when , we end up doing more comparision and swaps while trying to gain heap property.

If the recursive max_heapify algorithm runs and it recursively goes to the longest path, then we can say : a possible worst case.

Well, all the longest paths are in the left sub-tree (because height is h+1 ).

So, to get more longest paths we need to have make left subtree completely full. Since left subtree is of height h+1 , it will have  leaf nodes and  longest paths from root. This is the maximum possible number of longest paths ( of h+1 height ) in T, such that while max_heapify()  is running in a recursive way, it may traverse to the bottom of the left subtree. And we maximize such longest paths by considering left subtree as FULL to make the possibility of deep traversing more frequent in max_heapify() function.

Below is tree structure in worst case situation :

From the above figure assume yellow and red portions has x nodes each. Red portion is total right subtree and yellow portion is excluding the last level of left subtree. Both red and yellow sections now have height h.

How many nodes we have to add ( or attach or pad ) in the bottom layer of yellow portion to make the left subtree completely full  as well as of height h+1 ?

Well, bottom layer of yellow portion has  nodes and we now add 2 children to each of these nodes, => total x ( ) nodes have been added. Why adding, just to make left subtree of height h+1 and full to meet worst case criteria.

OK !! DONE !! .. now , count how many nodes overall...

total =

And left subtree contains 2x nodes = 2n/3 nodes.

So, for worst case one of the subtree should have 2n/3 nodes.

More in the following links :
https://stackoverflow.com/questions/9099110/worst-case-in-max-heapify-how-do-you-get-2n-3

https://math.stackexchange.com/questions/181022/worst-case-analysis-of-max-heapify-procedure


prove(disprove) asymptotic exact bound (theta) I want to prove (or disprove) that

$$\sum_{i=1}^n\log_2 i = \Theta(n\log_2 n)\,,$$

but I totally get stuck with this example. May someone help me with that.


Non-brute force algorithm for a Eulerian like path I have a graph with an arbitrary amount of edges and vertexes.  Each vertex having an arbitrary amount of edges connecting to it but in practice the number is usually around 3 or 4 no less than one and no more than a dozen.  I want to find the path that goes to as many vertexes and edges as possible without using any edge more than once.
In addition there are a few special cases that I would like to add but an algorithm that doesn't solve for these is fine:

There are pairs of vertexes that are connected with multiple edges.  I can traverse multiple of these edges but I cannot immediately return to the previous vertex I was at without first going to another vertex.
There are some edges that are one way.
Some vertexes will change the destination of edges connected to themselves depending on the edge you arrived from.  In practice this is always a vertex with two edges that if arrived from one edge will change the other edge to return to the source of the first edge and if arrived from the other edge the first will not change.  In theory it doesn't have to be though.

I know this problem cannot be solved in polynomial time and I have thought of ways to speed up the brute force method I am just wondering if anyone else has any ideas.

Regarding the problem of visiting as many vertices/edges as possible without using any edge twice: one can look at this problem as the problem of finding an Eulerian subgraph with a maximum number of vertices/edges.  Or alternatively, as the problem of deleting a minimum number of vertices/edges so as to make a graph Eulerian.
You might be interested in the following paper, which studies the complexity of such problems in detail.  In particular, they show several polynomial-time solvable or fixed-parameter tractable cases.  In particular, the edge deletion problems are solvable in n^3 time if a constant number of edge deletions is sufficient.
https://doi.org/10.1007/s00453-012-9667-x


Show that a set is turing reducible to another set Consider an operator $+$ defined on $P(N)$ as follows: $A + B = \{2x\mid x \in A\}\cup \{2x + 1\mid x \in B\}$
Show that both $A$ and $B$ are Turing-reducible to $A+B$
I am kind of confused about this notion of turing reducibility thing.
Does it mean that There is a turing machine which converts an input from $A$ to an element of $B$
on the tape. There is a term called oracle that also pops up. So if we have an oracle for $B$
does it mean that there is a decider for $B$? What's an intuitive workable definition of oracle?

The definition of Turing reducible, is that there exists a Turing reduction - an algorithm for $A+B$ that uses an oracle to $A$.
To understand this, you must first understand oracle machines. Those machines, are like turing machines, but can ask an "oracle" whether any $x$ is in $A$ or not, and would get an answer in $O(1)$, regardless of what $A$ is (doesn't even matter if it is not decidable!)
So, a turing reduction basically means that if you know for any $x$ whether its in $A$ or not in $A$, then you can decide whether a given $x$ is in $A+B$. Formally, this statement can be written as ${(A+B)}^A\in R$.
So basically the question asks you to show that ${(A+B)}^A,{(A+B)}^B\in R$


What is the closest result relating perfect shuffle closure of primitive words? A perfect shuffle of two words $u=a_{1}a_{2} \cdots a_{n}$ and $v=b_{1}b_{2} \cdots b_{n}$ where $a_{i}$'s and $b_{j}$'s are letters from the alphabet $\Sigma$ is defined as $u \diamond v=a_{1}b_{1} \cdots a_{n} b_{n}$.

It is obvious that if for two primitive words $u$ and $v$, their shuffle $u \diamond v$ need not be primitive. (e.g., for $u=abc$, $v=cab$, $u \diamond v=acbacb$ is not primitive.

So, my question is is there any result that proves that under certain conditions set of all primitive words is closed under this perfect shuffle? (There are results in the literature that talks about square-free shuffle but not primitivity, at least I didn't come across any.)

Please help.

I am not aware of any result of this type. And as your example shows, the set Q of all primitive words is not closed under this operation.

You can find subsets of Q which will result only in primitive words. For example a a+ b b+. The perfect shuffles will be from a a+ (ba)+ b b+ and all of these are primitive again (though not from the original set).

The results on square-free shuffle seem to be not about the perfect shuffle, but the general case. Then they say that at least one square-free word is in the shuffle. That should be easy to show for primtive words. In your example, all resulting words are primitve except the one from the perfect shuffle.


Chromatic polynomial of a square Consider a square, ABCD. Intuitively it seemed to me that its chromatic polynomial is $\lambda(\lambda - 1)(\lambda - 1)(\lambda - 2)$ where there are $\lambda$ colours available..

That is there are $\lambda$ ways in which a colour for A can be picked, there are $\lambda - 1$ ways for colours for B and D to be picked(B and D are adjacent to A) and $\lambda - 2$ ways for colours for C to be picked.

However using the decomposition theorem (slide 47, Example 11.33) and decomposing the square into a path of length 3 and a triangle, shows that my initial reasoning is wrong.

Could you tell me where I am going wrong with my thinking.

You must remember that the vertices diagonal from one another can be colored the same! Your formula does not take that into account. We can find the chromatic number of a graph via the inclusion-exclusion principle. It is a very general counting technique that allows us to count complex structures, if we can prove certain bounds on certain subsets.

The main idea is that we count all possible ways some property happens. Then we remove some "bad" items. However, we may have removed too much, and need to add back some "good" items. This goes back and forth until we've gone through all subsets.

Inclusion-exclusion principle tells us that given some ground set $|X|=n$, the number of elements of $X$ which lie in none of the subsets $A_i$ is
$$ \sum_{I \subseteq [n]} (-1)^{|I|}|A_I| \text{, where } \\ I \text{ is the set of indices in } X \text{ and } A_I = \bigcap_{i \in I} A_i$$

Let $\lambda$ be the number of colors, and let $X$ be the set of all possible colorings (i.e., $|X| = \lambda^4$), and let $$A_{e} = \{\text{coloring} : e=(i,j) \in E, \text{color}(i) = \text{color}(j) \}$$

Before we get our final polynomial, we need to count the size of our sets $A_{e}$, and the size of all intersecting subsets.

Observe that $|A_{12}| = |A_{23}| = |A_{34}| = |A_{41}| = \lambda^3$. This is  due to the fact that we are just coloring $G$ but always picking the same colors for neighboring vertices. Going forward we have,

$|A_{12} \cap A_{23} | = |A_{23} \cap A_{34} | = |A_{34} \cap A_{41}| = |A_{41} \cap A_{12}| = |A_{12} \cap A_{34}| = |A_{41} \cap A_{23}| = \lambda^2$

I'm not going to list each 3-set, but they all have the same count. $|A_e \cap A_{e'} \cap A_{e''}| = \lambda$. And Finally, $|A_{12} \cap A_{23} \cap A_{34} \cap A_{41}| = \lambda$. Now lets collect our terms and add up.

$$\lambda^4 - 4\lambda^3 + 6\lambda^2 - 4\lambda + \lambda = \lambda^4 - 4\lambda^3 + 6\lambda^2 - 3\lambda$$

Now counting with inclusion-exclusion for this problem wasn't so bad because we had a simple 4-cycle. If the graph had more structure it would quickly get annoying to figure out each intersection size for all possible intersections.


Classification of technologies used for communication in distributed systems I am currently writing a State of Art about technologies used for distributed communication (like CORBA for example). I want to structure the document in way that I don't leave any subset of this technologies out of the research. My proposed solution is to structure the document by Communication Paradigms:

Interprocess Communication
Remote Invocation
Indirect Communication

Am I missing a paradigm? Are there another classifications that could be usefull for structure the document? Also if you can recommend me a good source to read about this topic, I would really apreciate it.

Finally I decided to classify the distributed system technologies by the communication paradigm that they implement. The categories of communication paradigms I considered are:

Remote Procedure Call
Berkeley Sockets
Message Passing Interface
Message Oriented Middleware
Distributed Shared Memory
Stream Oriented Communication
Multicast Communication (based in peer-to-peer architecture)

I still have to do some research about some more modern implementations that can eventually use a paradigm not listed here.


What is an example for a decidable language not in P? I'm having trouble showing that $P\neq R$. Obviously $P\subseteq R$, but is there  a decidable language which is definitely not (under all answers to open questions s.t. $P=NP$ or $NP=PSPACE$) in $P$ ?

Yes, there are decidable languages that are definitely not in P. The time hierarchy theorem says that P$\,\neq\,$EXP, so P$\,\neq\,$R, independently of the P vs NP problem. Any EXP-complete problem is definitely not in P: for example determining whether white has a winning strategy from a position in generalized chess ("generalized" in the sense of allowing a board of any dimensions, with any arrangement of any number of pieces, but otherwise following all the rules of standard chess).


Understanding of Turing's Answer to the Entscheidungsproblem I apologize if this question has been asked before, but I was not able to find a duplicate.

I have just finished reading The Annotated Turing and I am a bit confused.

From what I understand, the Entscheidungsproblem is whether or not an algorithm exists that can determine whether a statement is provable. In the paper, Turing defines a K machine that will prove all formulae that are provable. This seems almost like a resolution to the problem, but later Turing writes:

  If the negation of what Gödel has shown had been proved, i.e. if, for
  each A, either A or -A is provable, then we should have an
  immediate solution of the Entscheidungsproblem. For we can invent a
  machine K which will prove consecutively all provable formulae.
  Sooner or later K will reach either A or -A. If it reaches A,
  then we know that A is provable. If it reaches -A, then, since
  K is consistent (Hilbert and Ackermann, p.65), we know that A is not provable.

Gödel's Theorem showed that some statements are true, but not provable. I guess what I don't understand is how Gödel's result prevents Turing's K machine from being a solution to the Entscheidungsproblem. Is it just as simple as that there are some formula that the K machine will never encounter, so it will keep running forever and never conclude that the formula is unprovable?

What Gödel showed is that there is no finite first-order axiomatization of the theory of the natural numbers. What this means is that if you give a finite list of first-order axioms and schemas, then the corresponding proof system won't be able to prove all true statements about the natural numbers. For example, it won't be able to prove its own consistency (this is Gödel's second incompleteness theorem). (A proof system is consistent if it doesn't prove a statement and its converse.)

Turing's machine, when applied to any given finite first-order proof system $\Pi$, will thus be able to prove neither the statement that $\Pi$ is consistent nor its negation.

Of course, this is not a proof that the Entscheidungsproblem itself is unsolvable; perhaps there is an altogether different approach that does work. Turing was able to show that, in fact, no (computable) approach works.


What is the name of the following algorithm? I am  using the following algorithm to solve an optimization problem I have. I was wondering if there is a proper name for this algorithm in the literature.

Let $f(x)$ be my objective function.

I guess some $x_0$ and see have it performs.

Next, I randomly generate around $x_0$, some $\{x_k \}$ for $k \in [1:K]$  and see how the compare to $x_0$.  If I find  $x_n$ that perform better than $x_0$.
I perform the same procedure again with $x_n$.

I am only starting to learn about algorithms and would be grateful if you point me to the name and some reference on similar algorithms

This is a form of local search.  It is similar to hill climbing.  It's also reminiscent of stochastic hill climbing, as @Juho suggests.


Can the human brain be considered Turing complete? I'm not a student in computer science, but from what I understand from the Wikipedia article on the topic, a programming language is Turing complete if it can emulate another Turing complete language's algorithm.

Now if we consider that languages like Java, C, C++ and so on are considered Turing complete, and that all algorithms implemented in programmation are by necessity first formulated in our brain, does this mean the human brain is Turing complete?

Also a human can simulate the processes going on in a processor (or we couldn't have been able to build them), but a processor can't simulate a human brain, so how is the human brain placed in terms of Turing equivalence?

Let's do this in order:

We do not say "another Turing complete language's algorithm" because "language's algorithm" is at best a confusing phrase. You might have meant "language's interpreter" but we cannot tell. It would be better to say "a programming language is Turing complete if it can emulate another Turing complete programming language". Note however that this is a circular condition, you need to get started somewhere. The place to start is Turing machine, of course. So: a language is Turing complete if it can be simulated by Turing machines and can simulate Turing machines. We would still have to precisely explain what "simulate" means here.
Languages such as C, C++ and Java are not "considered" Turing complete. They are Turing complete.
I deny that "all algorithms are by necessity formulated in our brains". For instance, a machine learning algorithm can come up with a new algorithm. Or perhaps an algorithm can be discovered by exhaustive search. Aliens could land and propose a new algorithm for sorting an array. Be that as it may, even if you are correct and all algorithm are formulated in our brains, your conclusion still does not follow. The following situation is in principle possible:

human brains are devices which spew out algorithms, i.e., they produce code to be executed, but
human brains are not capable of running such code

In the extreme case a human brain could be nothing but a device which mindlessly produces all possible algorithms. One can in fact build a machine which does this, but this machine would not be Turing complete.
Regarding a brain simulating a processor, I highly recommend that you read Turing's original paper, keeping in mind that in 1936 "a computer" was a person performing computations. Turing machines were designed to capture the mental abilities of humans performing calculations!
I take issue with your claim that a machine cannot simulate a brain. You have provided no evidence for this, and it seems in principle possible that a sufficiently powerful machine would simply simulate everything that is going on in a brain. It may seem complicated, but so far as we know, the laws of physics do not prevent this possibility.


In what cases is solving Binary Linear Program easy (i.e. **P** complexity)? I'm looking at scheduling problems in particular In what cases is solving Binary Linear Program easy (i.e. P complexity)?
The reason I'm asking is to understand if I can reformulate a scheduling problem I'm currently working on in such a way to guarantee finding the global optimum within reasonable time, so any advice in that direction is most welcome.
I was under the impression that when solving a scheduling problem, where a variable value of 1 represents that a particular (timeslot x person) pair is part of the schedule, if the result contains non-integers, that means that there exist multiple valid schedules, and the result is a linear combination of such schedules; to obtain a valid integer solution, one simply needs to re-run the algorithm from the current solution, with an additional constraint for one of the real-valued variables equal to either 0 or 1.
Am I mistaken in this understanding? Is there a particular subset of (scheduling) problems where this would be a valid strategy? Any papers / textbook chapter suggestions are most welcome also.

It is not true that fractional solutions can necessarily be turned into integral solutions.  For example, suppose that 1 requires either slots A and B, or slots D and E; 2 requires either slots B and C, or slots E and F; and 3 requires either slots A and C, or slots D and F.  It's easy to check there is no integral solution at all (A,B,C together can accommodate at most one, and D,E,F together can accommodate at most one).  However there is a fractional solution of giving everyone 1/2 of every slot that might possibly accommodate them.
There are conditions such as total unimodularity that guarantee that there are optimal integral solutions.  In that case, the problem is in P, because all that is needed is to solve the LP relaxation which can be done in polynomial time.


Does a polynomial-time reduction from A to B imply that B is in NP if A is? Let f be a polynomial-time reduction of a decision problem A to a decision
problem B. We know that, if B $\in$ P then A $\in$ P. Similarly, if B $\in$ NP then
A $\in$ NP. However, what about the other direction? Assume that A $\in$ NP and
consider the following non-deterministic algorithms to decide whether y $\in$ B:

"Guess" non-deterministically some x.
Verify that f(x) = y by computing f(x) in polynomial time and comparing
it with y. If f(x)$\neq$y, reject.
Check (using the polynomial-time nRAM for A) whether x $\in$ A and return
the answer.

Why does this not qualify as a proof that B $\in$ NP?

For your proof to work correctly, $f$ must be surjective:

\begin{align}
f: \Sigma_A^\star \to \Sigma_B^\star \\
\forall y \in \Sigma_B^\star \quad \exists x \in \Sigma_A^\star: f(x) = y
\end{align}

Otherwise, you cannot guess a $x$ for each $y \in \Sigma_B^\star$, with $f(x) = y$ in step 1.

Alghough some polynomial reductions are bijective (e.g. CLIQUE $\le_p$ INDEPENDENTSET), a polynomial reductions is not required to be either injective or surjective. This is why your proof fails. There are even proofs that use reductions, whose image only consist of two words.

Example for such an extreme case: Proove that $L_1, L_2 \subseteq \Sigma^\star$, where $L_2 \ne \emptyset$ and $L_2 \ne \Sigma^\star$, both $L_1$ and $L_2$ are in $P$ implies that there exists a polynomial reduction from $L_1$ to $L_2$.

Let $w_t \in L_2$ and $w_f \in \Sigma^\star \setminus L_2$. Construct $f: \Sigma^\star \to \Sigma^\star$, such that
\begin{align}
f(x) = \begin{cases}
w_t  & \mbox{if } x \in L_1\\
w_f  & \mbox{if } x \notin L_1
\end{cases}
\end{align}
Since $L_1$ is in $P$, $f$ simply calls a TM that decides $L_1$ and then outputs the corresponding words. Therefore, $L_1 \le_p L_2$.


How is the Varshamov-Tenegolts code decoded? For $0 \leq a \leq n$ the VT code $VT_a(n)$ consists of all tuples $(x_1,x_2,..,x_n) \in \{ 0,1\}^n$ such that $ \sum_{i=1}^{n} ix_i = a (mod (n+1))$

For example $VT_0(4) = \{ 0000,1001,0110,1111 \}$

Say someone has $x = 1001$ and deletes the first zero and transmits $x' = 101$. Now is the claim that a receiver who only has access to say $101$ string will be able to decode back to $1001$?
Searching on the net what I see being called as "decoding algorithm" seems to me to assume that the receiver at least has access to the sums $\sum_{i=1}^{n} ix_i$ and $\sum_{i=1}^{n-1} ix'_i$ and also knows stuff like number of 1s and 0s to the left and right of the deleted position. This doesn't make sense to me since I thought that the idea is that the receiver doesn't know anything about $x$!

Right, the code $VT_0(4)$ has Levenshtein distance (edit distance) of 4: to get from one codeword to another you must do 2 deletions and 2 insertions. Therefore, the code can correct one deletion.
Indeed, if 101 was received, the only possible way to get this message assuming one deletion, is if 1001 was sent.

Decoding can be done in several ways:

The naive approach: since the edit-distance is large, if only a single deletion occurred there is only a single codeword that could have been sent. To decode we can just go over all the codewords until we find the one that leads to the received word. More efficiently, we can start with the received word and try to insert 0 or 1 in all the possible position until we get a codeword. We are guaranteed that we will get only one code word. However, this still may take a lot of time/computation.

The more efficient approach is an observation that appeared in Levenshtein's original paper[1] and then also re-explained in Sloan's manuscript on single-deletion correction codes[2]. I'll repeat the essence of it, but you can find it there as well.

Assume each of the codewords $x=x_1\ldots x_n$ satisfies
$$ \sum_{i=1}^n ix_i = a  \mod n+1$$
If there was only a single deletion we will get the word $y=y_1\ldots y_{n-1}$. we can compute the value
$$a' = \sum_{i=1}^{n-1} i y_i$$
The key observation is the following. Let's assume the index $j$ was deleted. That is $y_1=x_1, \ldots, y_{j-1}=x_{j-1}$ and $y_j=x_{j+1}, \ldots y_{n-1}=x_n$. Denote with $R_0$ the $\{x_i\}_{i<j}$ that are a $0$, and with $R_1$ the ones that are a $1$. similarly, let $L_0=|\{ x_i =0 \mid i>j\}|$ and $L_0=|\{ x_i =1 \mid i>j \}|$.
Now let's look at $a'-a \mod n+1$. (below all computations are $\text{mod } n+1$.)

3.1. Let $w=L_1+R_1$ the weight of $y$ (the number of $1$'s).

3.2. If $x_j=0$, then
$$\begin{align*}
a'-a &= \sum_{i=j}^n  i(y_i-x_i) = \sum_{i=j}^n  i(x_{i+1}-x_i) \\
     &= ix_{j+1} + (i+1)(x_{j+2}-x_{j+1}) + \dotsb + (n-1)(x_n - x_{n-1}) - nx_n\\
     &=-x_{j+1} - x_{j+2} - \dotsb - x_n = -R_1
  \end{align*}$$
(note that $R_1<n$ so the mod $n+1$ is good enough; I also virtually set $y_n=x_{n+1}=0$ so it adds nothing to the sum but make them well defined)

3.3. But if $x_j=1$, then
$$\begin{align*}
a'-a &= \sum_{i=j}^n  i(y_i-x_i) = \sum_{i=j}^n  i(x_{i+1}-x_i) \\
     &= i(x_{j+1}-1) + (i+1)(x_{j+2}-x_{j+1}) + \dotsb + (n-1)(x_n - x_{n-1}) - nx_n\\
     &= -R_1 -i = -R_1 - L_0 -L_1 -1 = -w -L_0 -1
  \end{align*}$$

3.4. Forget about the minus sign (that is, look at $a-a'$ instead). If we get something which is $<w$ then we must be in the first case (since $R_1<w$), and we learn two things: (1) that a zero was deleted, and (2) we learn $R_0$, which means that we know where to put the zero back: before this deleted zero there are exactly $R_1$ ones!
if what we get from $a-a'$ is $>w$ we know we are in the second case. Now we learn that: (1) a one was deleted from the codeword, and (2) we learn $w+1+L_0$ but we know $w$ so we get $L_0$, and we can restore the deleted 1: to the left of this deleted one there are exactly $L_0$ zeroes.

See also

[1]: V.I. Levenshtein, Binary codes capable of correcting deletions, insertions, and reversals, 1966.
[2]: N.J.A Sloan, On Single-Deletion-Correcting Codes, 2002.


Maximum sum difference between two sorted array elements under one condition We're given two arrays $A$ and $B$ with size $N$ and $M$ respectively. We want to find a set $P = \{(a_1, b_1), \dots, (a_s,b_s)\}$ such that

for each $i\in\{1, \dots, s\}$, $a_i\in A$, $b_i\in B$ and $a_i>b_i$ and $a_i,b_i$ musn't be chosen before;
$\sum_{i=1}^s (a_i-b_i)$ is maximized.

A natural approach is to sort array $A$ in descending order and $B$ in ascending order, initialize $i$ and $j$ to $1$, then iterate: while $A[i] > B[j]$ add $A[i] - B[j]$. How we can prove that this solution works?

Two sets A and B.  Using i and j only once maximize the ∑(a[i] - b[j]).  Not required to use and i and j.

I don't know if this is a hard proof but

For $A[i] > B[j]$
∑(a[i]−b[i])  =  ∑(a[i]) - ∑(b[i])

So the problem is reduced to maximize $A[i] > B[j]$
Reverse sorting maximizes the number of $A[i] > B[j]$

Or another way to say it
maximizes ∑(a[i]) and minimizes ∑(b[i])
Descending sorting maximizes ∑(a[i])
Ascending  sorting minimizes ∑(b[i])


Technique for converting recursive DP to iterative DP I'm new to Dynamic Programming and before this, I used to solve most of the problems using recursion(if needed).

But, I'm unable to convert my recursive code  to DP code.

For eg, below is the pseudo-code for Finding longest common-subsequence in 2 strings :

int LCS(i,j):
    if A[i]=='\0' or B[j]=='\0':
        return 0;
    else if(A[i]==B[j]):
        return 1 + LCS(i+1,j+1)
    else:
        return max(LCS(i+1,j),LCS(i,j+1))

Now, I understand the above code and below is its DP equivalent:

//Some initializations are needed which have been skipped
if(A[i]=B[j]):
    LCS[i,j] = 1 + LCS[i-1,j-1]
else:
    LCS[i,j] = max(LCS[i+1,j],LCS[i,j+1])

I'm not able to figure out how did they construct its DP equivalent with the help of the recursion technique?

In the recursion technique, 1 + LCS(i+1,j+1) is written whereas, in DP 1 + LCS[i-1,j-1] has been used.

I am wondering how did they use minus in place of plus and how will I figure out myself(for other programs involving DP) that such adjustments need to be made in the code?

This DP code is the bottom up solution of the problem. The key is that you start with smaller subproblems and then use these solutions to solve a bigger subproblem.

The data structure we use to store these results is actually holding results to different subproblems of the problem. For eg. let say we want to find a LCS for strings abcbdab and bacdba and let the data structure be a 2D array called cache[][].

The smallest problem is when first string has only a and second string has only b. Here nothing is common. So the LCS has a length of 0 and hence $cache[1][1] = 0$ (1-based indexing). A slightly bigger problem than this would be when first string is a and second string is ba. Here the characters match and hence $cache[1][2] = 1$.

So in this way you can see we can keep growing the problem incrementally and use the previous solutions to have a solution of a bigger size problem.

The reason why we are using minus is because we are just using solutions of subproblems of smaller size represented by smaller indexes in our solution array.

You should not relate recursive and bottom up solutions. There is no direct relation. They are totally different way to solve the same problem. Hence you should keep in mind that you have to solve smaller subproblems and store their results.

I hope this clears the doubt.


Policies for handling symbols leaking out of a lexical scope Suppose it's possible for a symbol to escape the scope in which it is defined. What are considered the possible policies for handling that? I mean possible in the sense of what choices of language design that could be implemented -- different choices yield languages which differ in this respect.

For example, it's conceivable that two lexical scopes might each contain a symbol named "x". If these symbols escape from their respective scopes, what can we say about that? I can see three possibilities: all symbols named "x" are the same, so the symbol leaked out of the first scope is the same as that leaked out of the second; or each symbol named "x" is actually a distinct symbol, so the leaked symbols are not the same; or when a symbol escapes from its scope, something about that lexical context is carried along with the symbol, so that the result of the leakage is not a symbol but a more complex object representing the lexical context or environment and the symbol together. No doubt there are other possibilities.

I know Common Lisp implements the first policy -- (eq (let (x) 'x) (let (x) 'x)) yields T. I think Scheme does too. I don't know enough about other languages to say what might happen. I'm not aware of languages which implement the second or third ideas, but, as I was saying, my awareness is limited, and I would be interested to hear about any such languages.

I'm sure this is a topic which is well-known in the programming languages field, but through some reading and searching I haven't found it yet.

Your (let (x) 'x) will just return the atom x, and obviously all of those are the same. That you define variables called x (and give them no value whatsoever, and never use them) is just confusing the issue. I.e., your code is a roundabout way to write (eq 'x 'x).

How could a name "escape" from a lexical scope? The scope is precisely where the name has a particular meaning, an "escape" would just expand that scope somehow.

E.g. in Steelbank Common Lisp:

* (let (x) 'x)
; in: LET (X)
;     (LET (X)
;       'X)
;
; caught STYLE-WARNING:
;   The variable X is defined but never used.
;
; compilation unit finished
;   caught 1 STYLE-WARNING condition
X

enter code here


If the Clique-k Problem is in P, why not Clique as well? I have looked at the other answers to this but I still don't get it. (for instance: Why is the clique problem NP-complete?)

The general clique problem is defined as

$\text{CLIQUE} = \left\{ (G, k) | G = (V, E) \in \mathcal{G} \land \exists V_c \subseteq V . |V_c| \geqslant k \land V_c \text{ is clique in } G \right\}$

A clique of a given size can be found in polynomial time, for instance by this code:

# Iterates over all nodes. If node has at least size -1 neighbours,
# compares neighbour's neighbours with neighbours.
def CLIQUE(graph, size):

    for node in graph.nodes:
        if degree(graph, node) >= size - 1:
            neighbours = graph.edges[node]
            intersection = neighbours.union(set(node))
            for neighbour in neighbours:
                print neighbour
                print graph.edges[neighbour].union(neighbour)
        intersection = intersection.intersection(graph.edges[neighbour].union(neighbour))
            print intersection
            if len(intersection) >= size:
                return True
    return False

(rest of the program)

class Graph:
    def __init__(self):
        self.nodes = set()
        self.edges = dict()

    def from_file(self, deffile):
        with open(deffile, 'r') as f:
            for line in f:
                n1, n2 = line.split()
                self.nodes.add(n1)
                self.nodes.add(n2)
                if n1 in self.edges:
                    self.edges[n1].add(n2)
                else:
                    self.edges[n1] = set(n2)
                if n2 not in self.edges:
                    self.edges[n2] = set()

def degree(graph, node):

    return len(graph.edges[node])

So, given that the clique problem is 'Is there q clique of at least size k in G' and the above code returns true once it finds a clique of (at least) k nodes and runs in $\mathcal{O}(n^2)$, as it compares every node with every other node in the worst case, I don't understand how that code does not do what the general clique problem does... because apparenrtly it does not, as it runs in polynomial time and the general clique problem does not.

It's a matter of logical quantifiers.

Consider this statement: "if every natural number $n$ is bounded above by a constant $c$, how come there is no constant $c$ that bounds every natural number $n$ by above?".

The above is an example where $\forall n.\ \exists c.\ \ldots$ does not imply
$\exists c.\ \forall n.\ \ldots$. Indeed, in the former, we can choose $c$ after we see $n$, while in the latter we must do before, and we are unable to do that: whatever $c$ we choose, the statement becomes false for e.g. $n=c+1$.

To decide CLIQUE, once we take the instance $(G,k)$ to be checked,
we can use an algorithm which runs on $O(n^c)$ for some $c$ -- but here we are choosing $c$ after we have seen $k$. This does not prove that CLIQUE is in P. For that, we would need to find a constant $c$, and an associated $O(n^c)$ algorithm, which would decide any instance $(G,k)$, whatever $k$ is. And this is much harder.


Game tournament program, NP complete? I have been trying to find a solution both theoretical and practical to my problem but I just can't. The question is you have x players that should play some rounds y of games in groups of 4. Now if a player was in a game with somebody else, he is not allowed to be ever again with that player in the same group. Now the question is give n groups that satisfy this conditions. With n being maximal amount of possible groups.

My first approach was to just take a player put him into a group, now for the next player check the array already_played_with_players of the first player for the second player if he's not in add him and add the players he played with to the already_played_with_players array. Proceed so too for the next two players. Then mark these 4 players as in a group and take the next player out of the pool and so on.

This is not some educational question, but a real world problem. I would like to organize a game tournament, but so that people meet new people and don't play with the same people again. I already ask multiple people mathematicians, physicians, computer scientist, but the solution was not really evident to anybody. So I was wondering if the problem is NP-complete? I know I would need to find a reduction from another NP-complete problem to my problem to prove that, but I don't even know how to formalize my problem exactly.

Your problem has been solved by Brouwer in 1979 in his paper Optimal Packings of $K_4$'s into a $K_n$. Quoting from his paper, let
$$
J(2,4,v) = \begin{cases} \lfloor \frac{v}{4} \lfloor \frac{v-1}{3} \rfloor\rfloor - 1 & \text{if } v \equiv 7 \text{ or } 10 \pmod{12}, \\
\lfloor \frac{v}{4} \lfloor \frac{v-1}{3} \rfloor\rfloor & \text{otherwise}. \end{cases}
$$
The maximal number of groups when there are $v$ players, denoted $D(2,4,v)$, is equal to $J(2,4,v)$ unless $v \in \{9,10,17\}$, in which case $D(2,4,v) = J(2,4,v)-1$, and unless $v \in \{8,11,19\}$, in which case $D(2,4,v) = J(2,4,v)-2$.

The more general case in which every pair can appear at most $\lambda$ times has been solved by Assaf in his paper The packing of pairs by quadruples.


Longest common subsequence of a set of sequences There is as input a set of $m$ sequences of length $n$.

I thought it was pretty straightforward at first that the time complexity of the algorithm provided below is $O(m^2n^4)$ but then it occurred to me that the time taken depends on the length of a LCS such that the longer a LCS relative to the input length the shorter the computation.
The question I have is can you confirm that while the (measured) time taken does depend on the length of a LCS (inversely), that fact does not have an effect on the result of the O-analysis?

// Let there be m sequences of lenght n.

// Length of lcs of two sequences. Theta(n^2)
lcs_length(x, y)
// Edit distance of two sequences. Theta(n^2)
d(x, y) = |x| + |y| - 2*lcs_length(x, y)
// Edit distance (total) of y to all of X. Theta(mn^2)
d(X. y) = sum of d(x, y) for x in X

// Longest common subsequence of a set of sequences S. O(m^2n^4)
lcs(S)
    X <- copy of S
    while true
        if exists x in X: |x| = 0
            return ""
        if exists x in X: for all s in S: x is a subsequence of s
            return x
        for x in X
            d_min <- +infinity
            i_min <- +infinity
            for i in 1..|x|
                // Make a copy of x with the ith symbol removed:
                x_i <- x[0..i-1] + x[i+1...]
                // Compute the sum of edit distances to all of the original sequences:
                d_i <- d(S, x_i)
                if d_i < d_min
                    d_min <- d
                    i_min <- i
        X <- X difference { x }
        X <- X union { x[0..i_min-1] + x[i_min + 1...] }

There may be multiple different ways to upper-bound the running time of an algorithm.

Saying that the running time of an algorithm is $O(m^2 n^4)$ is analogous to saying that the running time is at most $m^2 n^4$ (ok, $c \cdot m^2 n^4$, for some constant $c$).  The keyword there is "at most".  So, think of $O(\cdot)$ as more like $\le $ than like $=$.

I haven't tried to analyze the running time of your specific algorithm, but to make up some numbers, it is possible that the running time could simultaneously be $O(m^2 n^4)$ and it could also be true that the running time is (say) $O(m^2 \ell^4)$ where $\ell$ is the length of the longest subsequence.  I'm totally making up those figures -- don't take them too seriously, as I don't claim they are actually valid running times for your algorithm -- I am just saying that both claims are consistent, i.e., they could both be true, without contradicting each other.

It's analogous to the fact that we could have both $x \le 3$ and $x \le 4$ be true.  Or, we could have both $x \le c^2$ and $x \le d^3$ be true.

Side remark: I haven't looked at your algorithm closely, but it looks suspicious to me. I would be surprised if it is a correct solution for the longest common subsequence problem.


Do we need to read the input completely in Turing machine? This question is motivated from the question $\mathrm{SPACE}(o(\log\log n)) = \mathrm{SPACE}(O(1))$. I am wondering, how is it  possible to decide a language without reading the entire input. I have seen the similar situation in space complexity ( L and NL ,where we define new model of computation).

My model of computation is Turing machine (for e.g. see lecture note on Turing machine)

My question :  Do we need to read the input completely in Turing machine ?

There is no such requirement. A Turing machine which decides a language can do whatever it wants as long as it always halts; the language it decides is the set of words which it accepts.

There are many languages which don't require reading the entire input:

The empty language.
The complete language.
The language of all words starting with 0.
The language of words of length 2.

Here is a more non-trivial example:

Given a language $L$, define the language
$$ X(L) = \{ 0^\ell 1 w x : |w|=\ell \text{ and } w \in L \}. $$
The language $X(L)$ can be decided by a Turing machine which doesn't always read the entire input. Moreover, generally speaking $L$ and $X(L)$ have roughly the same complexity (though $X(L)$ requires the ability to count).


How does conversion from fixed-point to floating-point happen? I came across to the code that convert 32-bit signed fixed-point number (16.16) to a float and it looks like (pseudocode)

floating = fixed / 65536.0

Could you please explain me what's the essence of dividing by this? Why does this dividing works when fixed-point and floating-point numbers have different internal structures?

Your code converts a fixed-point number into its value. It also works for converting a fixed-point number to a rational number, for example.

A fixed-point number of the form $16.16$ consists of 32 binary digits, the first 16 to the left of the decimal dot, the second 16 to its right. When you insert the decimal dot, you are dividing by $2^{16} = 65536$.

Here is a decimal example. Consider a number stored in decimal fixed-point $2.2$. What is the value of the number stored as $1234$? It is $12.34 = 1234/100$.


Prove that $coRP \subseteq RP^{RP}$ I've read in an article that $coRP = RP$ is an open question, but that it is obvious that $coRP \subseteq RP^{RP}$.

If $L \in coRP$, I don't understand how access to the oracle helps to build a probabilistic machine that proves $L \in RP^{RP}$.

Any explanation would be appreciated.

Suppose $L \in \mathsf{coRP}$, so that $\overline{L} \in \mathsf{RP}$. Using an oracle to $\mathsf{RP}$ we can determine whether a given string $x$ is in $\overline{L}$, and so whether $x \in L$. This gives a $\mathsf{P}^{\mathsf{RP}}$ algorithm for $L$.


Finding the $k$th largest element in an evolving query data structure Basically, the problem I am solving is this. Initially, the array $A$ is empty. Then I am given data to fill the array and at any time I have to make a query to print the $|A|/3$-th largest element inserted so far.

I was solving the problem with segment trees, but I am not able to make a little modification to the query function of the segment tree. The query function that I wrote returns the largest element between indices $a_{\text{begin}}$ and $a_{\text{end}}$:

int query(int Nodenumber,int t_begin,int t_end,int a_begin,int a_end)
{
    if (t_begin>=a_begin && t_end<=a_end)
        return Tree[Nodenumber];
    else
    {
        int mid=((t_begin+t_end)/2);
        int res = -1;

        if (mid>=a_begin && t_begin<=a_end)
            res = max(res,query(2*Nodenumber,t_begin,mid,a_begin,a_end));

        if (t_end>=a_begin && mid+1<=a_end)
            res = max(res,query(2*Nodenumber+1,mid+1,t_end,a_begin,a_end));

        return res;
    }
}

Note to make a query, I call the query function as query(1,0,N-1,QA,QB).

But I want to return the $|A|/3$-th largest element between indices $a_{\text{begin}}$ and $a_{\text{end}}$. So how should I modify the function to do this?

So updating, queries, updating, queries, updating, queries and so on are done randomly and several (upto $10^5$) times.

So, for solving the problem, did I pick the right data structure? I thought of using heaps, but that will be too slow, as I would have to pop $|A|/3$ elements from the top and reinsert them for every query.

Have a look at the Wikipedia page for segment trees:

  It is, in principle, a static structure; that is, its content cannot be modified once the structure is built.

So it does not seem to be a good data structure for your scenario at all.

Note that the kind of query you want to perform is called selection (unimaginative, I know). Check the linked article for loads of algorithms. One simple way to solve your problem is this:

Store elements in a sorted list. That means, updates (that is insertions) take linear time.
For the queries, run a selection algorithm on the specified interval.

This approach can be improved by extending the list to a skip list.

Another approach is using binary search trees. If you use a self-balancing variant, that makes updates possible in $O(\log n)$ time. The queries you want can be implemented by storing in every node how many descendants it has, so we can find the $k$-th largest element in $O(\log n)$ time.


Matching elements of two lists to identify the missing ones Given two arrays of integers, A and B, with same size (or two bit vectors A and B with some bits enabled)

What would be the faster way to create a list C containing the elements from B not in A, (or the indexes of the bit vector B not enabled in A)?

The two questions are rather different. If $A$ and $B$ are given as unsorted lists, then one thing you could do is to sort $A$ and $B$ together, putting elements of $A$ before those of $B$ in case of ties, and then do a simple linear scan. This runs in $O(n\log n)$ time, where $n$ is the length of both arrays.

If the arrays are sorted then you can just merge them, in $O(n)$, and continue as before.

If the "arrays" (really sets) are given as bit-vectors, then you can use bitwise operations; details left to you.


Strong Uniform Total Order vs Weak Uniform Total Order The definition for SUTO and WUTO is the following:

Suto

  If some process TODelivers some message m before message mʹ, then a process TODelivers mʹonly after it has TODelivered m.

And for WUTO

  If process p and process q both TODdeliver messages m and mʹ, then p TODelivers m before mʹ if and only if q TODdelivers m before mʹ.

I have a hard time getting my head around this. For me, both of them sounds the same...

Any help?

Consider for example two processes $p_1$ and $p_2$, with $p_1$ that delivers in this order $m$ and then $m'$.
In SUTO, $p_2$ will either deliver $m-m'$ as $p_1$ did, or it won't deliver $m'$ at all.
But why?
Because if $p_2$ will deliver, for example, $m - m'' - m'$, then every process can deliver $m'$ only after $m''$.
This means that once $p_1$ and $p_2$ don't deliver the same messages, the  following  messages delivered by $p_1$ and $p_2$ must be disjoint.
In WUTO instead it's possible to have $p_1$ that delivers $m - m'$ and $p_2$ that delivers $m - m'' - m'$.
This example is taken from Baldoni, Cimmino and Marchetti, A classification of total order specifications and its application to fixed sequencer-based implementations.


How to connect line segments to form the least number of paths I have a list of unordered line segments, some of whose endpoints lie on the same point. How do I connect these segments efficiently to form a minimal amount of paths?

For example, if I have the following lines $(x_1, y_1, x_2, y_2)$: [[0, 0, 2, 2], [4, 0, 2, 1], [2, 2, 4, 0]] the algorithm should be able to join these three segments into one path $(x, y)$: [[0, 0], [4, 0], [2, 1]].

You could solve this using any algorithm for the traveling salesman problem.  Construct a graph with one vertex per line.  Add an edge of cost 0 from line to another if they share an endpoint (these correspond to extending an existing path).  Add an edge of cost 1 between each other pair of lines (these correspond to starting a new path).  Now find the shortest traveling salesman tour of this graph.  That will correspond to a minimal set of paths that cover all of the lines; the number of lines will be equal to the weight of the traveling salesman tour.  There are standard algorithms and solvers for the TSP.


Basic linear programming question Trying to answer this question:

A factory produces chocolate and candy. In order to produce 100 kilograms of chocolate, the factory has to use machine A for 1 hour, machine B for 4 hours, and machine C for 2 hours. In order to produce 100 kilograms of candy, the factory has to use machine A
for 2 hours, machine B for 1 hour, and machine C for 1 hour. The factory will earn 5 pounds for each kilogram of chocolate it produces and 3 pounds for each kilogram of candy it produces. Machine A and machine B belong to the factory and can be run for free 24 hours a
day. However machine C is rented from a different company and can only be run up to 16 hours a day and costs 20 pounds for each hour it is run. Write down an LP model to maximize the factory profit per day. Explain what each of the variables in the LP formulation means.

Initially I had

$max z = 5x_1 + 3x_2$

$x_1 + 2x_2  \leq 24$ // machine A

$4x_1 + x_2  \leq 24$ // machine B

$2x_1 + x_2  \leq 16$ // machine B

$x_1, x_2, x_3 \geq 0$

However, I then realised that machine C costs £20 for every hour it is used, which affects the objective function. Been looking at this for a while and still can't figure out how to formulate this, any ideas? Would be highly appreciated.

edit: Should the objective function have something like $-20x_3$ at the end? Where $x_3$ is the number of hours machine C runs for

Suggestions:

Varaibles:

introducing a dummy varaible $t$.

Objective function:

add term $-20t $ to the function

Constraints:

Replacing the last constraint w.r.t. Machine C with
\begin{align}
t \leq 16 \\
2x_1 + 1x_2 \leq t \\
t\geq 0.
\end{align}
Done !


Prove that $I(A;B|C)=0$ given $I(A;B)=0$ Let $A$, $B$ and $C$ be 3 discrete random variables. If $A$ and $B$ are independent ($I(A;B) = 0$, where $I$ represents the mutual information), how can we prove that $I(A;B|C)=0$? When I draw a Venn diagram this seems trivially true, but I just cannot find a way to prove it.

Your claim is false. Let $A,B,C$ range uniformly over the set
$$
\{(x,y,z) \in \{0,1\}^3 : x \oplus y \oplus z = 0 \}.
$$
On the one hand, $I(A;B) = 0$. On the other hand, $I(A;B|C) = 1$.


Why is a (collision-less) hashtable lookup really O(1)? Disclaimer: I know there are similar sounding questions already here and on Stackoverflow. But they are all about collisions, which is not what I am asking for.

My question is: why is collision-less lookup O(1) in the first place?

Let's assume I have this hashtable:

Hash  Content
-------------
ghdjg Data1
hgdzs Data2
eruit Data3
xcnvb Data4
mkwer Data5
rtzww Data6

Now I'm looking for the key k where the hash function h(k) gives h(k) = mkwer. But how does the lookup "know" that the hash mkwer is at position 5? Why doesn't it have to scroll through all keys in O(n) to find it? The hashes can't be some kind of real hardware addresses because I'd lose the abbility to move the data around. And as far as I know, the hashtable is not sorted on the hashes (even if it was, the search would also take O(log n))?

How does knowing a hash help finding the correct place in the table?

The hash function doesn't return some string such as mkwer. It directly returns the position of the item in the array. If, for example, your hash table has ten entries, the hash function will return an integer in the range 0–9.


Generators of families of langauges? From Wikipedia's definition of regular langauges

  The collection of regular languages over an alphabet $Σ$ is defined
  recursively as follows:

  The empty language $Ø$ is a regular language.
  For each $a ∈ Σ$, the language $\{a\}$ is a regular language.
  If $A$ and $B$ are regular languages, then $A \cup B$ (union), $A • B$ (concatenation), and $A^*$ (Kleene star) are regular languages.
  No other languages over$ Σ$ are regular.

The regular languages also form a (full) AFL.

Parallel to the concept of generator for a sigma algebra, do the regular languages form the minimal  (full) AFL (or (full) semi-AFL, full trio, trio, ...)  that contains the empty language, and  $\{a\}, a ∈ Σ$? In other words, are the minimal  (full) AFL (or (full) semi-AFL, full trio, trio, ...) generated by the empty language, and  $\{a\}, a ∈ Σ$ exactly the regular langauges?

For the sake of notation, let's call a family of languages $\mathcal{L}$ that contains

the empty set $\emptyset$ and
all singleton sets $\{a\}$, $a$ some symbol,

a founded family, and

$\qquad\displaystyle \mathcal{L}_+ = \{ L \in \mathcal{L} \mid \varepsilon \not\in L\}$.

Let $L \in \mathrm{REG}_+$ arbitrary. We will construct $L$ from only the empty and singleton sets using the trio operations

$\varepsilon$-free homomorphism,
inverse homomorphism and
intersection with regular languages,

thus proving that (1) all founded trios also contain $\mathrm{REG}_+$. Furthermore, (2) $\mathrm{REG}_+$ it is a founded trio itself. Therefore, we have shown that $\mathrm{REG}_+$ is the minimal founded trio.

It suffices to show that $\Sigma^+ \supset L$ is contained in every founded trio $\mathcal{T}$; the rest is trivial by $L = \Sigma^+ \cap L \in \mathrm{REG}_+$.

We define for any alphabet $\Sigma$ a marked copy $\hat{\Sigma} = \{ \hat{a} \mid a \in \Sigma \}$ and two homomorphisms $h,g : \Sigma \cup \hat{\Sigma} \to \Sigma^*$ by

$\qquad\displaystyle
  h(a) = \begin{cases}
           a &, a \in \Sigma \\
           \varepsilon &, a \in \hat{\Sigma}
         \end{cases}
$

and

$\qquad\displaystyle
  g(a) = \begin{cases}
           b &, a = b \in \Sigma \\
           b &, a = \hat{b} \in \hat{\Sigma}
         \end{cases}
$.

Now consider

$\qquad\displaystyle L' = \Sigma \hat{\Sigma}^*$.

By noting that

$\Sigma = h(L') \iff h^{-1}(\Sigma) = L'$,
$g(L') = \Sigma^+$ and
$g$ is $\varepsilon$-free,

we obtain from the trio closure properties that

$\qquad\displaystyle \Sigma \in \mathcal{T} \implies \Sigma^+ \in \mathcal{T}$.

But since $\Sigma$ is the pre-image of every $\{a\} \subseteq \Sigma$ with suitable constant homomorphism $h_a(b) = a$ we have $\Sigma \in \mathcal{T}$ by foundedness and closure under inverse homomorphism.
We check the conditions of a founded trio for $\mathrm{REG}_+$:

Closure under $\varepsilon$-free homomorphism: clear since $\mathrm{REG}$ has this property and no such homomorphism can generate $\varepsilon$ from an $\varepsilon$-free language.
Closure under inverse homomorphism: clear since $\mathrm{REG}$ has this property and the image of $\varepsilon$ is always $\varepsilon$.
Closure against intersection with regular languages: clear by def.
Foundedness: clear by def; all required sets are regular and don't contain the empty word..

$\mathrm{REG}$ actually is the minimal "founded" trio if you add $\{\varepsilon\}$ to the base; a similar proof goes through.

Furthermore, $\mathrm{REG}_+$ is not a full trio (cone) because of it's lack of empty words. We extend above proof by noting that containment of $\mathrm{REG}_+$ now implies containment of $\mathrm{REG}$ (any regular language $L$ is the image of $\hat{a}L \in \mathrm{REG}_+$ by a homomorphism that deletes only $\hat{a}$). Since $\mathrm{REG}$ is itself a cone it is also the minimal cone.

The properties extend to (semi-)AFLs, i.e. $\mathrm{REG}_+$ is the minimal (semi-)AFL and $\mathrm{REG}$ is the minimal full (semi-)AFL.


Is there an efficient way to cluster a graph according to Jaccard similarity? Is there an efficient way to cluster nodes in a graph using Jaccard similarity such that each cluster has at least k nodes?

Jaccard similarity between nodes i and j: Let S be the set of neighbours of i and T be the set of neighbours of j. Then, the similarity between i and j is given by  $\frac{|(S \cap T)|}{|(S \cup T)|}$.

Any hierarchical clustering algorithm should meet your needs.  There are many efficient methods for hierarchical clustering; you can use any of them for your application.

With agglomerative (bottom-up) clustering, you simply keep merging clusters until all clusters have at least $k$ nodes.

With top-down clustering, you keep splitting clusters, except that if the algorithm tells you to split some cluster in a way that would leave one of its subclusters with fewer than $k$ nodes, you cancel the split and mark that cluster as finalized.

In general, hierarchical clustering gives you a tree.  You can pick any consistent cut through the tree that leaves all clusters of size $\ge k$.  So, it is easy to adapt any hierarchical clustering algorithm to satisfy your requirement that all clusters have at least $k$ nodes.  Many of the hierarchical clustering methods let you use any pairwise distance function, so you can use them with your Jaccard similarity metric.


Does real linear programming produce bipartite perfect matching using maxflow reduction? Given a bipartite graph the standard reduction to max flow is with the construction similar to following diagram:

We can formulate max flow as an linear programming problem  with integer variables in latter.

If we do not use integer variables does solving for maxflow in linear programming formulation with only real variables still produce valid perfect matching of given graph?

Is there a formal proof of this?

Let us consider $K_{2,2}$, the complete bipartite graph with two vertices on either side. A valid max flow sends $1/2$ units of flow across each edge of the bipartite graph. This gives a negative answer to your first question.

On the other hand, the integral flow theorem guarantees that there exists an integral max flow, and such a max flow can be found algorithmically. An integral max flow does correspond to a maximum matching.


Can any constant-time operation be applied N times in O(log(N)) time? Suppose f is a constant-time function. Is it always possible to apply it n times in O(log(n)) time?

Example

If f is not, then, apply_not_n_times(n,bool) = if n % 2 == 0 then bool else !bool, which is O(log(n)), since it is linear in the number of bits. That means the answer is yes for that particular choice of f. I wonder if it can be proven that, for any choice of f, there is always a O(log(n)) implementation of apply_f_n_times(n,x).

Not necessarily. Let us use the most common (according to some people) model of computation: the single tape Turing machine where the output of an algorithm is simply what is left on the tape. Here is a counterexample by Bergi. The operation $m$ that moves the head one step forward and writes a fixed symbol will absolutely need $n$ steps if we want to repeat $m$ $n$ times.

On the other hand, in some models of computation, any constant-time operation can be applied $N$ times in $\mathcal{O}(\log(N))$ time and in $\mathcal O(1)$ amortized time.

This section is devoted to prove the above partial positive answer.

For the sake of discussion/proof/disproof, let us make OP's question precise.

Let $f$ be a function that maps a set $S$ to $S$ itself. Define function $r(f,n)$ as applying $f$ repeatedly $n$ times. That is, for any $n\in\Bbb N$, $r(f,n): S\to S$ is defined by the following.
  $$ r(f,n) := \begin{cases}
     f               & \text{ if }n = 1,\\
     f\circ r(f,n-1) &\text{ otherwise.}\\
   \end{cases}$$

Claim: Suppose we can compute $f$ in constant time and $f(S)$ contains finitely many values, then we can compute $r(f,n)$ in $\mathcal{O}(\log n)$ time and in $\mathcal O(1) amortized time.

Proof of the claim: (The simple observation is that we are dealing with states whose cardinality is smaller than a constant.)

Without affecting the correctness of this proof, we will assume that $|S|$ is smaller than some constant; Otherwise, we can replace $S$ by $f(S)$ and $f$ by itself restriction to $f(S)$.

Let $SS$ be the set of functions from $S$ to $S$. Since $|S|$ is smaller than some constant, $|SS|$ is also smaller than some constant. So the sequence of functions $r(f,1), r(f,2), \cdots$ will be eventually periodic since each term in the sequence is determined by the previous term in the same way, that is, composition of the previous term with $f$. So, there are constants $c_1, c_2$ such that $r(f,n+c_1) = r(f,n)$ for any $n>c_2$. Now let us just compute and store the two dimensional constant array $a[i,s]$ where $a(i,s)=r(f,i)(s)$ for $1\leq i\le c_2+c_1$ and $s\in S$ in constant time. Given $N>c_2+c_1$, we will find the remainder $n_0$ of $N-c_2$ divided by $c_1$ in $\mathcal{O}(\log(N))$ time. Now we have
$$r(f,n)(s) = a(n_0+c_2,s)$$

Note that the only (possibly) non-constant operation needed for any $N$ is the one-time operation to get the remainder of $N$ divided by a constant. So once we have done some $\Theta(\log N)$ operations, the amortized time will become $\mathcal O(1)$.

We have proved the claim.

In which models of computation?

Now we want to show that there exists some models of computation such that $f$ can only have finitely many values if we can compute function $f$ in constant time or, more precisely, in less than $c$ steps for some constant $c$ independent of the input, $f(S)$ can only have finitely many values.

One such model of computation is, as mentioned by David Richerby, the multi-tape TMs where the output must be written on a designated tape which must not have any part of the input. (I would venture to say this might be the most common model that fits most people's mental image of computation, where we have input at one side of a box and output at the other side of a box. However, whether this model is even common or not is not the focus of this post.) In this mode of computation, since any constant-time operation $f$ can only move the head on that designated tape at most $c$ steps forward and at most $c$ steps backward for some constant $c$, it can produce at most $|\Sigma|^{|2c+1|}$ states, where $\Sigma$ is the set of symbols used on that designated tape. That is, $f$ can only have finitely many values.

Because of the multitude of the models of computation, we will not and cannot list all those complying models of computation. Anyway, thanks to the claim we just proved, in those models of computations, we will have the partial positive answer stated in the second paragraph of this post.

Although we have shown that in some models of computations, we can apply a given constant-time operation $N$ times in $\mathcal O(\log(N))$ time, the constant term hidden in the $\mathcal O$ notation might be impractically large. For example, for some endomorphism $f$ of a set of 1000 elements, the smallest $c_1=1516385558956728808659224171023365600$ (which is $g(1000)$ for Laudau's function g). For a cryptographic hash operation which can have about $2^{256}$ state, the smallest $c_1$ might have more than trillions of digits. Although that constant term can be reduced significantly, it remains impractically large. In that sense, that partial positive answer may not be what OP might have been hoping for at all. It does not lessen our confidence in those cryptographic hash operations in anyway.


Proving specific prefixes of regular languages are regular There are particular problems in Kozen that I'm unable to solve, and they seem to be similar to each other. It is showing that sets:

$$ \{x \mid \exists y: |y| = 2^{|x|} \text{ and } xy \in A \}$$
$$ \{x \mid \exists y: |y| = |x|^2 \text{ and } xy \in A \}  $$

are regular for a regular set $A$.
The only method I'm familiar with that is similar is proving that first-halfs or first-thirds or any other linear parts of a regular language are regular (using a 2-NFA). I've tried looking online, but I only found that it's hard to construct NFAs for that. Is there some other way of proving existence?
I also don't understand how we can even compute $|x|^2$ or $2^{|x|}$ for different strings in the language to use that value.

Basically, you do not compute these lengths $2^n$ or $n^2$, but only the from-to computations that the automaton would be able to make on input with this particular lengths.

For the first two problems the automaton computes (in its internal states) the relation $E_\ell = \{ (p,q)\in Q\times Q \mid q\in\delta^*(p,y) \text{ for some $y$ with $|y|=\ell$} \}$ for some value of $\ell$ (which depends on $|x|$).

Then $E_{2\ell}=E^2_\ell$ which helps to solve the first problem. Here $E^2$ is the composition $E\circ E$ of the binary relation $E$ with itself: $E^2 = \{ (p,r) \mid \text{ for some } q\in Q \text{ both } (p,q)\in E \text{ and } (q,r)\in E\}$

I add some details. This is still rather formal, without much intuition. I hope it helps you into the right direction.

Assume we are given a FSA $\mathcal  A= (Q,\Sigma,\delta,q_0,F) $ for language $A$. We will construct an automaton for your first problem.

The new states are of the form $(p,E)$ where $p\in Q$ and $E\subseteq Q\times Q$; i.e., the new state set equals $Q\times{\mathcal P}(Q\times Q)$.
Note that the number of possible relations $E$ is finite, hence adding such a relation to the states of the automaton will still lead to a finite state automaton.
The second component will always contain the relation $E_{2^n}$ where $n$ is the length of the input read.

The initial state equals $(q_0,E_1)$, where $E_1$ is the one-step relation on $Q$, just like defined above.

Now from every $(p,E)$ reading letter $a$ we move to state $(\delta(p,a),E^2)$. Thus, the first component copies the original move in $\mathcal A$, the second component steps from $E_{2^n}$ to $E_{2^n}\circ E_{2^n}=E_{2^{n+1}}$ following the recipe above.

When is a state $(p,E)$ final? When there is a pair $(p,q)\in E$ such that $q\in F$ is final in $\mathcal A$.

The $n^2$ problem is along similar lines, but actually slightly more involved (I think). It uses the fact that $(n+1)^2 = n^2 + 2n +1$. The automaton stores both $E_{n^2}$ and $E_{n}$ to easily update the square.


Looking for non-entry level implementation of foundational algorithms and data structures in python. where to look? I'm an autodidact who works best with a mix of theory and implementation examples. I'm having a hard time finding resources on implementing algorithms and data structures in Python (2.7-3.X  preferably). I found a text ...mastering basic algorithms in the python language but I find it to be far too introductory and thus cluttered with unnecessary prose, which makes it for me difficult to move efficiently over it. What I have in mind is a text or github gist or whatever really, that has some coded python imps of what I've determined to be foundational data-structures in algorithmic's(not to sure on the usage/conjugation of that). Specifically I'm looking for trees, traversal, dynamic and greedy algorithms and the like. If this question is a repeat, or adequately answered elsewhere, links are adequate replies.

David Eppstein has a bunch of algorithms implemented in Python in his PADS repository.


What is a "sentential form"? I do know what a "left-most-" and a "right-most derivation" is, but I stumble across the term "sentential form" and its specific differences "right-sentential form" as well as "left-sentential form" and I just don't understand what is meant with this term.

Is the concept "sentential form" so different from the concept "derivation" that it is necessary to "have" it" ?

Can some of you please explain?

Yours sincerely

Assuming you know what leftmost and rightmost derivations are, let $S \Rightarrow^*W_1W_2\dots W_m$ be a derivation (a sequence of replacement using derivation rules), where $W_i$ is a terminal or nonterminal symbol. Then the string $W_1W_2\dots W_m$ is a sentential form of a grammar $G$. In addition, if $W_1W_2\dots W_m$ contains only terminal symbols then it is called a sentence.

If the derivation $S \Rightarrow^*W_1W_2\dots W_m$ is leftmost (rightmost) then the sentential form $W_1W_2\dots W_m$ is called left-sentential form (right-sentential form).

  Is the concept "sentential form" so different from the concept "derivation"

Yes, these are different concepts. A derivation is a sequence of replacements of nonterminals using derivation rules given as a part of grammar, while a sentential form is a string over terminals and nonterminals. You generate/derive/obtain sentential form using derivation (process).

Example:

$S \rightarrow aSa \mid bSb \mid \epsilon$

Derivation: $S\Rightarrow aSa \Rightarrow abSba \Rightarrow abbSbba \Rightarrow abbbba$

Sentential form: $abbSbba$.
Sentence: $abbbba$ (since it has no nonterminal)


Can a non-regular language $L$ have a non regular $L^*$? I have been looking around and i cant seem to find an example of such case that a non-regular $L$ has a non regular $L^*$. Is it possible? If so, can you provide an example of such case please?

Take the Dyck language $D$. It is context-free but not regular and satisfies $D^* = D$.


Representing abstract syntax tree as a graph Does it make sense to represent an AST as a graph? How can one achieve a mapping between ASTs and graphs that preserves both semantic and syntactic properties of source code?
The goal and application of such a transformation would be to use graph neural networks and other deep "graph" learning techniques to extracts features, clustering source code, find code similarities and suggest code completion tasks.
Any suggestion of current algorithms and research in this area?

Every tree is itself a graph, so of course an AST is a graph -- no mapping is needed, it is already a graph.  I don't see any way that this is useful in practice, though.
Rather than trying to convert to a graph and then use graph neural networks, I suggest using a more direct approach: e.g., using a neural network on the AST or on the code itself.  Since you haven't told us what you want to do with the neural network, it's impossible to suggest something more concrete, but I encourage you to do a literature search; there are many recent papers on using neural networks on code.

Alternatively, if you insist on having a graph somewhere, perhaps you will be interested in learning about control-flow graphs, which are one use of graphs in program analysis where the graph structure is useful.


Resource Reservation: No Greedy Approach? I'm considering the general resource reservation problem: n processes, m resources. Each process requests a set of resources and each resource can be used by exactly one process. Processes are only active if they have all requested resources.

Instance: A set of processes P, a set of resources R, the set of resource requests for each process, and an int k.
Question: Is it possible to allocate resources so that at least k processes are active at the same time?

My initial inclination was that a greedy approach makes sense here. Sort the jobs in increasing order of number of resources requested, then allocate resources to processes until all resources are allocated or all processes have been attempted to be scheduled, as below:

procedure reserve_resources(P, R, k):
  int jobs_active = 0;
  Order processes in ascending order of number of resources requested;
  for each process:
    if (all of the processes' requested resources are available):
      allocate resources to that process;
      jobs_active++;
    end if;
  end for;

  if (jobs_active >= k):
    return "YES";
  else:
    return "NO";
  end if;
end procedure;

I've come across an answer for this problem which shows NP-completeness by reducing Independent Set to this resource reservation problem. For the IS instance G = (V, E), it makes the set of resources equal to E, the set of process equal to V, and any edge incident to an vertex is a resource requested by that process. If k processes have disjoint resource requests, then the vertices corresponding to those processes form an independent set.

This reduction makes sense to me and I know that IS is NP. I believe that P != NP, and I certainly don't think I've just proven the opposite while working on homework in my undergrad algorithms class. But I also can't find a counterexample to the algorithm I've presented. My question is, where does this algorithm fail?

Your algorithm is correct when all resources are interchangeable. For example, the resources are 100 memory units.

However, it may not return the right result when the resources are not of the same kind. One way to find a counterexample is to search for counterexample of the greedy algorithm on the maximum independent set is to, uh, search online. One counterexample I found is the following, where vertex $C$ is selected first.

.

User j_random_walker proposed the following strategy to figure out a counterexample, where the tip in the last statement is added by me.

  Figure out how to force your algorithm make the "wrong" choice in the first step: Since your algorithm always chooses the process with the fewest resource requests first, that means you have to design the problem instance so that this choice can only lead to suboptimal solutions. Work backwards to discover constraints: Clearly if the optimal solution has all 2 processes, then they can't have any conflicts, so any order of choosing them will give the same answer. So the smallest counterexample must have at least 3 processes. We will not consider processes that only request one resource; it cannot be wrong to included those processes.

Here is the smallest counterexample on which the greedy algorithm might fail, which has 3 processes and 4 resources. Process $P$ requests resources $a$ and $b$. Process $Q$ request $a$ and $c$. Process $R$ request $b$ and $d$. When the greedy algorithm select $P$ first, it cannot select any more process.

Exercise. Find a counterexample on which the greedy algorithm will always fail.