texts:
Below is my simplification of part of a larger research project on spatial Bayesian networks:

Say a variable is "$k$-local" in a string $C \in 3\text{-CNF}$ if there are fewer than $k$ clauses between the first and last clause in which it appears (where $k$ is a natural number).

Now consider the subset $(3,k)\text{-LSAT} \subseteq 3\text{-SAT}$ defined by the criterion that for any $C \in (3,k)\text{-LSAT}$, every variable in $C$ is $k$-local.  For what $k$ (if any) is $(3,k)\text{-LSAT}$ NP-hard?

Here is what I have considered so far:

(1)  Variations on the method of showing that $2\text{-SAT}$ is in P by rewriting each disjunction as an implication and examining directed paths on the directed graph of these implications (noted here and presented in detail on pp. 184-185 of Papadimitriou's Computational Complexity).  Unlike in $2\text{-SAT}$, there is branching of the directed paths in $(3,k)\text{-LSAT}$, but perhaps the number of directed paths is limited by the spatial constraints on the variables.  No success with this so far though.

(2)  A polynomial-time reduction of $3\text{-SAT}$ (or other known NP-complete problem) to $(3,k)\text{-LSAT}$.  For example, I've tried various schemes of introducing new variables.  However, bringing together the clauses that contain the original variable $x_k$ generally requires that I drag around "chains" of additional clauses containing the new variables and these interfere with the spatial constraints on the other variables.

Surely I'm not in new territory here.  Is there a known NP-hard problem that can be reduced to $(3,k)\text{-LSAT}$ or do the spatial constraints prevent the problem from being that difficult?


texts: Does affinity propagation work well for for multidimensional data? While I was reading about it I couldn't find much information on this topic and all the examples I've seen we about 2D data. Could it be that Affinity propagation is still good for 3D and 4D data but is bad for 10+ dimensions? I am quite sorry for asking a question that could probably by myself after doing a research on the Internet, but I got to say that I am a very definition of newbie and all the information I've found was rather obscure to me. Don't want to make a false conclusion.


texts: Deterministic linear time algorithm to check if one array is a sorted version of the other

texts:
Consider the following problem:

Input: two arrays $A$ and $B$ of length $n$, where $B$ is in sorted order.

Query: do $A$ and $B$ contain the same items (with their multiplicity)?

What is the fastest deterministic algorithm for this problem?
Can it be solved faster than sorting them?
Can this problem be solved in deterministic linear time?


texts: What is the difference between caching, buffering and paging? Expecting a detailed answer on the OS level

texts: I have been reading about caching and buffering it seems about the same to me can't get hold of the differences clearly and paging, for now the only difference I understand between paging and caching is that, pages store locations of data that are frequently accessed and so CPU can use the address to locate the data, whereas in caching the data itself is stored and wanting process directly acquires the data from the cache. I'm not sure if I'm entirely right which is why I posted the above question.


texts:
I implemented a queue using two stacks which gives me $O(1)$ en-queue time, $O(1)$ amortised time. Now suppose I want to find top $10\%$ elements in the queue at any time. How am I suppose to implement it.

For example: queue takes the element in this order
$$ \{ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 \}.$$

Top $10\%$ elements means $10 \% $ of $20 = 2$.

Hence the answer will be $19$ and $20$.

The best way I can think of is to sort it and then calculate $N%$ of size of queue and return that many elements. This takes about $O (n \log n + k)$ time.

Is this the most efficient way? I came across this algorithm. It's a linear solution. It seems like an answer, however I would like to know your views.


texts: How to pack polygons inside another polygon?

texts:
I have ordered a few leather sheets from which I would like to build juggling balls by sewing edges together. I'm using the Platonic solids for the shape of the balls.

I can scan the leather sheets and generate a polygon that approximates the shape of the leather sheet (as you know, it's animal skin, and it doesn't come in rectangles).

So now, I would like to maximize the size of my juggling ball.

In my example, the polygons are regular ones, but I'm looking for a solution with simple polygons.

What is the largest scale factor that I can apply to my polygons so that they all fit inside the sheet ?

I am trying to minimize the waste by using as much as material as possible.

Obviously, cutting the polyhedron net into individual polygon will increase the space of possible combination, but also decrease the quality of the final geometry, because there is more sewing involved and accumulated errors. But this question is not about enumerating the different ways of unfolding a polyhedron. They can be considered independently. So the polygons are simple polygons.

Formally:

Input:

$P$ : a simple polygon (the target)
$S$ : the set of polygons I want to place
$G$ : a graph of $n$ simple polygons - each node represents a simple polygon in $S$, and there is one edge edge between each pair of polygons that share a common edge
$\alpha >= 0, \beta >= 0$ (usage of material and connectivity)

Output:

a scale factor $f$
$H$, a subgraph of $G$
$Loc$: a location and an angle for each polygon in $V(G)$
a measure of the quality $m$ of the solution: $ m = \alpha.f + \beta. {|E(H)|\over|E(G)|} $

Maximize $m$ subject to these conditions:

$ | V(H) | =  |V(G)| $  (1)
$ | E(H) | <= |E(G)| $  (2)
for every polygon $S_i$ in $S$, $S_i$ scaled by a factor $f$ at location $Loc(S_i)$ is inside $P$ (3)
polygons in $V(H)$ don't overlap (4)

( V(G) are the vertices in the graph, and S is the set of polygons, but they describe the same set of objects. Maybe there is a more compact way to do this.)

Explanation of the conditions:

(1) I want all the polygons to be in the final layout
(2) Some connections may be broken if necessary
(3) (4) the ball is made of leather

Here is the target polygon

Here is the set of polygons I want to pack:


texts: self embedded nonterminal in derivation of a Word

texts:
consider this question of finding words with no self embedded nonterminal in their derivation.
The author(cohen) says that If CFG is in CNF then all the words with length greater than 2^p are guaranteed to have self embedded nonterminal. So, all i need to do to solve these questions is to consider words that have length less than 2^p (where p is no. of "live" productions aka productions containing atleast one Nonterminal, in the grammar). But consider question 5 in image, i can easily tell any word of length >= 4 will have self embedded nonterminal in its derivation, without converting it into CNF. and this pattern is repeating in many questions. Do i really need to convert CFG in CNF? what could go wrong if i don't? Does this restriction on length still holds if CFG is not in CNF?


texts: Does $\mathcal{P}\neq\mathcal{NP}$ imply $\mathcal{NP}\neq\mathcal{NP}^{\mathcal{NP}}$?

texts:
I cannot see whether the implication in my question title holds. To me, it sounds reasonable to assume that, but I cannot find any source stating that this is true, false, or unknown at the moment.

So, does $\mathcal{P}\neq\mathcal{NP}$ imply $\mathcal{NP}\neq\mathcal{NP}^{\mathcal{NP}}$?


texts: I am really confused about clique problem and clique cover problem. I tried googling it,but I don't see to be able to visualise the clique cover problem.


texts:
I am slightly confused by some terminology I have encountered regarding the complexity of optimization problems.  In an algorithms class, I had the large parsimony problem described as NP-complete.  However, I am not exactly sure what the term NP-complete means in the context of an optimization problem.  Does this just mean that the corresponding decision problem is NP-complete?  And does that mean that the optimization problem may in fact be harder (perhaps outside of NP)?

In particular, I am concerned about the fact that while an NP-complete decision problem is polynomial time verifiable, a solution to a corresponding optimization problem does not appear to be polynomial time verifiable.  Does that mean that the problem is not really in NP, or is polynomial time verifiability only a characteristic of NP decision problems?


texts: How does a predictive coding aid in lossless compression?

texts:
I'm working on this lab where we need to apply a lossless predictive coding to an image before compressing it (with Huffman, or some other lossless compression algorithm).

From the example seen below, it's pretty clear that by pre-processing the image with predictive coding, we've modified its histogram and concentrated all of its grey levels around 0. But why exactly does this aid compression?

Is there maybe a formula to determine the compression rate of Huffman, knowing the standard deviation and entropy of the original image? Otherwise, why would the compression ratio be any different; it's not like the range of values has changed between the original image and pre-processed image.

Thank you in advance,

Liam.


texts:
I have an undirected Graph $G$, which is stored in the form of an adjacency list in external memory.

I'm looking for an I/O efficient algorithm which computes a valid coloring for $G$ with at most $k+1$ colors where I provide the $k$.

I tried searching for I/O efficient graph coloring algorithms but couldn't find anything which suits my needs. I would appreciate any pointers to websites/books/papers which could help me with this problem.

I have an internal memory of size $M$ and a practically unlimited amount of external memory. Data is transfered from external to internal memory in blocks of size $B$. By I/O-efficient algorithms I mean algorithms which are designed to minimize the number of transfers between internal and external memory.


texts:
I came across this question:

At the beginning of transmission t, a TCP connection in congestion avoidance mode
has a congestion window w = 60 segments.Packet loss is observed during transmission
rounds t, t+10, and t+20 by getting multiple ACKs. What is the congestion window
at the end of round t, t + 10, and t + 20?

If there's no further packet loss, when will the window of w = 60 segments be reached again?

Answer:

Congestion window is halved during transmission round t, leading to w = 30. At the
beginning of transmission round t + 10, the window has increased to w = 40 but it will be
halved again during transmission round t + 10 to w = 20. Similarly, after transmission round
t + 20, the window will be w = 15. With no further packet loss, 45 transmission rounds later
at t + 65, the window will reach again the original size of w = 60.

I know that due to multiple ACKs, packet loss reduces the window size to half. So at t+10, w = 30 makes sense. However, I don't really get the rest. Why does the window size increase by 10? And at t+20, why doesn't it reduce to 10 instead of 15? If someone could explain the steps, that would be great.


texts: p constant in pumping lemma for regular languages

texts:
We have a language

$L = \{ a^{n^{2}}, n < 12\}$ We have to find minimum constant P for pumping lemma.

What does p represent here? I thought p in pumping lemma represent number of states , yet the right answer is $p >= 122$ , i would understand if it was $p <= 122$.

So for example it would be correct when $p = 155$. But how could we create such automat with 155 states?


texts: does appending an element to a list through a for loop work in O(1) time or O(n) time? In addition, what is the time complexity does "".join that list into a string work in?


texts: Djikstra's algorithm to compute shortest paths using at least k edges

texts:
I have a graph G = (V, E) where each edge is bidirectional with positive weight. I want to find the shortest path from vertex s to vertex t using at least k edges but less than 20. No vertex may be repeated in a path.

I am aware of this problem: Dijkstra's algorithm to compute shortest paths using k edges?

That problem wants to find the shortest paths using at most k edges.

My current idea is to create the product graph via V' = V x {0, 1, 2, ..., 20} and then ignore any shortest paths from (s, 0) to (t, n) where n < k.  However, because the product construction essentially duplicates nodes, I am not aware of a way to ignore duplicate vertices in the path-finding algorithm.

P.S. If k were very large, say, k = |V|, wouldn't this be the Hamiltonian path problem and therefore NP-complete?


texts: Lexicographically minimal string rotation

texts:
In this page: https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation there is the Booth's Algorithm for lexicographically minimal string rotation but there is no proof. I can't access to article(https://www.sciencedirect.com/science/article/pii/0020019080901490?via%3Dihub), can someone put here the proof?
Maybe also here: https://www.cambridge.org/core/books/applied-combinatorics-on-words/C64AAEDFA9A2EFE97671453EADE29E6C there is something on this argument.


texts: In instruction pipelining, can we forward an operand more than one clock cycle?

texts: Most operand forwarding examples that use the standard 5-stage MIPS pipeline forward operands from EX or MEM by ONE clock cyle to a later instruction. Is it possible to do so for more than one (from the 5th to the 8th clock cycle, for example)?


texts: Why "reduce to", not the other way around?

texts: This action confuses me for a while. As you know, once we come up with a problem and we want to know how hard it is, we will do the "reduction". Intuitively, if we prove problem B is as hard as problem A, we can know the complexity boundary of B. But if problem B is harder than A, why we call the reduction process -- reduce problem A to problem B, not reduce problem B to A?


texts: Why can we ignore the constant factor in Weis's proof of the Master Theorem

texts:
In the 4th edition of his Data Structures textbook, Weis gives a proof of part of the Master Theorem.  This proof says "Let us ... ignore the constant factor in $\theta(N^k)$ ...  I don't understand why it ignoring that constant is valid.  (I know that the real Master Theorem is broader  than the version presented in the text.  I'm just having trouble understanding the argument presented in the text.)

Specifically, the relevant part of Theorem 10.6 on page 469 is

The solution to the equation $T(N) = aT(N/b) + \Theta(N^k)$ is $T(N) = O(N^{log_b} a)$ if $a > b^k$

The proof includes the phrase "ignore the constant factor in $\theta(N^k)$ ..." and then goes on to use a telescoping sum to get

$T(N) = T(b^m) = a^m \sum_{i=0}^m (\frac{b^k}{a})^i$

At this point, he argues that because $a > b^k$, then the sum is a geometric series with a ratio less than 1.  However, if we don't ignore the constant in the $\Theta$ expression, isn't there a constant inside the summation that would affect whether the geometric series converges?


texts: Why do ACLs (access control lists) have better persistence than capabilities?

texts: Although I understand the principles on which both ACLs and Capabilities operate, I do not see why on system restart it would be favourable to store privileges by using ACLs, instead of capabilities lists as it is suggested in the Operating systems course I am taking. In other words, why do ACLs have better persistence than capabilities?


texts: How to find sum of maximum K elements in range in array

texts:
Recently, I came up to the following problem:

Given array $A$ of size $n$ and integer $k$, We should answer $Q$ questions of the type:
for  given range $[l, r]$ we should find sum of the $k$ maximum elements over all $A_i$ such that $l \leq i \leq r$.

Trivial solution would be to sort all values in the range and iterate over the k biggest elements, however this has complexity $O(QN\log N)$. After some searching on the internet, I found out that this can be solved by segment trees, however I couldn't think of proper use of segment trees for this problem.

Is it possible to solve this problem in complexity better than $O(QN\log N)$


texts: Proving the existence of a $\Pi_1$-sentence in True Arithmetic that is independent of Peano Arithmetic

texts:
I am trying to wrap my head around how to prove the following statement:

  There exists some $\Pi_1$-sentence $A$ such that $A \in \textbf{TA}$ but $\{A, \neg A\} \cap \textbf{PA} = \emptyset$.

$\textbf{TA}$ represents True Arithmetic which is the set of statements in the language of arithmetic that are true under the natural model $\underline{\mathbb{N}}$. $\textbf{PA}$ represents Peano Arithmetic which is the set of statements in the language of arithmetic that are logical consequences of the set of Peano axioms $\Gamma$. In this context, we are under the assumption that $\textbf{PA}$ is, in fact, sound.

Under the assumption of soundness of $\textbf{PA}$ and its axiomatizability we can begin to prove parts of this statement. If $A \in \textbf{TA}$ then we are sure that $\neg A \notin \textbf{PA}$ by the soundness of $\textbf{PA}$; moreover, since $\textbf{PA}$ is axiomatizable  (hence $\Gamma$ is recursively enumerable) by the completeness of the first-order $LK$ proof system if $A \in \textbf{PA}$ then $\textbf{PA} \vdash A$. With this in mind, the main statement I am interested in proving might be the following:

  There exists some $\Pi_1$-sentence $A$ such that $A \in \textbf{TA}$ but $\textbf{PA} \not\vdash A$.

Is this going to just be a simple usage of the Godel sentence $G$ or am I missing something?


texts: Is it OK to change any polynomial time to another polynomial time without breaking equivalency of Turing machines?

texts: Is it true that adding to a Turing-machine-equivalent an "oracle" calculating any polynomially calculable (in this machine) function using some other nonzero polynomial time than this machine itself could do, leaves the new Turing machine equivalent (in the sense that polynomial algorithms remain polynomial and exponential ones remain exponential)?


texts: Solving recurrences using substitution method

texts:
I already have a solution for this problem but it's just not making sense to me.

Here is the problem (It's from Introduction to Algorithms by CLRS found in CH.4):

  Show $T(n) = 2T(\lfloor n/2 \rfloor +17)+n$  is $O(n \log n)$

This is what I have so far:

So Assume $T(k) \leq cn\lg n$, for $k<n$.

$\qquad \begin{align*}
  T(n) &= 2T(\lfloor n/2 \rfloor +17)+n \\
       &\leq 2c(\lfloor n/2 \rfloor +17)\lg(\lfloor n/2 \rfloor + 17) +n \\
       &\leq 2c(n/2 + 17) \lg (n/2 + 17) + n \\
       &= c(n + 34) \lg((n+34)/2)+ n
\end{align*}$

And this is where I stop understanding what is going on. Looking at the solution to this problem tells me:

  Note that $(n + 34)/2 \leq (3n)/4$ for $n \geq 68$
  so that $\lg((n + 34)/2) \leq \lg((3n)/4) = \lg(n) + \lg(3/4)$ for $n \geq 68$.

But it fails to tell me why/how we know that $(n+34)/2 \leq 3n/4$ for $n \geq 68$. Where did this number come from and how would I arrive at this if I did not know the solution beforehand?


texts: Minimize sum of squares of rows in matrix when sum of columns have some constraint

texts:
I'm looking for an algorithm that can find any matrix $a_{j,i}$ such that
$$
  \sum_{i \in I} \left(\sum_{j\in J} a_{j,i}\right)^2
$$
is minimal, while also for each $j\in J$ satisfying the constraint
$$
  k_j = \sum_{i \in I} a_{j,i}
$$
where $k_j$ is some non-negative constant. Furthermore every $a_{j,i}$ must be non-negative, and some arbitrary selection of $a_{j,i}$s in the matrix are fixed to be zero.

This problem models a situation where each $j$ has some fixed amount of resources that need to be divided in some way between a row of buckets. The constraint saying that some values are fixed to zero means that some buckets are missing on some rows.

We then want to find the way to divide the resources between buckets such that the columns of buckets have their contents divided as equally as possible between them.

Notice that if no values are fixed to zero, the solution is easy, since we can simply assign the values
$$
  a_{j,i} = \frac{k_j}{\#I},
$$
where $\#I$ is the number of columns. This way every line of buckets has an equal amount of resources assigned, and since decreasing the contents in one line would increase the contents of another, this is optimal.

The only solution I've currently been able to find is using some sort of linear programming solver that supports quadratic objectives, but I hope that this problem could be solved more efficiently than that.

Nontrivial example Suppose we are looking for a 3x3 matrix where
\begin{align}
  1 &= a_{1,1} + a_{1,2} \\
  2 &= a_{2,1} + a_{2,2} + a_{2,3} \\
  1 &= \phantom{a_{3,1} +\,} a_{3,2} + a_{3,3}
\end{align}
Notice that some terms are missing in these sums. This is equivalent of fixing those terms to zero.

We then want to minimize
$$
  (a_{1,1}+a_{2,1})^2 + (a_{1,2}+a_{2,2}+a_{3,2})^2 + (a_{2,3}+a_{3,3})^2.
$$
Notice that a lower bound on the minimum is $3\cdot\left(\frac{4}{3}\right)^2=\frac{16}4$, since in this case the $4$ total resources are equally divided.

In this case we can achieve that lower bound with the solution
\begin{bmatrix}
1/3 & 2/3 & 0 \\
1   & 0   & 1 \\
0   & 2/3 & 1/3
\end{bmatrix}
which indeed has the minimum $\frac{16}3$.

A different solution is
\begin{bmatrix}
2/3 & 1/3 & 0 \\
2/3 & 2/3 & 2/3 \\
0   & 1/3 & 2/3
\end{bmatrix}

Example that doesn't hit lower bound of minimum. Suppose we have the constraints
\begin{align}
  1 &= a_{1,1} + a_{1,2} \\
  4 &= \phantom{a_{2,1} +}\,\, a_{2,2} \\
  1 &= \phantom{a_{3,1} +}\,\, a_{3,2} + a_{3,3}
\end{align}
In this case we have $a_{1,1} \leq 1$, but in order to reach the lower bound where every line is equal to $2$, we must have $a_{1,1} = 2$, which is not possible.

In this case there is only one optimal solution, which is:
\begin{bmatrix}
1 & 0 & 0 \\
0 & 4 & 0 \\
0 & 0 & 1
\end{bmatrix}


texts: Which features can be considered for neural network based SAT solving?

texts:
I'm trying to implement SAT solver, based on backtracking algorithm and BCP. This SAT solver is trying to pick one literal from each clause, from 3-CNF SAT instances. I've implemented a neural network based heuristic to pick valid literal at first, and degree of how valid is given literal from clause is determined by neural network output from 0.0 to 1.0 value. SAT instances on which I'm operating are big (hundreds of thousands clauses and similar amount of variables).
Currently I'm approaching about 97% accuracy on the training set, and about 90% accuracy on the test set, which means, that statistically, solver picks wrong literal in clause in 1 case out of 10, which is not bad, but not ideal.
The network has constant size vector at its input (about 30-40 neurons, depending on features that I'm picking in particular test scenario). The features are mainly some statistics about given SAT instance and situation which is currently solver in - they are derived from list of already solved literals, current clause, and clauses sharing literal, that I'm asking a netowrk to compute the score for. These features are commonly ratios, counts and conditionals (like 0.0 or 1.0 if given condition is present) - For example ratio of clauses reduced by choosing literal to the total clauses count, or ratio of trimmed clauses by this literal to total clauses count etc.
The score of 90% in the test set, is still not enough to solve such istances quicker.
The question is, which features should i consider to add to the input ANN vector to achieve better accuracy?
EDIT:
Here is the list of used features in one of test scenarios:
For the selected literal L in clause C (which is currently neural network focusing on), and partial solution S (which was previously selected literals - all valid):

Number of clauses that has 3 literals, but under partial solution S, was reduced to 2 literal clauses
Number of clauses that has 3 literals, but under partial solution S, was reduced to 1 literal clauses
Number of clauses that has 2 literals, but under partial solution S, was reduced to 1 literal clauses
Number of clauses that has N literals, but under partial solution S, has still N literals
Number of clauses entirely removed under partial solution S (at least one literal in such clause belongs to S)
Number of clauses sharing literal L
Number of clauses sharing literal -L
The same features as above, but repeated to one of other literal in clause C

By clauses sharing some literal L, I mean in these clauses L appears: for example 1,2,3 and 1,-4,5 (sharing literal is 1).
Above features are normalized, so the input vector is always valued between 0.0 and 1.0 for each feature.


texts:
What is meant by the term 'state' in a finite-state machine?

I have not seen a proper definition on the web and am looking for a university-level answer.

Thank you in advance.


texts: Register Allocation and Definition of Interference

texts:
In my textbook on compiler design [1], it describes interference between two variables (the property that they cannot be in the same register at once) as follows:

  Definition 9.2:  A variable $x$ interferes with a variable $y$ if $x \neq y$ and there is an instruction $i$ such that $x \in kill[i], y \in out[i]$ and instruction $i$ is not "$x := y$"

This definition does not make sense to me. If I interpret this in plain English:

  A variable interferes with another if some variable $x$ is being overwritten, while some variable $y$ is live at the exit of the instruction, and the instruction is not $x := y$ and $x$ and $y$ have distinct values.

To me, a more logical definition of interference is if two variables $x$ and $y$ appear in the same $gen$ set of some instruction $i$. This necessarily means that these two variables are used (i.e their value) in the same instruction. Is there some crucial detail that I am missing?

For those interested, this definition appears on page 197 of the book referenced above.


texts: How can Machine Learning be used to find attributes/characteristics of graphs?

texts:
I am aware ML is not necessary for many graph classification problems (as the graph theorists have many clever solutions), but I'm specifically interested in ML approaches to these types of questions. I imagine if you had enough training examples (1000s?) you could use a supervised approach for classification type of questions. I also assume an adjacency matrix would be a good data representation to use for ML approaches to undirected graph classification. Example problems are shown below.

1.) Given an undirected graph represented by an adjacency matrix, broadly speaking, how (if possible) could machine learning be used to find if said graph has a hamiltonian path?

2.) Given an undirected graph represented by an adjacency matrix, how can ML be used to determine if the graph is a tree?


texts: Does $\mathsf{NSPACE}( f (n)) = \mathsf{coNSPACE}( f (n))$ hold for $ f(n) < \log (n) $?

texts:
It's known that for $f(n) \geq \log n$,  $\mathsf{NSPACE}(f(n)) = \mathsf{coNSPACE}(f(n))$.

What if $f(n)<\log n$? Are they also equal?


texts: How is context switching disabled in a process?

texts: By what provision is context switching disabled in a process ? Or is it the case that if a process is in in kernel mode , context switching is disabled by default ?


texts:
I'm working on a proof for following question

$L=\{(R,S)\mid \text{R,S are regular expressions and } L(R)\subset L(S)\}$. Show that this language is/isn't decidable.

A language is decidable iff we have a Turing machine that halts for all input strings. If $L$ is regular, we can construct a DFA and therefore a Turing machine. Now we just have to show that this DFA/TM accepts/declines every input.
At least that's what I was told. But isn't it sufficient to show that $L$ is regular? Since reg. languages have a DFA and im pretty sure a DFA is decidable (because it can be converted to a TM and is finite)?
Since $L(R)\subset L(S) \Rightarrow L(R)\cap L(S) = L(R)$ we get that $L=L(R) \Rightarrow L$ regular?


texts: Where were the ideas of vote, accept and commit phases originally introduced?

texts:
In the Stellar Consensus Protocol SCP, the voting procedure follows a 3 phase commit i.e. vote, accept and confirm i.e. see section 5.

Is this a novel introduction or has this been previously been introduced, and if so, where? More specifically, I refer to definitions of these given in section 5.


texts: Relative position of a point with respect to a 3D non-convex polyhedron with triangular facets

texts:
I have a 3D triangle mesh with the following properties:

unique vertices (triangles are stored as 3 vertex indices, the indices are stored in a point set backed up with an octree and a tolerance, to ensure that they are unique)
watertight: each edge of the triangle mesh is shared by exactly two triangles
The following adjacency matrices are available: triangle<->vertices, triangle<->edges, edges<->vertices, where a<->b means that I can access a for b, and b for a, in O(1).
a bounding volume hierarchy (BVH) of the triangles is available.

I want to accurately compute whether a point is inside, outside, or on the surface mesh in O(log(N_triangles)).

Computing whether a point is on the surface mesh is easy, I just use the BVH to find the closest triangle to the point, and perform a point triangle intersection.

I am attempting to computing whether a point is inside/outside the mesh using odd/even-count ray casting but I don't know how to handle some the following cases (when the point does not lie on the triangle):

intersection(ray, triangle) -> single point

triangle vertex
point on triangle edge
point inside triangle

intersection(ray, triangle) -> edge (ray lies on the plane of the triangle)

triangle edge (ray coincides with a triangle edge)
line segment whose endpoints are not any triangle vertices
line segment with one triangle vertex as end point

When the intersection result is a single point, the following approaches seem to work correctly:

a point inside the triangle (not a vertex or a point on an edge), I increase the count by one.
a triangle vertex, I add the vertex to a set and increase the count by one, so that vertices are only counted once.
a point on an edge, I add the edge to a set and increase the count by one, so that that point is only counted once.

When the intersection point is a line segment, that's a bit more complicated.

I guess that for each triangle where this happen I could take the vertices of the adjacent triangles, project them to a 2d plane with normal in ray direction, and check if the ray intersects that plane, but I am not sure if this will work, nor what to do when e.g. all these points lie on a plane (because all the adjacent triangles lie in the same plane as the triangle).


texts: Calculating speedup of this parallel program

texts:
I have a sequential program that has a cost of
$(\sum_{n=1}^{N} Ti )$  Where Ti is the load time of the i-th element, so if consider $Tm = max({Ti}) $ i can approximate the sequential cost as $N*Tm$ that has a linear cost.
Let's suppose that i have c cores and i decide to parallelize this program, i can divide the loading of these items among c cores so i have (At most)
$(\sum_{n=1}^{N/C} Ti ) \leq Tm \cdot N/C$
So in brief:
Sequential (approx.) cost: $N*Tm$
Parallel(approx.) cost: $[N/c]*Tm$
How can i calculate the speedup? what about the efficiency?
Thank you.


texts: How to interpret scoped variables next to each other within Lambda Terms and CL-terms?

texts:
In both the lambda calculus ($\lambda$-calculus) and Combinatory Logic (CL), we have the notion of function application. For example:

\begin{array}
& \left( \lambda x . x \right) y = y & \text{(function application) } \\
([ x ] . x)  y = y & \text{(function application) } \\
\end{array}

Fair enough. But, in each of these respective systems, how to interpret the following?

\begin{array}
\left( \lambda x . \underbrace{xy}_{\text{?}}) \\
([ x ] . \underbrace{xy}_{\text{?}})\\
\end{array}

Is $xy$ inside these scopes also just function application?

EDIT: To be clear, I know $xy$ doesn't further reduce to anything within these expressions, but I am still curious as to how this term should be interpreted by a human.


texts:
I am struggling in finding the name of this game (in order to find research papers related to it in the literature).

Given an initial word $X$ and a target word $Y$, what is the minimum number of (letter) flips needed for $X$ to reach $Y$ assuming $X$ and $Y$ having the same number of letters, we flip only one letter each time and such sequence(s) of flips exist.

That is, there is a sequence $A_1\rightarrow A_2\rightarrow \dots\rightarrow A_n$ where $X=A_1$ and $Y=A_n$ and every thing in between is a correct word (i.e. has a meaning in a given dictionary).

For instance, $X=Pork\rightarrow Park\rightarrow Dark=Y$

Yes; I do not have the minimum knowledge in games.


texts: What is +1 in binary search time complexity

texts: Why is binary search time complexity for worst case log (n) + 1 instead of just being log(n)? the way I understand it, the number of times we divide the list till we find our desired element is log (n) times in the worst case scenario. Where does this extra 1 come from? (it's log (n) + 1 according to the power point of my class)


texts: What is the right data structure for MST in a stream

texts:
In a single pass stream you can compute the minimum spanning tree (MST) in an undirected graph using the following algorithm:
H ← ∅
for each (u,v) in the stream
    H ← (u, v)
    if H includes a cycle
            remove largest weight edge in the cycle

To make this fast we need a data structure that allows you to check if (u,v) makes a cycle and also allows you to remove the largest weight edge from a cycle.
What is a suitable data structure for this?


texts: For a flow network, is it possible to show that there always exists a maximum flow which would assign integer values to all the edges?

texts: Is it possible to prove that for a flow network, there always exists a maximum flow which assigns an integer value to every edge?


texts:
I start with a matrix, lets say 4x4. So I want the N top scores, with the sum of one element of each row. For example:

M[4][4] = {
    (13, 8, 5, 3),
    (11, 9, 7, 4),
    ( 8, 6, 2, 1),
    ( 6, 5, 4, 1)
}

So the top 6 scores of that matrix will be:

top_scores = {
    (13, 11, 8, 6), // 38
    (13, 11, 8, 5), // 37
    (13, 11, 6, 6), // 36
    (13, 11, 8, 4), // 36
    (13,  9, 8, 6), // 36
    (13, 11, 6, 5), // 35
}

What I want is to get the best scores directly, not calculating all the possible combinations and picking the top ones, because the matrix can be much bigger. I've tried to solve it with different approaches, but I failed in all of them.


texts: Determine the main memory size using cache line and cache size

texts:
Assume a computer architecture with 32 bit address.The system has been designed with 1MB cache which comes with 64KB cache line(cache block size).

1.What is the maximum main memory capacity this system can have?

Since computer architecture is 32 bit does it mean word size is 4 bytes?am i correct?

Words in one cahce line= 64KB/4Bytes= 2**18 words

Total cache blocks= 1MB/64KB=8 cache blocks

Am i going the right direction?I dont know what to do after this.Plz point me t the right direction.Thank you


texts: How to represent bottom element (integer domains) in SMT formula

texts:
I'm doing some work with static analysis and need to represent local variables as SMT formulas.  In general this is fairly straight forward, depending on the domain of the static analysis.  However, my question lies when needing to represent impossible or infeasible values, e.g., divide by zero paths from the static analysis under an integer domain.  This is often referred to as the bottom element, ⊥.
I'm struggling to develop a formula which can represent these "impossible"  (integer) values.  Is there a way to do this?
I've been thinking along the lines as an impossible inequality, but I've been unsuccessful thus far.  Similarly, I've thought about attempting to represent using divide by zero within an SMT formula, such as the following Z3/SMT formula:
(declare-const a Int)
(assert (= (/ a 0.0) 1.0))
(assert (= (/ a 0.0) 2.0))
(check-sat)

However, given the application, I'm not sure this is going to be helpful.
Application: I'm using this to compare results between two different static analyses between different domains.
tl;dr:
How to represent infeasible, bottom integer elements as SMT formula?
Edit
I didn't try this enough, maybe the question is more along the lines of "is there a more eloquent way to model a bottom value besides the following?":
(declare-const a Int)
(assert (and (>= a 0) (< a 0)))
(check-sat)

The above will yield unsat, as expected.  And since I'm trying to compare results of different static analyses, I can formulate questions about locals as such (is a top value equal to a bottom value):
(declare-const a Int)
(declare-const b Int)
(assert (= (and (>= a 0) (< a 0))
           (or (>= b 0) (< b 0))))

(check-sat)

This will also yield unsat.


texts: Can we solve this problem more efficiently than trying all possible combinations

texts:
Here is the context of the problem I am struggling with.

I have a set of strings, for example:

"my name is john",
"i like cheese",
"what is your name",
"the cheese is in the kitchen",
"john likes cheese"

Let $S$ be union of all words appearing in the previous strings.
my,name,is,john,i,like,cheese,what,your,the,in,kitchen,likes

The problem seeks an optimal combination of words, that construct the maximum number of strings from the initial set, under the following conditions :

Words are separated by a comma.
The sum of the lengths of selected words is bounded by a constant number (say 25).
A sting can be rebuilt only if all words occurring in this string are contained in the selected combination.

For example, the combination john,cheese,like,likes,i uses 24 characters and allows to rebuild  both "i like cheese" and "john likes cheese".

Here is what I have tried to implement.

First, I sort every single word by the number of strings it's contained in. In this example:

is      (3)
cheese  (3)
john    (2)
name    (2)
my      (1)
i       (1)
like    (1)
what    (1)
your    (1)
...

So I'm now using this array: [is, cheese, john, name, my, i, like, ...], let us call it initial_array

And here is the idea of the algorithm I amm using.
First, I initialize another array of strings containin of all the strings g the first word from initial_array, let's call it new_array:

[is]

Then, while the total length of all the strings of new_array plus the commas does not exceed the limit of 25 chars, I append them:

[is,cheese] (9)
[is,cheese,john] (14)
[is,cheese,john,name] (19)
[is,cheese,john,name,my] (22)
[is,cheese,john,name,my,i] (24) --> best potential combination so far, can rebuild 1 string: "my name is john"
[is,cheese,john,name,my,i,like] (29) --> up to 25 chars

When I reach a length up to 25 chars, I try to replace the last element of new_array by the following of initial_array:

[is,cheese,john,name,my,i,what] (29) --> up to 25 chars
[is,cheese,john,name,my,i,your] (29) --> up to 25 chars
...

And when I reach the last word of initial_array, I remove it from new_array and replace the previous one by the next one of initial_array:

// if the last word of initial_array is "likes"
[is,cheese,john,name,my,i,likes] --> we reached the last word
[is,cheese,john,name,my,like]
[is,cheese,john,name,my,like,what]
etc...

If this solution allows me to try all the possible combinations without repetitions, the running time increases exponentially as words are being added to the initial_array, and quickly becomes unusable. So I am looking for a better idea to improve this algorithm.

Thank you for your help.


texts: Genetic Algorithms - Why wouldn't we use the principle of Elitism?

texts: In Genetic Algorithms, the idea of elitism is that we keep our best solution from the generation in our population regardless of what happens throughout the iteration. However, elitism seems to be discussed as an optional thing; so what situations is using elitism actually a negative aspect of a genetic algorithm?


texts: Find a truth assignment of 2SAT that has the most number of true variables?

texts:
Given a 2SAT instance in CNF where each clause has at most two literals. Let $m$ be the number of clauses and $n$ be the number of variables et let $k$ be a positive number.

Question: Is there a truth assignment such that the number of variables that are true is $k$ or more?

I cannot find the name of this problem, if it was already studied? If so, is it NP-hard?


texts: Conflicting definitions of language accepted by Turing Machine?

texts:
I am reading Papadimitriou, Computational Complexity, page 24, where it is says

  We say that $M$ accepts $L$ whenever for any string $x \in (\Sigma - \{\sqcup\})^*$, if $x \in L$, then $M(x) =$ ``yes''; however, if $x\notin L$, then $M(x) = \nearrow$.

The key issue is what happens for $x \notin L$. This definition insists that $M$ must not halt for $x \notin L$. Other sources I read, e.g., this says that  if $x\notin L$ then either $M$ does not halt, or $M$ halts at ``no''.

Prima facie this seems to me to be a significant difference. Could someone clarify to me if these definitions are equivalent and if there is no loss of generality in talking of acceptance in the sense of Papadimitriou? Or is only one of these definitions the correct one?


texts: Select certain number of column elements of a stochastic matrix, maximum one element per row

texts:
Consider a $m \times n$ Matrix.
Every column represents a class and every row an observation. Every row/observation is a probability distribution, hence every row sums up to 1.
We now want to choose elements $a_{i,j}$ of the Matrix.
For every column $k_j$ elements have to be chosen, but we can choose just one element per row. The sum of the chosen elements have to be maximized.

I guess this problem is NP-hard. I didn't found an efficient solution.
To prove that, I want to find a reduction from a NP-hard problem to my problem.

Hopefully someone has an idea for a reduction (or an efficient algorithm).


texts: What needs to be done after deleting an item in a hash table built under opening addressing with linear probing

texts:
In some textbook problems, the problem asks me to insert a bunch of elements and remove a bunch of elements.

Insertion is done using linear probing, i.e. h = XmodR + I, when there is a collision, I just hop one item over until I find a good spot

But for deletion...do I just remove the item from the table? Is that all there is to it? Can someone inform me whether I should be reshuffling the existing items after the removal?

Attached is a sample of what kind of problem I'm describing

In the above problem, if I were to remove 58, is there anything else I need to do?


texts: Books to prepare before reading Knuth's The Art Of Computer Programming (TAOCP)

texts: Many people say that TAOCP is not supposed to be read as a book (actually a volume of books), but if I decide to go that way, which math/computer science books/topics do I need to study to help me follow it? There is a related question on stackoverflow but I would like to read the suggestions of cs.se users.


texts: Union and intersection of a regular and a non-regular language

texts:
Lets say we have $L_1$, which is a regular language and $L_2$ which is not. Are $L_1 \cap L_2$, $L_1 \cup L_2$ , $L_1$ \ $L_2$ and $L_1 \cdot L_2$ are always non-regular languages?

We know that two regular languages always gives us a regular language under all of the above. I can't find anywhere any proof that combination of two languages, one regular and one non-regular results always in a regular or a non-regular language. It seems for me that it should be a non-regular in all above cases. Am I wrong?


texts: What is the relation between parsing languages and checking languages?

texts:
I have looked at a number of textbooks on computability theory. They typically have the following form:

Define a language class (regular, context-free, context-sensitive, recursively enumerable)
Define an automaton that recognizes the class (finite automaton, pushdown automaton, linear-bounded automaton, turing machine)

However, another fundamental question is how to parse a language. I have not found an treatment of parsing as a computational problem in these textbooks.

Is there a simple relation between an automaton that recognizes a language, and an automaton that parses the language (and outputs a parse tree)?


texts: If a bitstring is compressible, is the minimal Kolmogorov sufficient statistic most likely large or small?

texts:
If a bitstring is incompressible, then its minimal Kolmogorov sufficient statistic (MKSS) is zero, since the bitstring is best represented by a structure function that enumerates bitstrings, and thus the size of the index in the set is the bitstring's length.

However, if a bitstring is compressible, this is no longer true, and its MKSS is greater than zero.

My question is, given that a bitstring $b$ is compressible, $K(b) < \ell(b)$, is its MKSS more likely to be closer to zero or closer to $K(b)$?

My intuition is that it is more likely to be closer to zero for a reason similar to why most bitstrings have $MKSS(b) = 0$.

Also, can a probability be related to the length of the MKSS given that $b$ is compressible?

\begin{align*}
P\{MKSS(b) > a | K(b) < \ell(b)\} = ?.
\end{align*}


texts: Algorithm to translate a deterministic Büchi automaton to LTL (when possible)

texts:
Linear temporal logic and deterministic Büchi automata are incomparable: DBA cannot express $FGa$, and LTL cannot express "at least each odd letter is 'a'". But sometimes it is interesting to know whether the language of a DBA can be expressed in LTL.

I need an algorithm that decides whether a language of a given DBA is describable in LTL. Do you know algorithms for that?


texts: Can it be decided whether there exists a string accepted by a given NFA at least k ways?

texts:
Can I think this way:

We can convert a NFA to a RE using GFA.

We build a series of GFAs. At each step, one state (other than start or accept) is removed and replaced by transitions that have the same effect.

So, if we can convert k REs which have different forms but accept same language, then there must exists a string that the NFA accepts along k paths.

Does that sound right?

How to prove it properly?


texts: How can you construct 3-regular graphs with minimal diameter?

texts: Given an even $N$, is it possible to procedurally construct a 3-regular graph $G$ with $N$ vertices such that the maximum distance between any pair of vertexes is the minimum possible for that $N$? I know that a cube, for example, is the solution for $N = 8$, but what about other N's?


texts: Algorithm to compute power function on interval [0, 1]

texts:
I am looking for an efficient algorithm to compute $$f(x) = x^a, x\in[0, 1] \land a\,\text{constant}$$

If it helps, $a$ is either $2.2$, or $1/2.2$. Knowing valid values for $x$ and $a$ could make it possible to take some shortcuts a general pow function cannot make.

General tailor series expansion has some serious convergence problems when $x \to 0^+$, at least when $a < 1$.

The algorithm must be faster than pow
The maximum error on the specified interval must be less than or equal to $10^{-4}$.


texts: Use substitute algorithm to prove T(n) =4T(n/2) + n^2 compact lower bound

texts:
how to use substitute algorithm to prove T(n) =4T(n/2) + n^2 compact lower bound.
this is a algorithm of my class home work,but i dont know how to solve it.


texts: TM that finds the middle of an input string in O(n) time

texts:
Is it possible to find a TM with O(n) complexity that finds the middle of an input string?
Or at least to prove that it cannot be done?

I can use a two-taped TM if it helps.


texts:
If you have a dynamic array where the size $s$ becomes $4s$ when you fill the array and there are no delete operations. How much do you spend per insert?

I am asking because when the size doubles, you only spend 3 dollars per insert (based on this analysis). But when you make the size 4 times bigger, then for some of the inserts you would need to spend 3\$ and for the rest you spend 2$?

Is this right? Or do we always need to spend the same amount? And if there is extra we just store it in the bank?


texts:
I want to learn about Volterra classifiers in-depth to understand the following papers
Papers

https://openaccess.thecvf.com/content_cvpr_2014/papers/Kang_Convolutional_Neural_Networks_2014_CVPR_paper.pdf
https://www.researchgate.net/publication/51855543_Trainable_Convolution_Filters_and_Their_Application_to_Face_Recognition#:~:text=Each%20Volterra%20classifier%20is,has%20a%20three%2Dtiered%20architecture.
I planning to do a mini project and want to understand these papers.
Need introductory materials for better understanding


texts: Restricted version of the Clique problem?

texts:
Consider the following version of the Clique problem where the input is of size $n$ and we're asked to find a clique of size $k$. The restriction is that the decision procedure cannot change the input graph into any other representation and cannot use any other representation to compute its answer, other than $\log(n^k)$ extra bits beyond the input graph. The extra bits can be used for example in the brute-force algorithm to keep track of the status of the exhaustive search for a clique, but the decision procedure is welcome to use them in any other way that still decides the problem.

Is anything known at this point about the complexity of this? Has any work been done on other restrictions of Clique, and if so, could you direct me to such work?


texts: In Hashing-collison resolved by chaining: Intuition behind $O(1) + \alpha= \Theta(1+\alpha)=O(1)+1+\frac{\alpha}{2}-\frac{\alpha}{2n}$

texts:
Hashing-collison resolved by chaining: $O(1) + \alpha= \Theta(1+\alpha)=O(1)+1+\frac{\alpha}{2}-\frac{\alpha}{2n}$
I was going through the text Introduction to Algorithms by Cormen et. al. and in the chapter dealing with hashing with collision resolved by chaining I found that the asymptotic tight bounds were just simple written just after finding the raw expression of the running time of the SEARCH algorithm. The details are as follows:

Here the authors assume that
$$m=\text{number of slots in the hash table}$$
$$n=\text{number of elements in the hash table}$$
$$\alpha=\frac{n}{m} \text{(the load factor)}$$

Theorem 1: In a hash table in which collisions are resolved by chaining, an unsuccessful search takes time $\Theta(1+\alpha)$, on the average, under the assumption of simple uniform hashing.
The expected running time is found out as $O(1) + \alpha$ which they write simply as $O(1) + \alpha=\Theta(1+\alpha)$

So first I made an attempt to show to the tight bound mathematically then try to give an intuitive logic of the same.
The authors do not quite mention here the parameter or the variable whose approach to $\infty$ defines the asymptotic behaviour. Now since the $n$ is the size of the set of keys and it is sort of the input size, I assume it as the parameter and let $\alpha = f(n)$ and by definition of $\alpha$ we have $f(n) \geq 0$
Now $c$ be the constant corresponding $O(1)$ for all $n>0$
Now let us consider the function $g(n)= 1+f(n)$,
We choose constants $\lambda,\mu >0$
We assume $c<\lambda$ and also $1<\lambda$ such that $f(n)<\lambda.f(n)$.
so we have $c+f(n)<\lambda(1+f(n)) \tag 1$
Again let us assume $\mu<c$ and $\mu<1$ such that $\mu.f(n)<f(n)$
so we have $\mu(1+f(n))<c+f(n) \tag 2$
From (1) and (2) we have , $O(1)+\alpha= \Theta(1+\alpha)$ as $\alpha=f(n)$
Now about the intuition, what I feel is that since for any $f(n)$ we have $f(n)=\Theta(f(n))$ and we do not know which is dominant: the $O(1)$ term or $\Theta(\alpha)$; we incorporate both of them and hence we have the above result.

Similarly.

Theorem 2: In a hash table in which collisions are resolved by chaining, a successful search takes time $\Theta(1+\alpha)$, on the average, under the assumption of simple uniform hashing.
Now the expected running time is found as $O(1)+1+\frac{\alpha}{2}-\frac{\alpha}{2n}$ and the authors write it as $O(1)+\frac{\alpha}{2}-\frac{\alpha}{2n}=\Theta(2+\frac{\alpha}{2}-\frac{\alpha}{2n})=\Theta(1+\alpha)$

Again I move on to my hardcore proof, now in $1+\frac{\alpha}{2}-\frac{\alpha}{2n}$ the term $\frac{\alpha}{2n}$ becomes insignificant when $n \rightarrow\infty$ so $1+\frac{\alpha}{2}-\frac{\alpha}{2n} = \Theta(1+\frac{\alpha}{2})$
Now let $a>0$ and $b>0$ be the hidden constants in $O(1)$ and $\Theta(1+\frac{\alpha}{2})$ $\forall n>0$
Now let us consider the function $g'(n)= 1+f'(n)$, where $f'(n)=\alpha$
We choose constants $\lambda ',\mu ' >0$
So for the proof we need to have,
$$\mu' (1+f'(n))< a+b.(1+\frac{f'(n)}{2})< \lambda' (1+f'(n))$$
$$\iff \mu'+ \mu'f'(n))< (a+b)+\frac{b}{2}.f'(n))< \lambda'+\lambda'.f'(n))$$
which holds if $\mu'<\frac{b}{2}<\lambda'$
So from the above proof we have $O(1)+\Theta(1+\frac{\alpha}{2})=\Theta(1+\alpha) \tag 3$,
but I find it quite difficult to find (3) intuitively...

Doubt:
What is the intuition which the authors have used to find the tight bound directly in (3) ?


texts: Case where anti-dependency doesn't need pipeline stalling

texts:
While exploring the various types of data hazards in a pipeline, I came across a statement in my book which said that anti-dependency mayn't lead to cycle stalling.

But i couldnt find at example for the same. Can anyone help me with it please?

Thanks in advance!


texts: is mappings optimization problems onto neural networks still a thing?

texts: Is mappings optimization problems onto neural networks still a thing? I only found papers are written prior to 1999. These old papers mostly deal with Hopfield network, which i read is obsolete and only for theoretical properties. So is there any progress with neural networks (maybe different ones to Hopfield) and solving optimization problems (for examples combinatorial ones, like TSP, Vertex Cover, Job scheduling ects.)?


texts: Search algorithm that returns the lowest cost path to one, of many possible goal nodes?

texts:
I am working on a problem where I have a set of goal nodes of which some, all, or none of will appear in a search tree.

Is there a search algorithm which returns the lowest cost path to one goal node, when there are potentially many different goal nodes present in a tree, or failure?

This can obviously be solved by iterating through the set of goal nodes and applying a search algorithm on each of the goals and then comparing the paths to find the lowest cost path, but I would like know if there is a more elegant solution.

Thanks


texts: Prove multiple cell move instructions don't increase power of Turing Machines

texts: How can you prove that multiple-cell-move instructions, for example (X, Y, 5R) and (X, Y, 17L), do not increase the power of a Turing Machine?


texts:
I am interested to know the complexity of the NAE-HORN-SAT problem
(not all equal).  We know that HORNSAT is $\mathsf{P}$-complete, but
on the other hand, NAE-SAT is $\mathsf{NP}$-complete.  I want to know
what can we say about NAE-HORN-SAT problem.  Let me define the problem
formally:

  Given: One Boolean formula $\phi$ is given to us in CNF where each
  clause has at most one positive literal (HORN-property).
  Question: Is there any assignment for the input variables of
  $\phi$ such that any clause has at least one False and at least one
  True literal (NAE-property) ?

N.B.:

Positive literal: any variable directly,
Negative literal: negation of any variable.
True literal: literal is assigned to Boolean True by any assignment,
False literal: literal is assigned to Boolean False by any assignment.

According to Schaefer's dichotomy theorem, this problem must be either
in $\mathsf{P}$ or $\mathsf{NP}$-complete.  I can just find one
polynomial reduction from HORNSAT to this problem, which proves
actually nothing.  Is there a polynomial time algorithm to solve this
problem?

Or, is there any way to prove this problem to be $\mathsf{NP}$-hard?
Any thoughts about this ?


texts: Using the Chomsky-Schutzenberger theorem to prove a language is not context-free?

texts:
The Chomsky-Schutzenberger representation theorem states that a language $L$ is context-free iff there is a homomorphism $h$, a regular language $R$, and a paired alphabet $\Sigma = T \cup \overline{T}$ such that $L = h(D_\Sigma \cap R)$, where $D_\Sigma$ is the Dyck language over $\Sigma$. This is a necessary and sufficient condition for a language to be context-free, so in principle it seems like it should be possible to show that a language is not context-free by showing that there are no valid choices for $h$, $\Sigma$, and $R$ satisfying the theorem.

This earlier question talks about approaches for showing that a language is not context-free, but doesn't mention this approach. Additionally, I can't seem to find any constructive examples of proofs of non-context-freeness along these lines.

Are there any known examples of languages that have been shown not to be context-free by means of the Chomsky-Schutzenberger theorem?


texts: Big O vs Big $\Theta$ during coding interview

texts:
Almost every time I see an article about time or space complexity, people are expressing the complexity with Big O, whereas it should be $\Theta$.
From the book "Cracking the coding interview":

  "In industry (and therefore in interviews), people seem to have merge Θ
   and
   together. Industry's meaning of big O is closer to what academics mean by
  Θ
  , in that would be seen as incorrect to describe printing an array as $O(n^2)$. Industry would just say this is O(N)"

In an interview context, would it be considered ok to say $\Theta$ instead of O?
If the interviewer is asking : "What's the Big O of this algorithm?", is it alright to answer :"The time complexity of this algorithm is $\Theta$(n)"?
I'm wondering if most interviewers would think I'm trying to outsmart them by saying that. But I don't feel comfortable by replacing O by $\Theta$ since they don't have the same meaning.


texts: Complexity of 4-coloring a map with constraints

texts:
The well-known Four color theorem states that every map which is divided into regions, can be colored using 4 colors such that no two adjacent regions have the same color.
In fact, there exists a quadratic algorithm for 4-coloring planar graphs.
Suppose you are given a map (e.g. the world's map) and a list of $k$ constraints, e.g. Greece is colored blue, and Spain, Italy and Uruguay are red.

Can this problem be solved in poly time if $k$ is part of the input?
Can this be solved in poly time if $k$ is fixed (i.e. is the problem fixed parameter tractable with respect to $k$)?


texts:
Even if programming by itself is not an integral part of computer science,
I would bet any B.Sc. student learns fundamentals of binary code, fundamentals of assembly code and at least one high programming language (above assembly).

What programming languages always learned in computer science B.Sc.?

I define programming as: writing source code in one or more computer languages, of the programming language type.


texts: Aside from problems such as the halting problem, which aren't computable, are there any useful problems in computer science that can only be solved in time $O(2^{2^n})$, or in time $O((n!)!)$? I've heard of many difficult problems which require O(2^n) algorithms, but none that have required running times worse than that... are there any of that sort?


texts: Query about FP Divide latency and Initiation Interval

texts:
Latency is defined as the number of intervening cycles between an instruction that produces a result and an instruction that uses the result. The initiation or repeat interval is the number of cycles that must elapse between issuing two operations of a given type.

In the Appendix C, pages 52-54 of Computer Architecture: A Quantitative approach 5th edition, it was mentioned that

the FP adder is of 4 stages and pipelined, so latency =3(No. of pipeline stages -1) and initiation interval =1 (as pipelined)
the FP multiply is of 7 stages  and pipelined, so latency =6(No. of pipeline stages -1) and initiation interval =1 (as pipelined)

So for
3. The FP divide of 24 stages and unpipelined, so latency =23(No. of pipeline stages -1) and initiation interval =24 (as unpipelined). But it was mentioned that   the latency was 24 and initiation interval was 25.

latency and initiation interval and FP pipeline

Why is this?

Can anyone explain me? As I missing something


texts: Quickly pruning edges below average weight for a membership-based weighting

texts:
I have points represented as sparse high-dimensional binary vectors, or put another way, I have a list of groups that each point belongs to. For two points, the edge weight between them is $\sum_i 1/|B_i|$ where $|B_i|$ is the number of points that belong to group $i$, and the summation is over all shared groups that both points belong to.

My distribution on group size is very skewed  where there are a few large groups that contain about 5 million points and many small groups that contain 2-10 points. Each point belongs to about 5 groups on average and there are roughly a million groups. Also there are roughly 10 million points total. The goal is to identify all edges that have weight above some pretty high threshold, e.g. the mean edge weight.

Currently the best algorithm I have in hand is to check all pairs of points within each group and compute the edge weight between them. However there are groups that give rise to on the order of $10^{13}$ pairs, which is too high. I was thinking of maybe going through groups from smallest to largest and somehow eliminating a lot of pairs to check once the larger groups are reached, since after all the overall edge weight has to be above a pretty high threshold. But I'm not 100% sure how to formalize that, or whether it would really help. Any help would be greatly appreciated, either advice on how to make my pruning idea effective, or even completely fresh ways to approach the problem.


texts: Practical usage of the λ-calculus self-interpreter and the self-reducer?

texts:
I came across the paper: "Efficient Self-Interpretation in Lambda Calculus" by Torben Mogensen, 1994:

http://repository.readscheme.org/ftp/papers/topps/D-128.pdf

It talks about the intepreter $E$ and the reducer Lambda Calculus forms, but after a brief reading I cannot see, what is the real usage for them. Could someone elaborate and point out what is the function of self-interpreter (also the reducer) in this text?

$$E = Y \space λe.λm.m (λx.x) (λmn.(em)(en)) (λm.λv.e(mv))$$

Addition

I found short notes of this topic from:
https://crypto.stanford.edu/~blynn/lambda/#_lambda_calculus_with_lambda_calculus

  E⌈M⌉ evaluates to the normal form of M if it exists


texts: Does hiding variables work in terms of blocks or line-by-line?

texts:
Let's assume I have the following code:

declaration of a
declaration of b
..a..b
{
  ..a..b
  declaration of a
  declaration of b
  ..a
}

In this code {} represent the inner block. declaration represents binding occurrence, and .. represent applied occurrence.

So my question is that is it legal to use the outer scope variables inside an inner scope and then redeclare them ? If so how does the hiding of outer variables system work (Does it start to work when it sees a redeclaration)? Thanks in advance.


texts: What data structure would efficiently store integer ranges?

texts:
I need to keep a collection on integers in the range 0 to 65535 so that I can quickly do the following:

Insert a new integer
Insert a range of contiguous integers
Remove an integer
Remove all integers below an integer
Test if an integer is present

My data has the property that it often contains runs of integers in the collection.  For example, the collection might at one point in time be:

{ 121, 122, 123, 124, 3201, 3202, 5897, 8912, 8913, 8914, 18823, 18824, 40891 }

The simplest approach is just to use a balanced binary tree like the C++ std::set, however, using that, I am not leveraging the fact that I often have runs of numbers.  Perhaps it would be better to store a collection of ranges?  But that means a range needs to be able to be broken up if an integer in its middle is removed, or joined together if the space between two ranges in filled in.

Are there any existing data structures that would be well suited for this problem?


texts: Simple (non-mathematical) definition of polynomial time?

texts:
Computational Complexity Theory is complex.  My understanding of polynomial time is in relation to other time complexity classes, such as non-deterministic polynomial time.  This is fine for engineers and mathematicians, but I'm looking for a simple definition of the term, suitable for laypeople.

Would it be incorrect to cast polynomial time as "time measured in (computational) operations?"

Obviously there would be subsequent qualifications for different time complexity classes, and time complexity may be more properly a ratio based on the problem size, but again, that's a bit more complex than what I'm looking for here.


texts: As far as I know, finite languages have a finite number of strings or words, while context-free languages are generated by context-free grammars. I don't know which aspect should I know that they are correlated with. All I know is that finite languages are regular, and regular languages are context-free. How should I know this?


texts: Integer Programming - packing wolves and sheep

texts:
I'm new to linear/integer programming and I'm trying to solve a little problem I made up. I want to "pack" animals into a minimum number of bins where some of the animals cannot co-exist (wolves and sheep). Here is a picture of my little flow network that's guiding me.

Imagine that each animal node outputs 1 animal of that type.
The maximum each bin can hold is 2 animals
You don't want wolves together with sheep

I've figured out how to write constraints that would allow me to minimize the number of bins if there is no distinction in input type.

What I've tried so far is the following. I take two inputs and sum them. I also take the input type and compare them so that I get either a zero or 1. At the final node, multiple the 0 or 1 with the summation and you get either the sum or nothing.

My questions come into play here in the following:

Is there such a thing as a comparison operation that you can use in Integer Programming? I can subtract two types and if it's zero, they're the same, otherwise no. I'm not sure how one would represent this mathematically if one wanted to solve something like this in software.
My "solution" below won't work for just one sheep node since I can't compare sheep to anything to get the sheep through. Actually, if I were to do wolf and sheep first, and then wolf, this would return 0 as well. Would I have to duplicate my little tree snippet and run through all combinations of input nodes? Is there a more scalable way to do this?

Any suggestions are appreciated.

mj


texts: Voronoi diagram of a set of simple polygons

texts:
The Voronoi diagram is a well-known data structure that helps solve various proximity problems. We have several nice algorithms that build this diagram for $n$ point in optimal time $O(n\log n)$.

I am interested to solve this problem for a set of simple, disjoint polygons and I am collecting information about known solutions. Actually, what matters to me is to know for every polygon which other polygon shares an edge of the diagram with it, which is a quasi-equivalent problem (I mean that the graph structure is enough, I don't need the exact geometry).

I have heard of the compact Voronoi diagrams and the are certainly an option. I am also interested in the Voronoi diagram of the convex hulls of these polygons, which might be easier to construct, but in this case it is no more guaranteed that they are disjoint.

My polygons have a few dozens vertices and there are a few dozens of them. Approximate solutions are allowed. Speed and ease of implementation are more important.

I would welcome any information about these problems and their algorithmic resolution.


texts:
What are the possible ways to calculate $(x^y) \bmod z$ quickly for very large integers?
Integers $x,y \lt 10^{10000}$ and $z \lt 10^6$.


texts: Why table-driven LL (1) parser does not work with division and subtraction?


texts:
Is the treewidth of this graph equal to 2?

I have tried to prove it through the definition of a tree decomposition.

If its not correct can someone give any hints?


texts: What's the value of this game (rebalancing counters)?

texts:
Suppose you have the following game:

There are infinitely many counters $\{c_1,c_2,\ldots\}$, all initialized to 0.

In each step, you may choose a counter $c_i$ and increase it's value by 1.

Unfortunately, every $T$ steps, each counter that has a positive value is decremented by 1.

Also, the values of the counters are bounded by $M$, so you can't increment a counter any further.

Given as many steps as you like, can many positive valued counters can you reach?

EDIT: As this question is unanswered for two weeks, I have posted it in CSTheory as well.

Detailed buildup for $\approx T\log(M)$ positive counters:

While you have less than $T-1$ counters at value $M$:

Increment the minimal index counter whose value is strictly less than $M$.
This has to converge as the sum of the counters are bound to increase every $T$ steps.

Let $r = T$.
While ($c_0>0$)

a.  while ($c_0>c_r$)

Increment $c_r$

b. $r = r + 1$

Now for the analysis: first observation is that the number of positive counters is $r$.

Now let $m_r$ be the maximal value $c_{r}$ have reached. For $r=T$ we get $M(1-\frac{1}{T})$. For $r=T+1$ we get $m_r(1-\frac{1}{T})=M(1-\frac{1}{T})^2$, or in general $$\forall r\geq T:m_r = M(1-\frac{1}{T})^{r-T+1}$$

Next we notice that when $\forall m_r$ is achieved, $c_0=m_r$.
This means the loop will halt when $m_r < 1$ (give or take integrality and end-of-game-strategies).

This gives us
$$M(1-\frac{1}{T})^{r-T+1} < 1$$
$$(1-\frac{1}{T})^{r-T+1} < M^{-1}$$
$$({r-T+1}) \log (1-\frac{1}{T}) < -\log M$$
$${r-T+1}  < \frac{-\log M}{\log (1-\frac{1}{T})}$$
$$r  < \frac{-\log M}{\log (1-\frac{1}{T})} + T - 1$$
$$r  < \frac{\log M}{\sum_{k\geq 1}^{\infty} {\frac{1}{kT^k}}} + T - 1 < T(\log M + 1) -1$$

Does this look right?

Is it possible to do better? Can anyone prove this is optimal?


texts: Context-free grammar to a pushdown automaton

texts:
I'm trying to convert a context free grammar to a pushdown automaton (PDA); I'm not sure how I'm gonna get an answer or show you my progress as it's a diagram... Anyway this is the last problem I have on a homework that's due later today, so I'd appreciate some kind of help, even if it's just an explanation of the correct answers diagram. I need a PDA corresponding to this CFG:

$$S \rightarrow aSa | bSb | B$$
$$B \rightarrow bB | \epsilon$$

I know it will have to push X every time 'a' is read before a 'b', and pop X every time 'a' is read after a 'b'. But I'm not sure how to arrange the PDA in order to tell which a's came after b's. Also, I'm unsure of how to deal with the b's in terms of the stack, as there can be as many in the middle of the string as you want. Help appreciated.

Thanks, Pachun


texts:
I'm relatively familiar with spacial access methods and related data-structure such as Kd-trees and R-trees, but there is a related issue which I don't remember having seen mentioned when reading on that subject.

I'm concerned with the 2 dimension case.  Programs manipulating shapes often sort overlapping shapes in z-order, giving a predictable behavior.  Querying a data structure for a range access usually provides the shapes in the region in an order not guaranteed to respect the z-order.  It is obviously possible to sort the result, but are there some data-structure allowing to avoid that step? Especially when z-order is considered important only for overlapping shapes.


texts: Asymptotic Runtime of Interrelated Functions

texts:
I have two functions $S$ and $T$ which are interrelated and I want to find the asymptotic worst case runtime. The fact that they are interrelated is stumping me...

How would I find the asymptotic runtime $S(n)$ and $T(n)$?

$$
\begin{align*}
S(n) &= 2S(n/4) +  T(n/4) \\
T(n) &=  S(n/2) + 2T(n/2)
\end{align*}
$$


texts: Writing a Context-Free-Grammar using Backus Naur Form for a for-loop?

texts:
I'm pretty new to CFG, and I've tried out some samples as well. As of now I'm trying this for-loop to write it in CFG using BNF:

Start{
    int z = 20;
    for(int b = 0; b < 5; b++)
    {
        //some statement
    }
}

Attempted BNF:

<program> ::= Start <blockstatements>
<blockstatements> ::= <statement> | <statement>; | <statement_list> | <empty>
<statement> ::= <typespecification> <varDeclaration> <assignment-operator> <expression>
<typespecification> ::= char | short | int | long | float | double | string
<varDeclaration> ::= a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | x | y | z
<assignment-operator> ::= =
<expression> ::= <value>
<value> ::= <digit> | <letter> | <number> | <word>
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<letter> ::= "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" |
            "T" | "U" | "V" | "W" | "X" | "Y" | "Z" | "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" |
            "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z"
<number> ::= <digit> + <digit> | <digit> - <digit> | <digit> * <digit> | <digit> / <digit>

The above CFG isn't complete and I wanted to make sure that I'm doing it correctly. Am I heading towards the right path? Should it be written as above or have I missed anything?

Any help could be appreciated.


texts: Examples of exact computation of Kolmogorov complexity?

texts:
First question: It is known that Kolmogorov Complexity (KC) is not computable (systematically). I would like to know if there are any "real-world" examples-applications where the KC has been computed exactly and not approximately through practical compression algorithms.

Second question and I quote from the "Elements of Information Theory" textbook:
"one can say “Print out the first 1,239,875,981,825,931 bits of
the square root of e.” Allowing 8 bits per character (ASCII), we see that
the above unambiguous 73 symbol program demonstrates that the
Kolmogorov complexity of this huge number is no greater than (8)( 73) =
584 bits. The fact that there is a simple algorithm to
calculate the square root of e provides the saving in descriptive complexity."
Why take the 584 bits as an upper bound for the KC and not include the size of the actual "simple algorithm" that calculates the square root of e?? It is like cheating...


texts: No. of disk blocks writes required for writing the file

texts:
Assume that a file is written using write(fd, buf, K) system calls, where fd is the file descriptor, and K, the number of files to be written to the current file offset which is a multiple of the disk block size D. The total number of disk block writes required to be executed before the system call returns is:

(a) is equal to K/D

(b) is less than K/D

(c) is greater than K/D

(d) None of the above.

In my opinion, the answer should be (c). But the solution manual says it's (d).

I believe the number of file writes required for writing a file is $ceil(K/D)$
So, the answer should be (c).

Am I correct? If not, what am I doing wrong?

Thanks in advance!


texts: Auction where each bidder bids on a bundle of items

texts: Is there some optimal solution in an auction where each bidder bids on a bundle of items?


texts: Is it possible to solve 3SUM in $O(n^2)$ time?

texts:
Problem: 3SUM

Input: Three lists A, B and C of integers and an integer k. Each list contain $n$ numbers.
Task: Decide whether there exists a tuple (a, b, c) ∈ A × B × C such that a + b + c = k.

Question : Is it possible to solve 3SUM in $O(n^2)$ time using constant space ? Prove or disprove it


texts: Why is my proof wrong for $L = H_{TM} \cap \overline{A_{TM}} $

texts:
$A_{TM} = \{<M,w> | $ M  is a TM and M accepts w $\}$

$H_{TM} = \{<M,w> | $ M  is a TM and M halts on w $\}$

I thought that $L = H_{TM} \cap \overline{A_{TM}} \in R$

But I saw the proof for why $L \in RE \setminus R$

But I don't understand why this is wrong:

$H_{TM} \in RE$ and $\overline{A_{TM}} \in Co-RE $

We know that $RE \cap Co-RE = R$

So why is this wrong $L = H_{TM} \cap \overline{A_{TM}} \in RE \cap Co-RE = R$ ?


texts: It is well-known that 1-in-k SAT is NP-complete for k=3. What about for k > 3?


texts: Find all items which are subsets of an item

texts:
I have a problem that I think should have been studied. I am looking for algorithms for it.

Each item is a set of key-value pairs.
Let $x$ be an item and $F$ be a set of items.

Each key and each value can appear multiple times.
The number of possible keys and possible values can be arbitrary large.

We are given $x$ and $F$. We want to find all those items $y$ in $F$ such that $y.val \subseteq x$.

For example,

$x = \{(a,1), (b,2), (c,3), (d,4)\}$

$F= \{$
$(A, \{(a,1)\}), $
$(B, \{(a,1), (b,2)\}),$
$(C, \{(a,1), (b,3)\}),$
$(D, \{(b,2), (c,3), (d,4)\}),$
$(E, \{(a,1), (b,2), (c,3), (d,4)\}),$
$(F, \{(a,1), (b,2), (c,3), (d,4), (e,5)\}),$
$(G, \{(a,1), (b,2), (c,3), (e,5)\})$
$\}$

The answer is:
$A$ yes, $B$ yes, $C$ no (right keys, wrong values), $D$ yes, $E$ yes (exact match),
$F$ no, $G$ no.

Has this problem been studied?

The problem seems similar to finding features from a DNA sequence or detecting plagiarism in a document.

I asked this problem in theoretical CS stack exchange and did not get very helpful answers. https://cstheory.stackexchange.com/questions/18052/find-all-items-which-are-subsets-of-an-item


texts:
Consider two strings $S$ and $T$ of length $n$. Here both the strings $S$ and $T$ consists of only
( and ) that is made of parenthesis. I need to find a string $w$ which is balanced parenthesis and it should be sub-sequences of both $S$ and $T$ among all those strings $w$ i need the maximum length strings.
This problem is clearly a dynamic programming problem, but i am having hard time in finding states and also their transitions. Could anyone help me.
P.S - Problem E , but it is in Russian


texts:
The proof for the $\Omega(n\log n)$ lower bound for calculating the convex hull by using order-type predicates that I have come across uses the fact that if there was possible to calculate the convex hull in time better than this, then we could do sorting using the same technique, but as it is known that sorting has an lower bound of $\Omega(n \log n)$, hence the lower bound for calculating the convex hull is also the same.

My question is, what if we don't want the convex hull in a cyclic order (clockwise or anticlockwise)? What if we just want the points lying on the convex hull. Surely, in such a case, we can't reduce sorting to this problem and hence the logic for lower bound does not hold. Do there exist any such algorithms? Or some alternative proof that still makes the previous lower bound hold true for this problem?


texts: Minimum cost edge in path between nodes (tree)

texts:
I'm working on a problem and I've managed to design an efficient algorithm, but I'm stuck at the last part.

After some processing I'm left with a tree and I have to answer several queries of the form $(x,y)$, such that for each such query we have to print the minimum cost edge on the path from $x$  to $y$.

Now, this can be done by getting the smaller value between the shortest edge on the path from $x$ to $\text{lca}(x, y)$ and the shortest edge on the path from $y$ to $\text{lca}(x, y)$.

My question is, how do we actually get the min-cost edge on the path from say $x$ to  $\text{lca}(x, y)$  ? Do we just simply use a breadth first search? And wouldn't that actually beat the purpose of computing the lowest common ancestor?


texts: Solving "coin exchange" for coins of power values by greedy algorithm

texts:
When solving the problem of coin exchange by greedy algorithm, why will we will always have the correct result if the coin values are $1, a, a^2, \cdots, a^n$, where $a\ge 2$ and $n\gt 0$?

For example, if $a = 3$, $n =3$, we get the following coin values: 1, 3, 9, 27. When total exchange is 16, answer is 4 coins, as returned by greedy algorithm, $16=9+3+3+1$.


texts: Max Flow / Linear Programming Reduction Variant

texts:
While studying max flow / LP, I came across a couple of reduction problems that gave me a bit of pause:

Here are two variants of the standard Maximum Flow problem. Show that both of them can be solved efficiently by reducing each to linear programming. (Note: (1) and (2) are separate problems)

(1) Each directed edge has, in addition to its capacity, a nonnegative lower bound on the flow that it has to carry.

(2) The total outgoing flow from each node $v$ (excluding the source node and sink node), does not equal the total incoming flow, but is smaller by a factor of $(1 - \epsilon_v)$, where $\epsilon_v$ stands for a loss coefficient associated with node $v$.

My initial thoughts on each are as follows:
(1) Aside from the constraints for the standard Max Flow problem, add the following constraint for each edge $e$:
$0 \leq l_e \leq f_e \leq c_e$ (where $l_e$ stands for the lower bound on the flow).
Is this all the modification that is necessary for a reduction?

(2) For every vertex $v$ except the source and sink vertices:
$($sum of flow into $v)=($sum of flow out of $v - (1-\epsilon_v))$, where $0 \leq \epsilon_v \leq 1$.
I figured that since the problem states the sum of outward flow must be smaller than incoming flow by some factor, epsilon must be nonnegative and at most 1. Am I missing something?


texts: What does "Outstanding" mean in the context of architecture?

texts:
I'm taking an Advanced Computer Architecture course and I've come across the term "outstanding" a few times and I've searched online about what it means in the context of computer science/architecture but I can't find anything relevant. For example, on my notes there are some references such as:

"IBM Power5 allows 8 outstanding cache line misses"
"Each thread can perform 8 outstanding memory accesses"


texts:
Modification of vertex cover problem.
Given a graph G,does G have a vertex cover with 10 vertices? Is this problem still in NP?
Given a graph G and integer k, does G have a vertex cover with k vertices?
Is there any important difference between this two problems?


texts:
I want to implement mutual exclusion for $n$ processes. Critical section code:

int turn = 0;        /* shared control variable */

Pi:                  /* i is 0 or 1 */
while (turn != i)
   ;                 /* busy wait */
CSi;
turn = 1 - i;

This solution from this page but it is only made for two processes.

I tried to adapt it for $n$ processes like this:

turn = 0 // shared control variable

i = turn;

while (turn != i);

// CS

turn = (turn + 1) % n;

Does this work?


texts: Equivalent terms in call-by-name but not in call-by-value

texts:
Working in the untyped lambda-calculus, I'm asked to give two terms that are equivalent in call-by-name semantics but not in call-by-value.

Call $\text{fls} = \lambda x. \lambda y. y$ and $\Omega = (\lambda x. x x) (\lambda x. x x)$ . I was proposed to look at these terms:

$\text{fls} (\lambda x. \Omega)$ which in both semantics reduces to $\lambda y. y$

$\text{fls} (\lambda x. \Omega x)$ which in call-by-name reduces to $\lambda y. y$ but in call-by-value "diverges evaluating the argument to $\text{fls}$".

I don't see how these diverges except if I assume $\text{eta}$-conversion which was not assumed in my course. On top of that, I don't see how one can diverge and evaluate the argment to $\text{fls}$. Does this make sense to you?

Aside

I proposed the terms $(\lambda f. \Omega)$ and $(\lambda t. \lambda f. t) \Omega$ I think this is a valid example...

The notion of equivalence:

The notion of equivalence that I'm using is behavioral equivalence (see Pierce's TAPL book for details). The definition says that for any sequence of values to which my terms are applied I should have the same observation: either the two results diverge or the results don't diverge.

A separate notion is that of call-by-value or call-by-name which are some standard evaluation strategies for lambda terms.


texts:
All-SAT is the problem of enumerating all satisfying assignments of a boolean formula.
All-SAT is different from #SAT, where it suffices to find the number of satisfying assignments without enumerating them.
Is the computational complexity of All-SAT known, or is this an open problem?
In this CS Theory question, some solvers for All-SAT are discussed, but the papers do not seem to give complexity results.


texts: Is O(mn) considered "linear" or "quadratic" growth?

texts:
If I have some function whose time complexity is O(mn), where m and n are the sizes of its two inputs, would we call its time complexity "linear" (since it's linear in both m and n) or "quadratic" (since it's a product of two sizes)? Or something else?

I feel calling it "linear" is confusing because O(m + n) is also linear but much faster, but I feel like calling it "quadratic" is also weird because it's linear in each variable separately.


texts: How to minimize large DNF formula into deeper but smaller formula?

texts:
I want to minimize DNF formula which has ~200k products combined into a sum.
The depth of that formula is 2 - first level is the OR, and second level is AND for all conjunctions.

I have tried using the Espresso program to minimize it, but it only reduces the number of products from 200k to 50k. Espresso still retains the formula's depth of two, and there isn't an option to go deeper, it only puts "don't care" bits.

Are there any algorithms or techniques for taking a large DNF, and producing a smaller, more managable formula – one that isn't just product of sums, or sum of products?

If there isn't, how should one go about doing such task?


texts: Can I have actions that, if taken, cannot be taken again in the following N timesteps?

texts:
I'm trying to train a load-balancing system with reinforcement-learning (RL) s.t. the incoming jobs are queued evenly at the available servers.
The system will not be able to directly dispatch the jobs, but it will only offer suggestions to use a set of servers over another.
The system will also be capable of reducing the speed at which new jobs arrive and at each time step, to reduce the queue lengths.
The agent must decide whether to change this speed or keep it constant.

Changing the speed at time T, however, disables any other changes until time T+N, with N constant (basically, we need to prevent speed changes at every time-step).

Are these actions an obstacle in training the system?
All RL systems I know only deal with actions that can be taken at every time step and don't put any constraints in future use of the action. Is this a limitation of RL agents?


texts: Which classifier is more accurate for a SVM classification?

texts:
I am learning the SVM classification and encounter a problem. I am not sure if this dilemma has a terminology for it.

Assume we would like to classify patient by SVM given the samples of healthy people ( of both gender) and people with liver cancer ( of both gender). If we label healthy people sample as class 1 and the people with cancer as class 2, we can train a binary SVM and obtain a classifier 1 to predict any new patient. Now, image another scenario. Assume that we first divide all samples by gender before SVM classification. For each gender, we still label healthy patients vs cancerous patients into 2 classes and train a binary SVM to obtain classifier 2 and classifier 3 for female and male samples respectively. The question is if there is a new female patient, which classifier, 1 or 2, should be used to obtain more accurate prediction ? Here is the dilemma for the arguments I have

(1) When the number of samples is large, the prediction should be more accurate. Based on this argument, the classifier 1 seems a good choice.

(2) However, if we divide samples into female and male groups first, the classifier 2 seems a better choice since the new patient (unknown test sample) is female.

Does this kind of dilemma have a terminology or does anyone know any further information or how to solve problem like this ? I am not even sure if this is a legit question and sorry for the naive question in advance. Thanks


texts: Is there any greedy solution for bitonic tour

texts: I have found dynamic solution for Bitonic tour but I could not find any greedy approach for this problem. Is it possible to solve it in a greedy manner?


texts: How does the halting theorem interact with the recursion theorem?

texts:
Recursion theorem (paraphrasing Sipser, Introduction to the Theory of Computation):

Let T be a program that computes a function t: N x N --> N. There is a program R that computes a function r: N --> N, where for every w,

        t(<R>, w) = r(w)

The proof is by construction. The program R thus constructed computes the same thing as program T with one input fixed at <R>. But what if the right side does not compute anything? In that event we can reason as follows:

T(<R>, w) halts  <-->  R(w) halts

and by modus tollens

T(<R>, w)  does not halt  <-->  R(w) does not halt

In particular we have

R(w) halts  --> T(<R>, w) halts
T(<R>, w)  does not halt  --> R(w) does not halt

The transposition is based on the table below

T(<R>, w) halts__________________R(w) halts

   T                         T
   F                         F

But what if the value in the right column is unknown and unknowable?

T(<R>, w) halts__________________R(w) halts

   T                         T
   ?                     unknowable
   F                         F

We know that there is no universal halting decider, so the value in the right column may be unknowable to a given decider. So what if the decider concludes that T(<R>,w) does not halt? Is there anything wrong with the table below?

T(<R>, w) halts__________________R(w) halts

   T                         T
   F                     unknowable
   F                         F

In particular is there any compelling reason that if the value in the left column is F that the value in right column must also be F, i.e. that it cannot remain unknowable? It seems to me that if T(<R>, w) does not halt then it does not imply anything.

Is it possible for a decider to say [for some T] that T(<R>, w) does NOT halt yet remain agnostic about R(w) halting??


texts: What is the difference between physical level and internal level of a database according to ANSI/SPARC?

texts:
According to ANSI/SPARC model a database consists of three (or four?) levels. These are internal (and/or physical?), conceptual and external levels.

Most information resources say like physical and internal levels are the same, i.e. these are two alternative names for the same actual level. But my tutors' lecture material say that these are two different levels, though no convincing arguments are provided.

So where is the truth and what is it? Or did I messed up something?


texts: Data Structure for k Nearest Neighbour Search in D dimension using only point cloud as query points

texts:
I have a point cloud of N points in D-dimensional space with periodic boundary conditions, where N can range from 500 to 10^8 and D can range from 1 to 20. The distribution of points varies wildly, from completely uniform to very clumped together, however, each dimension is restricted to the range [-pi, pi). For each point in the point cloud I need to find the k nearest neighbours to that point. I also need to find how many (but not exactly which) points exist within a distance of each point. Both of these need to be done with maxnorm distances.

I've tried kd-trees, but they don't handle the wrapping boundaries, and for the larger trees, duplication is not feasible. Additionally, it gets slow at higher dimensions.

I've just come across Vantage Point Trees, and tried out some code, but it is slower than the kd-tree. Although, the code I found uses a recursive search method, with no batching. On the positive side, it can natively handle the wrapping conditions, and as such doesn't require duplication.

I'm about to see if I can squeeze some more performance out of the VP tree by converting to an iterative approach and seeing if I could batch search, but I had a thought. All these data structures work for finding nearest neighbours to arbitrary query points, while my query points are restricted to being points already in the point cloud. I figure this restriction might allow for some more performant structure (maybe a nav-mesh of sorts?). I tried searching for structures that would handle this, but my google-fu is failing me. So just wondering if anyone knows of a data structure that can handle the following:

Handle a small and large number of points, i.e 500-10^8 points
Handle up to 20 dimensions
Work with periodic boundaries (i.e., a flat torus)
Work with maxnorm distance (soft requirement. Euclidean can give me a potential list which I can manually cull, but maxnorm would be preferred)
Can find k-NN to query point as well as find how many points exist with distance to query point
Query points are only points in the structure, not arbitrary points
Queries can be batched. i.e I need to find the k-th NN for every point in the point cloud. I also need to find how many points exist within d[i] for each point i. That is each point has a different search radius.
Doesn't need to support insert or deletion.

Thanks for any help


texts:
let's say we have a set of players that we want to match into teams of aproximatly same strength, so that no team is much stronger than another team.

Each team consists of two players. One player is taking a defense position, another player is taking an offense position. The teams can decide for themself which of the players if playing at what position. We can assume that the teams try to win and will take the best possible combination of defense/offense player.

Each player has an offense rating (e.g. discrete number between 0 and 10) and a defense rating (same scale) that describes how strong the player is in the offense or defense position.

The strength of a team is determined by the defense strength of the player in the defense position and the offense strength of the player in the offense position. So we can assume:

TeamStrength = max(PlayerADefense + PlayerBOffense, PlayerAOffense + PlayerBDefense)

The question is, what is a good algorithm to find teams of similar strength using above metric.

My thinking is that I can easily evaluate a single result by calculating an average team strength and build the sum of difference (square).

Based on this it is obvious that I can just create random matches and then choose a "good" solution. However I'm curious if there is a way to find an optimal solution without brute forcing of all variants.

Any ideas?

Edit: There seems to be some confusion about the metric of optimal strength / average strength.

The goal is to have teams of similar strength, nothing more nothing less. Specifically I don't care if there are other combinations where the total strength of all teams is higher.

I can imagine various metrics to achieve this goal. One idea I presented was to use the following metric:

For each team t calculate its strength by calculating:
    strength_t = max(PlayerADefense_t + PlayerBOffense_t, PlayerAOffense_t + PlayerBDefense_t)
Calculate the average team strength: avgStrength = sum(strength_t) / teamCount
For each team t calculate its deviation from the average squared and sum it:
    m = m + (avgStrength - strength_t) ^ 2
m should be minimal

I want to minimize the value $m$. I want to emphazize that I'm open to other metrics if they provide comparable results.


texts: Data structure that supports finding frequency of given element in $O(\log n)$ and most frequent elemnt in O(1) time

texts:
Ok, so I got this for homework and been struggling for a while now.
The full assignment requires this:

While N = number of elements in given array and n = number of different elements,

init(S,A[1...N]) - accept an array A as input and initialize S data structure in O(Nlogn) time

insert(S,x) - insert the key x to S in $O(\log n)$ time

freq(S,x) - return the number of appearances of x in S, in O(logn) time

mostFreq(S) - return the most frequent element in S, in O(1) time

I was thinking of using a balanced bst, inserting elements from the array one by one, but it would be $O(n \log n)$ and not O(Nlogn) as required.

As for the frequency functions, I was thinking of storing each element with an int attached to it or something, indicating number of appearances so far, thus enabling me to just search for some element to know the number of times he appears in S, but that's messy too.

as for the last function (mostFreq) - I have no idea how to deal with it whatsoever. I guess it involves holding some variable that will be updated on each insert, but I got nothing.

So it's clear I'm pretty lost :) any suggestions?


texts:
I want to find some characteristics for a set of points $S$ which contains $n$ points and has some Voronoi Diagram $V(S)$. This diagram should have exactly $2n-5$ vertices.

I tried to use the Euler formula for planar graphs which says $v-e+f = 2$:

$\Rightarrow 2n -5 -e + n = 2 \Rightarrow e = 3n-7$ - but what can I now do with the information that $V(S)$ has $3n-7$ vertices?


texts: Does location transparency imply access transparency?

texts:
In distributed systems theory, I have found the definition that a distributed system requires, among others, location and access transparency.

I was wondering if location transparency does not already include access transparency.

Wikipedia defines the two as follows:

  Access transparency – Regardless of how resource access and representation has to be performed on each individual computing entity, the users of a distributed system should always access resources in a single, uniform way.

  Location transparency – Users of a distributed system should not have to be aware of where a resource is physically located.

If I am not to become aware of where a resource is physically located, doesn't that automatically imply that I have to be able to access all resources in a uniform way?

If yes, could you leave out access transparency from the definition without changing its meaning?