texts: Polynomial time algorithm for finding a maximal monotone subset

texts:
Input:
Some fixed $k>1$, vectors $x_i,y_i\in\mathbb R^k$ for $1\le i\le n$.
Output:
A subset $I\subset\{1,\dots,n\}$ of maximal size such that
$(x_i-x_j)^T(y_i-y_j) \ge 0$ for all $i,j\in I$.
Question:
Can this be computed in polynomial time in $n$?
Remarks:

For $k=1$ this is equivalent to the problem of finding a longest increasing subsequence. Indeed, assuming that $x_1<\dots<x_n$, we search for a longest increasing subsequence of $y_1,\dots,y_n$. Such a subsequence can be found in $O(n\log n)$.
The problem is related to the notion of a monotone operator $F:\mathbb R^k\to\mathbb R^k$. Monotonicity of $F$ means that $(x_1-x_2)^T(F(x_1)-F(x_2))\ge 0$ for all $x_1,x_2\in\mathbb R^k$.
The problem can be formulated as a search for a maximum clique in the graph $G=(V,E)$ with vertices $V=\{1,\dots,n\}$ and edges
$E = \{(i,j) \;:\; (x_i-x_j)^T(y_i-y_j)\ge 0 \}$.
The general clique problem is NP-complete.
However, it might be possible to exploit the special structure of $E$ (as shown in the first remark, this is possible when $k=1$).

I would appreciate any hint or comment on this problem.


texts: CNNs: Why do the filters identify more complex features as the model goes on?

texts: I have a feeling that it's related to how different output layers are stacked up against one another? However, there's a missing link in that argument that I can't completely get to.


texts: Retrieving data from hash table ordered by insertion time

texts:
By default, a hash table is unordered.  I have a simple question on the retrieval of elements in a hash table

  Can we retrieve elements from a hash table in the same order as they are put inside?


texts: Minimum Length Hamiltonian Path Pair in O(n^2) or better

texts:
A friend and I have been discussing turning a $O(n^2)$ graph problem's algorithm into $O(n\log n)$, or at least less than $O(n^2)$. And no - this is not a homework question. We've narrowed it down to the following subproblem:

Let $A,B,P,$ and $Q$ be a group of 4 nodes, with coordinates $(x_A,y_A),(x_B,y_B)$,etc... such that:

$x_A$ and $x_P$ are less than both $x_B$ and $x_Q$
$y_A$ and $y_B$ are greater than $y_P$ and $y_Q$.

Let there be an arbitrary cluster of nodes contained within the quadrilateral formed by $A,B,P,$ and $Q$. Find a pair of paths $A\rightarrow B$ and $P\rightarrow Q$ such that:

Every node in the cluster is hit by exactly one of the two paths
The two paths have the minimum possible total (Euclidean) length
The two paths do not intersect
The paths always increase in $x$. That is, if we enumerate path $A\rightarrow B$ as $\{A,(x_1,y_1),(x_2,y_2), ...(x_n,y_n),B\}$, then   $x_i<x_j$ for $0<i<j\leq n$. Also, $x_A<x_1$ and $x_n<x_B$. This property must hold for the $P\rightarrow Q$ path as well.

It is also worth mentioning that no two nodes in the entire problem will have the same $x$ coordinate.

I'm positive some geometric trick will play a huge role in finding the solution. Keep in mind this is just a subproblem and a solution to this in $O(n^2)$ will still be helpful - though I'm hoping for $O(n\log n)$.

Here's an example problem for clarity:

Any solutions or even helpful ideas are always appreciated. Diagrams are also very much appreciated.

Finally, for added clarity, here is what a sample solution might look like:


texts: Separating numbers with a minimal difference

texts:
Given is a positive integer integer $n$, and integers $a_1,b_1,\dots,a_n,b_n$ with $ a_i\leq b_i$ for each $i$. What is the complexity of deciding whether there exist integers $c_1,\dots,c_n$ such that $a_i\leq c_i\leq b_i$ for all $i$ and $|c_i-c_j|\geq 2$ for all $i,j$?

What can be observed is that a greedy algorithm, wherein we assume that $a_1\leq\dots\leq a_n$ and choose $c_i$ according to this order, does not necessarily work. For example, we may have $a_1=1, b_1=4, a_2=b_2=2$. Putting $c_1=1$ does not work (it leaves no room for $c_2$), but what works is putting $c_1=4$ and $c_2=2$. Is the problem perhaps NP-hard?


texts: Union of a language in P and a language in NP\P

texts:
TRUE or FALSE Statement:

  Assume that $P \neq NP$. Then, for all languages $L_1$ and $L_2$, if $L_1$ is in P and $L_2$ is in NP but not in P then $L_1 \cup L_2$ is in NP but not in P.

I have a doubt about the point: $L_1 \cup L_2$ is in NP but not in P.

I know P is a subset of NP, then $L_1 \cup L_2$ is in NP (because $P \subseteq NP$), but the sentence "is in NP but not in P"
it puzzles me.


texts: Matching elements of two sequences: choosing the best one

texts:
I have the following problem.

Let $P$ and $Q$ be two ordered sequences of time instants. $[p_0,p_1,\ldots,p_n]$ and $[q_0,q_1,\ldots,q_m]$ are the elements of $P$ and $Q$ respectively.
A first constraint on the elements of those sequences is $p_i \in \mathcal{R}$ and $p_i < p_{i+1}$ (the same applies for $q_i$)

From $P$ and $Q$ a sequence $R$ can be obtained. $R$ is a sequence of sets of elements of $P$ and $Q$:  $[r_0,r_1,\ldots,r_n]$. As $P$ and $Q$ are sequence of time instants, $R$ is a sequence of time intervals.

There are a few constraints on the sets $r_i$:

They must contain elements of both $P$ and $Q$
They must contain at most one element of $P$ or at most one element of $Q$. For example, $(p_0,p_1,q_0)$ is valid, but $(p_0,q_0,q_1,p_1)$ is not
Sets must not overlap: if $p_0 \in r_i$ then $p_1 \in {r_i,r_{i+1}}$ (the same for Q), and $max(r_i) < min (r_{i+1})$.

I'm stuck on this point: the output sets $r_i$ should be as precise as possible, meaning that the interval as to be the as tight as possible. So I have to define a metric that can be used to select the best sequence $R$ among all the achievable from two sequences $P$ and $Q$. The precision of a set $t(r_i)$ is defined as $max(r_i)-min(r_i)$

For example:let $P$ be $[0,2,6]$ and $Q$ be $[1,5,7]$. According to the aforementioned rules, two possible sequences $R$ are possible:

$R_0=[(0,1,2),(5,6,7)]$
$R_1=[(0,1),(2,5),(6,7)]$

What metric should be used to select the best between $R_0$ and $R_1$?
$R_0$ minimizes $\sum_i t(r_i)$ and seems to have better properties compared to $R_1$ (it correctly states that in both $P$ and $Q$ there aren't time instants between 2 and 5. However, $R_1$ has a lower mean value (1.67 vs 2).


texts: Why can't I evaluate this L-Attributed SDD with a pre-order traversal?

texts:
My powerpoints for a compiler class says "an L-Attributed SDD can be evaluated with a pre-order (root, left, right) traversal", and to be L-Attributed the nodes need to have either synthesized values or inherited values from a parent node or a sibling node on the left or itself (sorry if it's unclear, it's originally in another language). All SDD based on an LL(1) grammar are L-Attributed. So for example this grammar with the semantic rules
1. T --> FT'
2. T' --> *FT'
3. T --> epsilon
4. F --> digit

1. T'.inherited_val = F.synthesized_val, T.synthesized_val = T'.synthesized_val
2. T'.inherited_val = T'.inherited_val * F.synthesized_val, T'.synthesized_val = T'.synthesized_val
3. T'.synthesized_val = T'.inherited_val
4. F.synthesized_val = digit.lexical_val

here's the parse graph:

If we do left-right-root, then the order of the semantic rules being executed would be

F_1.synthesized_val = 2
T'_1.inherited_val = 2
F_2.synthesized_val = 3
T'_2.inherited_val = 3
F_3.synthesized_val = 5
T'_3.inherited_val = 5
T'_3.synthesized_val = 5
T'_2.synthesized_val = 5*3 = 15
T'_1.synthesized_val = 15*2 = 30
T.synthesized_val = 30

However a preorder traversal (root-left-right) would just produce an error as all the values root (T) needs would be undefined.
What am I missing here?
Thanks


texts: If hypothesis class is agnostic PAC-learnable it is PAC-learnable

texts:
I'm trying to prove formaly this claim, given that $\mathcal{H}$ is a hypothesis class of binary classifiers.

According to the definition, Hypothesis class $\mathcal{H}$ is agnostic PAC-learnable with respect to $ \mathcal{Z}=\mathcal{X}\times \mathcal{Y}$, if exists a function $ m_\mathcal{H}:(0,1)^2\rightarrow \mathbb{N}$ and algorithm $\mathcal{A} $, such that for every distribution $\mathcal{D}$ over $\mathcal{Z}$ - $ \mathbb{P}_{S\sim \mathcal{D}^m}[L_\mathcal{D} (\mathcal{A}(S))\leq min_{h\in \mathcal{H}}(h) +\epsilon ]\ge 1- \delta$.

Proving effort-

Assuming that that the target function $f\in \mathcal{H}$, i know
that $min_{h\in \mathcal{H}}(h)=0.$
Lets look at the set $\{(x,y)|f(x)=y\}$. Obviously $\mathcal{Z}'\subseteq\mathcal{Z}$.
Suppose $ \mathcal{D}'=\mathcal{D} |_{\mathcal{Z}'}$.

Is it sufficent to show that $\mathcal{Z}$ - $ \mathbb{P}_{\mathcal{D}'^m}[L_{\mathcal{D}'} (\mathcal{A}(S))\leq\epsilon ]\ge 1- \delta$? If yes, why?

Assuming that it may be sufficent, how can i show that given $S\sim \mathcal{D}^m$, the event $ \{L_\mathcal{D} (\mathcal{A}(S))\leq min_{h\in \mathcal{H}}(h) +\epsilon \} $ equals to the event  $\{L_{\mathcal{D}'} (\mathcal{A}(S))\leq\epsilon \}$ and this complete the proof -

According to the first bullet: $ \{L_\mathcal{D} (\mathcal{A}(S))\leq min_{h\in \mathcal{H}}(h) +\epsilon \} $ =$ \{L_\mathcal{D} (\mathcal{A}(S))\leq\epsilon \} $. But what is the relation between $L_\mathcal{D} (\mathcal{A}(S))$ and $L_\mathcal{D'} (\mathcal{A}(S))$.


texts: Can Turing Machines solve non-decision problems?

texts: Since TMs are equivalent to algorithms, they must be able to perform algoriths like, say, mergesort. But the formal definition allows only for decision problems, i.e, acceptance of languages. So how can we cast the performance of mergesort as a decision problem?


texts: What does it mean that HDLs "explicitly include the notion of time"?

texts:
I got onto the topic of HDLs (Hardware Description Languages) from a comment elsewhere on this site.

The Wikipedia article states, rather tantalizingly:

  One important difference between most programming languages and HDLs is that HDLs explicitly include the notion of time.

I tried to dig deeper in the article to better understand this statement, but I didn't get far.

One thing I did find was this great diagram of a flip flop, which certainly demonstrates the need to consider timing in hardware design.  Rather than dealing with explicit on/off states, you are also dealing with high/low voltage propagation.

Naively, though, my immediate thought was, "Huh?  All imperative languages include the notion of time.  Only declarative or functional programming languages could be said to exclude the notion of time, and only by certain specific interpretations."

I think there is a valid point being made here, though, and I would very much like to better understand it.  It's even stated to be an "important" difference.  :)

So, again, what does it mean that HDLs "explicitly include the notion of time"?  How does that distinguish them from programming languages in general from a CS standpoint?


texts: How to approach Vertical Sticks challenge

texts:
This problem is taken from interviewstreet.com

We are given an array of integers $Y=\{y_1,...,y_n\}$ that represents $n$ line segments such that endpoints of segment $i$ are $(i, 0)$ and $(i, y_i)$. Imagine that from the top of each segment a horizontal ray is shot to the left, and this ray stops when it touches another segment or it hits the y-axis. We construct an array of n integers, $v_1, ..., v_n$, where $v_i$ is equal to length of ray shot from the top of segment $i$. We define $V(y_1, ..., y_n)
= v_1 + ... + v_n$.

For example, if we have $Y=[3,2,5,3,3,4,1,2]$, then $[v_1, ..., v_8] = [1,1,3,1,1,3,1,2]$, as shown in the picture below:

For each permutation $p$ of $[1,...,n]$, we can calculate $V(y_{p_1}, ..., y_{p_n})$. If we choose a uniformly random permutation $p$ of $[1,...,n]$, what is the expected value of $V(y_{p_1}, ..., y_{p_n})$?

If we solve this problem using the naive approach it will not be efficient and run practically forever for $n=50$. I believe we can approach this problem by indepdently calculating the expected value of $v_i$ for each stick but I still need to know wether there is another efficient approach for this problem. On what basis can we calculate the expected value for each stick independently?


texts: Showing an equivalent definition of $CO-RE$

texts:
Let $L_1$ be a language.

I would like t prove that $L_1\in CO-RE$ if and only if exists a language $L_2$ s.t. $L_1=\{ u\,\, |\,\, \forall_{v\in\Sigma^*} : <u,v>\in L_2  \}$ and $L_2\in R$.

I'm not quite sure on where do I start here from?

I've tried writing down what I know and trying to develop any ideas, but got stuck at the very begining.

Since $L_1\in CO-RE$ then $\overline{L_1} \in RE$. That is, exists a TM $M$ s.t. $M$ accepts any $u\in \overline{L_1}$ (that is $u\notin L_1$) and either rejects or loops forever for $u\in L_1$.

But I dont see how does this assist me to construct such a language $L_2$ that will both be in $R$ and assist me?

And even if I do succeed, how am I to show the other way around - that if such a language $L_2$ exists that satisfies the above conditions, $L_1\in CO-RE$?


texts: Problem with understanding the lower bound of OPT in Greedy Set Cover approximation algorithm

texts:
From what I know of analyzing and designing approximation algorithms, we need to find a lower bound on the optimum (in the case of minimization). For example if our solution is greedy ($SOL_G$) and if we find a lower bound $L_B$ on $OPT$ then $$L_B \leq OPT$$

and if we correctly analyze the following $$SOL_G \leq f . L_B$$ Then we can conclude that $$SOL_G \leq f. OPT$$ where $f$ is the approximation factor of our greedy solution.

Vijay Vazirani in his book approximation algorithm on page 16 proposed the Greedy Set cover and his analysis of the lower bound on the optimum (Lemma 2.3). I have problem with understanding this Lemma:

From his convention at the beginning of the book, $OPT$ stands for the optimum solution of the problem instance (not the optimum that is obtained by the approximation algorithm).

At the beginning of the Lemma he says

  In any iteration, the leftover sets of the optimal solution can cover the remaining elements at a cost of at most OPT

It is clear because $\sum_{e \in U} price(e) = OPT$. (The price assignment is based on the selection of the sets)

In the next sentence he says

  Therefore, among these
  sets, there must be one having cost-effectiveness of at most $OPT/|\bar{C}|$ where $\bar{C} = U - C$

and $C$ is the current list of selected sets.

I can't understand, why is it true? $OPT$ is the optimum of problem instance not the algorithm. Because in the algorithm the price of each set is distributed among its elements, it seems he uses this fact but $OPT$ is not about the algorithm! it is the optimum of problem instance

Thanks.


texts: What is the time complexity for getting the size of a heap?

texts:
Assuming the regular Heap ADT.

What is the time complexity of getting its size ?

I tend to think that because insert is O(log(n)), then I always know the last index of my heap. So in order to get its size all I need is to return the last index + 1.

However I have seen in some places that refer to the size of the heap's complexity as O(n), since I need to count all the nodes in my heap.

Why am I wrong ?


texts: Is it decidable to know the number of positions used by a Turing machine for a fixed input?

texts:
I'm having trouble proving if the following language is recursive, recursively enumerable, or not r.e. at all: the set of all encodings of Turing machines $M$ such that the number of positions in the tape used by $M$ when the input is 0011 is less than 10.

I'm suspicious the problem is unrecognizable but I can't come up with any reduction to prove it. Any help would be appreciated.


texts: What is the complexity class of solving hash decision problems?

texts:
With $hash_n$, I mean a standard cryptographic hash like sha256, scaled up to have arbitrary length $n$ of its output with the same underlying principles. What is the time complexity class of the following problem?

  Given an $n \in \mathbb{N}$ and data $d$ with $length(d) = n$, determine whether $\exists p : ((length(p) \le n) \wedge (hash_n(p) = d))$.

I find it really hard to find a class for it because it seems like a hard problem and it's definitely not $\in P$ (except if $P = NP$ or there is a vulnerability of the hash function (assume there isn't one not already known (so sha256 basically just printing the state of a state machine can be used, of course))) but you can't use it to solve any of the classical NP hard problems.

Determining the space complexity is of course trivial: It's only $\mathcal{O}(n)$.

This is of course just one example of a hash decision problem and it's meant to only be an example. I'm more interested in the general classification of hash decision problems.

Edit: You may assume a perfect hash function instead of a commonly used cryptographic hash function. E.g. if you're more comfortable with it, you don't want to exploit properties of cryptographic hash functions which are commonly used in practice, what you want to show is threatened by those properties, etc.


texts: Query: Given a graph, is edge x in an optimal TSP tour?

texts:
Consider the decision problem that when given a graph, we need to decide if a particular edge belongs to any optimal solution to the traveling salesman problem on that graph.

It may be argued that the complexity of this problem is strictly greater than any co-NP problem. The idea is that it's perhaps impossible to come up with a counter-example, since we need e.g. an optimal tour candidate before we can consider a counterexample (but no optimal tour candidate is given in this problem statement).

On the other hand, it may be argued that the complexity of this problem is strictly smaller than any P-space-complete problem, as our problem may be seen as

$\exists$"a tour A containing x" $\forall$"tours B": (some formula stating that A <= B)

whereas some probably "minimal" P-space-complete problem has O(n) alternations of $\exists$ and $\forall$: the quantified boolean formula problem (QBF).

Based on this argument, is it reasonable to expect that there's a complexity class between co-NP and PSPACE? Does this particular class have a name? Can we expect to find arbitrarily more such classes by adding another one alternation of $\forall$ or $\exists$ to the previously found such class?


texts: For arbitrary RR(1) grammar $G$, is there an equivalent LL(1) grammar $G'$?

texts:
Failed to find similar term, here I coin the noun RR(Right-to-left, Rightmost derivation) as an opposite concept of LL.

The question is inspired by an interesting example grammar $G$:
$$S \rightarrow S S + | a$$
It's obviously an RR(1) language. After some time to explore, I find an equivalent LL(1) grammar:
$$
\begin{array}{l}
S \rightarrow a A \\
A \rightarrow S + | \epsilon
\end{array}$$

So, there seems a road to more generalized conclusion. Consider arbitrary RR(1) grammar, is there an equivalent LL(1) grammar $G'$, where equivalent means $L(G) = L(G')$?


texts: Machine learning approach to auction game

texts:
I am newbie with machine learning. In order to learn more I decided to try solving a specific problem/game that I have in mind. The problem is the following:

I have a list of $N$ items which are auctioned in a random sequence. There are $n$ participants to the auction. They have a fixed budget and $M$ items to buy. Each agent will decide whether to make a bid and how much to bid each time a new  item is auctioned; bids have to be integer numbers and the agent with the highest bid gets the item; correspondingly its budget is decreased of the amount of the bid. Items, once bought, cannot be released, so if an agent has already bought $M$ items, it cannot participate to other auctions. If nobody places a bid, the item is discarded and the auction continues with the next one. Thus, an agent ends its auction if it has bought $M$ items or the available budget has reached $0$.

At the end, the value of the final set $I$ of items items bought by each agent is evaluated by an external oracle function $f(I)$.  The function is not explicitly known and will in general be more complicated that the sum of values of each item, e.g. two items may be essential parts of a single object and are worthless one without the other. However, it is known that
$$ f(I \cup J) \geq f(I) + f(J).$$
Each agent is free to evaluate the function $f$ on any set of items.  Each agent's goal is to maximize the value of $f(I)$, where $I$ is the set of items successfully bought by that agent.

Which strategy would you suggest to approach this problem?
At each time, the agent has information about the list of items that have been auctioned, which participant has bought each of them and the costs, so that it knows the number of available slots and budget of each participant. According to these data, it must decide if and how much to bid for each item. Note that the list of items is fixed and the function $f$ are fixed.
I suppose this is a reinforcement learning question but I don't have a clear understanding of how the input would be structured in this case.


texts:
I am struggling with a specific question regarding complexity classes. The question goes as follows:
There are three languages A,B,C so that:

A is NP-complete

B is in P

C is polynomial time reducible to A $\triangle$ B (symmetric difference)

Which of the following statements is valid:

C is in P

C is in NP

C is in coNP

C is in NP $\cap$ coNP

I was able to determine that C is in NP due to the polynomial time reducibility but am unsure about the other statements.


texts:
Given an universum $U$ and two sets $A$ and $B$ of sets of elements from $U$. I want to find (if such a pair exists) $a \in A$ and $b \in B$: $a \cap b \equiv \emptyset$. Currently I can do it only in $O(|A| \cdot |B| \cdot |U|)$, is there way to improve this?
Say, $|U| \leq 32$. Is there a way to speed algorithm up?
If it matters, one can assume, that all elements in $A \cup B$ are unique. Another variation of the problem is $A \equiv B$ and there is a need to search $a$ and $b$ from the single set.


texts:
If $L_1 = \emptyset$ , $L_2= \{a\}$
then what is $$L_1\cdot L_2^* \cup L_1^*$$

The answer given is $\{\epsilon\}$ but I think it should be $\{\epsilon,a\}$.
My Approach :
$L_1^* = \{\epsilon\}$
$L_2^* = \{\epsilon,a\}$
$L_1\cdot L_2^* = \{\epsilon,a\}$
$L_1\cdot L_2^* \cup L_1^* = \{\epsilon,a\}$.

Where's my mistake?


texts: This figure says according to moore's law number of transistors doubles about two years. but clock speed, power flattening after given stage. can anyone describe the reasons this flattening in clock-speed. Why can't we increase the clock speed more and more?


texts: What happens with register usage in deeply nested functions calls (in theory)?

texts: I am far from being able to construct a meaningful test for this using godbolt or some C compilation tool. But basically I am wondering what it would look like to have deeply nested function calls, where each function had let's say a dozen temporary variables throughout. What happens to register usage? It seems like everything would have to be stored in memory and the register usage would almost be negligible. What is it like in reality? Where am I going wrong?


texts: Find the minimum set of intervals for given set of numbers

texts:
For any given set of real numbers, find the minimum set of intervals with length 1 that include all elements. For example, for the set: $${\{1.5,2.3,2.4,2.5,2.8,3.3,3.6,3.8}\}$$
the answer is $${\{[1.5,2.5],[2.8,3.8]\}}$$

On the example above $[1.5,2.5]$ is an interval with length $1$ ($2.5-1.5=1$). And there are 2 sets of intervals ($[1.5,2.5]$ and $[2.8,3.8]$).

I need to find the most efficient greedy algorithm for this problem with $O(n\log n)$ time complexity.

My thought is to sort the elements in ascending order (using merge sort for minimum time complexity) and then, starting from the first element, use the current element as the lowest limit, and (element+1) as the highest limit.

This has a running time of $O(n\log n + n)$. $n\log n$ from mergesort and $n$ for running through the elements to decide the intervals.

But I can't tell whether this is the most efficient greedy algorithm I can use for this problem.


texts: How hard is this constrained $n$-rooks problem?

texts:
I asked this over on math.stackexchange.com, then I found out about this forum.

Suppose you have an $(n\times n)$-chessboard, together with a constraining function $C : n \times n \to 2$ where $C(i,j) = 1$ iff you're allowed to place a rook in the $ij$-square.  Consider the problem:

  Can $n$ non-attacking rooks be placed on the board in squares allowed by $C$?

Is it NP-Hard?

Here's an alternative formulation: Let $x_1, \dots, x_n$ be elements (integers, say) and $P_1, \dots, P_n$ unary predicates such that $P_ix_j$ can be evaluated in constant time.  Is there a permutation $\sigma \in S_n$ such that $P_ix_{\sigma(i)}$ for all $i$?

The equivalence can be seen by letting $C(i,j) = 1$ iff $P_i(x_j)$.  Then a placement of rooks yields a witness to the permutation problem by letting $\sigma(i) = j$ iff there's a rook in square $ij$.  $\sigma$ is a permutation because all $n$ rooks are placed in a non-attacking arrangement.  $P_ix_{\sigma(i)}$ holds because $\sigma(i)=j$ implies theres'a  rook in the $ij$ square, which implies $C(i,j) =1$, which, by definition, implies that $P_i(x_j)$.


texts: I read the Wikipedia entry about "List of NP-complete problems" and found that games like super mario, pokemon, tetris or candy crush saga are np-complete. How can I imagine np-completeness of a game?  Answers don't need to be too precise. I just want to get an overview what it means that games can be np-complete.


texts: Robustness of Turing Machines - 3 dimensional case

texts: How can one show that a machine with a three dimensional memory arranged in an infinite grid can be simulated by a single-tape Turing machine? I'd imagine there's some sort of mapping possible from three dimensional coordinates to single coordinates (eg. (0,0,0) -> 0, (1,0,0) -> 1, (-1,0,0) -> 2, ...) but I can't figure it out. Or maybe there's some clever way to separate the points using special symbols. Either way, I'm at a loss.


texts: Goemans' Extended Formulation of the Permutahedron And Comparator Networks that are not Sorting Networks

texts:
I am interested in using Michel Goemans' extended formulation first developed for the permutahedron to study comparator networks that are not sorting networks.  In his paper "Smallest Compact Formulation for the Permutahedron" (An online version is available here http://math.mit.edu/~goemans/PAPERS/permutahedron.pdf), he shows that any sorting network can be used to obtain an extended formulation for the permutahedron. This is done by expressing each comparator in the network by a set of linear constraints.

In another paper, "Extended Formulations in Combinatorial Optimization," Conforti et al. discuss this formulation and show that it can also be applied to any comparator network, sorting networks being a special case (It's Theorem 6.8 in Section 6.5 in the version of the paper shown here http://integer.tepper.cmu.edu/webpub/ExtFor-Feb2010.pdf).  I am interested in using this extended formulation to look at a specific class of comparator networks.

My question is this (basically a sanity check to make sure I understood the proof correctly and that it is valid).

Can the extended formulation developed by Michael Goemans be applied to comparator networks that are not sorting networks such that in every vertex the input to the network will be a permutation of {1, 2, ... n} that the comparator network will sort?  I believe that's what the proof in Conforti et al says but I just wanted to be sure.

Thank you,


texts: Why are most mutex implementations unfair?

texts:
My understanding is that most popular implementations of a mutex (e.g. std::mutex in C++) do not guarantee fairness -- that is, they do not guarantee that in instances of contention, the lock will be acquired by threads in the order that they called lock().  In fact, it is even possible (although hopefully uncommon) that in cases of high contention, some of the threads waiting to acquire the mutex might never acquire it.

This seems like an unhelpful behavior to me -- it seems to me that a fair mutex would yield behavior more in line with what a programmer would want/expect.

The reason given for why mutexes are typically not implemented to be fair is "performance", but I'd like to understand better what that means -- in particular, how does relaxing the mutex's fairness requirement improve performance?  It seems like a "fair" mutex would be trivial to implement -- just have lock() append the calling thread to the tail of the mutex's linked list before putting the thread to sleep, and then have unlock() pop the next thread from the head of that same list and wake it up.

What mutex-implementation insight am I missing here, that would explain why it was considered worthwhile to sacrifice fairness for better performance?


texts: Using coloring optimization or coloring decision to solve coloring search

texts:
How can you show that coloring search can be solved by making a polynomial number of calls to the solution for coloring optimization or coloring decision? (Coloring search is the algorithm to color the vertices of a graph such that adjacent vertices have a different color.)

I wasn't sure how to solve it, but here is what I attempted (I chose to use coloring optimization):

  Coloring search can be solved by calling coloring optimization and finding the value $m$, which is the amount of colors needed so
  that no two adjacent vertices have the same color. Once $m$ is found,
  coloring search can color the vertices of the graph by rotating through the $m$
  different colors for each vertex.

Am I on the right track?


texts: STCON in L using matrix multipication algorithm?

texts:
I'm trying to understand why the following is incorrect.

Given a $STCON$ problem, specifically a graph and nodes $(G, s, t)$, we can assume we are given it's adjacency matrix, $A$. By adding self-loop (filling the main diagonal with $1$'s) we can multiple this matrix with itself n times, each time checking if the $s,t$ entry is $1$, and if so returning true.

We know multiplying binary matrices is in $L$ (need to "save" only couple of indices), and by also saving $n$ (number of total matrix multiplications) one can solve $STCON$ also in $L$.

Where am I wrong here?


texts: Lower bound on running time for solving 3-SAT if P = NP

texts: Is there a lower bound on the running time for solving 3-SAT if P = NP.  For instance, is it known that 3-SAT can't be solved in linear time?  What about quadratic?


texts: Relative order of values and weights in Knapsack

texts:
In knapsack problem, we have some items with some values and weights. We also have a knapsack with a specific capacity, and we intend to fill the knapsack with these items. The main objective of this problem is to maximize the value of items in the knapsack.

Knapsack can contain maximum 11 kg items

item1: value(1) weight(1 kg)

item2: value(6) weight(2 kg)

item3: value(18) weight(5 kg)

item4: value(22) weight(6 kg)

item5: value(28) weight(7 kg)

Are the items also sorted by their weights when we sort them by their values ?

In other words, are the weights parallel with the values ?

For example, can the item2 have a value 20 but its weight is equal to 2 kg ?


texts: Is my simplified explaination of the XOR swap correct?

texts:
The XOR swap is a well-known in-place algorithm to swap two values, by XOR:ing them bitwise. It goes as follows:

a = a ^ b
b = a ^ b
a = a ^ b

Now, I was thinking to myself if I can find a way to help with my intuition regarding this algorithm. And here's what I thought of:

Bitwise XOR is the same as bitwise addition (1 + 1 = 0, as the carry is lost). Hence, if we write down the operations as addition, we get:

a = a + b
b = a + b + b
a = a + b + a + b + b

I then cancel any matching pair, i.e. b simply becomes a and a becomes b + b + b, which becomes b.

This is all very simple, so does it hold up to scrutiny?


texts: Is PSPACE closed under the following forall-there-exists construction?

texts:
Suppose I have a language $L$ (over alphabet $\Sigma$), such that
$$
w \in L \iff (\forall x \in \Sigma^*) (\exists y \in \Sigma^*) P(x,y,w).
$$
and I can give a turing machine that decides $P(x,y,w)$ in polynomial space in $w$, where $x$ and $y$ are given as separate read-only, forward-only tapes. That is, on input $x$ in tape 1, $y$ in tape 2, and $w$ in tape 3, I use only a polynomial-in-$w$ amount of tape 3's space, and I only move forwards in tape 1 and tape 2.

Does this imply $L \in \text{PSPACE}$?

I feel it should, because if there were only one quantifier, say ($\exists y \in \Sigma^*) P(y,w)$, then $\text{NPSPACE} = \text{coNPSPACE} = \text{PSPACE}$ implies the result. But somehow for two quantifiers I can't figure out how to prove this. I should be able to eliminate the tape $y$ using $\text{NPSPACE} = \text{PSPACE}$, but I don't know if this result still holds in the presence of the additional tape $x$.


texts: Data extaction vs information extraction

texts:
How is information extraction related to data extraction? Is it a subfield or can it be used equivalently? Data is also information. What is the relation and what are the differences?

I want to write about the general topic "data extraction". I can hardly find papers about "data extraction", but most papers deal with "web data extraction", which I want to consider separately. Maybe someone can provide me some solid papers about "data extraction".

Of course, I had a look at https://en.wikipedia.org/wiki/Information_extraction and https://en.wikipedia.org/wiki/Data_extraction but this is not a reliable source. There must be more solid information about that somewhere.


texts: NeuroEvolution: NEAT algorithm innovation numbers

texts:
I have been reading up on the NeuronEvolution of Augmented Topologies and there's this little thing that's been bothering me. While reading Kenneth Stanley's Paper on NEAT I came on this figure here:

The innovation numbers go from 1,2,3,4,5,6 to 1,2,3,4,5,6,7 on the first mutation.

On the second one it goes from 1,2,3,4,5,6 to 1,2,3,4,5,6,8,9.

My question is why does it skip number 7 and goes straight up to 8 instead? I didn't find anything related to deleting innovation numbers.

Same thing on this second figure, how did Parent 1 lose 6,7 and where did the 8th gene go to in Parent 2?


texts:
Suppose there are $m$ items, and each item has a price. We order the subsets of items according to their price. For example, if the price of $x$ is 1 and the price of $y$ is 2, then the order is:

$$
\emptyset < x < y < xy
$$

What is an algorithm for enumerating all orders of subsets that can be generated by such prices? For example, for two items the output should be two orders:

$$
\emptyset < x < y < xy
\\
\emptyset < y < x < xy
$$

For three items, the output should be 12 orders - 2 orders for each permutation of $x,y,z$. For example, for $x<y<z$ the two orders are:
$$
\emptyset < x < y < z < xy < xz < yz < xyz
\\
\emptyset < x < y < xy < z < xz < yz < xyz
$$

One solution is to generate all $(2^m)!$ orders and then check, for each order, whether it is compatible with some prices. However, it is not clear how to do this check, and even with a good algorithm for such a check, it will still very wasteful as most orders will be incompatible. For example, for 3 items we will need to check $8!$ orders to return only 12.

Note: I asked a similar question in math.SE, but the answer is apparently incorrect.


texts:
We know that coNL = NL. But, is this also true?

  If A is NL-complete then complement of A is also NL-complete?

I don't see a reason for that it could be true.


texts: Polynomial by the size of the output and the input

texts:
I wounder why the complexity of algorithms always depend on the size of the input, but not on the size of the output.

For example, in a problem that I have solve, the size of the input is exponentially smaller than the size of output. In addition, the complexity of the algorithm is polynomial by the size of the output, and pseudo-polynomial by the size of the input.

I think that in such case, the complexity of  algorithm  is said to be "polynomial", but I am not sure about it.

What are your opinion?


texts: Why is average-case complexity analysis considered hard?

texts:
Why is average case analysis considered more difficult than both best and worst case analysis? Specifically,  how do you approach  and complete best and worst case analysis as opposed to average case?

Thanks!


texts:
In the sense of a string distinct from a null reference string, what is the importance of an empty string in CS (and specially in formal languages)?

Why do you need a separate concept, that of 'empty string', which even has it's own Greek letter (ε)?

Couldn't just an EOL character replace it?


texts: Tight instance for unweighted maximum coverage problem?

texts:
The maximum (unweighted) coverage problem is defined as follows:

Instance: A number $k$ and a collection of sets $S = \{S_1, S_2, \ldots, S_m\}$.
Objective: Find a subset $S^{'} \subseteq S$ of sets, such that $\left| S^{'} \right| \leq k$ and the number of covered elements $\left| \bigcup_{S_i \in S^{'}}{S_i} \right|$ is maximized.

This problem is NP-hard. I am trying to find a counterexample when the greedy algorithm fails but I failed. Especially, can you find a family of instances when the greedy algorithm always fails? (Or at least one simple instance?)

The greedy algorithm:
at each stage, choose a set which contains the largest number of uncovered elements.

I found a family of instances here but it was for the weighted case and I cannot transform it to the unweighted case.


texts: What is the computational complexity of the first-order theory of real arithmetic?

texts:
Tarski proved that the first-order theory of real-closed fields is decidable. Is the exact computational complexity known? The best upper bound I could find is EXPSPACE [1], where it is also conjectured to be EXPSPACE-hard.

Update: The complexity without multiplication, i.e., of FO$(\mathbb{R},+,<)$, is complete for the unusual complexity class STA$(*,2^n,n)$ [2]. This implies NEXPTIME-hardness.

Here STA$(s(n),t(n),a(n))$ is the class of problems solvable by single tape alternating TMs in space $s(n)$, time $t(n)$, and number of alternations $a(n)$, and a $*$ means no restriction.

[1] https://dblp.org/rec/journals/jcss/Ben-OrKR86

[2] https://doi.org/10.1016/0304-3975(80)90037-7


texts:
By reading literature on (denotational) semantics of types, I see that people tried to give several models of types. Reynolds showed that types in general cannot be given a set semantics in classical set theory. However, it was shown later that constructive sets could be used. Now, I also stumbled upon papers where types are seen as complete partial orders and Scott domains. Further, Cardelli presents types as ideals, but acknowledges that retracts should be used to handle parametric types.

I understand that one can give different models depending on the type system, but is there a known model of types that handles parametric types, universal parametric polymorphism, existential polymorphism, recursive types, and subtyping? For instance, where would I start if I want to give a denotational model for OCaml types (but without the side-effect features)?

Also, how does Reynolds' relational model relate (no pun intended) to the existing models?


texts: Bentley–Ottmann algorithm time complexity issue

texts:
In the Bentley–Ottmann algorithm, Regarding :

  Find the segments r and t that are immediately below and above s in T
  (if they exist) and if their crossing forms a potential future event
  in the event queue, remove it.

That means, every insertion of a segmant may lead to an intersection event deletion.

I am thinking what makes it stay within the said time complexity.

Is it valid to say that it is because i have up to n such insertions that would lead to up to n such deletions, which causes O(nlogn) operations at most hence the time complexity is not effected?


texts: Running time of algorithms that sometimes loop forever

texts:
Consider the following algorithm that computes the sum of two integers (toy example):

INPUT: Integers (a,b)

 1. Toss a coin c
 2. If c = 0, then loop forever
 3. If c = 1, then compute and output a+b

What is the running time of this algorithm? The "strict" running time (defined as a strict upper bound on the running time over all inputs and all possible random choices of the algorithm) is infinite. The "expected" running time (defined as the average running time over all inputs and random choices) is infinite, too.

Thus, apparently this is an algorithm whose running time (strict/expected) is infinite. However, the algorithm still appears to be useful, since it produces a reasonable result with probability 1/2.

Is there a notion of "running time" in computer science that captures such algorithms? Can you point me to references or a textbook?

Thanks!


texts: Origins of the numerical notation for types in type theory

texts:
In several papers on type theory it's possible to see some sort of numerical notation for types based on the number of possible constructors for the type. For example, the unit type is usually written as $1$, as there's only one possible constructor for it; similarly, they use $2$ for booleans, $x + y$ for disjoint unions (sum types), $x * y$ for product types, and so on.

This kind of notation seems to be assumed familiar to the reader. Where does it come from? Are there any sources that explicitly explain this notation?


texts: Look for a pair of elements closest to two start positions in both directions until a condition is met

texts:
For a list which contains a set of elements I have two starting positions pos1and pos2 that are selected randomly. Next, I check if I can swap these elements. If the swap is not possible I want to look at the next pair of elements closest to the two starting positions.

list = |9|1|2|3|5|4|6|7|8|10|

Lets say my start positions are startPos1 = 2and startPos2 = 6. If the two values from these positions (2and 6) cannot be swapped I want to move on to the next closest pair. Now lets say I increment pos1 by one and find that the two elements in positions 3 and 6 cannot be swapped, too. If this is the case I want to look at the pair of elements in pos1 = 2 and pos2 = 5. That is, I would like to implement some kine of loop that gives me a sequence like this:

pos1 = 2
pos2 = 6
---------
pos1 = 2
pos2 = 5
---------
pos1 = 2
pos2 = 7
---------
pos1 = 3
pos2 = 6
---------
pos1 = 1
pos2 = 6
---------

If the elements in pos1 = 2 and pos2 = 7 can be swapped I terminate and otherwise I have to move on to the next pair of elements.

One can observe that the pairs listed above have a total deviation of 1 from the start values of the positions startPos1 = 2and startPos2 = 6. The next closest pair would have a total deviation of 2 and I think I can use this somehow but I haven't figured out how exactly.

Can anyone give me a hint how to implement this concept?


texts: Artificial Intelligence: theory vs processing power

texts:
It is common to see articles praising the advances in AI (here is one example).
There is no doubt that significant progress has occurred on all kinds of automation, hard games like chess, etc.
The question is, how much of that progress is due to conceptual proogress, as opposed to increase in processing power? Or, to phrase it in a different way: if today's best AI would be shown to a computer scientist from the 60s, would they be impressed by the algorithms? Or just by the raw power of the hardware?


texts: What is the earliest use of the "this" keyword in any programming language?

texts: I understand the this (or self or Me) is used to refer to the current object, and that it is a feature of object-oriented programming languages. The earliest language I could find which has such a concept was Smalltalk, which uses self but was wondering where and when (which programming language) the concept was first implemented?


texts:
The set of lambda calculus expressions $Expr$ is generated by the grammar
$$
 Expr \ni e ::= x \mid \lambda x\ldotp e \mid e_1 e_2
$$

We can define an interpreter without explicit substitution by using environments and closures:
$$
  \begin{align*}
  Env &= Var \rightharpoonup Cl &\text{($\rightharpoonup$ is partial function space)}\\
  Cl &= Env \times Expr
  \end{align*}
$$

The evaluation function $eval : Env \times Expr \to Cl$ sends each expression in a given environment to an evaluated closure:

$$
\begin{align*}
  eval_\rho(x) =& \rho(x) \\
  eval_\rho(\lambda x\ldotp e) =& (\rho, \lambda x\ldotp e) \\
  eval_\rho(e_1 e_2) =& \mathrm{let~}eval_\rho(e_1) = (\rho', \lambda x\ldotp e_1') \\
   & \mathrm{in~} eval_{\rho'[x \mapsto eval_\rho(e_2)]}(e_1')
\end{align*}
$$

Using substitution, a closure $(\rho, e) \in Cl$ can be expanded to yield the represented expression:
$$F([x_1 \mapsto c_1, ..., x_n \mapsto c_n], e) = e[F(c_1)/x_1, ..., F(c_n)/x_n]$$
This however forgets all sharing. E.g., $F([x \mapsto ([], f)], x x) = f f$ duplicates the expression $f$, which might be very large. An alternative expansion retains sharing:

$$
G([x_1 \mapsto e_1, ..., x_n \mapsto e_n],e) = (\lambda x_1 \ldotp \cdots (\lambda x_n \ldotp e) \cdots) ~G(e_1)~\cdots ~ G(e_n)
$$

This on the other hand repeats definitions in nested scopes, e.g.:
$$
  G([x\mapsto ([],f), y \mapsto ([x \mapsto ([],f)], g)], x y) \\
  = (\lambda x\ldotp \lambda y\ldotp xy)~(f)~((\lambda x\ldotp g)~f)
$$
An equivalent but more economical expansion that doesn't duplicate $g$ would be
$$
  (\lambda x\ldotp (\lambda y\ldotp xy) g)~f
$$
For practical purposes, if one wants to "render" a closure as a plain expression, both $F$ and $G$ are unsatisfactory: The closure environments can be efficiently represented by pointer datastructures that takes avantage of sharing, but most of that sharing seems to be lost with either approach.

Do you know of any efficient data structures and algorithms related to this problem?
Is this problem called something more specific in the literature? I tried search for "lambda calculus closure expansion", but without much success.


texts: Is that a regular express? Proof using closure properties or pumping theorem

texts:
I am studying regular express. I understand how to proof a xa ya. However, I don't know how to proof the below problem. Please help me.
L = { xa yb | a ≠ b }


texts: CNF satisfiability with a bound on number of clauses

texts:
Consider the CNF-sat problem with n literals and k clauses. If k scales linearly in n, we get np-completeness (e.g., 3-sat where each literal appears at most 4 times). Do we still get np-completeness if we restrict attention to problem instances where k scales sublinearly in n? For this question, I am not requiring clauses to consist of 3 literals, but I still need the formula to be CNF.

More generally, how does complexity scale (for known algorithms) with k?


texts: A simple, concise, strong and a formal model of computation

texts:
Most mathematical objects can be said to be defined in simple terms, are usually really concise and still manage to capture the essence of what they are trying to talk about. For example, topology does a great job at capturing a broad and variety of interesting objects, but still its definition is simple enough to be used directly for (pretty much) everything (in topology of course).
However, unlike topology and other mathematical notions, the definition of a Turing Machine is really complicated. This definition does capture a big chunk of interesting problems, but it is too complicated to be considered when trying to solve them. For example, you won't start thinking about turing machines, when you want to design an algorithm that computes the BFS algorithm.
You may say, that in those terms, it might be better to think in terms of "computer code" or "RAM machines". However, I am not satisfied with that answer, since such things are not formal enough when considering other uses, such as proving lower bounds, or when proving theorems such as the time hierarchy theorem.
My Question
Is there some notion of a computational model (doesn't necessarily have to be equivalent to TMs), that is formal enough to work with, for such theorems and lower bounds, but also simple and expressively interesting?


texts: String edit distance between strings x, y, with restrictions on 'intermediary' strings

texts:
This is a problem I encountered in a recent interview test. I achieved a slow-ish solution to it, and I'm keen to figure out the most efficient.

Problem

Given a starting string $x$, a target string $y$, and a set of valid strings $V$, find the minimum edit distance between $x$ and $z$ where edits can only be character exchanges and each intermediary string $z_i$ must be in $V$.

Further constraints on problem

All strings are length 8
The complete character set for strings is $\{A, T, G, C\}$
The starting string $x$ does not need to be in $V$, but $y$ is

My Straightforward an slow-ish solution

When I see an edit-distance problem I immediately think of Dynamic Programming, but tradition Dynamic Programming approaches don't care about the intermediary stages of the string when transitioning between $x$ and $y$, so I wasn't 100% confident in this approach.

Noticing that given a small enough set $V$ I could quite quickly find all strings in it that were $1$ edit distance from my current string, I went we the following approach.

Start at string $x$ with target $y$ and set $V$ and current distance $0$

If $x == y$ the return current distance

Mark $x$ as 'seen' by removing it from $V$
Find all strings in $V$ that are 1 edit-distance from current string
recur on all candidate strings, keeping the same target, the updated $V$, and an incremented current distance

This approach isn't too terrible, and with some memoization thrown in it gets even more acceptable, but I get the strong feeling there is a much faster approach to solving the problem with out 'searching' through the set $V$.


texts: Finding longest prefix of a given string in set of strings that satisies some property

texts:
I have a set of strings, lets call them RULES. I have a function F which given 2 strings deterministically returns boolean value. Given one string, lets call it QUERY, what is the fastest way to find longest prefix (lets call it P) of QUERY which is a member of RULES for which F(P,QUERY) returns true?

That was very generic definition of a problem. The reality is that I have a huge tree of objects. Each object has one of predefined types. I want to have a way to define different views on that tree. Each view is set of rules describing which types of objects are (in)visible in subtree subtree described by that rule. Basically a rule is a pair - path/prefix in tree and map from type to boolean. An object of type T is visible via given view iff the longest rule that has path that is prefix of that objects path has true as an entry for type T.

An example:

Types are {A,B,C}.

Tree contains those objects: /A1, /A2, /A1/B1, /A1/C1, /A1/B1/C1, /A2/B1, /A2/C1

View is defined by those rules: {/; C=>true, A=>true}, {/A1/B1; C=>true}, {/A1; C=>false}, {/A2; B=>true,C=>true}

Objects visible via that view: /A1, /A2, /A1/B1/C1, /A2/B1, /A2/C1

Right now I'm solving this by storing all rules for view in (hash)map - key is path and value is set of rules. When I've checking given object, I start from its full path and check in a loop each of is prefixes by removing top path component and looking it up in (hash)map. When it contains entry for that prefix I check if it contains entry for the type of object - if it does I return it as value of visibility. Otherwise I continue with next shorter prefix. If no rule was found I decide that object is not visible.


texts: Show that a language is decidable iff some enumerator enumerates the language in lexicographic order

texts:
The proof is given in the below:

If $A$ is decidable, the enumerator operates by generating the strings in lexicographic order and testing each in turn for membership in $A$ using the decider. Those strings which are found to be in $A$ are printed.
If $A$ is enumerable in lexicographic order, we consider two cases. If $A$ is finite, it is decidable because all finite languages are decidable. If $A$ is infinite, a decider for $A$ operates as follows. On receiving input $w$, the decider enumerates all strings in $A$ in order until some string lexicographically after $w$ appears. That must occur eventually because $A$ is infinite. If $w$ has appeared in the enumeration already then accept, but if it hasn't appeared yet, it never will, so reject.
Note: Breaking into two cases is necessary to handle the possibility that the enumerator may loop without producing additional output when it is enumerating a finite language. As a result, we end up showing that the language is decidable but we do not (and cannot) algorithmically construct the decider for the language from the enumerator for the language. This subtle point is the reason for the star on the problem.

I could not understand the rejection case in the last line in the second paragraph. The author said "if it has not appeared yet, it never will". Why, could anyone explain it for me in a simpler way?

Also I could not understand the last paragraph at all, could anyone explain it to me in a simpler way?


texts:
Let $L_1$ be some language in $R$. Let $L_2$ be some language in $RE$. Is it necessarily that
$L_1 \leq_m L_2$ ?
I know that for non trivial $L_1$,$L_1$ in $R$ it is right to say that $L_1 \leq_m L_2$.
But I can't prove the first case.
and another question:
I am almost certain that the following is true, though I have not found any reference to it on the Internet:
The identity function is a mapping reduction from $\emptyset$ to $\emptyset$.


texts:
Construct the CFG given the following language:

$$\{a^i \; b^j \; c^k \;|\; i = j \; or \; j = k \}$$


texts: Why does the time hierarchy theorem use a rather intricate diagonal argument?

texts:
Isn't it possible to prove it by defining some problem that can be solved in $f(n)^2$ in the worst case due to its output always being $f(n)^2$ characters so that it won't be solvable in $f(n)$?
Where am I wrong?


texts: asymptotic tight bounds for quadratic functions

texts:
In Introduction to Algorithms by CLRS, it's said

For any quadratic function $f(n)=an^2+bn+c$, where $a$, $b$ and $c$ are constants and $a>0$, $f(n)=\Theta (n^2).$ Formally, to show the same thing, we take constants $c_1=a/4, c_2=7a/4$ and $n_0 = 2 \cdot max(|b|/a, \sqrt{|c|/a}).$ You may verify that $0\leq c_1n^2\leq an^2+bn+c \leq c_2n^2$ for all $n\geq n_0.$

They didn't specify how values of these constants came? I tried to prove it but couldn't.


texts: A certain submatrix of the correlation polytope

texts:
I am kind of confused by the argument at the top of page 5 here, http://homes.cs.washington.edu/~jrl/notes/bonn-lecture-notes.pdf

Firstly given that the author wanted to look at quadratic multilinear functions on $\{0,1\}^n$ why is he finding it enough to look at functions of the form, $f(x) = a_0 + \sum_{i,j} A_{ij}(xx^T)_{ij}$ for some real symmetric matrix $A$ and a real number $a_0$?

These $f$s won't have any linear term and doesn't that mean a loss of generality?
The author defines the set $QML_n^+$ as the set of functions of the above type which are non-negative on the Boolean hypercube. Isn't this set an uncountably infinite set?

Because I don't understand how the author now hopes to define a matrix $M_n$ whose rows seem indexes by $f \in QML_n^+$ and the columns seem indexed by $x \in \{0,1\}^n$ and the entries are $M_n(f,x) = f(x)$.

How does this make sense as a matrix (of finite dimensions!)?
Given everything  above how is it obvious that this matrix $M_n$ is a submatrix of some slack matrix of the correlation polytope $conv(\{ xx^T \vert x \in\{0,1\}^n \})$ ?


texts: How to find max number with a single-tape turing machine?

texts:
I'd appreciate hints for this problem

I'm trying to design a Turing Machine which calculates $\max \{x_1, x_2,..,x_k \}$.

Assuming $1 = 1^1; 2=1^2; n=1^n$ and all numbers/strings are separated by a blank character $B$.


texts: In Hindley-Milner system, how can I prove that let id=\x.x in id id is well-typed?

texts:
I am trying to infer the type and prove that this is well-typed:

let $f =\lambda x.x$ in $f f$

Obviously the $f$ is the identity function, so it's the same as

let $id =\lambda x.x$ in $id$ $id$

I am trying to use these rules to infer the type, going bottom-up:

First I am using (T-LET') and on the left-hand side it's easy to show that $\lambda x.x$ is of type $\alpha \rightarrow \alpha$.

However, I have a trouble with the right hand side. Can someone please help me how to finish this?


texts: Find all intervals that overlap with a given interval

texts:
Note: I moved this question from stackoverflow.com

I have an algorithmic problem where I would like to see if it can be solved in better than $O(n)$:

I have given a table $T$ of $n$ elements where each element is a tuple $(s_i, e_i)$ with $s_i, e_i \in \mathbb{N}$ and $s_i < e_i$, i.e. each tuple is some kind of an interval. I have to find all intervals that overlap with a given interval $[t_0, t_1]$ with $t_0, t_1 \in \mathbb{N}$ and $t_0 < t_1$. Further, I have available two sorted lists $S$ and $E$, containing the $s$ values, or $e$ values respectively, together with the index $i$ pointing to the respective entry in $T$. The lists are sorted by $s$ values, or $e$ values respectively. (Let's assume both, $s$ and $e$ values, are unique.)

Problem:

We have to find each interval/tuple $(s_i, e_i) \in T$ where $s_i \leqslant t_1$ and $e_i \geqslant t_0$.

My thoughts so far:

We can exclude some elements by either applying one of the interval boundaries, i.e. searching $t_1$ in $S$ or $t_0$ in $E$. This gives us a list $L$ of remaining elements:
$$
    L \leftarrow \{e \in E \mid e \geqslant t_0\} \text{ or } L \leftarrow \{s \in S \mid s \leqslant t_1\}
$$
However, there is no lower bound on the number of elements in $L$, no matter which search we perform. Further, we have to check every element in $L$ if $s \leqslant t_1$, or $e \geqslant t_0$ respectively depending on which search we performed before.

The complexity for this solution is $O(n)$.

However, let's say that $k$ is the maximum number of elements overlapping with interval $[t_0, t_1]$. If we assume $k \ll n$, then the complexity is $O(n/2)$ since we can exclude at least $n/2$ elements by choosing the appropriate search for $L$. Still $O(n/2)$ is in $O(n)$.

Can you think of a better approach to solve this problem?

For record:

The complexity for finding all intervals overlapping with a certain given interval using an interval tree is $O(\log n + k)$ where $k$ is the number of overlapping intervals. However, in my practical case I am using a MySQL database which provides index trees for each value, i.e. $s$ and $e$, separately. This way I can not find overlapping intervals in less than $O(n)$. I would need to create an interval tree which is a search tree that stores both interval boundaries, i.e. $s$ and $e$, in a single data structure. The complexity for constructing the interval tree is $O(n \log n)$. [http://www.dgp.utoronto.ca/people/JamesStewart/378notes/22intervals/]


texts:
Consider the non-deterministic finite automaton A: (in below figure)

1> convert this NFA to DFA

2> Find if there are equivalent states of your DFA

3> Minimize the DFA of <2> if possible

This is what i have got so far

4> further question: Prove that the DFA in <3> recogniese the intended language L.

I got stuck on this question, since the language says that "every occurrence of a is preceded by and followed by an occurrence of b"
this means:

L = {x bab)^n y |  x,y belongs to {b,empty}^n   where n is natural number}

In this case: the language can be:   bbb.....bbbb bab ... bab bbb....bbbb

But for my <3> DFA, the occurrence of a can appear without preceded by an occurrence of b.

I hope if there is anyone can point out my mistake.

many thanks


texts: Function that enumerates a recursively enumerable language

texts:
I have an exercise where one is supposed to give a function that will enumerate the following language:

$L_1 = \{ a^pb^p \hspace{1mm} |\hspace{1mm} p \in  \mathbb{N} \hspace{1mm} \wedge \text{ (P is a prime number )} \}$.

The solution is the following function: $f:  \mathbb{N} \rightarrow \Sigma^*$ with $f(i) = a^{p_{i+1}}b^{p_{i+1}}$,
where $p_{i+1}$ is the $(i+1)^{th}$ prime number, ordered by the prime's order.

Could anyone explain to why does this solution work? And especially why does the function include $p_{i+1}$ instead of $p_{i}$ ?

Thank you!


texts:
In the partition problem, the task is to partition $n$ given integers into two subsets $A$ and $B$ with equal sum. This problem is known to be NP-hard, but it becomes easy if the "equal sum" requirement is replaced with the following:

  The difference $|\sum_A - \sum_B|$ should be at most the largest integer in the set with the larger sum.

A solution always exists, and can be found using the following algorithm:

Order the integers by descending value.
Put the largest integer in subset A, the second in subset B, the third in subset A, etc.

The sum in subset A is always at least as large as the sum in subset B, but if we remove the largest integer from subset A, then the sum in subset B is at least as large as the remainder. Hence, the partition is equal up to one integer.

MY QUESTION IS: what happens when there are cardinality constraints on the subsets? Formally, the task is to partition $n$ given integers into two subsets $A$ and $B$ that have sizes $a$ and $b$, with $a+b = n$ and $a \le b$. The algorithm above does not work, and indeed an equal partition up-to-one-integer may not exist. What is an algorithm to decide whether such a partition exists?


texts:
I know that if a language $L_1$ and a language $L_2$ are regular, then
$L1/L2$ is regular.

When we construct a DFA $M'=(Q, \Sigma, \delta, q_0, F)$, for each state $i$
we can make $i$ the start state (we'll represent is using $L'i$) and if $L'i \cap L_2 \neq 0$ then put $q_i$ in $F'$ in $M'$.

I understand the process of constructing an automaton M if both
languages are regular, but what if L1 is regular but L2 is any language?
How would I construct an automaton for this?

Thank you!


texts: Optimization of 3D graph position calculations

texts:
I am trying to find reasonable algorithm for 3D grpah visualization. So far I've been using Force directed graph with octree for optimization. But the speed of computation is very bad.

My dataset is network traffic record and consists of thousands of nodes that are randomly distributed within it, so nodes that are connecting to one another can be in various places. What's also important is that I am reading line by line and this way I am adding new nodes to program.

Pseudo code for my current algorithm would be:

Read line form dataset
Generate new/update value of existing node
Generate new octree
Add all nodes to octree
Compute forces
Return to 1

Is this algorithm correct? Because I still think that the speed of this is very slow.


texts: Algorithms or specific approaches for maximum independent set problem in triangle free graphs

texts: And obviously there will be no trivial vertex which has only 2 edges. I think triangle free graphs are (subjectively) easier than complicated graphs, i wonder if you know some heuristic approaches/steps specificly for triangle free graphs. Thanks in advance


texts: What does the set {n | n is an integer and n = n + 1} represent?

texts:
I am reading Michael Sipser's book Introduction to the Theory of Computation, which mentions the set $$S = \{ n \mid \text{$n$ is an integer and $n = n + 1$}\}.$$ This  doesn't make any sense to me.
I would understand if $n$ were equal to infinity or something, so it probably wouldn't matter if we added $1$ to it.
Am I understanding it correctly?
Or is this just an empty set?


texts: Equivalent regular grammar with minimum number of nonterminals

texts:
Given a set of terminal symbols $\Sigma=\{a,b\}$ and a set of nonterminal symbols $N=\{S,A,B\}$ with start symbol $S$, then the two following sets of production rules are equivalent:

$S\to aA$
$A\to aA$
$A\to bB$
$B\to aA$
$B\to bB$
$B\to \epsilon$

and

$S\to aA$
$A\to aA$
$A\to bA$
$A\to b$

They both match any string starting with $a$ and ending with $b$, but the second set of rules has only two nonterminals instead of three.
Is there a standard way to convert an arbitrary (regular) grammar to the equivalent grammar with the smallest number of non terminals?
I don't think this can be achieved by the rules for Chomsky normal form.


texts: Towers of Hanoi Algorithm "Using Auxiliary" Peg

texts:
I'm trying to fully understand how the recursive Towers of Hanoi Algorithm works and to implement it in code.

Something that keeps throwing me of is the use of phrases like "move n-1 discs from A to B using C."

I understand that the peg which is referred to is as being "used" is the auxiliary or spare peg, but the language seems misleading because if n-1 has a value of more than 1, then more than one peg is used to perform the move. So the phrase "using C" or "using B" or "using A" doesn't seem accurate and is hindering me from thinking clearly about the problem.

Am I missing something, or can I substitute the phrase "with C as the spare/auxiliary peg" for "using C" without loss of meaning?

I've seen one video where for the n=2 problem, the first move is described as "move a disc from A to B using C" - in this case C isn't involved at all!

I wonder if anyone who has managed to fully grasp the algorithm can advise if it would be helpful to adopt the "using A/B/C" language or if there is another alternative that you have found more helpful, such as my suggestion above - "with C as the spare/auxiliary peg"?


texts: Need help understanding regular expressions

texts:
I was reading up about formal languages (see here: https://pdfs.semanticscholar.org/18b2/d685d5e244a6bfc5a31d312f1e8d322c16a9.pdf) and got confused when I started reading about this expression: 0(0+1)∗+(0+1)∗0

This is how I think it works:

The first and last 0 indicates where these two characters must be present. In other words, the string this expression describes must start and end with one 0. (0+1)* describes any combination of 0's and 1's (including none at all), and the plus in between each of these sets of brackets ((0+1)* +(0+1) *) describes a concatenation of these two strings. Therefore, this expression applies to any binary string that begins and ends with a 0.

If this is indeed how the expression works, wouldn't 0(0+1)*0 achieve the same thing?

(Also, is there a site I can check these sorts of expressions? I tried this expression in sites like regex101.com but it didn't work on any of them. This isn't important, I was just curious)


texts: Why there is no FPTAS for multiple knapsack problem for two knapsacks unless P=NP?

texts:
The multiple knapsack problem (MKP) is defined in "A PTAS for the Multiple Knapsack Problem" as:

Instance: A pair $(B, S)$ where $B$ is a set of $m$ knapsacks and $S$ is a set of $n$ items. Each bin $j\in B$ has a capacity $c(j)$, and each item has a size $s(i)$ and a profit $p(i)$.
Objective: Find a subset $U\subseteq S$ of maximum profit such that $U$ has a feasible packing in $B$.

To prove that there is no FPTAS for MKP, the authors reduce partition problem (PP) to MKP with $m=2$ as follows:

  Given an instance of PP, $a_{1},\ldots,a_{2n}$. We set $c(1)=c(2)=\frac{1}{2}\sum_{i=1}^{2n}a_i$. We have $2n$ items, one for each number in the PP: the size of item $i$ is $s(i)=a_i$ and the profit is $p(i)=1$. If the PP has a solution, the profit of an optimum solution to the corresponding MKP is $2n$; otherwise it is at most $2n-1$.

However, I do not understand why the created instance of MKP is hard. I mean we have a set of $2n$ items where each item $i$ has size $s(i)=a_i$ and a profit $p(i)=1$. Also, we have $2$ knapsacks with identical capacity $c(1)=c(2)=\frac{1}{2}\sum_{i=1}^{2n}a_i$. We would like to maximize the number of assigned items to the two knapsacks such that the capacity of each knapsack is respected. Why we could not do the following?

Sort the items in increasing order of their sizes;
Pick an arbitrary knapsack, say $1$;
Fill it with items until its capacity is attained; and
Repeat 2. and 3. for knapsack $2$.

Sure I am missing something here but I do not know where.


texts: Proving that a specific language is a CFL, and that another language is not a CFL

texts:
I have two languages $C_1$ and $C_2. \left(\Sigma=\{0,1\}\right)$:

$C_1=\left\{xyz\mid x,z \in \Sigma^*, y \in \Sigma^*1\Sigma^*, \text{ where } |x|=|z| \geq |y|\right\}$, and $C_2=\left\{xyz\mid x,z \in \Sigma^*, y \in \Sigma^*1\Sigma^*1\Sigma^*, \text{ where } |x|=|z| \geq |y|\right\}$

I want to show that $C_1$ is a CFL, while $C_2$ is not a CFL.  I'm trying to create a grammar / pushdown automata that accepts $L(C_1)$, but the $|x|=|z| \geq |y|$ part is throwing me off.  I plan on using the pumping lemma for $C_2$, but I'm not sure which string to pump.


texts:
• Given the above virtual to physical address mapping,

1 What is the page size?

2 How many virtual pages can we have in maximum?

3 How many physical pages can we have in maximum?

Approach:

1 For the page size I would say I don't know because we have no information that gives us a clue about page size.

2 I think that we can have as many as the number of physical frames in memory

3 As many as we want, but since we have to constrain the number pages to the number of bits in the address then I would say 2^15 pages.

Can you give me some insight to get to the right idea to solve this problem?


texts: Select fixed-size connected induced subgraphs in a graph

texts:
I have a connected graph with $nk$ vertices, and would like to select $n$ disjoint induced subgraphs with $k$ vertices such that each subgraph is connected, selecting one out of all possible solutions at random. It doesn't necessarily need to be uniformly at random, I just want the possibility of getting any possible solution.
For example, with this graph:

and $k=3$, $n=2$, here is a solution (in fact it's the only one):

And here's one of the two possible solutions for the same graph with $k = 2$ and $n = 3$:

Sometimes this is not possible, like with this graph, for $k = 3$ and $n = 2$:

Is there any (efficient) way of determining whether there is a solution, and if so, selecting one (not necessarily uniformly) at random?


texts: How to get synonyms from definitions using Bayes algorithm

texts:
I work on a project: an online dictionary where the user can find definitions of a word he's looking for.
My supervisor asked us to add synonyms using machine learning. He recommend us to use Bayes algorithm.
but I don't see how to do this, how to put every word in a category and make probabilities.

Please how can I use this algorithm? knowing that my project is in java.

Thanks, for any suggestions or opinions.


texts: 0/1 Knapsack problem. How does the total weight does not exceed the limit?

texts:
I am trying to wrap my head around the knapsack problem algorithm. I understood the most of it except one tiny thing.

On the left is the [val,weight] and on the top is the weight 0-7.
As per my understanding, the cell marked in red depicts the maximum value that could be achieved with available options [1,1] and [4,3] while the maximum weight capacity is 3 (determined by the topmost row of the same column.
If my understanding is correct then how could the value be 4? You have chosen to pick both the items
which means you will have to add their weights too. 1+3 = 4 which is greater than the capacity 3.
What am I missing here?


texts: Algorithm to determine two binary expression trees will give the same result based on associative and commutative properties of some operators

texts:
Given n different numbers, I would like to find out whether there exists an algebraic expression using all the n numbers, with n−1 binary operators and unlimited number of parentheses, that evaluates to a certain number T. My idea is to make use of binary expression trees, construct all possible trees and then find the result by brute force.

As I have learned, the number of possible combinations will be:

$$\begin{aligned}
        \frac{(2(n-1))!}{(n-1)!n!} n! s^{n-1}\\
      \end{aligned}$$

where s is the number of different binary operators that is allowed to be used (e.g. if we allow +, −, × and ÷, then s=4), and

$$\begin{aligned}
        \frac{(2(n-1))!}{(n-1)!n!}
      \end{aligned}$$

is the number of different types of binary expression trees that can be constructed without considering the content of the nodes.

To speed up the search, I have an idea to make use of the associative and commutative properties of the operators + and ×. An intuitive case will be, if all the n−1 operators chosen are all +, then all the trees will evaluate to the same result, regardless of how the n numbers are allocated in the leaf nodes. However, this obviously does not apply to operators − and ÷. And, in the general case, the operators chosen will consist of a mixture of +, −, × and ÷, so is there an algorithm to check the trees will evaluate to the same result without actually doing the calculation?

e.g. A binary expression tree that represents (8−5)×(6+3)×(7−4) will give the same result as a binary expression tree that represents (8−5)×((6+3)×(7−4)). Going even further, they will also give the same result as a binary expression tree that represents (3+6)×(7−4)×(8−5). Is there such an algorithm to detect these trees will evaluate to the same result?


texts: Why is the initial state of Zobrist hashing random?

texts: When generating a board for Zobrist hashing, why are the initial elements random? How can you detect changes to elements later if the initial values are random?


texts: Managing an hotel using AVL trees - Data Structures

texts:
I have a Data Structure question where I need to manage an hotel, each room has a number between $1-n$
and it can be occupied or not.

Available Data structures: AVL* Trees, B-Trees, Arrays, Stacks, Queues, Binary Trees.

$O(n)$ Space complexity available.

Using AVL OR B-Tree is a must.

I have to support these functions:

1) $\text{Init(n)}$ : Initializes the data structure with $n$ unoccupied rooms, the indexing of the rooms is $1-n$
this has to work at $O(n)$ time complexity

For the next functions: $l$ and $r$ do not have to be a number of an occupied room-

2) $\text{GetUnOcc(l,r)}$ : Gets $l$ -Left and $r$ - Right (Does not have to be an occupied room number) , 2 numbers that defined a range of numbers and I need to count how many hotel rooms are not occupied between them (Including).  Has to work at $O(\log_2{n})$ Time complexity

3) $\text{GetMinUnOcc(l,r})$ : Gets $l$-Left and $r$-Right, 2 numbers that define a range of numbers, this one adds the person to the hotel at the smallest room that is not yet occupied between $l-r$ (Including).
Has to work at $O(\log_2{n})$ Time complexity

4) $\text{GetOut(r)}$ : It gets a room number and deletes the person from that Room/Hotel, making room number $r$ unoccupied.
Has to work at $O(\log_2{n})$ Time complexity

My Go:

Init: I thought about using an AVL tree with a boolean array.
We initialize it $O(n)$ by just making an array of False (Unoccupied) which takes $O(n)$

GetUnOcc(l,r) : I thought about this formula:
$\text{#UnOcc} = r - l + 1 - \text{Occupied}$  so we need to find how many rooms are occupied between $l-r$ but I am not sure how to do so in $O(\log_2{n})$

GetMinUnOcc is much harder because I cannot determine which value is the smallest, let's say $l=3$ and $r=10$ and every room between $3-8$ and room $10$ are occupied, and I need to return $9$ (because it is the smallest which is not occupied)

Let's say I have this tree (as Steven suggested to build an AVL of unoccupied rooms) so in this matter it is $\text{Init(10)}$  And Now I want to do $\text{GetMinUnOcc(5,7)}$ so it should delete $5$ from the tree as it will become occupied. But in what you suggest, we find the successor of $l=5$ which is his parent, $6$ and delete it, but, $5$ is not occupied and we want to return the minimum so we need to actually delete $5$, where am I wrong?  Thank you!

I would appreciate your help / hints to solve this hard question! Thank you!


texts: Detemine if two DFA's are non-disjoint in polynomial time?

texts:
Given two DFA's , $M_1$ and $M_2$, I want to create an algorithm that determines if their languages are disjoint or not. The algorithm will run in polynomial time.

My idea is this: Let's say WLOG that $M_1$ has 1 accepting state. We run DFS from that state and look at paths from the state to a starting state. Ideally, a path will be of the form $abb (a\cup b)abbb(ba)^*$ The "or" operator will be used in places where the "path" from the root to the leaf node splits and then merges, and the "*" operator will be used in case of cycles.
We can then do the same thing for $M_2$ and then do an intersection of their paths to find if they have any common paths.

This is basically just an idea that I had; I'm not too sure about the fine details, like how cycle detection will work, and if I need to modify DFS a bit for this to actually work.

Am I totally wrong? Are there any issues with this algorithm?
Any help would be appreciated.


texts: What is the complexity class of exponential parallelism?

texts:
Consider the class of problems that can be computed when you have access to exponentially many processors working in parallel.

How does one capture that in a proper formalism? Is there some literature on it already? Would it be true that such a class would be a superset of BQP?


texts: How to call something that can be either a terminal or a nonterminal?

texts:
I had written a compiler compiler a few years ago and I'm now cleaning it up, improving it, and turning it into C.

I came across a terminology problem however that I remember in the past I couldn't solve it either.

Imagine an LL(k) stack. In this stack, you may have terminals, that are expected to be matched with the next token, or non-terminals that would expand based on the next token. In either case, there is a string in the stack.

The word I am looking for, is a term that means either a terminal or non-terminal. Wikipedia was of no help.

To clarify a bit more, imagine a grammar with $t = \{a \mid a \text{ terminal}\}$ and $T = \{A \mid A \text{ non-terminal}\}$. If you have a set $X = \{x | x \in t \vee x \in T\}$, how would you refer to an element of $X$? "Grammar symbol"? "Grammar element"? "Terminal or non-terminal symbol"?

I am in particular looking for a name as short and to the point as possible, since this will end up becoming a variable name!


texts: Summary of types of equivalence and equality in type theory, with notations and examples

texts:
Coming from non-computer science background, I am trying to understand the different types of equivalence and equality usually used in type theory. Ideally, I am looking for clear definitions and notations (ie the symbols commonly used) of:

difference between equivalence and equality of types $T_{1}$ and $T_{2}$
definitional equivalence(/equality?) of types $T_{1}$ and $T_{2}$
structural equivalence(/equality?) of types $T_{1}$ and $T_{2}$
observational equivalence(/equality?) of types $T_{1}$ and $T_{2}$
denotational equivalence(/equality?) of types $T_{1}$ and $T_{2}$
[other] equivalence(/equality?) of types $T_{1}$ and $T_{2}$
etc...

Illustrations of the different types of equivalence/equality in a common programming language (ideally C++) would also really help.


texts:
https://en.wikipedia.org/wiki/B-tree#Initial_construction

Currently I know of 2 ways for building a B-Tree : bulkloading and just inserting key after key.

In the wiki example the keys are sorted, which I guess is a condition for this bulkloading concept.

What is the advantage of bulkloading if the keys are unsorted ?
 because I have to sort them myself still resulting in O(nlogn) , same as inserting key after key in the B-Tree.

Thanks.


texts: Array with queries to decrement or find sum of range

texts:
I have been given an array of integers of size n and q queries which can be of 2 types:
1.Decrement all elements in the given range by some value
2.Find sum of all elements in the given range
1<=n,q<=10^5
I have tried brute force but it gives TLE
Same goes for prefix sum and even segment trees which improve sum query but slow down updation
I cannot figure out how to update in O(log n)
Would lazy propagation help ?
If not , how else can i proceed with this?
P.S. First timer here . Apologies if i missed out on something


texts: Chromatic polynomial of a cycle - Interpreting its terms

texts:
I am learning about graph coloring. One of the exercise problems(grimaldi) led me to derive the chromatic polynomial for any cycle($C_n, n \ge 3$).

$P(C_n, \lambda) = (\lambda - 1)^n + (-1)^n(\lambda - 1)$, where $\lambda$ is the number of colours available

Is it possible to interpret the terms of above polynomial? I need help doing the same.


texts: How To Best Learn About Algorithms In Depth

texts:
I have been reading this site with a great deal of interest, but I find a lot of it goes over my head. This has made me wish to learn a lot more about algorithms and CS in general. As far as I can tell from my research, there are 2 main ways of doing this.

I can by a nice thick heavy book and work my way through it slowly but surely.
I can "learn by doing" and by a nice book, but instead of reading it cover to cover, move to parts that interest me and work on implementing and applying algorithms I like.
?

My question is, which of the above did the you use and would you recommend the same approach to someone else?


texts:
Assume I know that there is an algorithm of complexity
$ \mathcal{O}( log ( \vert V \vert^2 \vert E \vert ) ) $
for a Graph $G(E,V)$.

How do I compare this for example to the complexity of
$ \mathcal{O}( \vert V \vert^2 + \vert E \vert ) $ or other complexity algorithms on $G$.

There has to be a connection between $\vert E \vert$ and $\vert V \vert $ if I am right which is needed to solve this. But the only thing I found is $max .\vert E \vert = \frac{\vert V \vert }{2}(\vert V \vert -1)$, what does not help here and in many other cases.

Or should I just assume
$max .\vert E \vert = \frac{\vert V \vert }{2}(\vert V \vert -1)$ and $min.\vert E \vert = \vert V \vert -1$ ?
Btw. must a vertex be connected via an edge to the graph per definition?


texts:
I'm studying dimensionality reduction (SVD in particular), and I saw the following question:

  Assume we have a vector $x \in \mathbb R^d$, and consider $F(x)=s^t x$ ,  where
  $s$ is a $d$-dimensional random vector with entries drawn uniformly
  independently from $[-1,1]$.

What is the value of $\mathbb E[F(x)^2]$?

I'm starting now from zero, so I need to study more. The exercise asks for a formal proof, but I wish to just understand the philosophy.

I see many questions in which valued are drawn uniformly and independently from $[-1,1]$. Is this distribution used due to its symmetrical range? Is the expectation in this range often $1/2$?


texts:
I recently took a practice exam for the Computer Science GRE and this was one of the questions:

  Assume that set $A$ has 5 elements and set $B$ has 4 elements, how many functions exist from set $A$ to set $B$?

I had no idea what this means, I don't recall ever studying functions between sets, could someone shed some light on this question for me ?


texts: Given two formulae E[G F p] (which is CTL*) and EG EF p ( which is a CTL) with a Model prove that they are not equivalent

texts: I am trying to prove they are not equivalent , a model which satisfies the fist one but not the second since I think EG EF p is stronger than E[GF p],any leads would be helpful. Thanks.


texts: Can a safe state in Banker's Algorithm cause deadlock eventually?

texts: I know that unsafe state does not always mean deadlock. That is a situation that banker's algorithm does not detect deadlock accurately. I am just wondering if there is any example of a safe state that deadlocks?


texts: Would this algorithm fail to count solutions $>$ $1$ for Exact-3-cover?

texts:
Decision Problem: Given a set $S$, is there at least a given $N$ $>$ $1$ amount of solutions, for an $Exact~Cover~by~3-sets$ for $C%$?

$s$ = $1,2,3,4,5,6$

$c$ = $[[1,2,3],[4,3,2],[4,5,6],[5,1,6],[5,6,3]]$

Solutions

$[1,2,3],[4,5,6]$

$[4,3,2],[5,1,6]$

$N$ = $2$

Yes, there are $N$ solutions.

Algorithm

Remove sets that have repeating elements

(eg. [1,1,2] is deleted from $C$)
Remove sets that have elements that don't exist in $S$

(eg. [9,5,6] is deleted because $9$ not in $S$)
Make sure all elements in $S$ exist in $C$.

$for$ a $in$ $range(0, length(s)):$

$~~~~~~~~$$IF$ $s[a]$ $not$ in $c$:

$~~~~~~~~~~~~~$OUTPUT NO

Convert $C$ into a complete list

$WHILE$ $c[i]$ has [brackets]:

$~~~~~~~~~~$ DELETE [BRACKETS] FROM $C$

now $c$ = $[1, 2, 3, 4, 3, 2, 4, 5, 6, 5, 1, 6, 5, 6, 3]$

Finally, Decide

$n$ = $('Enter~for~N:~'))$

$yes$ = $0$

$for$ a $in$ $range$(0, $length(c)):$

$~~~~~~$$if$ $c$.count($c$[a]) >= $n$ :

$~~~~~~~~~~$$yes$ = $1$

$~~~~~~$else:

$~~~~~~~~~~$OUTPUT NO

$~~~~~~~~~~$HALT

$if$ $yes$ == $1$ :

$~~~~$OUTPUT YES

Edit: The above should do the same below.

yes = 0
for a in range(0, length(s)):
    if c.count(s[a]) >= n:
        yes = 1
    else:
        OUTPUT('No')
        break

if yes == 1:
    OUTPUT('yes')

Facts to consider

There cannot be any sets with elements that don't exist in $S$.
There cannot be any sets with repeating elements.
All elements in $S$ must exist in $C$. Else, a $no$ is given.
$N$ must be > $1$
If any element in $C$ occurs < $N$ times then the output must be $No$, because there wouldn't be at least $N$ solutions.

Question

Will this algorithm always work if the input is > $1$, and if no how would it fail?


texts: Is the complement of the Turing machine equality language not recursively enumerable as well?

texts:
The language that determines if two Turing machines are equivalent is not recursively enumerable because you can reduce it to the emptiness problem (does a Turing machine take no input).

Then for the complement of this language (ie. if two Turing machines are not equivalent) would you be able to reduce that to the non-emptiness problem (a Turing machine takes some input)?

And thus this language would be recursively enumerable.

However, I thought the Turing machine equality language is an example where both a language and its complement are not recursively enumerable.


texts:
Consider the following grammar:

$$
    A\to Ba|Aa|c \\
    B\to Bb|Ab|d
$$

How do I convert this grammar to be LL(1) by eliminating direct and indirect left recursion?

I have tried applying the rule which converts $A \to A\alpha|\beta$ to $A \to \beta A'$ and $A' \to \alpha A'$:

For $A \to Ba|Aa|c$, $\beta = Ba|c$ and $\alpha = a$.
For $B \to Bb|Ab|d$, $\beta = Ab|d$ and $\alpha = b$.

In this way I eliminate direct recursion from each one, but then when I try to substitute A or B with its product and eliminate indirect left recursion, the parsing table finds collisions so the grammar is not LL(1). Any ideas?


texts: Why every rational langage is the image of a local automaton

texts:
I have seen this result but I don’t understand why it’s true :

  Every rational language is the image of a local language by a morphism : $\phi : \Sigma^{*’} \to \Sigma^*$

I know what a local automaton is. It’s just an automaton that recognizes a local language. A local language is basically a language where all factors of size two are not in a certain set $S$.
Now if I take a morphism from this language then it will still give me a local language right ? (i.e. the image of local language by a morphism is a local language). So I didn’t understand this result, I mean every rational language is not local...

Thank you !


texts: Knapsack-type problem where the objective function is a ratio

texts:
I have a problem where I have a number of proposed initiatives each with a cost and payoff. I need to select a subset of these initiatives in order to maximize the ROI for the selected set as a whole while staying within a total cost constraint. Specifically, the problem is:

Maximize [sum(v_i*x_i)/sum(c_i*x_i)]
Subject to sum(c_i*x_i) <= C and x in {0,1}
Where v_i = payoff from initiative i, c_i = cost of initiative i, and x_i = 0/1 decision to select investment i or not

I understand that if the objective function in such a problem is just a sum then it is a 0/1 knapsack problem. If the function is a ratio as in this case, is there a specific name for this kind of a problem, or a recommended algorithm for solving it?


texts: How is this reduction of 3-SAT to Half-SAT not valid?

texts:
I am studying algorithms and there is a question in CLRS called the Half-SAT problem

We are given a 3-CNF formula with n variables and m clauses where m is even. We wish to determine whether there exists a truth assignment to the variables of f such that exactly half the clauses evaluate to zero and the other half to 1. Prove that the half 3-SAT problem is NP-Complete.

What is to stop me from taking any input f to 3-SAT and adding m clauses (y or y or y) where y is not in the original m clauses. The transformation of input and output is clearly polynomial time.
And, given a solution to 3-SAT, there must be a satisfying solution to Half-SAT (the solver sets y to false). If there is not a solution to 3-SAT this means that one of the original m clauses is not satisfied these clauses are disjoint from the new clause, so either m - 1 or 2m - 1 clauses are True.
Yet all the solutions online are more complicated which makes me think I am missing something obvious.


texts:
I have an undirected simple graph and an integer x.
My goal is to remove x edges from the graph so the largest connected component of the graph after the removal will be minimal.

I tried to think how to solve this problem, and i thought maybe using Girvan-Newman algorithm for removing edges with highest Betweenness. Works but very time consuming (running betweenness each round).

Any suggestions or other ideas how to tackle this problem?


texts: What algorithm would compute the maximum choices from two sets?

texts:
Given two vectors of integers of possibly unequal lengths, how can I determine the maximum result possible from accumulating choosing the maximum between corresponding pairs of numbers between the two vectors with extra zeros inserted into the shorter vector to make up for the size difference?

For example, consider the following two vectors as inputs:

[8 1 4 5]
[7 3 6]

The choices for inserting the zero and the resulting sum are:

[0 7 3 6]  => Maximums: [8 7 4 6]  =>  Sum is: 25
[7 0 3 6]  => Maximums: [8 1 4 6]  =>  Sum is: 19
[7 3 0 6]  => Maximums: [8 3 4 6]  =>  Sum is: 21
[7 3 6 0]  => Maximums: [8 3 6 5]  =>  Sum is: 22

Therefore, in this case, the algorithm should return 25.

I could do this by brute force by calculating for all permutations of placing zeros into the smaller vector (as just done above) but this would be computationally expensive, and worst in the case when one vector is exactly half the size of the other.

Is there a way to compute the answer in linear time proportional to the length of the longer vector even when the vectors differ in length?  If not, can we do better than the number of factorial permutations being chosen?


texts: Head Position Function of Oblivious Turing Machines

texts:
I am trying to understand oblivious Turing machines. According to the book of Arora and Barak, a TM $M$ is oblivious if the location of each of its heads at the $i$-th step of execution on input $x$ is only a function of $|x|$ and $i$ for every input $x\in{\{0,1\}^*}$ and $i\in{\mathbb{N}}$.

Here is my understand, suppose at step $t$, the head of tape $k$ is at position $p$, and the transition to the step $t+1$ will move the head to the right, i.e., to position $p+1$. However, the position function of step $t+1$ yields position $p-1$ for tape $k$. Then the machine will need to move all the content of tape $k$ two cells to the left and mark the symbol at position $p-1$ as head symbol.

I don't know if my understanding is correct. But if it is correct, the oblivious TM needs to store some symbols when it scans from right to left and shift the content. Like in the example, the OTM also needs to remember 2 symbols to make a correct shift. If the function can generate any position at any step, say $p-k$, it seems that the TM needs to be able to store a variant number of symbols, which seems to be hard to implement if we want to use an oblivious TM to simulate a standard TM.

Also I'm not sure if this is what the book really means because the content of the work tape is right after the input content, it seems that we can't shift the work tape content to the left because it will override the input content (although we can shift all the content to the left...).


texts:
About the state of art that I'm running ahead of Type Theory I have the these questions all related about history of Types.

Where did the idea of Type come from? (It seems that all start when Russell and Whitehead propose a way to avoid the contradiction that we know today as Russell's Paradox, am I right?)
Before considering the type concept, was there something similar? (Maybe a refinement of a set, but I don't find a reference distinct of Russell).
Who was the first person to put it on formal terms? (Was Russell with this paper of 1908 or ?


texts: Maximal number of rotations after deleting a node in an AVL tree

texts:
What is the maximal number $c$ of single rotations after deleting a node from an AVL tree? We treat double rotations as two single ones.

I know that it is $O(\log n)$ but I'm trying to find a more precise number – it is in $[\log n, 2\log n]$ of course.

Nevertheless, I am dying to see the exact value of $c$.


texts: Is this a generic way to convert any recursive procedure to tail-recursion?

texts:
It seems that I've found a generic way to convert any recursive procedure to tail-recursion:

Define a helper sub-procedure with an extra "result" parameter.
Apply what would be applied to the procedure's return value to that parameter.
Call this helper procedure to get started. The initial value for the "result" parameter is the value for the exit point of the recursive process, so that the resulting iterative process starts from where the recursive process starts to shrink.

For example, here is the original recursive procedure to be converted (SICP exercise 1.17):

(define (fast-multiply a b)
  (define (double num)
    (* num 2))
  (define (half num)
    (/ num 2))
  (cond ((= b 0) 0)
        ((even? b) (double (fast-multiply a (half b))))
        (else (+ (fast-multiply a (- b 1)) a))))

Here is the converted, tail-recursive procedure (SICP exercise 1.18):

(define (fast-multiply a b)
  (define (double n)
    (* n 2))
  (define (half n)
    (/ n 2))
  (define (multi-iter a b product)
    (cond ((= b 0) product)
          ((even? b) (multi-iter a (half b) (double product)))
          (else (multi-iter a (- b 1) (+ product a)))))
  (multi-iter a b 0))

Can someone prove or disprove this?


texts: Is complement $L = \{ w : |w|_{a} \equiv |w|_{b} \vee |w|_{c} \equiv |w|_{d} \}$ context-free

texts:
$L = \{ w : |w|_{a} \equiv |w|_{b} \vee |w|_{c} \equiv |w|_{d} \}$

In my opinion complement of the L language is

$L^{C} = \{ w : |w|_{a} \neq  |w|_{b} \wedge |w|_{c} \neq  |w|_{d} \}$

I choose to Ogden pummping lemma word $s = a^{p}b^{p + p!}c^{p}d^{p + p!}$ and $ p > n$

I would like to distinguish $c ^ {p}$. And then I have to have at least one distinguished symbol and the rest not distinguished and in my opinion it can't be pumped in any case because i can $c^{p}$ pumped to $c^{p + p!}$  so it isn't context-free

Do I think right?


texts: Do algorithms always have a return value?

texts:
I learned that algorithms written in programming languages always return some value, not necessarily an input value.

But, if the return type of the main function is void, then does the algorithm return any value?


texts: Consensus problem of distributed systems

texts:
I just started reading about distributed systems for the first time ever. There is a fairly slick proof of the impossibility of consensus in an asynchronous model using some combinatorial topology. On the other hand, there are multiple consensus protocols used in practical systems to synchronize distributed state machines like Paxos and Raft. It seems like the key to this perceived contradiction is what is called failure detection.

My question is the following: What does protocols like Paxos and Raft give up, i.e. how are they not contradicting the theorem? How does failure detection fit in here?

Are there any papers that discuss these relationships that are worth looking at?


texts: Is boolean formula isomorphism NP-complete?

texts:
Problem. Given 2 functions $f,~g$ of the same length $n$, decide if we can change variables in $f$ such that it will be identical to $g$. There are exponentially many non-isomorphical functions (as number of total assignments is bounded by exponent).

Example. $f=(x\land y\land z)\lor(\overline x\lor z)$. $g=(x\lor\overline y)\land(x\lor y\lor z)$.

Replacing $x$ and $y$ in $g$: $g = (\overline x\lor y)\land(x\lor y\lor z)$.

Replacing $y$ and $z$ in $g$: $g = (\overline x\lor z)\land(x\lor y\lor z)$. It became equal to $f$.

While this is considered not to be $\mathsf{NP}$-complete for 2SAT (we can compare their implication graphs and this is GI), is this problem $\mathsf{NP}$-complete for other variants of SAT (Horn3SAT, XOR3SAT, unambiguos 3SAT; if not, then at least 3SAT)?

Also there are two variations of problem:

All clauses in formula become equal (but in this case number of non-isomorphic functions is superexponential).
Number of satisfying assignments is equal (don't suspect to be in $\mathsf{NP}$ except for 2SAT; and it is $\mathsf{NP}$-hard for 3SAT).