Using B trees to search inside dynamically changing array segments Let $A$ be a sorted array. Suppose that this array is huge and can only be stored in a disk. In the I/O model and algorithms built in this model, every time we access the disk we spend an I/O and we get $B$ elements to the RAM. Since accessing the disk is much more expensive than accessing the main memory, we assume that what ever operations we perform in main memory, they come for free. So even if you scan 1 million times the entire RAM, in the I/O model, this would cost $O(1)$ I/Os, and that's the only thing we care about.

Suppose that you now receive queries in the form $[l,r, key]$ where $l$ and $r$ are indices which define a continguous chunk of the array $A$, and $key$ is a value that you want to search inside this chunk. So you want to know whether the key is somewhere in that chunk or not.

If you expect many queries to come, and we will make this assumption as well, it might be worth spending $O(\frac{N}{B})$ I/Os to build a B tree on top of the array $A$, and use the $B$ tree for your searches. Since the height of a B tree is $O(\log_{B}(N))$ each search will require $O(\log_{B}(N))$ I/Os.

However I was wondering, if the size of the chunk defined by the query is $n$, is it possible to use the same B tree to achieve $O(\log_{B}(n))$ I/Os? Because if we always start searching from the root of the B tree, we would first have to find where our chunk is, and then search inside the chunk, which is why the total number of I/Os would be $O(\log_{B}(N))$.

My idea would be to spend 1 I/O to access the leaf block in the B tree containing element $A[l]$, 1 I/O to access the leaf block in the B tree containing element $A[r]$, and then spend $O(\log_{B}(n))$ I/Os to find the least common ancestor block in the B tree of these two leaf blocks.  Then since we found the least common ancestor block in the B tree, we can start searching from there, spending in total $2 + O(\log_{B}(n)) + \log_{B}(n)$ I/Os.

Unfortunately I am very novice in the I/O model and this approach sounds too good to be correct. Is it really that easy for this problem or am I missing something?

I assume the "B-tree" in your post is in fact a "B+-tree" and array $\small A$ is stored in an increasing manner. Your idea is almost good and needs some small revision.

You need to test whether $\small A[l] \leq key$ and $\small A[r] \geq key$. If $\small A[l] = key$ or $\small A[r] = key$, it is done.
If it is found that $\small A[l] < key$ and $\small A[r] > key$, find the LCA of the blocks containing $\small A[l]$ and $\small A[r]$, as you have done. The height of the LCA is of $\small \mathcal{O}(\log_B(n))$.
If $\small A[l] > key$ or $\small A[r] < key$, then obviously $\small key$ does not exist in $\small [l, r]$.

Why testing $\small A[l] \leq key$ and $\small A[r] \geq key$ is important?

The LCA block may contain entries that direct to blocks outside $\small [l, r]$. If you start from the LCA, you may find a $\small key$ even if $\small key$ does not exist in $\small [l, r]$.


How to use Master Theorem with strange format of $b$ parameter? I have a funcion $T: \mathbb{N}\to\mathbb{N}$ defined as:

$$T(n)=\begin{cases}
6 &\text{ if } n=0,\\
T(n-1) + 6n + 6 &\text{otherwise.}
\end{cases}$$

How can I apply the Master Theorem to this problem? I have only seen the M.T. in one of these two formats:

$$T(n) = aT(n/b) + f (n)$$
$$T(n) = aT(n/b) + \Theta(n^c)$$

So I'm wondering how to transform the $T(n-1)$ to something usable. Is it even possible to apply the theorem to this kind of problem?

Not every recurrence falls within the bounds on the master theorem. Your recurrence is an example. However, by unrolling your recurrence, we can come up with an explicit formula:
$$
T(n) = 6(n+1) + T(n-1) = 6(n+1) + 6n + T(n-2) = \cdots = \\
6(n+1) + 6n + \cdots + 6\cdot 2 + T(0) = \\
6(n+1) + 6n + \cdots + 6\cdot 2 + 6\cdot 1 = \\
6 \sum_{m=1}^{n+1} m = 6\frac{(n+2)(n+1)}{2} = 3(n+2)(n+1).
$$


Partitions of star-free languages and questions on the proof of the Splitting Lemma by Diekert/Gastin I'm currently reading a paper on First-order definable languages by Volker Diekert and Paul Gastin.
Im having trouble understanding a part of the proof for lemma 3.2 (splitting lemma).
The part I'm having a problem with, is about the complement:
(Note: I've substituted $B^\infty = B^* \cup B^\omega$ with $B^*$ which shouldn't cause problems)
From the paper:
It remains to deal with the complement $\Sigma^* \setminus L$ of a star-free set. By induction, we have $L \cap B^* A B^* = \bigcup_{1 \leq i \leq n} K_iAL_i$.
If some $K_i$ and $K_j$ are not disjoint then we can rewrite $$K_iAL_i \cup K_jAL_j = (K_i \setminus K_j)AL_i \cup (K_j \setminus K_i)AL_j \cup (K_i \cap K_j)A(L_i\cup L_j)$$
We can also add $(B^* \setminus \bigcup_{i} K_i)A \emptyset$ in case $\bigcup_{i}K_i$ is strictly contained in $B^*$. Therefore, we may assume that $\{K_i \mid 1 \leq i \leq n\}$ forms a partition of $B^*$. This yields: $$(\Sigma^* \setminus L) \cap B^*AB^* = \bigcup_{1\leq 1 \leq n} K_iA(B^* \setminus L_i)$$
Questions:

In the last part of the proof $\bigcup_{1\leq 1 \leq n} K_iA(B^* \setminus L_i)$, why is it enough to only build the complement for $L_i$ with $B^* \setminus L_i$? Why don't we need $B^* \setminus K_i$?
Why does $\{K_i \mid 1 \leq i \leq n\}$ form a partition of $B^*$?

For the set $\{K_i \mid 1 \leq i \leq n\}$ to form a partition of $B^*$, it is necessary, that all $K_i$ are pairwise disjoint and every element in $B^*$ is cointained in some $K_i$. You already showed that they are disjoint, as is is possible to split two overlapping $K_i$ into three disjoint ones by using the parts that don't overlap and the intersection instead. The second condition, that everything is contained, is achieved by adding $(B^* \setminus \bigcup_i K_i)$ to the set $\{K_i \mid 1 \leq i \leq n\}$ so $n$ is incresed by one and still is finite. And this $(B^* \setminus \bigcup_i K_i)$ contains everything that was not previously contained.

As $\{K_i \mid 1 \leq i \leq n\}$ forms a partition, everything in $B^*$ is contained in some $K_i$ and is, therefore, also contained in the complement of another one, which means, it doesn't change anything to use the complement of the $K_i$s.


How to solve recursion T(n) = T(n/3) + T(2n/3) + n? $T(n) = T(n/3) + T(2n/3) + n$
How can I solve this recurrence formula?

Look at the recursion from QuickSort for the average case:
$T(n) = T(n/2) + T(n/2) + n$
which ends up in $O (n \log n)$.
Note that $n/2 + n/2$ sums up exactly to $n$. Just like $n/3 + 2n/3$ sums up exactly to $n$. Substitute the formula for $T(n)$ in $T(n/3)$ and $T(2n/3)$ and you'll see it's the sum of $T(x)$ for four values $x$ which add up to $n$, plus $2n$. Substitute again, and you see it's the sum of $T(x)$ for eight smaller values $x$ which add up to $n$, plus $3n$. And so on. Since the $x$ shrink by at least a factor $2/3$, the number of rounds until you end up at $T(1)$ is $O(\log n)$.
So that's what you guess, and once you guessed it you can prove it: $T(n) = O (n\log n)$.


Convert ambiguous grammar to unambiguous and SLR(1) I have the following ambiguous operator grammar:

E->E+E*E | E-E*E
E->E+E | E-E | E+E | E*E | E/E
E->(E) | x

I must convert it to an unambiguous one which is also SLR(1).
The following rules regarding precedence and associativity must hold:

Operators * and / have the highest precedence (and precedence between them must be equal)
Operators - and + have the same precedence (lower than * and /)
All operators are left associative.
Reducing with the first 2 rules is preferred if it does not break the precedence and associativity rules.

My problem is the first line of the grammar (E+E*E , E-E*E). I can't find i way to convert it and the new grammar will be SLR(1).

Edit:
The closest i came is this grammar, but it has 2 SLR conflicts:

E->E+F | E-F | T
T->T+F | T-F | F
F-> F*C | F/C | C
C-> (E) | x

Let's start where you probably started, with the classic expression grammar:

$$\begin{align}E&\to T\mid E + T\mid E - T\\
T&\to F\mid T * F\mid T / F\\
F&\to ( E )\mid x\\
\end{align}$$

and then we add the "fused" productions:

$$\begin{align}E&\to E + T * F\mid E - T * F\\
\end{align}$$

That grammar has a conflict because of the ambiguity:

$$\begin{align}E&\to E+T*F\\E&\to E+T \to E+T*F\end{align}$$
(and similarly for the $-$ operator).

So how to get rid of the ambiguity? Clearly, we don't want $E\to E+T$ to match $E+T*F$. So we need to define $$T' = T \setminus T * F$$ in order to be able to restrict the $E$ production to $E\to E + T'$.

Since the set difference operator is not valid in a CFG, we need to write the definition out the long way:

$$\begin{align}E\to&\;T\mid E + T'\mid E - T'\;\mid\\
&\;E + T * F\mid E - T * F\\
T'\to&\;F\mid T / F\\
T\to&\;T'\mid T * F\\
F\to&\;( E )\mid x\\
\end{align}$$


Show that a language with union is not regular by using pumping lemma Given the language $L:= { \{ c^{2k} w \ \vert \ k \ge 1, \ w \in \{a,b,c\}^* \ and \  \vert w\vert_a \ = \ \vert w\vert_b \} \  \cup \ \{ a,b \}^* }$
I'm really unsure how to even start because of the union.
I tried it with $w=a^nb^n$ but my correction said that it's
pumpable because it is in $\{ a,b \}^*$ which makes sense.
What would be a good word to start with?
I guess there are several cases i need to show?

If $L$ was regular, so would be $L \cap c^+\Sigma^* = \{c^{2k}w\mid k\geq 1, w\in\{a,b,c\}^* \text{ and }|w|_a = |w|_b\}$.
That means that if you prove that this language is not regular, then $L$ cannot be regular too (that way, we got rid of the union).
Now you can take it from here with pumping lemma, starting from $c^2a^nb^n$!


Reader and Writer mutex I am looking over the classic  Reader and Writer Problem
Just to give a quick overview:

Many readers can be in CS (as long as no writers are)
Only one writer can be in the CS (with no combination of other readers/writers)

So the solution is:

binary semaphore wrt, mutex = 1;
int No_of_Readers = 0;

Writer Process
wait(wrt);
write
signal(wrt);

Reader Process
wait(mutex);
No_of_Readers ++;
if (No_of_Readers == 1)
   wait(wrt);
signal(mutex);

Read
wait(mutex);
No_of_Readers --;
if (No_of_Readers == 0)
   signal(wrt);
signal(mutex);

My question is simple but I just don't understand it, what is the use of the binary semaphore mutex? why do we have to wait(mutex) when we enter Reader Process and then also wait(mutex) after we Read ?
If someone can give a clear explanation that would help me completely understand this algorithm I am just getting tripped up on that little part.

Lets begin with defining some terms.

  Semaphore is one form of software implementation for process synchronization. It's an int value that is used by processes for the purpose of signalling. Only three atomic operations: initialize, increment and decrement, can be performed.
  A binary semaphore is restricted type of semaphore which only takes three values, 0 and 1.

  wait(): Process executing wait() is blocked if the value is zero. If the value is one then, the process is allowed in critical section and value is decremented to 0.
  signal(): This checks if any process(es) are blocked (semaphore value equals 0). If yes, then a process is unblocked. If no, then value of semaphore is set to one.

Writer's Code
Writer process code is simple. wait() is used to enforce mutual exclusion. When wait(wrt) is executed wrt is decremented to 0 from 1. So, as long as there is on writer in the critical section, no other writer or reader process has access to the section. After performing it's task, signal() is implemented to allow other blocked process (if any) to execute over the critical section. signal(wrt) increments the value of wrt from 0 to 1.

Reader's Code
'mutex' variable is used for synchronization among different reader processes. No_of_Readers is a shared variable among reader processes. So, if more than one process is updating this variable then it's very likely that we will end up with wrong value. Thus, the first wait(mutex) and signal(mutex) is used to create a block, which only allows one reader to update (increment) the value of Number_of_Readers. When wait(mutex) is called the mutex is decremented to 0 (from 1). This makes sure that no other reader process will try to update the value of Number_of_Readers. After updating the value of Number_of_Readers siganl(mutex) is called. This increments the value of mutex releasing the section to be used by other readers.

  if(Number_of_Readers == 1)

implies that the current reader process is the first reader process to access the main critical section. Thus it is his duty to make sure that the coming writer processes are blocked. Thus wait(wrt) is enforced. Subsequent readers coming don't need to do that, as the first reader has already signalled writers to be blocked.
In the second block of the code, Read operation is being performed by the process(es). After a process has performed it's reading task it will exit the code section. The third block of the code is exit portion. Here also wait(mutex) is implemented as we only want one reader process to update the value of Number_of_Readers. A reader process implementing this will decrement the value of mutex to 0 (from 1), signalling other reader processes not to update the value of the variable. After value is decremented, process checks for

  if(Number_of_Readers == 0)

If this condition is satisfied, then it implies that the current reader process is the last one to exit. Thus, it is the responsibility of this process to signal(wrt). This will increment the value of 'wrt' to 1 allowing writer program to enter is required. Value not satisfying implies that there are still reader process(es) in the critical section and thus signal(wrt) is not executed. After Number_of_Readers is updated singal(mutex), increments the value of mutex (to 1), is called allowing other reader processes to access this value for updating.
Thus wait(wrt) and signal(wrt) are used to synchronize between 'Reader and Writer' processes. While wait(mutex) and singal(mutex) are used for synchronization among different 'Reader' processes. This makes sure that the value of Number_of_Readers value is not updated by many reader processes at the same time.


Does left factoring CFG make it unambiguous? I came across following problem:

  If the CFG is left factored then it must be Unambiguous and Not left Recursive.
  TRUE/FALSE?

I have many thoughts about this. But I feel they are somewhat contradicting and hence form a bigger doubt. May be I lack some understanding.

Thought 1

Ambiguity has nothing to do with determinism (even if grammar does not have productions with same prefix of their right side, they still can have a string with two parse trees). So CFG is still ambiguous after left refactoring. Hence, the sentence should be false.

Thought 2

Left factoring is used to eliminate common prefixes of right hand side of productions in the grammar. Doesnt that make grammar deterministic? Deterministic grammar derive deterministic context free languages. So isnt turning grammar deterministic makes it unambiguous? If yes, given statement should be true.

Thought 3

I have completely ignored left recursion in thought 1 and 2. Is it ok?

Doubt: I feel thought 1 and  thought 2 are contradicting. And I am not able to figure it out which one is correct. Which of the above thoughts are incorrect and why? Am I missing any more subtleties?

The answer is no. Some context-free languages are inherently ambiguous: every context-free grammar defining a language of this kind will be ambiguous. An example is

$$\{a^ib^jc^k \mid i = j \text{ or } j = k\}$$


Will this algorithm terminate on any input? One can compress data with straight-line grammars. An algorithm that employs this technique is called Sequitur. If I understood correctly, Sequitur basically starts with one rule representing the input and then does these three steps till the grammar does not change anymore:

For each rule, try to find any sequences of symbols in any other rule that match the rule's right hand side and replace these sequences by the rules left hand side.
For each pair of adjacent symbols in any right hand side, find all non-overlapping other pairs of adjacent symbols that are equal to the original pair. If there are any other pairs, add a new nonterminal, replace all occurrences of these pairs by the new nonterminal and add a new rule that defines the nonterminal.
For each nonterminal that appears exactly once on all right-hand sides of all rules, replace its occurrence by its definition, remove the nonterminal and the rule that defines it.

For each (non-empty) input, can one guarantee that the above algorithm terminates?

This is my idea for a proof although I am not quite sure whether it works:

Consider $r$, the number of symbols on all right-hand sides and $n$, the number of distinct nonterminals. Each grammar has a specific tuple $(r-n,n)$. Let's define an order on grammars. We first sort by $r-n$ and in case the values are equal by $n$.

Whenever step one fires, $r$ decreases as each rule has at least two symbols on its right hand side. Whenever step two fires, $n$ increases by one and $r$ stays the same (in case only two pairs are found) or decreases (if two or more pairs are found). If the third step fires, $r$ decreases by one and $n$ also decreases by one as one nonterminal is replaced by the whole right hand side of its definition which is removed. Let $G'$ be the tuple of the grammar (whose tuple is $G$) after the application of any of those steps, then:

step 1 always reduces $r-n$ by at least one, $G' < G$
step 2 always reduces $r-n$ by at least one, $G' < G$
step 3 does not change $r-n$ but reduces $n$ by one, $G' < G$

The application of each step reduces the tuple of $G$ to a lower tuple. What is left is to show, that both $r-n$ and $n$ have a lower bound. Per definition $n\ge1$. Since each nonterminal is defined in terms of exactly one rule, $n$ is also the number of rules. Since each rule has at least two symbols on it's right-hand side, $r\ge2n\to r>n\to r-n>0$. The tuples  have a lower bound that is eventually reached. Thus the algorithm must eventually terminate.


Is regex with backreference still able to be implemented by finite automata? I recently learned that regex support backreference which enables referring to a matched group in the pattern itself. E.g. a regex (.)\1{2,} matches two or more consecutive appearances of the same character like 'aa', '...', '------', etc. However, such feature seems exceeds the capability of finite state machine which is the underlying implementation of regex. It seem like it needs to remember the matched part and match with it again, but the matched part its self have infinite possible values. I'm just speculating but have no idea to prove or disprove it. My doubt is, does the regex with backreference still have finite number of states?

No, it doesn't. With backreferences, it is trivial to write a regex that matches exactly the standard textbook example of a non-regular language, $\{ a^nb^n \mid n \in \mathbb{N} \}$. A finite number of states can only distinguish between finitely many different prefixes in $a^*$, so it won't do.


Path NFA-eplison to DFA conversion Does a path (as in path graph or linear graph) NFA-epsilon have a simpler or more efficient algorithm other than the subset construction to convert to a DFA?  The only simplifications I have come up with relate to the NFA-epsilon representation, the computation of the epsilon closure, and the DFA representation.  Each NFA node can be represented as a set of symbols transitioned on, if it has an epsilon transition, and a unique reference to the following node.  The DFA representation can use shared references as it is acyclic.

Unless I misunderstood your question, in a NFA $N$ that is a path one vertex has in-degree $0$ and outdegree $1$, one vertex (possibly the same) has in-degree $1$ and out-degree $0$, and all the other vertices have in-degree $1$ and out-degree $1$.

Let $N'$ be the NFA obtained by identifying all the vertices in the same component of the (undirected version of the) subgraph induced by all the edges labelled $\varepsilon$ in $N$. All vertices of $N'$ have maximum out-degree $1$, moreover $N'$ contains no edge labelled $\epsilon$. This shows that $N'$ is a DFA. The process can be performed in linear time.

A note: when a set $S$ of vertices from $N$ is identified into a single vertex $v$ in $N'$, you will need to mark $v$ as a final state in $N'$ iff at least one the vertices in $S$ is a final state in $N$.


Is this a CFL: $L_1 = \{wxyx | w, x, y \in (0 + 1)^+\}$? I recently found a question asking whether the language given below is context-free or not:

$L_1 = \{wxyx | w, x, y \in (0 + 1)^+\}$

My intuition is that I can design a non-deterministic push-down automaton for the language. I would appreciate if you could correct me if I am wrong, or brief me on how I could prove that it is indeed context-free.

It’s a trick question. There must be four letters or more. Let the last letter be a, where a is 0 or 1. If any other letter other than the first or second to last is a, then the string is in L. (Pick x = a, w = everything before the first a, y = everything between first and last a). If you can’t find a in these places, the string cannot be in the language because you can’t match the last x with another one.

So you don’t have to check for two equal strings of identical length at all, the language is much simpler. And it is regular.


Multicommodity circulation formulation On the circulation problem page on wikipedia, the multicommodity circulation problem formulation seems to be insufficient, since we can just set all but one flow to $0$, and reduce it to a circulation problem.

I can't find any concrete description of multicommodity circulation problem to verify the correctness. There is only one paper I can find and it's behind a pay wall.

Here is a formulation I thought to make more sense:

Let $G=(V,E)$. $l_i,u,c_i:E\to \mathbb{R}$ for $1 \leq i\leq n$. We want to find a sequence of flow function $f_i$, such that:

$$
\begin{align}
\text{min} & \sum_{(v,w) \in E} c_i(v,w)f_i(v,w) \\
\text{s.t.} & \sum_{(v,w) \in E} f_i(v,w) = 0 \text{ for } 1 \le i \le n, v \in V, \\
& l_i(v,w) \leq f_i(v,w) \text{ for } 1 \le i \le n, (v,w)\in E\\
& \sum_{i=1}^n f_i(v,w) \leq u(v,w) \text{ for } (v,w)\in E\\
\end{align}
$$

Is this a formulation of multicommodity circulation problem?

I think the reference for many optimization and structural problem is Schrijver's book:

Combinatorial Optimization - Polyhedra and Efficiency

In the case, you do not have access to the book you can find his lecture notes on disjoint paths, but it's not complete, and is not comparable to the book.

Circulation is just a general definition and it's not important alone, it's important with given underling context, e.g here difference between the muticommodity circulation is just we have multiple circulation (no matter if all of them are 0), but if we want to use it for the muticommodity integer flow problem we cannot reduce it to the normal flow unless $P=NP$.

As a side note: In the Schrijver's book circulation does not include lower bound or upper bound, just flow's conservation rule holds.

This is the definition of circulation in that book:

Circulation:

  Let $D = (V,A)$ be a digraph. A function $f : A \rightarrow R$ is
  called a circulation if
       $f(\delta^{in}(v)) = f(\delta^{out}(v))$
  for each vertex $v \in V$ . So now the flow conservation law holds in
  each vertex $v$. (in page 171)

And:

  $δ^{in}(v)$ := set of arcs entering $v$, $δ^{out}(v)$ := set of arcs
  leaving $v$. (in page 29)

The corresponding problem is defined as follow:

Circulation Problem:

  Input: Let $D = (V,A)$ be a digraph and let $d, c : A → Q$ with $d ≤ c$.
  Question: Is there a circulation $f$ satisfying $d ≤ f ≤ c$. (page 175, with a little variation).

But the minimum-cost circulation problem is as follow:

Minimum-Cost Circulation Problem:

  Input: A digraph $D = (V,A)$, a demand function $d : A → Q$, a capacity function $c : A → Q$, and a cost function $k : A → Q$.
  Question: Find a circulation f subject to $d ≤ f ≤ c$, minimizing $\text{cost}(f)$. (Page 177).

Finally I should mention that, I didn't see the multicommodity circulation definition (or corresponding problem) explicitly, and in my opinion, as I mentioned at start is not important alone. But I do agree with the owner of problem, that wikipedia's definition is not good, and the definition provided in this question is better and more precise than the wiki's.


What algorithm could I use to find the largest set of disjoint members from a set of subsets of a set? I've written a political quiz based on data from the public whip.  They group politicians' votes by policy; each vote can belong to many policies.  There are too many policies for me to ask a question for each one, and anyway some are duplicates and some policies' votes are subsets of other policies.  In the past, I've manually chosen a subset of policies to use in my quiz try to maximise the number of votes included without double-counting any, but I'm worried that that may introduce my biases into what is supposed to be as neutral as possible a quiz.  So I'd like to find the set of policies which maximises the number of votes included without counting any of them twice.

Is there a known algorithm I could use to do this?  I've seen similar questions elsewhere on this site but they generally seem to involve sets of intervals or geometric shapes.

The problem you describe is known as set packing, and it has a natural ILP formulation. You can start with some ILP solver you have access to, and it should be a highly competitive solution. There are many heuristics to choose from as well if you don't require optimal solutions.


Alternatives to evolutionary computing for structure, design and policy optimization (optimal structure search)? I once had this question https://math.stackexchange.com/questions/1083338/structural-design-meta-optimization-is-there-mathematical-theory-optimiza about the methods for finding optimal structures, designs and policies (as another kind of structures - set of rules), i.e. optimization of the structure of the models not just the parameters for some pre-selected structure. So far I am sure that the genes of evolutionary computation (EC) can effectively encode structure and evolutionary computing can perform effective search for more optimal structures. EC algorithms are quite sophisticated - there is evolutionary programming (for search of strings in some grammar) and there is cultural algorithms (which incorporates already known certain knowledge for speedup of the search). But are there some other kind of search procedures (besides evolutionary computing) for searching more efficient structures. EC is stochastic search methods and is there deterministic search methods for the search of optimal structure? I expect only key-words, pointers and trends.

Or - more clearly - is EC the most general search framework? Are there search alogrithms or approaches than can not be reduced to the string of application of crossover, mutation and other operators of EC?

At a broad level, there are two types of optimization: continuous optimization, and discrete optimization.  They tend to use different techniques.

Continuous optimization deals with problems where the parameters are continuous; methods include gradient descent, Newton's method, and other iterative methods, linear programming, and more.

Discrete optimization, or combinatorial optimization, deals with problems where the parameters come from a finite site; methods include integer linear programming, SAT, simulated annealing, particle swarm optimization, and more.

Genetic algorithms are another technique.  However, my experience is that they are rarely the best one; other methods often beat genetic programming and evolutionary optimization methods.  Your experience may vary.


Relationship between graph expansion and conductance I'm quite confused about the exact relationship between the expansion of a graph and its conductance. My first question is:

Could someone point me to a reference that discusses both of these notions? (I've found various lecture notes on related topics but these seem to focus either on expansion or on conductance...)

I've read that the expansion of $G$ is a measure for the speed of mixing of a random walk on $G$, i.e., the time for getting close to the stationary distribution. For a $d$-regular graph with constant expansion, for example, the mixing time is $\Theta(\log n)$. The same seems to be true for the conductance $\Phi(G)$, i.e., if $\Phi(G)$ is constant, then a random walk on $G$ will also mix in $\Theta(\log n)$ time. Moreover, this property of conductance holds even in non-regular graphs, and, for $d$-regular graphs the expansion of $G$ can be found by simply dividing the conductance of $G$ by $d$. This begs the following question:

Why should we consider the expansion of a graph $G$, when the conductance seems to be a stronger measure (that subsumes expansion)?

There are several different definitions for the expansion of a graph, but all of them are spatial. One common definition defined the expansion $h(G)$ of a graph $G$ as $$ h(G) = \min_{|S| \leq |G|/2} \frac{|\partial S|}{|S|}, $$
where $S$ is a set of vertices containing at most half of the vertices, and $\partial S$ is the (edge) boundary of $S$, the number of edges connecting $S$ to $\overline{S}$. For a $d$-regular connected graph, there is a strong connection between $h(G)$ and a spectral parameter, the eigenvalue gap $\lambda(G)$, which is the smallest non-zero eigenvalue of the Laplacian. For a $d$-regular connected graph, Cheeger's inequality states that
$$ \frac{\lambda(G)}{2} \leq h(G) \leq \sqrt{2d\lambda(G)}.  $$
This is often put in terms of the second largest eigenvalue $\lambda_2(G)$ of the adjacency matrix of $G$, which satisfies $\lambda_2(G) = d - \lambda(G)$. There must be versions of Cheeger's inequality for non-regular graphs, and I'll let you look them up.

A lot of information on expander graphs can be found in the survey (based on course notes) Expander graphs and their applications by Hoori, Linial and Wigderson. Other information is scattered among lecture notes and even recent papers.


External fragmentation in fixed size partitioning Can external fragmentation occur in fixed size partitioning ?

I searched everywhere but couldn't find a sentence which says external fragmentation is not possible in fixed size partitioning.

Please someone clear my doubt.

You seem to feel external fragmentation should not be possible with a fixed size algorithm – I wonder why?

Summary: A fixed size algorithm probably only helps if all requests are for the size it provides.

External fragmentation has, in general, more to do with the order of de-/allocation and the strategy for placement of allocation blocks in the available space than with the size of space allocated for a given request. However, if all requests are for the same single fixed size as the algorithm allows for the caller (i.e. minus any internal overhead), then fragmentation will no longer be a functional problem: although allocated and unallocated blocks may be interspersed, this will not reduce the total number of allocation requests that can be satisfied. There could however be consequences for performance, especially if the algorithm does not maintain a chain of free blocks.


Are comparison sort algos appropriate for SUBJECTIVE sorting? I've been tasked with creating an online feature that ranks 50 fantasy characters from a variety of domains based on combat acumen and polls users one which one is the most powerful based on their votes on a series of face-to-face matchups. (Spiderman vs. Jon Snow, etc. etc.). If this is designed well, we hope to attract a large audience and high participation.

My first instinct was to use some variety of comparison sort--probably Bubble or Heap, given the manageable size. But as I brush up on the mechanics, all the literature I can find seems to be oriented toward stochastic sorts in which any pair of items can be definitely compared.

Another curveball here is that, as more people participate, the ordered list can (but needn't mustn't) be informed by all the people who have already weighted in. This will probably be necessary since we can't expect every user to weigh for hundreds of matchups. I'm not clear on how to tell the algorithm which items are already somewhere near their appropriate place in the list thanks to a lot of preexisting votes.

I'm sure I'm not the first to confront this issue since comparison algos are commonly used exact crowd wisdom on the best of, say, a few dozen photographs. I'm just not quite sure where to start. Am I looking for a variation on comparison sort with some addition search phrase for Google, or a different approach entirely?

Thanks![Insert favorite fantasy sign-off.]

I suggest reading about the theory on rating systems and ranking systems.  There are many standard algorithms and methods for this.  I would recommend reading the following resources, to get you started and to give you an entry-point and overview and let you figure out which might be best-suited for your particular situation:

The Bradley-Terry model
Pairwise comparison
The Elo rating system, and other rating systems (TrueSkill, Glicko, etc.)
Resources on Stats.SE: https://stats.stackexchange.com/q/30976/2921, https://stats.stackexchange.com/q/71297/2921, https://stats.stackexchange.com/q/15776/2921, https://stats.stackexchange.com/q/6379/2921
Finally, there is work on experiment design: how to sequentially select which pair of characters to compare, based on the results of comparisons so far.  (Think of this like matchmaking in chess, where you want to figure out which pairs of players to have play each other, based on their results so far.)  I can't remember pointers right now, but I remember that I've seen some material on Stats.SE about this as well, so do some searching there and you might find additional references and resources.

I suspect it is likely that one of these will be a reasonable choice for you.

There is a major caveat.  It is important to understand is that there may not be any linear ordering of characters that has the property you want.

Think of the game rock-paper-scissors; there is no linear ordering of these three choices that ranks them in order of "power", and polling people about pairs of them won't let you find a linear order.  In particular, none of those three choices are any more powerful than any other; rock beats scissors, paper beats rock, and scissors beats rock.  This can show up in fantasy settings, too.


Prove complement a^nb^nc^n is contextfree So the complement of L1 = {$a^{n}b^{n}c^{n}$ | n $\geq$ 1} would be L2 = {a,b,c}* \ {$a^{n}b^{n}c^{n}$ | n $\geq$ 1}.

In other words, any combinations of a,b and c where we dont have an equal number of all three letters and w = $\varepsilon$ is also legit.

However,  while I'm certain that there should be a contextfree grammar for L2, I can't seem to find a grammer that allows you to generate the terminals freely without allowing $a^{n}b^{n}c^{n}$ with n $\geq$ 1.

My attempt was to make a starting Rule S -> $Q_{_{a}}$ ; $Q_{_{b}}$ ; $Q_{_{c}}$ ;  $\varepsilon$
 so that the individual Q rules would make it possible for two of the terminals a, b and c to have an equal number, but not for the third. (in $Q_{_{a}}$, a is restricted by max(b,c), in $Q_{_{b}}$, b is restricted by max(a,c), in $Q_{_{c}}$, c is restricted by max(a,b) so that the restricted terminal can never show up as often as the unrestricted terminal with the highest count)

The rules I set up though, only allow to have unlimited numbers of unrestricted terminals in any order. I'm not sure how to implement a rule for the restricted terminal, without allowing it to have as high a count as the unrestricted ones, if the unrestricted ones have the same count.

here's my P for G$_{_{L2}}$ so far

S $\rightarrow$ $Q_{_{a}}$ ; $Q_{_{b}}$ ; $Q_{_{c}}$ ;  $\varepsilon$

$Q_{_{a}}$ $\rightarrow$ $Q_{_{a}}$b $Q_{_{a}}$ ; $Q_{_{a}}$c $Q_{_{a}}$ ; $\varepsilon$

$Q_{_{b}}$ $\rightarrow$ $Q_{_{b}}$a $Q_{_{b}}$ ; $Q_{_{b}}$c $Q_{_{b}}$ ; $\varepsilon$

$Q_{_{c}}$ $\rightarrow$ $Q_{_{c}}$a $Q_{_{c}}$ ; $Q_{_{c}}$b $Q_{_{c}}$ ; $\varepsilon$

These are still missing the rules for the individual restricted variable.
In what fashion can I add those, without breaking the [ $a^{n}b^{n}c^{n}$ | n = 0 ] rule?

Edit: it occured to me that I could refine the restricting rules, such that the restricted terminal can be derived from a rule if, and only if one (and only one) of the unrestricted ones is always created with it. For example:

S $\rightarrow$ $Q_{_{a}}$ ; $Q_{_{b}}$ ; $Q_{_{c}}$ ;  $\varepsilon$

$Q_{_{a}}$ $\rightarrow$ $Q_{_{ab}}$b $Q_{_{ab}}$ ; $Q_{_{ac}}$c $Q_{_{ac}}$

$Q_{_{ab}}$ $\rightarrow$ $Q_{_{ab}}$b $Q_{_{ab}}$ ; $Q_{_{ab}}$c $Q_{_{ab}}$ ; $Q_{_{ab}}$ a $Q_{_{ab}}$ b $Q_{_{ab}}$ ; $Q_{_{ab}}$ b $Q_{_{ab}}$ a $Q_{_{ab}}$ ; $\varepsilon$

$Q_{_{ac}}$ $\rightarrow$ $Q_{_{ac}}$b $Q_{_{ac}}$ ; $Q_{_{ac}}$c $Q_{_{ac}}$ ; $Q_{_{ac}}$ a $Q_{_{ac}}$ c $Q_{_{ac}}$ ; $Q_{_{ac}}$ c $Q_{_{ac}}$ a $Q_{_{ac}}$ ;  $\varepsilon$

At this point my brain starts running in circles. Would this set me on the right path?

You're overcomplicating. There is no need for the grammar to be deterministic, so it's OK for cases to overlap.

Say $\omega \in \overline{L_1}$. At least one of the following statements must be true:

$\omega = a^ib^j\nu \text{ where } i \ge 1, j\ge 0 \text{ and } i \ne j, \text{ and } \nu \text{ does not start with } b$
$\omega = a^ib^jc^k \text{ where } i, j, k \ge 1, \text{ and }j \ne k$(I don't require $i = j$, although if $i \ne j$ then the first condition also applies.)
$\omega \text{ does not start with } a$

These all have reasonably simple grammars.

Just in case it's not obvious, there are a few ways to do $a^jb^k | j\ne k$. One simple one:

$$\begin{align}
S &\to A \mid B \\
A &\to aC \mid aA \\
B &\to Cb \mid Bb \\
C &\to \epsilon \mid aCb
\end{align} $$

$C$ is a balanced sequence of $a$ and $b$, $A$ has more $a$s, $B$ has more $b$s, and $S$ has either more $a$s or more $b$s.


DFA for accepting all binary strings of form power of $n$ (not divisible by $n$) i.e. $n^k$ for given $n$ We can form DFA accepting binary numbers divisible by $n$.

For example DFA accepting binary numbers divisible by 2 can be formed as follows:

Similarly DFA accepting binary numbers divisible by 3 can be formed as follows:

We can follow a well defined procedure to form these types of DFAs.
However can there be any well defined procedure or better to say logic for forming DFAs accepting numbers of of the form $n^k$?

For example, let us consider DFA accepting all numbers of the form $2^k$.
This language will be $\{1,10,100,1000,...\}$, thus have regex $10^*$. We can form DFA as follows:

I tried forming DFA for $3^k$ and similar ones? But was not able to do so. Or is it just that its pattern of $2^n$ binary equivalents which was making it possible to create DFA and we cannot form DFA accepting all binary numbers of the form $n^k$ for specific $n$?

Here is a quick and dirty proof using Pumping Lemma that language $L$ consisting of $3^n$ in binary is not regular (note: it is regular if represented in ternary, so representation is important).

I will use the notation from Wikipedia article re Pumping Lemma. Assume for contradiction that $L$ is regular. Let $w \in L$ be any string with $|w| \ge p$ (pumping length). By Pumping Lemma, write $w = x y z$ with $|y| \ge 1, |xy| \le p$ and for all $i \ge 0$ $xy^i z \in L$. I will write $x$, $y$, and $z$ also for numerical values of corresponding parts, and $|x|, |y|, |z|$ for their lengths in $w$. Numerically we have $w = 3^{k_0}$ for some $k_0 \in \mathbb{N}$. At the same time we have numerically $w = z + 2^{|z|} y + 2^{|z|+|y|}x$. Thus, we have

$$ z + 2^{|z|}y+2^{|z|+|y|} x = 3^{k_0}$$

Now, let's pump $w$ to get for all $i \ge 0$

$$ z + 2^{|z|} y \left( \sum_{j=0}^{i-1} (2^{|y|})^j \right) + 2^{|z|+i|y|} x = 3^{k_i}, $$

where $k_0 < k_1 < k_2 < \ldots$. Simplifying we get for $i \ge 1$

$$ z + 2^{|z|} y (2^{i |y|} - 1) / (2^{|y|}-1) + 2^{|z|+i|y|} x = 3^{k_i}.$$

Let $C = z - 2^{|z|} y / (2^{|y|}-1)$. Then we have

$$ 3^{k_i} = 2^{|z|+i |y|} y / (2^{|y|}-1) + 2^{|z|+i|y|} x + C. $$

Now, observe that

$$ 3^{k_i} - 3^{k_{i-1}} = (2^{|y|}-1)(3^{k_{i-1}} - C). $$

Therefore, we have $C (2^{|y|}-1) = 3^{k_{i-1}} (2^{|y|} - 3^{k_i - k_{i-1}}).$ Note that $|2^{|y|} - 3^{k_i - k_{i-1}}| \ge 1$. Thus, on one hand, the absolute value of the right hand side grows at least as $3^{k_{i-1}}$, which goes to infinity with $i$. On the other hand $C(2^{|y|}-1)$ is independent of $i$ and is a constant. This gives a contradiction.


propositional Modal logic filtration definition Hello I have a slightly unusual question which relates to a definition of filtration structure. The following is my current state of the definition:

$ \mathcal{M} = (W, R, L) $, W is a set of worlds,
$R$ is a binary relation on the worlds, $ R \subseteq W \times W$, and
$L$ is a labelling function $ L : W \rightarrow\ \mathcal{P} (PropAtoms) $, here $PropAtoms$ is the set of atomic formulas.

Let $ \mathcal{M} = (W, R, L) $ be a Kripke model and let $\Gamma$ be a set of formulas that is closed under subformulas. Now, for each world $ w \in W$ we define the following:
$ \Gamma_{w} = \{ \psi \in \Gamma : (\mathcal{M},w) \vDash \psi \}$,

that is, $\Gamma_{w} $ contains formulas from $ \Gamma $ that are true at $w$ and consequently in model $\mathcal{M}$. Next we define an equivalence relation $\sim_{\Gamma} $ on worlds $w, w' \in W$,
$ \sim_{\Gamma} w w' $ if and only if $\Gamma_{w} \sqsubset \Gamma_{w'}$,
that is, worlds $w$ and $w'$ are equivalent if and only if they satisfy the same formulas in $\Gamma$. We also have equivalence classes $[w]$ of worlds $w$ with respect to $\sim_{\Gamma}$.

Lets now present the following quotient structure $ \mathcal{M}_{\Gamma} = (W_{\Gamma}, R_{\Gamma}, L_{\Gamma})$ which is in fact filtration of $\mathcal{M}$ with respect to $\Gamma$. $\mathcal{M}_{\Gamma}$ is defined as follows:
.........

Here is the bit I need help with, I am struggling to define my filtration model. This is mainly because the definitions online don't use the same labelling function but rather use a valuation function which is of the form $v(p)$. And such function takes an atomic formula whearas my labelling function takes in a specific world written $L(x)$. Could someone please help me our here and try providing correct definition which will match my model $M$ definition?

You are probably looking for something like:
$L_\Gamma([w]) = L(w) \cap \Gamma$. This will falsify any propositional letter not in $\Gamma$.

(Filtration is (afaik) usually defined as a property that a model may have. There could be several (or none) concrete models satisfying this property.)


Can an alphabet be extended in a reduction proof? (with sample problem) So I am working on solving a problem on whether following language is decideable:

  $L = \{n \in \mathbb{N} \mid M_n$ never freezes (for any input)$\}$, where $n$ is the Gödel-number of a Turing machine.

The model for Turing machines that we use operates on a one-side-unbounded tape, so "freezing" in this context means going "out-of-bounds" on the other side of the tape. We also define a Turing machine as the tuple $(K,\Sigma,\delta,s)$, where $K$ is the set of states, $\delta$ is the transition function and $s$ is the starting state ($\notin K$).

Now I have an idea on how to prove it is not decideable by reduction, but it requires me to construct a new DTM which operates on a new alphabet $\Sigma' := \Sigma \cup \{§\}$, and assume that $§ \notin \Sigma$. (where $\Sigma$ is the alphabet of the machine $M_n$)

My idea is as follows: We prove that $L^c=\{n\in\mathbb{N}\mid M_n $freezes for at least one input$\}$ is undecideable. For that, we construct a DTM $Extend$ which takes $n$ as input. $Extend$ modifies the $n$ so that we get a new machine that operates exactly as $M_n$ would, except with the following tweaks:

For any (state,letter) pair with the $\delta$ function value $\delta(q,\sigma)=(h,\sigma')$ (where h is the halting state), we replace the function value with $(q_{|K|+1},\sigma')$ (so now the machine never halts on its own)
Introduce a new state $q_{|K|+1}$, where $\delta(q_{|K|+1},\sigma)=(q_{|K|+1},\sigma)$ (so if this state is reached the TM goes into an infinite loop).
We introduce a new letter to the alphabet, let's say '$§$', and set it so that $\delta(q,§)=(h,\#)$ (where # is the blank symbol) (so it only halts if any point it reads '$§$')
All of these are turing-computable steps (if we look at $\delta$ as a table of values for every (state,letter) pair (finite), it's the same as going through the table once, changing values as necessary, adding a row and adding a column).

Now we create a new DTM $M_j$ which works as follows (on input $n$):
$>Extend \to L_{\#} \to S_R \to L \to § \to R \to R_{\#}$, where $L_{\#}, R_{\#}$ is a TM which goes left or right respectively until it encounters a blank, and $S_R$ is a TM which shifts the word to the right of it by a blank (so $s,\underline{\#}w\# \vdash^*_{S_R}h,\#\underline{\#}w\#$).
So $M_j(w)$ works as follows: $s,\#n\underline{\#} \vdash^*_{M_j} h,§\#n_{Extend}\underline{\#}$

We know that the set $\mathcal{E}=\{ n\in\mathbb{N} \mid M_n$ accepts $\emptyset \}$ is in $\text{co-RE}$. This means $\mathcal{E}^c = \{ j\in \mathbb{N} \mid M_j$ accepts at least one input $\}$ is recursively enumerable, but not decideable. Since our new DTM $M_j$ only accepts iff $n$ would freeze for at least one input, this means that $n\in L^c \Leftrightarrow j\in \mathcal{E}^c$ and the reduction proof would be complete.

But again, I am not sure if the transformation of $n$ I made (by introducing the letter '$§$' to $\Sigma$) is allowed. Can someone clarify this for me?

A (computable) reduction from problem P to problem Q is a (computable) function that takes an instance of P to an instance of Q. In your case $P=\mathcal{E}^c$ and $Q = L^c$. So your reduction is "legal" (that is, conforms to the definition of reduction) if it takes an instance of $\mathcal{E}^c$ to an instance of $L^c$. That's all a function has to do in order to be a reduction.

(In principle there is no such thing as an instance of a problem – every string over the appropriate alphabet is an instance. But let's ignore this small issue.)


MAX,MAJ variants of NP complete problems We know that MAJSAT is PP-complete. Is it generally true that given an NP-complete problem, its majority variant is PP-complete? For example,

MAJ-Set-Splitting: are the majority of partitions of items going to split the sets?

MAJ-Subset-Sum: does the majority of partitions of items have a sum of exactly K?

etc...

MAJ-Subset-Sum is easy to solve. A majority of partitions sum to $K$ iff $K = 0$ and all elements are equal to $0$. Indeed, let $S$ be the (multi)set, and suppose that there were some element $x \neq 0$ in $S$. For each subset $A$ of $S \setminus \{x\}$, either $\sum A \neq K$ or $\sum A + x \neq K$, and so $K$ can be the sum of at most half the subsets. We conclude that if $K$ is a sum of the majority of the subsets that $S$ consists only of zeroes, and so $K = 0$ as well.


Backpropagation on a matrix of functions As nicely described in this article, backpropagation for multi-layer perceptrons defines the error term for a neuron in terms of the partial derivative of the weights.

It's traditional to represent the weights between neutrons in matrix form: $w_{ij}$ representing the weight between neuroma $i$ and $j$.
Since a weight can be considered as being as constant multiplier of any input, so a possible generalisation is instead to replace the $w_{ij}$ with some univariate function $f_{ij}$.

Since. a 3 layer MLP is already a universal approximator for continuous functions, this generalisation won't be more expressive, but the hypothesis is that it might converge faster for some problems.

My question then concerns the nature of the learning algorithm for this extended formulation:

How might it be possible to define backpropagation if the weight matrix is replaced by a matrix of functions? The functions can be assumed to be differentiable as required.

The problem isn't well-defined as you've stated it.  Backpropagation involves updating the weights, i.e., finding weights that cause the neural network to behave well.  If you have no weights, then there's nothing to update.

For these reasons, the standard approach to building neural networks involves both weights and univariate functions.  In the standard perceptron architecture, there are weights $w_{ij}$ along each edge (from neuron $i$ to neuron $j$), and a univariate function $f_j$ applied to the output of each neuron (neuron $j$).  So standard artificial neural networks already incorporate the univariate function.  The univariate function $f_j$ is called an "activation function".

Standard backpropagation does work with arbitrary activation functions.  You don't need to modify or generalize it: it already deals with them.  In particular, backprop can be used with an arbitrary activation function, as long as you know its derivative.  So, I suggest you take another look at how standard backprop works.

Backprop is basically just (a) computation of the partial derivatives (the partial derivative of some objective function, with respect to the weights), computed using the chain rule, plus (b) gradient descent.  Introducing arbitrary univariate functions affects only part (a), and the chain rule from calculus tells you how to calculate the partial derivatives.


Bankers Algorithm-Is the system in safe state? Could somebody please provide a step-through approach to solving the following problem using the Banker's Algorithm?

A system contains 10 units of resource class Ru. The resource requirements of three user processes P1, P2 and P3 are as follows

                      |   P1  |  P2  |   P3   |
Max Requirement       |   8   |  7   |   5    |
Current Allocation    |   3   |  1   |   3    |
Balance Requirement   |   5   |  6   |   2    |
New Request Made      |   1   |  0   |   0    |

Using Banker’s algorithm, determine if the projected allocation state is safe and whether the request of P1 will be granted or not.

My solution:

total recources :10
total allocation :7
available: 10 -7 = 3

Need
P1     5
P2     6
P3     2

3>2 so P3 can run now available is 6
6>5 so P1 can run now availabl 9
9>6 so P2 can run

System is safe state,Hence P1 will be granted.

But I'm not sure if my solution is true.

you can say there is no deadlock if there is a safe sequence for the completion, after $P1$ request is granted there must be a safe sequence where by which every process is completed.

After P1 request is granted
                      |   P1  |  P2  |   P3   |
Max Requirement       |   8   |  7   |   5    |
Current Allocation    |   4   |  1   |   3    |
Balance Requirement   |   4   |  6   |   2    |
now the resources left over are 10-4-1-3=2

so can we complete with 2 resources? any sequence is possible?

YES

if P3 is given 2 resources it will complete and release all the current allocated resources so our resource count becomes 5 , now we have 5 and we can complete P1 and get back 4 now our resource count is 9 and i need just 6 to complete P2 so a safe sequence is possible.
so safe sequence will be

$P3 \rightarrow P1\rightarrow P2$

so $P1$ request is granted


Understand the time complexity for this LCS (longest common subsequence) solution I would appreciate an intuitive way to find the time complexity of dynamic programming problems. Can anyone explain me “#subproblems * time/subproblem”? I am not able to grok it.

Code for LCS -

public static String findLCS(String str1, String str2 ) {
    // If either string is empty, return the empty string
    if(null == str1 || null == str2)
        return "";
    if("".equals(str1) || "".equals(str2)) {
        return "";
    }
    // are the last characters identical?
    if(str1.charAt(str1.length()-1) == str2.charAt(str2.length()-1)) {
        // yes, so strip off the last character and recurse
        return findLCS(str1.substring(0, str1.length() -1), str2.substring(0, str2.length()-1)) + str1.substring(str1.length()-1, str1.length());
    } else {
       // no, so recurse independently on (str1_without_last_character, str2)
       // and (str1, str2_without_last_character)
       String opt1 = findLCS(str1.substring(0, str1.length() -1), str2);
       String opt2 = findLCS(str1, str2.substring(0, str2.length()-1));
       // return the longest LCS found
       if(opt1.length() >= opt2.length())
           return opt1;
       else
           return opt2;
    }
}

I am just providing the actual code instead of pseudo code (i hope pseudo code or the algo is pretty self explanatory from above)

I assume you are interested in worst-case complexity.

A dynamic programming approach (recursively) breaks a problem into "smaller" problems,
and records the solution of these subproblems to make sure
that subproblems are not computed several times. So when the time required to combine subproblems is constant (it is the case for LCS), you only have to find an upper bound for the number of possible subproblems that will be solved along the program.

Here the subproblems are of the form
findLCS(s1,s2) where s1 is a prefix of str1, and s2 a prefix of str2.
There are (1+str1.length()) possible prefixes for str1, and
(1+str2.length()) for str2.
The number of possible subproblems is therefore (1+str1.length()) * (1+str2.length()).
Furthermore, a solution is obtained in constant time from its subproblems.
Hence complexity O( str1.length()*str2.length() ).

N.B. on some sequences all subproblems will be indeed computed, e.g., when letters in str1 and str2 are distinct.
Consequently, the quadratic bound is "tight".

N.B.2 you may find (short) explanations on the wikipedia page for LCS


How to make a NFA (or DFA) from $\varepsilon$NFA? I need to build a DFA from $\varepsilon$NFA, so first of all I assume that I need to convert the $\varepsilon$NFA to NFA and then to DFA (because I know the method of converting from NFA to DFA, and we learn how to remove $\varepsilon$'s from $\varepsilon$NFA and make it NFA.
But the I'm still stuck at some cases....
For example:
See this $\varepsilon$NFA:
I want to make it NFA (I don't know if to write the whole algorithm...), and I'm not sure which is right:
This:

Or this (at the comments.... I can't put more then 2 images)
I think that the first is the right one, but I'm not sure...
At the second one - the number of the 0-s must be even to be at $q_1$ but at the original $\varepsilon$NFA it can be any number of 0-s...
One more thing, it's correct that I'm not putting 0,1 insted of the $\varepsilon$? (Because 1 from $q_0$ brings me to $\varnothing$...)

I think the following should work. For each state q, define E(q) to be the set of all states reachable from q by following zero or more ε-transitions. Then, create a new NFA as follows:

The set of states in the NFA is the set $\{ E(q) | q \in Q \}$.
The start state is $E(q_0)$.
For each state $E(q)$ in the new NFA, the transitions are given as follows: for each state $r \in E(q)$ that has a transition to a state $s$ on a character $a$, add a transition from $E(q)$ to $E(s)$ on $a$.
The accepting states in the NFA are the states containing at least one accepting state in the original NFA.

The basic idea behind the construction is to have each NFA state correspond to a set of states in the ε-NFA. This effectively simulates taking all possible ε-transitions at each point in time.


What makes a common programming language non-context-sensitive but RE? I have a vague understanding that a (sane) programming language is RE as they are Turing-complete, being able to describe any Turing machine.

But I cannot pinpoint what aspect makes a programming language RE, not context-sensitive. For example, I'm guessing the variables in any scope structures like for can be described in a context-sensitive grammar with a fairly bulky (but finite) number of production rules.

One wild guess is that it's because of pointers or references, making it impossible to describe with a finite number of production rules. Can anyone teach me about why it is?

I think you are conflating syntax and semantics.

A formal language is RE if it is possible to recursively enumerate all valid "sentences" (read "complete programs"). Validity here effectively means only that a compiler could convert the program into an executable, without saying anything about what that executable does.

That has basically nothing to do with the semantics of the program. We could design a programming language which is arbitrarily difficult to parse, but whose semantics are simple enough that the generated executable is guaranteed to be a complete function. (Removing all looping constructs is a good start.)

On the other hand, we could design a language which is trivial to parse, as are most stack languages, but whose semantics are effectively Turing complete (aside from the finiteness of memory in a physical realization of a processor.)


How can a stack-based VM be Turing-Complete? I was trying to implement a stack-based Virtual Machine (e.g. like JVM or some early version of Lua) for some benchmarks in order to test its performance against a Register-based VM.

I originally implemented it as having a global stack for all values and an array of instructions, where for the sake of simplicity, no functions are implemented, but only goto statements that jump occationally in between the array of instructions, in order to operate on the stack. All instructions are decoded in a linear fashion, and then loaded into an array, which in turn gets fed into the gigantic switch, looping itself while directing instructions to different operations. The values contained in the instructions are decoded seperately within the switch, and then get stored into the global stack, when needed.

Later on, I heard that in order to be Turing-equivalent, the stack machine must have at least two stacks. So the question I'm asking here, is 1) is my original design Turing-equivalent? 2) If not, how to revise the design so that it would be Turing-equivalent?

The reason for the stack VM to be Turing equivalent is that then its speed and efficiency can be compared to another Turing-equivalent custom-made Register machine. Please correct me on this if it does not :)

Thanks!

If the stack machine is only allowed to access the top of the stack, and apart from the stack it only has a finite amount of storage, then it's a pushdown automaton. Pushdown automata are not Turing-complete; non-deterministic pushdown automata can only recognize context-free languages, and deterministic ones even less.

With two stacks, such that the machine can push and pop from either stack, the machine is equivalent to a Turing machine. This is fairly easy to see: given a Turing machine, you can build an equivalent two-stack automaton by pushing the input onto one stack, and then treating forward motion on the tape as popping from the first stack and pushing onto the second stack, and vice versa for backward motion.

If the stack machine is allowed to access data from any point in the stack, which is normally the case when a stack machine is used to build a virtual machine, it's a different story. In this case the shape of the stack doesn't matter, what you have is a random-access machine. From the point of view of computability, it's the same thing as a register machine, it's just a matter of how you name the registers: by calling it “stack machine”, you're just saying that the registers are numbered in a certain way.

RAM are equivalent to Turing machines. There is a subtlety with RAM: the registers are not finite registers, they are “variable-sized” registers that can accommodate numbers that are as large as needed for the computation. In practice, most concrete machines are like that — a register or memory cell is as large as it takes to store a pointer, and if the size of a pointer exceeds the register size, it means that you've overflowed the memory of your machine and you start the computation again on a machine with more memory and bigger registers.


Algorithm to generate integer sets fulfills restrictions I'm trying to solve the following problem.

Input

positive integers $v$, $b$ and $\ell$. ($\ell\leq v\leq b\ell$.)

Output

A list $S_1, \dots, S_k$ of all possible integer multisets (a generalization of the concept of a set that, unlike a set, allows multiple instances of the multiset's elements), such that each $S_i$ fulfills following constraints:

$|S_i|=\ell$
$\sum_{s\in S_i}s=v$
for all $s\in S_i$, $s\in \{1, \dots, b\}$

For example, a solution to the instance $v=4$, $b=4$, $\ell=2$, is $[\{1,3\},\{2,2\}]$.

For now I have a recursive function working to give something not exactly the same as what I'm expecting. For the input above, it returns $[\{1,3\},\{2,2\},\{3,1\}]$. I know I can use extra steps to eliminate the duplicates but I'm wondering if there's a mathematical formula I can use? Or some other algorithm acts smarter?

Below is my code:

public static List<List<Integer>> getIntegerSets(int v, int base, int l) {
    if (v < l || l <= 0) return null;
    List<List<Integer>> result = new ArrayList<>();
    if (l == 1) {
        if (v > base) return null;
        List set = new ArrayList<Integer>();
        set.add(v);
        result.add(set);
    } else {
        for (int i = Math.min(base, l * v); i > 0; i--) {
            List<List<Integer>> list = getIntegerSets(v - i, base, l - 1);
            if (list == null) continue;
            for (List<Integer> subset : list) {
                subset.add(0, i);
                result.add(subset);
            }
        }
    }
    return result;
}

Another extended problem is, can we (use another algorithm) directly get the size of the list, which is the $k$ value, with or without duplicates, perfectly both, without executing this very function?

You want to enumerate all integer partitions of $v$ into exactly $\ell$ parts, where each part is $\le b$.  Let $F(v,\ell,b)$ denote the set of all such partitions.

One can construct a recursive algorithm for this.  For instance, any such partition must include the number $b$ one, two, three, ..., or $\lfloor v/b \rfloor$ times, so:

$$F(v,\ell,b) = \bigcup_{i=0}^{\lfloor v/b \rfloor} F(v-ib,\ell-1,b-1) + b+\cdots + b,$$

where $F(\star)+b+\cdots+b$ represents the set of partitions (multisets) obtained by starting with each partition in $F(\star)$ and adding $i$ copies of the number $b$ to it.  Moreover, this is a disjoint union, so there is no need to use hashtables to eliminate duplicates.

However, the number of such partitions can be exponentially large in $v$, so in general the algorithm might be infeasibly expensive, unless $v$, $\ell$, or $b$ are sufficiently small.


Time complexity of subset sum problem with reals instead? It is well known that the conventional subset sum problem with integers is NP-complete. What if the array elements can be any real numbers and also target sum can be any real number? Is it NP-complete still or harder (NP-hard)?

What model of real numbers are you using?  If it's something like floating point, where everything is really rational, just multiply through by a common denominator and you're back in the world of integers. The bit-length is only polynomially larger than the ones you started with (the common denominator is at most the product of $n$ $n$-bit numbers, so it has at most $n^2$ bits), so nothing has changed, complexity-wise.

Beyond that, things will get more complicated – can you even tell in polynomial time what numbers are represented by the input?

However, the real-number version is definitely still NP-hard, since it has the integer version as a sub-problem.


Converting a recursive algorithm to a runtime function void Sort(int A[], int left, int right)
{
    int p;

    if (left < right)
    {
        p = (right + left + 2)/3;

        Sort(A, left, left+p-1);
        Sort(A, left+p, left+2*p-1);

        MergeSort(A, left+2*p, right);

        Merge3(A, left, left+p, left+2*p, right);
    }
}

I need to convert this function into a mathematical expression in order to solve it's run-time complexity.

I know  that MergeSort()'s complexity is of $\Theta(n \log n)$ and that Merge3()'s complexity is of $\Theta(n)$.

I can't figure how to transform this into a recursive mathematical expression.

The key is to use right - left as $n$ for the parameter of the runtime recursion. What is the size of the subparts?

Closer hint:

   Note that the algorithm separates the input part of the array in three approximately equal-sized parts; the first two are sorted recursively, the third with Mergesort. This should be reflected in your recurrence.

Almost finished:

   Assuming Merge3 runs in time $\Theta(n)$ und MergeSort in time $\Theta(n \log n)$, you get a recurrence of the form

 $\qquad\displaystyle T(n) \approx 2T(n/3) + \Theta(n) + \Theta(n/3 \log(n/3))$

 since all parts have size $\approx p \approx n/3$. Solve this with the Master theorem and flesh out the details.


Does a reduction with $\infty$ work? Lately, I saw an NP-complete proof that involves creating an instance of a problem using $\infty$. Is this a polynomial-time reduction?

More precisely, let a problem $\Pi$ has an instance $I=(n, A, v)$ where $A$ is a matrix of size $n\times n$, $A=[a_{ij}]$, and $v$ is positive.

The proof that $\Pi$ is NP-complete works by reducing the independent set problem (an instance is a graph $G=(V,E)$ and an integer $k$) to $\Pi$ as follows: $n=|V|,v=k$ and

$$a_{ij} = \begin{cases}
\infty \text{ if } \{i,j\}\in E\\
0, \text{ otherwise }
\end{cases}.$$
Also, $G$ has an independent set of size $k\iff\Pi$ has a value $v= k$.

I do not see how one can set $a_{ij}$ to $\infty$.

In most cases in which such a reduction is presented, the reduction also works with $\infty$ replaced by a large enough number $M$ which is at most exponential in some power of $n$. If you replace $\infty$ by $M$ then you get a bona fide instance of $\Pi$, and this instance has polynomial size (and so the reduction runs in polynomial time) since $|M| = O(n^C)$ for some $C$, where $|M|$ is the length of the binary encoding of $M$.

You are right that using $\infty$ instead of $M$ is a bit sloppy, but it often results in a cleaner description, it being understood that the "real" reduction uses some large enough finite $M$.


Computer Security versions of the Halting Problem I'm plenty familiar with the Halting Problem for Turing Machines. It occurred to me after reading several posts on this site that it would be interesting, educational and useful to start a list of equivalents to the Halting Problem in terms of Computer Security. I think this might help students of computer science and allied areas come to appreciate the true depth and application of the Halting Problem in whatever their application area.

So, I ask that the proposed (or actual) equivalent problem be:

(1) One that makes sense in the domain of computer security. This can be from information management, Cryptography, hacking, or programming (ideally with a security bent, since there are plenty of Halting equivalent problems already well known in the world of programming languages and compilers).

(2) One stated with a reference to literature on that subject if possible, and maybe even (although I wouldn't require it) a proof if you know of an elegant one.

Example: I have an antivirus software on my machine, and I want to know
whether it will ever execute malicious code. As far as I can tell, this is the Halting problem in disguise.

What you're looking for is Rice's Theorem, which is a generalized version of Halting Undecidability.

It basically says that any property of a Turing Machine (i.e. any computer program) is undecidable, if it's a property of the behavior of the program (i.e. a property of the language it accepts/produces), as opposed to a particular syntactic feature of the implementation. This holds unless it's a trivial property (always true or always false).

For example, deciding "Does instruction X ever get executed" or "Is a high security value stored in low security memory" are all questions about program behavior.

But things like "does this program contain a for-loop" or "is this program type-correct" aren't behaviors, because there might be equivalent programs which don't have the same values for those properties.
You can phrase a program with a for-loop as using while-loops without changing the behaviour, or you can make a version of a program which behaves correctly but doesn't check under your typing discipline. So these aren't properties of the behavior, they're properties of the particular implementation.


Fair assignment of storage for multiple writers (load balance) I'm trying to optimize a system with a better algorithm for allocating storage.  The system has 'N' writer processes and 'M' disks. (N < 30, M < 10. N can change, M is constant).
Any process can write to any disk and each process regularly writes a file every, say, 5 minutes, but the size of the file can be quite different. Each writer independently "chooses" which disk it writes to on a file-by-file basis; so it might write one file to Disk 2 and the next file a few minutes later to disk 8. There is no communication between writers.
This goes on forever.

In the steady state, all disks are "full" and a "deleter" process continuously deletes the oldest files until all disks are no longer "really full".  (there are two water marks: "almost full" and "really full", if that helps), so the "deleter" wants:
        Almost Full    Really Full
Disk 1       Y             N
Disk 2       Y             N
Disk 3       Y             N

I need to optimize how the writer chooses which disk to write to such that, as much as possible, different writers are writing to different disks. This is important to balance I/O load.
I had thought this wouldn't be too hard, but the more I think of it, the more problems arise. I've tried a number of things:

Randomly choose disk from those with free space. However since there aren't many disks (M is small), there is a good chance all writers will choose the same destination disk and overload the I/O system.  Bad.

Index/hash the writer number across the list of disks with free space. So if N == M, Writer 1 always ends up writing to Disk 1. However this fights with the deleter working to maintain free space by deleting the oldest files: eg, the first disk gets full but the oldest file is on a different disk.

Use first free disk. However this ends up with all writers writing to the same disk.

There are multiple solutions to this problem:

Consistent hashing with bounded loads
Generic Bin packing algorithm(Knapsack or other)

Both require that the writer know the free storage amount of the drives.
Consistent hashing with bounded loads is based on the consistent hashing algorithm published by akamai and fixed the issue of load inbalancing by overflowing across the ring to the next free "bin".


Hungarian Algorithm - Bipartite Graph Approach I have been having some difficulty making sense of the Hungarian Algorithm outlined here.  It seems incomplete and/or erroneous to me.  The main issue is the line:

  If R_T ^ Z is nonempty, then reverse the orientation of a directed
  path in...

How do we know which path to select as "a path"?  If we select the wrong path, how do we recover?  This seems to be a monotonically assigning algorithm, in that we can only ever create new assignments, but never remove or alter existing ones.

Suppose we have a simple example of S = {A, B}, T = {W, X} with weights AW: 2, AX: 2, BW: 6, BX: 4.  How do we select whether to add AW or AX to the mapping first, or how to we recover from making the wrong selection?

(Converting a comment into a proper answer. Note that I now use the minimum cost convention of the reference given in the question.)

Any augmenting path serves. Note that you reverse the order of the arcs. Say you choose AW of cost -2 first. Then you have forward arcs AX, BW, BX, and backward arc WA, which has been reversed. Now BW,WA,AX is an augmenting path, of cost -6+2-2=-6, and you end up with backward arcs WB,XA which represent the optimal solution 8.


Is this benchmark sufficient to consider my algorithm as an efficient matrix multiplication algorithm? I built a matrix multiplication algorithm and now I need some thoughts about following benchmark.
C++ chrono:: high resolution clock Time(micro second)

(Dim)256--> (Naive algo ) 296807, (My algo) 187479
(Dim)512--> (Naive algo) 2249495, (My algo) 1359046
(Dim)1024-->(Naive algo) 27930970, (My algo) 12309645

FYI, I have no knowledge about strassen matrix multiplication algorithm and how to utilize a github project.Therefore,I stole some benchmark from a github account for sake of some comparisons with strassen matrix mulplication algorithm.Those are as below.
C++ chrono:: high resolution clock Time(micro second)

(Dim)256-->(Naive algo) 260281,(Strassen algo) 216970
(Dim)512--> (Naive algo) 2122299, (Strassen algo) 1580466
(Dim)1024-->(Naive algo) 2algorithm?Strassen algo) 14696774

I don't know specs of github user's computer.I assume it's better than mine after observing both execution times of naive matrix multiplication algorithm.(quoted from https://github.com/rangelak/Strassen-Matrix-Multiplication)
Specs of my computer
Processor core i7 6th gen(2.60 GHz)
Ram 8gb
What do you think about my algorithm after observing above mentioned band what can I expect after comparing my algorithm with strassen matrix multiplication algorithm?

one thing I want to mention is that the strassen's matrix multiplication algorithm isn't often used in the real world and your algo is probably faster if the $n$ stays below a few thousands (explained here: https://stackoverflow.com/questions/13559928/why-is-my-strassens-matrix-multiplication-slow).
Now if you still want to compare your algorithm to the strassens algorithm I would recommend you to copy past a function from somewhere and run it on your computer.
The algorithm would get the same input as your algo and would run on the same hardware.
Here are some implementation of strassens algo:
vectors:
https://github.com/dmonaldo/strassen-matrix-multiplication/blob/master/main.cpp
arrays:
https://www.geeksforgeeks.org/strassens-matrix-multiplication-algorithm-implementation/
When I benchmark an algorithm I always want to plot the results to visualize the complexity. I think more is better; so you should probably use more n not only 256, 512, 1024. Also it would be good to know if your algo is made for a special case like sparse matrices etc. if that's the case you need to pay close attention to the input data, otherwise one algo might have a disadvantage.


Any way to find a 3-vertex cycle in a graph using an incidence matrix in O(nm) time? I have a graph with n edges and m vertices. This is an undirected graph.

I need to find a 3 vertex cycle. Only 3.

I'm confident I need to use an incidence matrix for this as this seems to be the best data structure. I'm familiar with cycle finding algorithms and they are all in crazy polynomial or even exponential time.

However those are for general cycles. Not 3 vertex cycles. I have O(n*m) time.

Any ideas on how to find this 3-vertex cycle in an undirected graph using an incidence matrix?

First off you can discard any row with less than 2 "1"s. Then I think I need to see some kind of a pattern in the matrix for the 3 vertex cycle. Not seeing it at the moment.

EDIT
Current idea:

Set up an array of vertices.
Go ---> in the matrix and build edges by assigning them in the matrix.
Each time edge is assigned check if that edge on both sides has a vertex with 2+ edges out.
If it has check if any of those edges out go to the same vertex [compare both lists for direct outward vertices from both sides of this edge].
If it's the same must be a 3 vertex loop.

I guess that's like rebuilding from incidence matrix to incidence list.

I'm looking at the below image from wikipedia:

https://en.wikipedia.org/wiki/Incidence_matrix

Let's assume first that your graph is connected, so that $m \geq n-1$. Convert your incidence matrix into an adjacency matrix in time $O(n^2) = O(nm)$. Now go over all $m$ edges, and for each edge $(i,j)$, go over all vertices $k$ and check in $O(1)$ whether $i,j,k$ is a triangle in the graph (using the adjacency matrix), for an overall running time of $O(nm)$.

If your graph is not connected, then use DFS/BFS to find its connected components, and run the procedure above on each of them. Assuming that the $i$th connected component consists of $n_i$ vertices and $m_i$ edges, the running time is $O(\sum_i n_i m_i) \leq O(\sum_{ij} n_i m_j) = O(nm)$.


How to calculate the minimum number of groups, by grouping groups with capacity together? I need to group cars (and their passengers) with other cars, and I don't know how to approach this problem.

If I have, for example, 3 cars. Car A with 7 seats and 2 passengers (3/7 because of the driver). Car B, 2/2. Car C, 1/3.
The most wasteful clustering would be [A, B, C]. But car C has room to pick up the driver and passenger of B, but no room for A, leaving us with [A, C]. Obviously, the best cluster would be one with only A because it has room to pick-up the other 2 cars. Now, this is a simple and small example, but how can I search for the minimum number of cars in samples with an arbitrary number of cars and passengers?

I tried to approach this problem in 3 different ways, but all fell short.

I thought about a maximum flow problem (image 1). But the maximum flow problem deals with capacities in edges of a graph. This specific problem has limitations on capacities of nodes/cars (not in its edges).

Maybe there's an adaptation of this method that I can use, but I couldn't think of any that would give me the list of groups that minimize the number of cars.

I also thought about the longest path problem (image 2). Every edge of my graph would be weighted by the number of people (driver + passenger) that would be picked-up if traversing to that node. And I could adapt the algorithm to decreased the capacity of the origin node accordingly with each node visited and stop that iteration if the max capacity was reached.

But to my understanding, I need to calculate the longest simple path (and not repeat any nodes) and that requires an acyclic graph. Given the context of my problem, most of the times there would be no way to turn my graph acyclic given that all the nodes would be strongly connected.

Lastly, I considered creating a list of trees (image 3). Where each root would be the origin car, and each child node would be a car that the root could pick-up. For each level of depth the available seats of the root would decrease until no more combinations existed. Then I would group trees' levels together and try to achieve the best combination and minimum of cars.

But at what level do I start. Does starting at the tree with the greatest depth and then grouping with other trees guarantee the minimum number of cars? Or is there a counterexample where grouping trees in their respective mid levels achieve better clustering? Do I just need to try every possible combination? That seems like an exhausting comparison and awfully inefficient.

I may be overlooking some characteristics of my problem, or maybe I'm just not comprehending the solutions I described. Is there a known solution to my problem, or maybe an adaptation I could implement? Any help or guidance is appreciated.

Thank you.

Edit:

u/gnasher729 mentioned the Bin packing problem in the answers which is indeed very similar to my problem.

Bin packing is calculated with bins of the same size. Given the context of my problem, my bins (cars) have different capacities.

With u/gnasher729 suggestions, the adaptation I came up with was:

Sort cars by remaining capacity first. Items weights are the size of the different groups of passengers.
Run the bin packing algorithm with bins of capacity equal to that of the car with more available seats.
Of the bin allocations produced by the algorithm, choose the bin with more items in it (meaning more groups of passengers were able to fit inside).
Remove the grouped cars (the bin + the items) from the sorted list and from the unplaced items.
Re-run the bin packing algorithm with the next emptiest car and with the remaining passenger groups.
Repeat until no more packing is possible.

It seems like it'll be an intense computation when given a large enough number of cars. If I have 20 cars with unknown passengers and unknown seats, and if I group 2/3 of those cars together with each iteration of the bin packing algorithm, then it'll be costly.

Is my adaptation wrong? Can i optimize it further?

The problem is NP-complete, because in the special case that all cars have the same capacity, it is just the bin-packing problem.

If car A has a higher capacity than car B, and you get an optimal solution (smallest number of cars) containing B but not A, then you can swap cars A and B, you won't need more cars, and because A has more empty capacity, you may fit the passengers from another car. So which cars you use in an optimal solution is obvious. You use cars sorted by capacity in decending order. So no matter what the numbers of passengers are, you would use the car with 7 seats, then the car with 3 seats, then the one with 2 seats. I assume you have groups of passengers you want to keep together, otherwise it is trivial.

You should be able to adapt any bin-packing algorithm to your situation. I can't see graphs being useful in any way.


how can i say a given problem is in co-NP using it's definition? I seem to be having trouble understanding the connection between the formal definition of co-NP and how problems are concluded to be in it. co-NP is defined to be the class containing the languages that are complements to languages in NP (I'm using this definition).

So, given this problem: "given a finite set of integers, is there a non-empty subset that sums to zero?" is in NP. How do i conclude that this problem: "given a finite set of integers, does every non-empty subset have a non-zero sum?" is in the class co-NP?

In other words, how do i know that the second problems corresponding language L2 is the complement to the first problems corresponding language L1?

Perhaps i'm missing something fundamental?!

Edit:
It seems I was not clear enough so hear is a clarification:
My question was why does the complement language L2 represent the second problem if it contains many seemingly random strings?

In other words, how are these seemingly random strings instances of the second problem?

Following the brief discussion in the comments, let me write an answer summarizing it.

When defining decision problems (e.g., based on $\{ 0, 1 \}^\ast$ strings), we usually make the assumption that every word in $\{0,1\}^\ast$ is a valid problem instance. Perhaps your source of confusion is that, usually, this is not made as explicit or given as much importance as it should or, rather, it is only too late (i.e., when discussing complementary problems such as those in $\textbf{coNP}$) that one realizes what the assumption actually entails. Under such an assumption it is obvious why $\textbf{coNP}$ is simply the complements of the problems in $\textbf{NP}$; in fact, without the assumption, such a definition would not make that much sense (since $\textbf{coNP}$ problems would contain invalid problem instances).

In the comments, I have also mentioned the notion of promise problems. This is an alternative way of defining decision problems without needing the aforementioned assumption. Basically, when the input string is not an encoding of a problem instance, the behavior of an algorithm solving the problem is left unspecified. The result is the $\{0,1\}^\ast$ string space being partitioned in three parts: valid "yes" instances, valid "no" instances, and invalid instances. Note that for poly-time algorithms this notion is equivalent to the former one since recognizing a valid instance (for reasonable problems) can always be done efficiently.


Pseudo-dimension of a subset of affine functions Let's say there are two sets of affine functions.

$\mathcal{A} = \{ax +b \mid a,b \in \mathbb{R}\}$
$\mathcal{H} = \{2x + 1, x, 3x + 4, 4x\}$

I know that the $\mathrm{Pdim}(\mathcal{A}) = 2$. From my understanding the $\mathrm{Pdim}(\mathcal{H})$ is also equal to 2 as I can find $\{x_1, x_2\}$ and $z_1, z_2$ such that for all subsets $T \subseteq \{x_1, x_2\}$, there is a function $f \in \mathcal{H}$ such that $\forall x \in T, f(x) \geq z_1$ and $\forall x \notin T f(x) < z_1$.
Is my intuition correct?

I am using the definition of pseudo-dimension found here, page 10 of the pdf.
Denote $h_1(x) = 2x+1$, $h_2(x) = 4x$, $h_3(x) = x$ and $h_4(x) =3x+4$.
Let's consider $C = (-2, 2)$ a vector. Then $r = (-2.5, 6)$ is a witness that proves that $C$ is pseudo-shattered by $\mathcal{H}$:

$h_1(-2) = -3 <-2.5$, $h_1(2) = 5 <6$;
$h_2(-2) = -8 <-2.5$, $h_2(2) = 8 >6$;
$h_3(-2) =  -2>-2.5$, $h_3(2) = 2<6$;
$h_4(-2) = -2 >-2.5$, $h_4(2) = 10 >6$.

Clearly $\text{Pdim}(\mathcal{H})< 3$ since the pseudo-dimension cannot be greater than $\log_2 |\mathcal{H}|$.
That proves that $\text{Pdim}(\mathcal{H}) = 2$.


Unary in $P$, binary not in $P$ I would like to know if there is a known decision problem with the following characteristics:

Represented in unary, the problem is decidable in polynomial time.
Represented in binary, the problem is not decidable in polynomial time (and this fact has been proved, not just conjectured).

For example, Subset-Sum is in $P$ when represented in unary, but it is $NP$-complete in binary. However, this problem does not satisfy my second requirement because we do not know whether $P=NP$.

Every single-exponential (i.e. known to be solvable in $O(c^n)$ for some constant $c$) EXPTIME-complete problem will answer your requirements.

For example, see checking thorough rerefinement on finite modal transition systems.


What are the current known implications of the complexity of Integer Factorization? According to my limited knowledge we know that since Integer Factorization lies in the intersection of NP and co-NP it cannot be NP-complete unless NP=co-NP.  However, do we know any other implications yet- like if P != NP, does this mean that Integer Factorization is necessarily not in P?  Conversely, if Integer Factorization is in P, does this imply anything about the polynomial hierarchy?  Thanks.

Before answering your questions a distinction has to be made, when talking about $NP$ completeness we are talking about the decision problem not the function problem, which is given an integer N and an integer M with 1 ≤ M ≤ N, does N have a factor d with 1 < d < M.

So answering your questions in order, Since integer factorization is not known to be NP complete, $P \neq NP$ would not cause it to automatically not be in $P$ since quite often things that were thought to be in $NP$ are moved to $P$, only an $NP$ complete problem would be excluded from being in $P$. For the second one, again since it is not $NP$ complete a polynomial time solution to it will not effect the hierarchy for the same reason as before.

As an extra note, the actual location of factorization in the hierarchy is unknown, we know is is $BQP$, $NP$, $co-NP$, $FNP$ and $UP$. It may end up being $NP$-Intermediate, but no one knows for sure.


on coq: Why is the proof complete after proving only for one induction when we have more than one variable? So I'm learning coq. And I came across the proof for associativity in addition forall (a b c : nat)

Appearntly when we do induction a. after intros a b c., it creates 2 subgoals

and afterwards we simply need to show that the two sides in both subgoals are equivalent, and the proof is completed.

So I'm just wondering why we don't need to do induction b. and induction c. to complete the proof? Why only performing induction on a is able to complete the proof?

Or in other words, how come in the function that returns the proof, we just get b and c for "free"? Constructively don't we need something like a double induction applied twice?

You do not have to prove things by induction. For example, you can prove $\forall n : \mathbb{N} \,.\, n = n$ without induction by applying reflexivity. In your proof, we use induction on $a$, but then we do not need to use induction on $b$ and $c$ because we can finish the proof simply using other methods. We could have used induction on $b$ and $c$, and you should try to do so, to see how unecessary applications of induction just make your proof longer and less clear.

P.S. This has absolutely nothing to do with constructivity.


How to find every negative cycle in a graph A graph with n vertices, no matter directed or not, may have maximally 2^n-n-1 negative cycles
(Think about combination of 2 to n elements and you'll figure out why 2^n-n-1. A graph that has no graph loops or multiple edges is my only concern)
and I want to find ALL of them if any, not just one of them. There are only answers to the latter question throughout the whole internet. To find a cycle means we get a list of vertices which form this cycle.
I also want to find the one negative cycle which is the smallest in one lap of traverse.
One solution, which is slow and not elegant, is to run Floyd-Warshall algorithm on the graph, and find those vertices, e.g. i, so that d[i][i]<0 (According to some researches collected in Wikipedia, this means vertex i is part of a negative cycle) and then check all 2^n-n-1 (if there are n of those i's) cycles to see if they are negative.

First of all, there can be exponentially many negative cycles, as @Steven already mentioned.  Take $K_n$ with only negative edges.  Enumerating all of them will be bound to take exponentially long time.
You also say that you want to find the most negative cycle in the graph (which should be simple if you enumerate them all), however, in case you want a special algorithm for this problem, note that this problem is NP-complete; the reduction from Hamiltonian is straight forward.
Since you ask for any algorithm, just run, for every subset of vertices, a DP algorithm to find the Minimum Hamiltonian Cycle for that induced subgraph.  (Since you don't want to revisit an edge, you can probably find a way to add $\min_{e \in E(G)} w(e)$ to every edge, thereby avoiding all the negativity.)
(P.s., OP stated in a comment that cycles on the same vertex set are considered equivalent.)


Turing machine and language decidability The document I am reading is here: Turing Machines

Before getting into the question, here is the notation used on the picture:

  Here $\Delta$ denotes the blank and R, L and S denote move the head right, left
  and do not move it, respectively. A transition diagram can also be
  drawn for a Turing machine. The states are represented by vertices and
  for a transition $\delta( q, X ) = ( r, Y, D )$ , where D represents R, L
  or S , an arc from q to r is drawn with
  label ( X/Y , D ) indicating that the state is changed from q to r,
  the symbol X currently being read is changed to Y and the tape head is
  moved as directed by D.

According to the document:

  A Turing machine T is said to decide a language L if and only if T
  writes "yes" and halts if a string is in L and T writes "no" and halts
  if a string is not in L

Here is the three examples:

Case 1:

Case 2:

Case 3:

I just want to verify my understanding. According to the definition, in case 1 and case 2, its turing machines cannot decide because the machines cannot tell whether invalid inputs rather than { a } (such as aa, aaa, aaaa....) is in L or not.

In case 2, if another a appears after the first a, or if the input is empty, the machine goes to state S and loop forever.

In case 3, if a is detected and only a single a exists, that a is replaced by 1 and the machine accepts. Otherwise, a 0 is replaced and the input is decided not in the language.

Am I correct on all of these? However, in case 3, what if I give any input which contains other character rather than a (such as string ab, bc...)? Or is it said that TM decides only languages over a set of alphabet $\Sigma$ allowed by the Turing Machine?

If a string which is longer than a single a (like aa, aaa,ab,bc...), the machine may loop forever (like in case 2) or halt without accepting (in other words, it is "crashed", where it does not have transition rules for a symbol in the input such as b in the case of above Turing Machines). Is this correct also?

A TM decides a language if it enters the accepting state for word in the language and it enters the rejecting state if it is not. Thus it halts on all inputs. Note the machines defined above are not entirely standard. They way they denote acceptance and reject is by writing a $1$ or $0$ and then by entering a halting state. This is equivalent to the standard definition, but less elegant.

Machine 1 does not reject words not in the language. It only accepts the language.

Machine 2 does not halt for words not in the language. It only accepts the language.

Machine 3 rejects and hence halts for words not in the language, therefore it decides the language.


"At least one" clause in Relational Algebra I'm fairly new to the syntax of relational algebra, and I'm having a hard time understanding how I could set a "at least one" clause.

Example: I have:

a table with books (listing the title, year published and ID),
a table with authors (listing their name and ID),
a table which lists what author wrote what book (through a tuple of the IDs mentioned before).

How could I, in relational algebra, get "All the authors that have published at least one book per year between 2008 and 2010"?

I have figured this so far. At step "b", the Natural join is used since both tables have PublicationID in common. Thus, the resulting table is |PublicationID|AuthorID|Year|. So I'm simply missing the step "c", where I don't understand how to gather a sub-set of the authors that published at least one book per year between 2008 and 2010.

$ a \leftarrow \pi_{PublicationID,Year} (Publication)$

$ b \leftarrow a \bowtie AuthorPublication $

$ c \leftarrow \sigma_{something} $

A first hint toward a solution is to think about "what's the result of a natural join between $Author$, $Publication$ and $AuthorPublication$?"
The answer is "the universal relation" $R(BookID,AuthorID,Title,Year,Name)$ describing who wrote a book and when. Note that a book without any author or an author without any book written won't appear in $R$. So an author in $R$ as written at least one book. The following query gives the authors who wrote at least a book in year 2008:
$$ \pi_{Name}(Author \Join AuthorPublication \Join \sigma_{(2008 =  year)}(Publication))$$

For the final answer, compute the intersection of this query with its variants:
$$ \pi_{Name}(Author \Join AuthorPublication \Join \sigma_{(2008 =  year)}(Publication)) \cap \pi_{Name}(Author \Join AuthorPublication \Join \sigma_{(2009 =  year)}(Publication)) \cap \pi_{Name}(Author \Join AuthorPublication \Join \sigma_{(2010 =  year)}(Publication))$$

You may provide other equivalent answers with outer $Author \Join$.


How does machine learning relate to artificial intelligence? For example, is it a subset?

Are they two separate fields in Computer Science?

I have hear conflicting information: one professor said they are synonyms. However, in the courses taught at Stanford CS they are two distinct classes:

CS221 (Artificial Intelligence)

and

CS229 (Machine Learning)

Machine Learning is a subset of (the scientific field of) Artificial Intelligence.

What is ML?

Machine Learning is defined by Tom Mitchel:

  A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P if its performance at tasks in T, as measured by P, improves with experience E.

Hence: When you write an algorithm that gets better the more data you give it, then you can call it ML.

What is AI but not ML?

SLAM
Path finding: Bellman–Ford algorithm, A* search algorithm, Dijkstra's algorithm
Markov chains
cellular automata
Logic: Although a lot of people (e.g. Pedro Domingos) include logic approaches (e.g. with inverse deduction) in Machine Learning, I would rather say it is AI.

Fuzzy logic (see Fuzzy logic vs AI vs Machine learning vs Deep learning)
Knowledge representation / Formal systems

See also

Difference between machine learning and artificial intelligence


Average time to solve maze through backtracking Given a set A consisting of all possible solvable mazes on an n by n square grid, what is the average running time to solve the mazes in A using a standard backtrack algorithm with no optimizations?

The algorithm checks each ajacent space clockwise for a channel, then visits each channel and either marks it off if it encounters a dead end, or previously covered point, or if it reaches the end point the algorithm completes.

This question was on an exam, and I figured O(n^2) cause there is O(n^2) spaces to visit for each maze, but my prof insisted the correct answer could be O(n log n).

A proof would be greatly appreciated.

Thanks!

Your question on the exam is asking for average case analysis -- visiting all the cells to solve the maze is the worst case.

Informally think this way: Whenever you move to a new cell, you can move to at maximum 3 directions, which one direction is to go back to your previous cell (this choice is discarded since it's of course not what you want to do to explorer the maze.) In the two other options left, one of the direction will lead you to the target, the other one does not. What's the expectation of find the target in each move? Does it hint something $O(n \log n)$?

Also try to picture this as you are exploring a tree structure. What's the average height of a tree?


Is it possible to simplify $O(A \times B \times C + A^B)$ into $O(A^B)$ I am wondering if it is possible to simplify $O(A \times B \times C + A^B)$ into $O(A^B)$, i.e. omit the left part. $A$, $B$, and $C$ are all independent from each other.

Personally, I think that the simplification is possible. $O(A \times B \times C)$ is a polynomial growth, and (I think) it can be rewritten as $O(A^3)$, $O(B^3)$, or $O(C^3)$. On the other hand, $A^B$ is a exponential growth. As a result, it is possible to omit the left part from the Big O notation.

In other to test my hypothesis, I develop a simple simulation to compare $A \times B \times C$ with $O(A^B)$, the value of $A$, $B$ and $C$ range from 1 to 1000. According to my simulation, there are only $3\%$ chance that $A \times B \times C \geq A^B$. It is enough to omit $A \times B \times C$ from $O(A \times B \times C + A^B)$?

No, it is not possible. The function $ABC$ is $O(ABC + A^B)$ but not $A^B$, since for no $M$ is it the case that $ABC \leq MA^B$ for large enough $A,B,C$; for any "large enough" $A,B$, this would imply that $C = O(1)$ is bounded, but $C$ need not be bounded.