texts: What is the polynomial time reduction between these two Hamiltonian cycle problems?

texts:
Problem 1: Given an undirected graph, return the edges of a Hamiltonian cycle, or correctly decide that the graph has no such cycle.
Problem 2: Given an undirected graph, decide whether or not the graph contains at least one Hamiltonian cycle.
What is the polynomial-time reduction of problem 1 to problem 2?

Let TSP1 denote the following problem: given a TSP instance in which all edge costs are positive integers, compute the value of an optimal TSP tour. Let TSP2 denote: given a TSP instance in which all edge costs are positive integers, and a positive integer T, decide whether or not there is a TSP tour with total length at most T. Let HAM1 denote: given an undirected graph, either return the edges of a Hamiltonian cycle (a cycle that visits every vertex exactly once), or correctly decide that the graph has no such cycle. Let HAM2 denote: given an undirected graph, decide whether or not the graph contains at least one Hamiltonian cycle.
From Roughgarden's online algorithms course

The solution:

If TSP2 is polynomial-time solvable, then so is TSP1. If HAM2 is polynomial-time solvable, then so is HAM1.


texts:
In order to generate scale-free networks, we can use this algorithm, derived from Barabási–Albert model:

1) we assign every node a "weight" $\theta_i$ (or two in the direct case).

2) we place $m$ edges between nodes by choosing the ends of the edges with probabilities proportional to the weights.

With the right choice of the coefficients $\{\theta\}$ we can generate a graph with the desired power-law distribution. A very popular method is the so-called Chung-Lu Model and it's, for example, used in the power.law.game function in the igraph library.
This model prescribes to number the nodes from 1 to N and then assign to each node a $\theta_i = i^{-\alpha}$, with $\alpha \in [0,1)$,  then select nodes as the ends of an edge with probability $p_{ij} \propto \theta_i \theta_j$, and repeating for all the edges to put in. The resulting graph will have a degree distribution $p(k) \propto k^{-\gamma}$, with $\gamma = \frac{\alpha}{\alpha +1}$.

My question is: why can't we simply consider a power-law distribution with a finite extent  $p(x) =  \frac{1-\gamma}{x_{max}^{1-\gamma} - x_{min}^{1-\gamma}} x^{-\gamma}$, then sample our $\theta_i$ from this distribution? This is more intuitive from my perspective, because if my expected degrees follow a power-law distribution, I expect that the graph degree distribution follows the same power-law.


texts: Construct unitary $Q$ such that $span\{q_1,q_2\} = span\{v_1,v_2\}$ where $v_1,v_2 \in \mathbb{R}^n$ are given as input

texts:
Assume also that $v_1,v_2$ are linearly independent, and $q_i \in \mathbb{R}^n$ denotes the $i$-th column of $Q$. This is what I've got so far. First obtain unit vectors $w_1,w_2$ which are orthogonal and $span\{w_1,w_2\} = span\{v_1,v_2\}$. Now compute a Householder matrix $H$ that aligns $w_1$ with $e_1$, i.e. $Hw_1 = e_1$ (since $\|w_1\| = 1$). Since $H$ is unitary, this means that

\begin{align}
    w_1 \cdot w_2 = Hw_1 \cdot Hw_2 = e_1 \cdot Hw_2 \Rightarrow Hw_2 = e_i
\end{align}
for some $i \in \{2,...,n\}$. If $i = 2,$ set $q_j = H^{T}e_j$ for $j \in \{1,...,n\}$. Else set $q_i = H^{T}e_2$ and $q_j = H^{T}e_j$ otherwise. Again since $H$ is unitary, we then have $\{q_1,...,q_n\}$ an orthonormal basis for $\mathbb{R}^n,$ i.e. $Q$ unitary. Finally, $q_1 = w_1$ and $q_2 = w_2$, so $span\{q_1,q_2\} = span\{v_1,v_2\}$, as desired.

Does this approach work? And if so, is there a way of doing this where I do NOT have to use Gram-Schmidt process at the beginning and rather to use something more numerically stable like Householder reflectors?

Edit:
I believe the following answers my questions. Assume $v_1,v_2$ are unit vectors without loss of generality. Construct a Householder matrices $H_1,H_2$ such that $H_1 v_1 = e_1$, $H_2 e_1 = e_1$, $H_2 H_1 v_2 = e_2$. Define $H = H_2 H_1$. Return $Q = [H^{T} e_1, H^{T} e_2, ... ,H^{T}e_n]$.


texts: How can I compute an exponential modulo a large integer?


texts: Can computation models be categorized in terms of efficiency?

texts:
It is widely accepted that turing-complete systems are equivalent in terms of computability - i.e., whatever a turing-machine can do, can be emulated by automatas, the lambda calculus and other computing systems.

Not much is said about the efficiency of such systems. Intuitively speaking, it makes sense to think that some systems are less efficient than others. Is it possible to meaningfully categorizing such systems in term of efficiency?


texts: Algorithm to mapping given probabilities to empirical probabilities

texts:
Consider following problem statement:

You have given $n$ actions. You can perform any of them. Each action gives you success with some probability. The challenge is to perform given finite number of actions to get maximum successes.

Here, we can perform actions and slowly decide upon possible probabilities of each action for success. I have no doubts in this problem.
Now consider following variant of the problem:

You have given $n$ actions. You can perform any of them. Each action gives you success with some probability. Also you are given set of $n$ probabilities, but you are not told which probability is associated with which action. The challenge is to utilise this additional information to perform given finite number of actions to get maximum successes.

I have doubt in this problem that how we can map probabilities to actions? I can do some enough number of actions to gather empirical probability and them try to associate given probabilties with actions having closest empirical probabities. But, is there any algorithm for such problem in the literature?


texts:
Definitions:

Alphabet $Σ$: finite, non-empty set
Language: subset of $Σ^*$
Grammar: Unrestricted grammar (Chomsky Type 0)
Language of a grammar: all words that can be produced by applying $P$ multiple times, starting from $S$

Grammars are finite, therefore there are only countable infinite of them. But there are uncountably infinite many languages. Each grammar can only describe one language. Therefore, there are languages without grammars.

Can you give an example for such a language without grammar?

I searched the internet, but strangely, I could not even find the question in context of formal language.


texts:
I recently came accross an interesting "sweep circle" algorithm for delaunay triangulation [1].

It's basic idea is seeding with a trivial triangulation (3 points), then gradually extending it outwards (points are sorted by their distance from a chosen origin - the sweep-circle center) while preserving the legality of the triangulation by flipping triangles if needed, always starting from the new one, and continueing to neighbouring triangles of flipped ones.

I've implemented it, and it works nicely, but I still struggle with making the seeding part flawless.

The thing is :

In order to ensure that each new point is outside of the current envelope ("frontier" in the article), you have to make sure that the swept points are closer to the origin than the unswept points.
In order to find where to connect the new point, you have to have the origin inside the envelope (so angular sort of the envelope and binary search will do).

Starting at some iteration this will natuarally happen, but the problem is making it happen for the seed points.

So what I aim at is finding an origin which fulfills :

Be inside the seed triangulation.
Have the seed points the closest points to it (have the sweep circle strictly containing the seed points empty of other points).

The article suggests taking some average point as the origin, and start with the 3 points closest to it, but this clearly fails if these 3 points are on the same side of the chosen origin, so they form a triangle that is not containing it.

A different but somewhat similar algorithm [2] is suggesting choosing an arbitrary point, then taking the point closest to it, and the point that creates the smallest circumcircle with the other two, and fix the origin as the center of their circumcircle, but that's clearly not working either, unless these 3 points happen to form an acute triangle (is this circle even ensured to be empty of other points?).

Currently I use a similar idea - arbitrary point + 2 closest points to it, as the first 3 points, but I fix the origin as some point inside the formed triangle (e.g their average), which basically works, but can fail in principal.

I'm looking for another simple way to do it, or a way to detect when the proposed method is not working and fix it in a clever way involving the point that "ruined it", before the iterations begin and without having to deal with more than 2 seed triangles (4 points), or having to make many iterations or guesses at init stage.

I know I can take the first point and shift it by some small $\epsilon$ towards inside the triangle, and it should work, as long as it's smaller than say the minimum distance bewteen 2 points, but I'm looking for a clever solution, and I am especially interested in a solution that can chose an integer origin for a set of integer points, for then the whole algorithm can be implemented using only integral arithmetics (faster, less error prone).

Bottom line :

I think it all comes down to this :

Given a set of n points in the plane, find a point O which lies strictly inside the triangle formed by the 3 points of the set closest to it (to O).

But I guess that put in the context, there might be solutions to implementing a working version of the algorithm that bypass this question.

References :

A faster circle-sweep Delaunay triangulation algorithm by Ahmad Biniaz and Gholamhossein Dastghaibyfard (2011)
S-hull:  a fast radial sweep-hull routine for
Delaunay triangulation by D. A. Sinclair (2016)


texts: Algorithm for computing volume of union or intersection of n-dimensional convex polytopes given their facets?

texts:
I've googled this problem somewhat pretty extensively, and all the relevant literature understandably deals with 2-d or 3-d cases, rather than the n-d case.

EDIT: Yes, ℝn. I've done many searches combining terms like union, intersection, volume, convex hulls, polytope, etc. I've come across papers like this and this. My math and CS background is weak, but I can tell from the latter paper that this is a difficult problem that I am after.

I appreciate both answers given, unless I misunderstand (probable), I'm not sure that they answer my question? The first answer is just about finding the volume of a polytope given its facets or vertices. I'm aware of algorithms to do so. The second answer may be more on track, but it still raises the question of how to determine IF two polytopes intersect, and where?

Thanks, everyone, for your help so far.


texts:
I've understood that $L$-uniformity means that there's a TM that can output the description of $C_n$ in $O(\log n)$ space. Now, that seems odd to me since the description itself (as far as I understand) must be a $O(n)$. I'd be glad for clarification.

Also, in that context: What does $L$-uniform $NC^k$ means?

Thanks!


texts: Complexity of Merge Sort that splits in a random position

texts:
I got a question that I don't fully understand:
Given a new algorithm to merge sort (AKA mergesort2) that instead of splitting the list in the middle it splits the list in a random number between $1$ and $n-1$.
Also, we know the probability of getting $1$ is $2/n$ and to every other number $1/n$.

I have tried again and again and came up with the regular when doing the "average case" $\Theta \ (n \log n)$ and of the merge sort algorithm and "worst case" $O (n^2)$ but I'm not sure about it.

Pseudo-Code:

   MergeSort2(A,p,q)
     if(p=q) then return
     i = random number from (1...q-p)
     MergeSort2(A, p,   p+i-1)
     MergeSort2(A, p+i, q)
     Merge(A, p, p+i-1, q)

How I did the calculations of the $O (n^2)$ "worst case" when I split it to $1$ and to $n-1$ every time: (if it's correct)

$$T(n)= T(1)+T(n-1)+O(n)$$

When $T(1)$ is the single number, $T(n-1)$ is the rest list and $O(n)$ is the merge

$$\begin{align*}
T(n) &= (T(1)+T(n-2)+O(n)) + T(1)+O(n) & \text{second recursive call}\\
     &= (T(n-3)+T(1)+O(n)) +2T(1)+2O(n) & \text{third recursive call}\\
     & \vdots\\
T(n) &= T(n-k)+kT(1)+kO(n) & k^{th}\text{ recursive call}
\end{align*}$$

Now we know that $T(1) = O(1)$ as it doesn't do anything.

In order to get to our stop condition, we need the $T(n-k)$ will be $T(1)$.

So to do so we will take $k = n-1$.

Therefore we will get the following:

$$T(n) = T(1)+(n-1)O(1)+(n-1)O(n) \implies T(n) = O(n^2)$$

How do I calculate properly the complexity of the given algorithm?


texts: Are these two regular expressions equivalent?

texts:
$u^*v(w \cup xu^*w)^*$ and $u^*v(w \cup x(u)^*w)^*$

Is that extra set of parentheses around the second $u$ needed?


texts:
Assume we run Prim’s algorithm when we know all the weights are
integers in the range {1, ...W} for W, which is logarithmic in |V|.  Can you improve Prim’s running time?
When saying 'Improving', it means to at-least:
$$O(|E|)$$
My question is - without using priority queue, is it even possible?
Currently, we learned that Prim's runtime is $$O(|E|log|E|)$$
And I proved I can get to O(|E|) when weights are from {1,....,W) when W is constant, but when W is logarithmic in |V|, I can't manage to disprove/prove it.
Thanks


texts: Pumping Lemma for $\mathcal{L} = \{ \omega \omega^R a^{|\omega|} : \omega \in \{a,b\}^* \} $

texts: I have to show that this language is not context free $\mathcal{L} = \{ \omega \omega^R a^{|\omega|} : \omega \in  \{a,b\}^* \} $, where the $R$ corresponds to the reverse. For this I will use the pumping motto for free context languages. I know how it works, but I have problems choosing the correct $ \sigma $, because when looking at the alternatives for $ vwx $, knowing that $ uv^kwx^kz$ has to be met, I can't get to something concrete, the $a^{| \omega |}$ makes me sick. Is there any other way to show that it is not context free? or that $ \sigma $ could occupy.


texts: 3-COL with a restriction on a number of vertices colored with a particular color

texts:
If I modify a 3-COL problem (with colors A, B, C) in a way that I now demand that at most, say, 50 vertices may be colored with color A, does the problem still remain NP-complete?

I've been thinking of a reduction from a standard 3-COL, but there is no way that I can solve a standard 3-colorability using the problem described above; I'd have to cut the graph into smaller pieces. Other NP-complete problems I know of, like independence set, have a parameter and in my problem there is a fixed number instead of a parameter. So this got me thinking, that maybe such a problem could be solved in P-time, but this doesn't make sense as I could probably replace 50 with any other number.

So this is simpler than asking whether there is a 3-COL such that at most k vertices receive color A, but still quite hard in general I think.

Am I correct?


texts: Computation Tree Logic and its Temporal Opeators

texts:
I've got some questions about the temporal operators in computation tree logic:

Does the Finally path-specific quantifier Fq mean that q has to hold in a subsequent state or is it also fulfilled when q holds in the current state?
Please consider the following example:

What exactly is specified here? Does it mean: If q AND r holds on a path P in a graph G then q has to hold somewhere on the subsequent path of P.
Or does it mean: ... q has to hold somewhere on the subsequent path of every path of G?


texts: Why Linear bounded automata requires Nondeterministic Turing machine ? Why not Deterministic Turing machine?

texts: Going through the topic of LBA, i.e., Linear bounded automata. I found that LBA requires the NTM with some constraints on tape. I found the same information from different sources. But I did not get why all the sources mentioned that it needs a NTM. I am not getting why I need a NTM for LBA? We also know that any NTM can be converted to DTM. Therefore, I can take a DTM and put those tape constraints for building a LBA. I think that with a tape constraints DTM would be converted to LBA! Please make me correct and kindly tell me why I need an NTM for an LBA?


texts: What is complexity of checking whether a natural number is a perfect square?

texts: As the title says, what is complexity of checking whether a natural number is a perfect square?


texts: Perceptron learning rule past exam question

texts:
I'm struggling to solve this past paper question and my lecturer is being less than helpful. The question is:

Apply the perceptron learning rule to update the current weight vector (0.1, 0.3) when the learning rate is 0.01, the input vector is (2.0, 4.0), and the error vector is (1, -1).

What has me confused is the use of vectors for the current weight, input and error value. We've never used vectors for this before (only regular numbers) and no examples I can find online use 2D vectors like this.

I know the perceptron learning rule is:

New weight = old weight + (learning rate * perceptron input * error value)

But I'm not sure how to do this kind of maths with 2D vectors to get a 2D vector as my result (which is what I assume I want, since the question seems to be asking for the new weight).


texts:
So I have this question:

  A shuffle of two strings X and Y is formed by interspersing the
  characters into a new string, keeping the characters of X and Y in the
  same order.
  Example would be

X = AND
Y = THE
Z = ATHNED -> A  N D
               TH E

So this would return true. I've seen solution to this using Dyanimc Programming, but I came up with just a purely iterative algorithm that runs in O(|Z|), but I'm guessing there must be something wrong with it  since all the solutions I've seen all use either memoization or DP.

Basic psuedocode for my solution (I omit some obvious base cases):

solution(X,Y,Z):
   i = j = 0
   for(k=0 to |Z|):
      if(either i or j out of bounds):
         return false
      if(Z[k] == A[i]):
         i++
      elif(Z[k] == B[j]):
         j++
      else:
         return false
   return true

Basically this just runs down string Z and marks off whichever string it came from, and when a character doesnt match either, it cant be an interleaved string.

Can someone pick this apart and tell me what's wrong and why I have to use DP?


texts: Which cellular automata rules are suitable for randomizing an input sequence?

texts:
S. Wolfram has in has book "A New Kind of Science" listed 256 simple rules of cellular automata. Which of these rules could via iteration essentially contribute to render an input sequence more random in a certain sense?

Rule 170, for examples, simply produces a left
shift and evidently is not of use in this, if I don't err. My limited computations with inputs
that are more or less random seem to indicate that the majority of the 256 rules are even contraproductive in this context. How could one best proceed to clarify this issue or are there already relevant published results available?


texts: Are these two definitions of 2NF database normal form equivalent?

texts:
I came across following definition of 2NF normal form:

  A relation schema is in second normal form (2NF) if every nonprime attribute is not partially dependent on any key of R.

Then the book reworded the definition as follows:

  A relation schema R is in 2NF if every nonprime attribute A in R is fully functionally dependent on every key of R.

However I don't feel that these two definitions are equivalent. In first definition "every nonprime attribute is not partially dependent on any key of R" means there can be a nonprime attribute which might be partially dependent on other non prime attribute, but not at all dependent (either partially or fully functionally) on any key. This is not allowed by second definition as it says "every nonprime attribute is fully functionally dependent on every key". Is the second definition wrong?


texts: How are codes like 5421 and 2421 unique?

texts:
For the number 6, if I need to represent it in 5421 code form, should I code it as
1001 or 0110? Why should I choose the one over the other?

Similarly for the number 5 in 2421, is it 1011 or 0101?

Edit 1:

In a weighted binary code, the name of the code indicates the weight assigned to each place.

So if the code is 8421, the number 9 would be written as 1001 (8*1 + 4*0 + 2*0 + 1*1=9). And the number 5 would be 0101 (8*0 +4*1 +2*0 +1*1=5). In each case, no other combination of weights add up to the values (9 and 5).

Edit 2:

But for 5421, can the number 5 be represented as 1000 (5*1+4*0+2*0+1*0=5) as well as 0101(5*0 + 4*1 + 2*0 + 1*1 = 5)? Which one should be chosen? Similarly for 2421, which one to choose between 1011 (2*1 + 4*0 + 2*1 + 1*1 = 5) and 0101 (2*0 + 4*1 + 2*0 + 1*1 = 5)?


texts: Simplest combination of logic gates to produce a given set of outputs

texts:
Given a truth table for a truth function that takes n inputs and produces a single output (true or false), what is the fastest way to find the simplest combination of logic gates that will output the given truth table?

A few rules for specificity:

Any binary truth function may be used as a logic gate. In other words, AND, OR, XOR, NOR, and NAND are all valid logic gates, but a binary truth function like AND(NOT(A), B) also counts as a single logic gate when determining the simplicity or complexity of a solution.
The "simplest" solution is the one which uses the fewest logic gates
The output of a logic gate may either be the output, or it may be an input to exactly one other logic gate.

Primary inputs themselves may go to more than one logic gate; it is only the output of a logic gate that may only be used once. I am most concerned with the minimal circuit necessary for the binary multiplication of two numbers. Do we know of a minimal circuit for multiplication? If so is there an efficient algorithm to construct the minimal circuit?


texts: Efficient algorithm for detecting overlaps in time intervals

texts:
Let's say I am building a time clock app. The employee can log into the interface and then enter time for multiple projects so that we can generate reports for billing as well as payroll.

A table in the database will record the time-in and time-out for each project as a row. A user should be able to sign out and back into the same project multiple times throughout the day, and also can enter time out of order (e.g. sign into Project X at 9:00 AM to 2:00 PM, then into Project Y from 7:00 AM to 8:30 AM).

So let's say my table looks like this:

Project   | Time In | Time Out
----------|---------|---------
Project X | 9.25    | 14.25
Project Y | 7.00    | 8.50

(I am representing the data as a decimal number of hours simply because it's easy to read in the example; the data is actually MySQL TIMESTAMPs.)

Assuming that the data is not in any particular order, I am wondering what would be the simplest and/or most optimized way to validate that the next entry does not conflict with the existing time in such a way that the employee is signed into two projects simultaneously.

e.g. If the user tries to sign in at 12:00 PM or at 7:30 AM, it throws an error because the user was already working on Project X at noon and Project Y at 7:30.

I know I could do this by getting all the time clock data and then detecting if time_in <= input[time] <= time_out, but I'm wondering if there's a cleaner method to accomplish this task.


texts: How to calculate the mergesort time complexity?

texts:
Recently while reading a book (Skienna) I came across the following statement:

  Mergesort works by dividing nodes in half at each level until the number of nodes becomes 1 hence total number of times we would need to do this would be $\lceil\log_{2}{n}\rceil$ and for each level we perform $O(n)$ work hence total time taken will be $O(n \log n)$

How to understand the above statement? Also, I am always confused about when to take ceil or floor. I am not a math major therefore it seems intimidating to me at first. I don't know about generating functions etc.


texts: What is the best of given hashfunctions?

texts:
In our exam on algorithms there was a question, where given 3 hashfunctions we had to chose one and explain why it's the best.

h_1(x,i)=(x+5*i) mod 1000
h_2(x,i)=(x+17*i) mod 1000
h_3(x,i)=(x+32*i) mod 1000

I am really unsure about this, but I suspect that it is the second one, because it can "hit" more values. If I choose the first one for example, I will be hitting the same buckets over and over (if they are full). Question seems quite simple but my math lecture on this has been a long time ago.


texts: Solving the recurrence $T(n)=T(n-1)*T(n-2)$

texts:
I have been trying to solve the following recurrence:

$$T(n)=T(n-1)*T(n-2)$$
The initial conditions are $n \ge 2$ and $T(0) = 2$ and $T(1) = 4$.

I started by taking the $\log_{2}$ of both sides to get

$$\log(T(n)) = \log(T(n-1)) + \log(T(n-2))$$

which looks an awful lot like a Fibonacci recurrence.

So if I set $S(k) = \log(T(n))$, then I have a recurrence of the form
$$S(k) = S(k-1) + S(k-2)$$ with $S(0) = 1$ and $S(1) = 2$.

I can solve this easily using a characteristic polynomial and get

$$S(k) = A*(0.5*(1+\sqrt{5}))^k + B*(0.5*(1-\sqrt{5}))^k$$ where $A$ and $B$ are constants. To get $A$ and $B$ I use the initial conditions for $S$, namely $S(0) = 1$ and $S(1) = 2$.

The problematic part is that I think to get $T(n)$ I just simply raise $2$ to the power of the entire bunch above to get

$$T(n) = 2^{n*A*0.5*(1+\sqrt{5})+n*B*0.5(1-\sqrt{5})}$$.

However, when I plug in some values for n to check I get some different integer values from the original recurrence.

Is my reasoning flawed somewhere in the process or am I just making an algebraic mistake somewhere?

Thanks!


texts: Is $a^n b^n$ an artificial language or does it occur in the real world?

texts:
The classic example of a context-free grammar is $a^nb^n$. That is, $n$ occurrences of $a$ followed by an equal number of occurrences of $b$.

Do such forms occur in the real world? Can you provide an example of a real-world case where there must be $n$ occurrences of something followed an equal number of occurrences of something else?

Let me give an example: if I run an on-line store, then for each purchase made to my store, there must be a corresponding delivery of the purchased item. That might be modeled as $n$ purchases followed by $n$ deliveries:

  purchase purchase purchase delivery delivery delivery

However, that is not a good data model since each delivery should legitimately be paired to a purchase:

  purchase delivery purchase delivery purchase delivery

So I am left wondering if there are any real-world examples where data would be (legitimately) modeled as a sequence of $n$ items of one type followed by $n$ items of another type. Can you provide a real-world example please?

Hendrik Jan provided this good example (see it in the comments below): This weekend I visited my mother. Three flights up, and three flights down when I left.

Neat example! Can you think of others?

A colleague just informed me of another example. In the KML specification it says that a <Track> element must contain N <when> elements followed by N <gx:Coord> elements:

https://developers.google.com/kml/documentation/kmlreference#gxtrack

Another excellent example. What are other examples?

Another colleague sent me an article about columnar databases. It is often more efficient to store data in columns rather than rows. For example, we may have a column of person's ages followed by a column of person's heights. Or, a list of N integers (ages) followed by a list of N decimals (heights). This enables efficient calculation of sums or averages. Here's the article:

http://www.postgresql.org/message-id/52C59858.9090500@garret.ru

More examples please! I would like for us to create a nice collection of compelling examples.


texts: Does amortized algorithm analysis make any assumptions about the sequence of function calls?

texts:
I have read that average case analysis makes some assumptions about the inputs to the data structure, and amortized analysis makes no such assumptions.

Does amortized analysis make any assumptions about the sequence of function calls to the data structure though?

I had had a dynamically sized stack (via an array) which only expanded the capacity by 1 element when it needed to expand the size, could I say that the amortized cost of this structure is $O(n)$ since I cannot guarantee that $pop()$ will ever be called?

Or should it still take $pop()$ into account therefore making an assumption about the sequence of function calls?


texts:
This question on the Mathematics SE addresses how to pack a sphere with unit cubes. This addresses how to pack a 2D grid with rectangles.
We can pack a sphere with the minimum number of unit cubes $m$ of a certain minimum volume $v$, necessary to capture fraction $f$ of the total volume inside the sphere, using octrees.
Is there a similar algorithm for the minimum number of cuboids?


texts:
Prove that $BPP^{BPP} = BPP$.

Obviously $BPP\subseteq BPP^{BPP}$. So we're left with proving $BPP^{BPP} \subseteq BPP$. Let's consider $L\in BPP^{BPP}$. Then, there's a PTM $M$ to decide $L$ for some $BPP(\alpha, \beta)$ which uses an oracle for some language $O\in BPP$. $O$ also has a $PTM\in BPP$, let's denote it $M_o$. So we could create $M'$, a PTM which behaves exactly as $M$, but everytime $M$ uses the oracle, it simulate $M_o$ on the given input for the oracle.

Now, I want to show that $M\in BPP$. By definition, $BPP=BPP(1/3, 1/3)$, so every time $M$ calls $M_o$ it takes a probabilistic risk basing a deciion upon $M_o$ answer.

We've learned in class that $BPP = BPP(1/3, 1,3) = BPP\left(\frac{1}{3^n}, \frac{1}{3^n} \right)$ and I think I shall explain that even though $M_o$ may return false answers, $M_o$ is still in $BPP$.

Can you help me with doing that?

Thanks

EDIT:
Basically, I want to give a lower bound for the probability of $M$, answering correctly. Let's assume that $M$ queries the oracle $n^c$ times for some $n\in\mathbb{N}$. I think the lower bound is $\frac{1}{3^{n^c}}$.

My explanation is that we're assuming the worst case. That is, if the oracle is returning a false answer then we are returning a false answer.

Is that right?

EDIT2
I'm not sure it's $100\%$ correct, since I didn't take into account the probabilistic behavior of $M$ itself.


texts: Why is Minimum $k$-cut NP hard when $k$ is specified as part of the input?

texts:
As you know a set of edges whose removal leaves $k$ connected components is called a $k$-cut. The minimum  $k$-cut problem asks for a minimum weight $k$-cut.

For $k=2$ this problem is P.

Vazirani in his book says for any fixed $k$ when $3 \le k$ it is NP-hard and When $k$ is specified as part of the input this problem is also NP-hard.

I would like to know what difference does it make when $k$ is specified as part of the input? and why is it NP-hard in this case?


texts: Logic, "and" operator between a set of formulas and a formula

texts:
Consider a set $S$ of formulas $\beta_i$ and a formula $\alpha$, if we have a condition such as $S \land \alpha$ is inconsistent what we have to calculate to check the inconsistency of $S \land \alpha$? In other words, what is the result of $S \land \alpha$?

For example, $S=\{\beta_1, \beta_2, \beta_3\}$


texts: Generating a set of minimal-length strings that, together, invoke every production of a context free language

texts:
Problem (tl;dr)

Given a context free grammar, $G$, find a set of strings that take $G$ through every production it has at least once.

How and how fast can it be done?

Background

I'm working on a compiler whose parser is implemented with a tool similar to Yacc+Antlr. I've written up most of the parser code, and I'd like to generate some code of the object language that invokes every production of the grammar at least once so that I can feed it to the parser and make sure that nothing is wrong.

In the interest of good testing, what I'd really like is one, short test file that has a particular production "under test" -- so, for each production rule, I want to generate a minimal string that takes the parser from the start state, through the production being tested, to a set of terminals.

Possible solutions

I imagine there is an elegant solution using graph theory, but I'm not quite sure what it is. I would like to just use Dijkstra's algorithm to find shortest paths through some appropriate structure, but I think that a string is parsed by a context free grammar in a tree structure rather than a path, so I don't know how to make that work.

I think there might be a clever way to pose it as a network flow problem. Something like this: take a graph that has a vertex for every symbol (terminal and nonterminal) and a vertex for every production. If a nonterminal has a production, add a directed edge from the nonterminal to the production. If a production produces a symbol,  add a directed edge from the production to the symbol. Add a source with some capacity $c$ and attach it to the vertex corresponding to the start symbol. Add a sink with infinite capacity and attach it to each terminal.

If a nonterminal has an in-arc with a capacity $k$, add an arc from the nonterminal to each of its productions with capacity $k$. If a production has an in-arc with capacity $k$ and it has an out-arc to $n$ nonterminals, add an arc with capacity $\frac k n$ from the production to each nonterminal.

Then run some maximum flow algorithm on the network and let the productions "trickle down" from the start symbol to the terminals. You should end up with a flow $c$ coming out of your source, and you can return all of the terminals you hit with a nonzero flow as your result string. Then you end up with something like $O(n^3)$ time complexity for each run, where $n$ is the sum of the number of terminals and nonterminals in your grammar -- not too bad.

However, I'm still not really sure what this graph looks like: I think that it needs to be infinite and I'm not sure if you can find the maximum flow of an infinite flow network. Past that, I'm not sure how to "remove" a production from consideration so that I'm guaranteed to get a new one for each test run.

I Googled and I couldn't find anything. Is there a nice solution to this problem?


texts: The meaning of 'Pool' in Computer Science

texts:
While reading about SIMD on Wikipedia, I noticed the use of the technical term Pool in the figure below:

I didn't know what it means; so after searching for it, I found only this article. Yet the definition wasn't very clear to me:

  In computer science, a pool is a set of resources that are kept ready
  to use, rather than acquired on use and released afterwards. In this
  context, resources can refer to system resources such as file handles,
  which are external to a process, or internal resources such as objects

This is not the first time since I have seen the term - I found it on other CS-related materials in the past as well.

Does anyone have any idea about the meaning of 'Pool' in CS? or can provide any reference?


texts: diagonal lemma and the negation function

texts:
Carnap's diagonal lemma asserts that for every computable formula f, accepting a natural number as argument and resolving to {false,true}, there exists a logic sentence s for which:

s $\leftrightarrow$ f($\ulcorner s\urcorner$)

With $\ulcorner s\urcorner$ the Gödel encoding for logic sentence s.

I have a problem with the example function f($\ulcorner s\urcorner$) = $\neg$s. It looks like according to Carnap's diagonal lemma, there exists a logic sentence s for which the following could hold:

s $\leftrightarrow$ $\neg$s

This is obviously, in one way or another, a wrong interpretation of what the lemma says or implies, but I cannot explain why it is wrong ... What's wrong?


texts: Prove: possible to construct automata accepting all strings of other automata sans 1-length strings

texts:
I believe that I have a procedure for doing this, but I don't know how to approach the proof (and for that matter I'm not entirely sure the procedure is correct).

Here's the exact problem statement:

  Given DFA $A = (\Sigma, Q, q_0, F, \delta)$ construct DFA $B$ from $A$ s.t. it accepts all words of the language of $A$ which have length distinct from 1.

And here's pseudocode that has to solve the problem followed by some explanation:

def ensure_word_length_ne_one(alphabet,
                              states,
                              initial,
                              final,
                              transition_function)
 loops = [i for i in alphabet if transition_function(initial, i) == initial)]
 new = make_new_accepting_state()
 # all arcs to the states directly accessible from the initial state
 # except the arcs from the initial state
 backarcs = [(arc.source, arc.destination, arc.input)
             for arc in arcs_to(set(for arc in arcs_from(initial))) -
                                set(arcs_from(initial))]
 for input in loops:
   # Remove all loops from the first state
   add_transition(initial, new, input)
   remove_transition(initial, initial, input)
   add_transition(new, new, input)
 for input in alphabet:
   # Bounce back from the new state to the first state
   add_transition(new, initial, input)
 for source, destination, input in backarcs:
   # For each state directly reachable
   # from the first state reattach
   # all inbound transitions
   # to the new state
   new = make_new_accepting_state()
   remove_transition(source, destination, input)
   add_transition(source, new, input)
   outbound = [(arc.input, arc.destination) for arc in arcs_from(new)]
   for input, destination in outbound:
     # Bounce back from the new state
     # to the states immediately
     # reachable from source state
     add_transition(new, destination, input)

The code tries to be more or less Python.  Auxiliary functions do what their name suggests.  The basic idea is as follows:

A DFA can accept words of length 1 in only these two scenarios:

It loops on some input in the first accepting state.
The state directly linked from the first state is accepting.

Below is the procedure to remove these accepting states while accepting
all other inputs.

If the first state loops on some inputs add a new state $q_1$, remove
all transitions from $q_0$ to itself and add transitions for the same
inputs from $q_0$ to $q_1$.  Add transitions on all inputs from
$q_1$ back to itself.

For any input which on which $q_0$ used to loop $B$ now necessary makes
at least two transitions before accepting it, possibly accepted string
with prefixes that did not cause the automate to loop on $q_0$ are
still accepted (nothing has changed).
For each accepting state $q_n$ directly linked from $q_0$ we do the
following:

change $q_n$ from accepting to non-accepting.
add a new accepting state $q_2$.
remove transitions from states $Q_i$ directly leading to $q_n$, unless they originate in $q_0$, for
each transition removed add a new one for the same input from $Q_i$
to $q_2$.
for each outbound transition from $q_n$ add new transition on the
same input from $q_2$.

Most proofs related to automata I've read so far use structural induction for similar tasks, but I cannot think about a way to approach the proof.  The difficulty is in ensuring that all strings accepted by $A$ are still accepted.

PS. I have the pseudocode set in LaTeX, if it is necessary, I can add it to the post.


texts: Connection between CPU address bus and max amount of RAM

texts:
So, i'm stack on the following question > "A system has a 12 bit address bus. What is the maximum amount of RAM that can be installed on the system?"

First of all, is this question correct? If so, can you explain to me way and how to determine the answer?

Thanks in advance.


texts: Can normal physics laws be simulated in Digital physics?

texts:
Physics is defined as the study of an object {matter or energy} with its interaction with other objects:

  Physics is the study of matter, energy, and the interaction between them.

On the other hand, Digital physics is  based on computations and information.

  Digital physics is a collection of theoretical perspectives based on the premise that the universe is, at heart, describable by information, and is therefore computable.

If we have a universal computer {a universal turing machine} and a program that can compute the evolution of the universe (Digital Physics) running on it, can this specific program simulate our normal physics laws like the classical mechanics laws or quantum mechanics laws ?

1- Can we simulate a universe with its fundemental laws {i.e physics} and change these laws by a universal computer accordingly ?

2- How a simulation of a universe (if any) with fundemental laws {like physics} would help to further understanding in physics ?

3- Is there any form of universal turing machine to apply these simulation ?


texts:
I am totaly new to theoretical computer science, so I am sorry if I get the terminology wrong:

I was reading the definition of a grammar, what I didn't get was the formal definition of the production rules:
Let V be the set of Variables and sigma the alphabet. Let P be the set of Rules or productions. Formal: $P \subset (V \cup\sum)^+\times (V \cup\sum)^*$.

I saw an example with G = ({P}, {0,1}, A, P) with the set of rules A:

1.P $\to \epsilon$

2.P $\to 0$

2.P $\to 1$

4.2.P $\to 0P0$

Now my question: How can the last rule (no 4) exist? It is not an element of the subset of the cartesian product mentioned above.


texts: "Spring" vs FFT spacial to frequency domain?

texts:
Before I found out about FFT https://m.youtube.com/watch?v=spUNpyF58BY but having seen and been impressed by spectrograms/sonograms, I developed my own algorithm for converting to the frequency domain from the spacial domain.

The following sudocode describes the approach.

// epsilon_n constants are small adjustable values

float[] wave = load_waveform() // input waveform
spring[] springs = new … // 1D springs representing frequencies
spectrogram = new float[wave.length,
    springs.length] // output frequencies over time

for (sample = 1 to wave.length)
    for (spring = 0 to springs.length) {
        phys_tick(
            springs[spring],
            abs(wave[sample - 1] - wave[sample])

        // output spring energy over time
        // swap out for any other approach
        spectrogram[sample, spring] = max(
            spectrogram[sample - 1, spring] * (1 - epsilon_4),
            abs(springs[spring].pos)
        )
    }

return spectrogram; // final output

// swap out for any other 1D spring model
// Updates a given springs values in two ways.
// Influences the spring with the waveform.
// Simulates the springs movement for the samples duration.
phys_tick(spring, sample_vel) {
    // push
    spring.pos += sample_vel × epsilon_1

    // phys
    if (spring.pos < 0) spring.vel += epsilon_2
    else spring.vel -= epsilon_2
    spring.pos += spring.vel

    // dampen
    spring.vel ×= 1 - epsilon_3
}

Q: How does the accuracy of this compare to other common approaches such as FFT?


texts: Irregularity of language of words whose length is of power of 2

texts:
How to show that the language containing the words whose length is a power of $2$, $L=\{w\mid|w|=2^i\}$, isn't regular using the pumping lemma?
The pumping lemma says that

Let be M a regular language. Then it exists a number $p>0$ such that for each word $w\in L$, such that $|w|\ge p$, it exists $x,y,z$ such that :

$w=xyz$
$|y|>0$
$|xy|<p$
For each $i\ge 0$ we have $xy^iz\in L$.

(I don't perfectly understand this lemma...). I have great difficulties to understand the examples which I can provide you in French here.
My question is different from How to prove that a language is not regular? as far as all answers are based on $L=\{w\mid|w|=a^pb^q\}$ scheme, mine only have one element and is playing on the size rather than the scheme.
My attempt
We take $w=a^{2^n}$. Therefore we have $w\in L$ and $|w|\ge p$. We need a partition $w=xyz$ (to fill in condition 1.) such that $|xy|<p$ (condition 3) and $|y|>0$ (condition 2).

Let's assume $L$ is regular.
I thought about taking $|w|>n$
$x = aaaa....$ , $y = aaaa...$,
$|x|=s$, $|y|=k$. We need to consider ALL the options, that is all
the possible $s,k$ such that $s≥0$,$k≥1$ and $s+k≤n$.

Let's take $i=0$, then $xy^iz=xz=a^{n-k}a^n\not\in L$ whatever may $s,k$ be and since $k\ge 1$, $L$ isn't regular at all (but why) and we reach a contradiction.
I have some difficulties understanding the conclusion.


texts: When describing a CS paper, can it be assumed that the meaning of "tick" is known?

texts:
I thinkt this question fits better here than on english.stackexchange.

When describing a figure in a computer science paper, is it safe to use "tick" meaning "tick mark"?

Examples:
... (see the thick line right of tick "17")  meaning tick mark "17"
or ... increase at tick "1e+02" ... increase at tick mark "1e+02".


texts: How do I compute the power consumption of a DRAM refresh?

texts: Given a DRAM-based memory system with a total capacity of $x$ bytes, $y$ DRAM rows and a refresh time of $t$ milliseconds, how do I compute the power consumption for one DRAM refresh? I couldn't find something concerning this question so far.


texts: Search in a partial ordering defined by tuples of numbers

texts:
This is a graph theory and partial ordering problem. Consider a set of triples {(di,ai,ci)}i=1...N, which specify edges between two nodes A and B, d denotes a departure time, a an arrival time and c a cost. Technically there can be multiple incomparable costs, for example in $ and % chance that your goods arrive safely.

An example of such a situation could be these 5 edges:

(I did not draw the time axis on scale)

There are five edges, I, II, III, IV and V. The costs are denoted at the edges, they are either 100, 10 or 1. Edge V is drawn red to easily discriminate it from the other edges, since it crosses through them. However, aside from that it is not different.

Given such edges, a few things are important:

An edge is only interesting if it departs after we arrive at A, for example in the image we can arrive at (a), then edge I is not an option anymore. The same goes for edges II and V if we arrive at (b), etc.
Given an arrival and its set of interesting edges, and edge ei is dominated if there exists an edge ej with ej< ei. This is the case iff aj ≤ ai ^ cj ≤ ci ^ (aj < ai v cj < ci). In layman terms, cost and arrival need to be at least as small, but one must be strictly smaller. This is a partial ordering, some edges are incomparable.
Given a arrival in A, I want to find all relevant, undominated (or Pareto) edges.

We can enumerate all the edges:

I:   (0  , 1, 100)
II:  (0.5, 2, 10)
III: (2  , 3, 100)
IV:  (2.5, 4, 10)
V:   (1.5, 5, 1)

Putting them in a partial ordering, using a directed acyclic graph (dag), we get this:

An arrow denotes the <-relation between edges. Note that an edge in this case is a node in the dag: confusing, I know. When I say edge, I mean a node in the dag above.

I added an edge (-∞, -∞), which is always irrelevant, but creates a nice 'root' of the dag. This way we sort of have a tree, where leaves sometimes merge without creating cycles. I also only denote the arrival at B and cost, needed to create the dag, but technically there is also a departure are A for each of the edges.

If we were to arrive at A at -1, we can simply return all the children of (-∞, -∞) as relevant and undominated, but for another arrival we may need to traverse the tree differently (in a more complicated fashion). I was thinking of this:

marker := map from edge to bool # marks whether edge has been traversed
for all edges: marker(edge) := false # none have been traversed

traverse(root, arrival):
    if(marker(root)) return []  #already been at this node
    marker(root) := true;
    if(departure(root) > arrival) return [root]; # return singleton list, all children will be dominated by this edge.

    # this node is irrelevant, but possible some children are relevant.
    l = [];
    for each child of root:
        append traverse(child, arrival) to l
    return l

Traverse returns a list of undominated, relevant edges. However, Is this an efficient way to tackle this problem? Is there a better solution to this problem? Is this problem known under a known name?


texts: What does it mean when each individual array is sorted in different array but bear no relationship to each other

texts:
There's a textbook problem that talks about making a binary search dynamic, then analyzing for its amortize cost. However I'm not exactly sure what is the organization scheme of this data structure.

Binary search of a sorted array takes logarithmic search time, but the time to insert a new element is linear in the size of the array. We can improve the time for insertion by keeping several sorted arrays. Specifically, suppose that we wish to support SEARCH and INSERT on a set of $n$ elements. Let $k = lg(n + 1)$, and let the binary representation of $n$ be $\langle n_{k‒1}, n_{k‒2}, \ldots , n_0 \rangle$. We have $k$ sorted arrays $A_0, A_1, \ldots , A_{k‒1}$, where for $i = 0, 1, \ldots , k − 1$, the length of array $A_i$ is $2i$ . Each array is either full or empty, depending on whether $n_i = 1$ or $n_i = 0$, respectively. The total number of elements held in all $k$ arrays is therefore $n$. Although each individual array is sorted, elements in different arrays bear no particular relationship to each other
(Excerpt From: Thomas H. Cormen et al., “Introduction to Algorithms: Third Edition.”)

What does this mean when we have a data structure with several sorted arrays that bear no such relationship? Does it mean that they all must be sorted relative to themselves, but not to the rest? If that's the case, when you try to perform an insert or delete, conceptually, how would you know which array to insert it to or to delete from, and how would it be reshaped?


texts:
I have an introductory class in computability theory and I'm currently working on my first exercises. I'm wondering if I'm on the right track with proving undecidable languages. Could you please have a look and give me some feedback?

I have the following decision problem and I want to show that it is not semi-decidable:

$H'=\{\langle M\rangle \mid \text{ M does not halt on } \langle M\rangle\}$

My solution so far is as follows:

Suppose $H'$ is semi-decidable, then there exists a TM $M_{H'}$, which semi-decides $H'$. This means that for all $x \in H'$, $M_{H'}$ accepts $x$, and for all $x \notin H'$, $M_{H'}$ halts without accepting or $M_{H'}$ enters an infinite loop.

I know this is not a valid proof and I also know that I have to show the contradiction, but I don't know how. Is there a certain pattern I can always use to show that a language is not semi-decidable?


texts: Can the end-to-end principle be formalized?

texts:
In the late 1990s, when I was in graduate school, the paper

  JH Saltzer; DP Reed; DD Clark: End-to-end arguments in system design. ACM Trans. Comput. Syst. 2(4):277-288, 1984. DOI=10.1145/357401.357402

was pretty much required reading in every operating systems class at every university, and it still seems to be one of the primary guiding principles underlying the design of the internet.  (See for example: J Kempf, R Austein (eds), and the IAB, "The Rise of the Middle and the Future of End-to-End: Reflections on the Evolution of the Internet Architecture," RFC 3724, March 2004.)

The end-to-end principle states (Saltzer et al., 1984):

  [If] the function in question can completely and correctly be implemented only with the knowledge and help of the application standing at the end points of the communication system, ..., providing that questioned function as a feature of the communication system itself is not possible. [Although] sometimes an incomplete version of the function provided by the communication system may be useful as a performance enhancement.

Or more briefly (from the abstract):

  The end-to-end argument suggests that functions placed at low levels of a system may be redundant or of little value when compared with the cost of providing them at that low level.

But I've had little success applying the end-to-end principle in my own experience (which is in computer architecture, not internet architecture).  Since the principle is stated as a "poem" (i.e., in English prose with a bunch of terms that are not mathematically defined) it is quite easy to fool oneself into thinking that "the function in question can completely and correctly be implemented only with the knowledge and help of the application."  But what is "the function in question," let alone "the knowledge and help" of an application?

Example: On-chip networks (unlike the internet) aren't allowed to drop packets, but have quite limited buffering, so you need to have some way of either avoiding or recovering from deadlock.  On the other hand, the application needs to make itself deadlock free as well, right?  So I might reason that I should make the common case (no deadlock) fast and push deadlock avoidance off on the app.  This is, in fact, what we tried on Alewife and Fugu (Mackenzie, et al., Exploiting Two-Case Delivery for Fast Protected Messaging, Int'l Symp High-Perf Comp Arch, (HPCA-4):231-242, 1998.  Or John Kubiatowicz's dissertation.)  It "worked," (by having the interconnect interrupt the processor when the buffers got filled and having the OS augment with software buffering) but I haven't seen anyone in academia or industry (including any of us that were authors on that HPCA paper) racing around trying to replicate the idea.  So apparently deadlock avoidance in a network is not the same "function in question" as application-level deadlock avoidance, or the end-to-end principle is wrong.

Is it possible to turn the end-to-end principle from a "poem" into a theorem?  Or at least, can it be stated in terms understandable to a computer architect?


texts: What is the LTL expression for "there is a value of y whose next value is 8"?

texts:
Basically i have a program which increases a variable by 1 in each iteration and resets it to 0 as soon as y becomes 8 (i.e. mod 8).

It is a quite simple example but it still bugs me out because i cannot clarify if my LTL-formula is correct for the property "there is a value of y whose next value is 8". For this i came up with the:

$$FX(y \doteq 8)$$

which means "somewhere in the future the next value of y is 8".

Is it the correct LTL formula for my question (even though it is of course invalid for my application)?


texts: How is a program executed at the CPU level?

texts:
I know this is a very common question. But I have a different angle in my mind. I will just try to articulate it here.

From what I know, every instruction that a CPU executes, is in machine language and all CPU can do is do some arithmetic operations thanks to ALU and to its transistors (if we go at hardware level).

However this is easier to type than to comprehend it. So if all CPU does is adding, subtracting, etc., then how is a program, say a JAVA program saying print Hello World, executed with these arithmetic operations?

I mean how is this program converted into something that is just an addition for the CPU?

P.S. If this question is not applicable for this website then I apologise.

-----Part TWO-----

Okay. Thanks to all for answering this fast and with this enthusiasm. I thought its better to modify my question a bit than to go and comment to all answers and ask them again.

So here it is.

First, all have answered specifically w.r.t example of Hello World. This is my fault. I should have kept this generic. Hello world example brings in question of output devices and how its processing is not just limited to the CPU, which is rightfully brought up in your answers.

Also  many of you brought to my notice that CPU does more than just addition. I agree with that. I just didn't write that and assumed it all the way.
From what I understand, this is the process:

read the instruction from memory (using data and address buses and program counter stuff)

store data in register inside CPU
Now ALU does arithmetic operations, of course after decoding the instruction, or take a jump if its an if like instruction
And then communicating with other resources if needed like with output device and so on. Processes beyond this are trivial for now.

So in step3 where CPU decodes an instruction and decides to do an arithmetic operation(here we are assuming that there is no other operation to be done like jump the current instruction..since arithmetic operations are mostly done..so we will stick to that)  This is where my visualization ends. How an instruction from my program is just an arithmetic operation for CPU. It does that arithmetic operation and that instruction serves its purpose.

I hope I made myself clear this time.

P.S. I am taking a big assumption here that ALU is just not restricted to actual arithmetic operation we do in our programs, rather it executes all instructions ,which are now in binary form, by adding or subtracting e.t.c them to yield result that they are meant to yield.
If I am wrong here than answers below correctly answer my question.


texts: Are space allocated to C/C++ variables in secondary storage also in Compiled file?

texts: Are data segments,heap,stack etc also present in secondary memory with compiled code then later mapped by OS to RAM when I open it?


texts: How does MCTS handle games with large numbers of poor moves?

texts:
I am trying to understand how pure Monte Carlo tree search (https://en.wikipedia.org/wiki/Monte_Carlo_tree_search) handles games where random playout will likely result in a loss easily avoided by other types of agents.

For example, imagine a hypothetical game with a single player. At game start, the player can choose between move A or move B.

Move A results in a fair coin flip that determines win/loss.

Move B results in a second set of 10 possible moves for player A, one of which is a win (move C, let's call it), and the other 9 a loss.

Random playout will have move A winning 50% of the time, and Move B winning 10% of the time, even though the ability to always pick the winning move B->C is within the player's power.

Can MCTS handle games of this nature well? How does it do so?

Obviously this toy example can trivially be solved by other search methods, but the real game I'm interested in has a prohibitive branching factor for things like depth- or breadth-first search, and a proper evaluation function is difficult.


texts: What solution to apply for finding the optimal parameters?

texts:
For a study, I have a system (black-box) that requires an input in the form of an array with 4 values (input_array) and depending on their values it produces an output (response) signal.

The input_array contains 4 real values (parameters P1-4), with given and separate ranges. The output signal's quality is measured by calculating its signal-to-noise ratio (SNR). Each input_array variant can be applied to the system once every 3 seconds (not faster than 3 s).

I have to find the optimal input_array that produces the greatest SNR (preferably, in the least amount of time). That is, the combination of the 4 real values that maximizes the SNR (an optimal solution is sufficient; an absolute solution is welcomed, but not necessarily required). If helpful in finding a solution, the 4 parameters can be discretized, but their ranges would include hundreds of possible (discrete) values.

The values can be considered independent, no prior knowledge is available for them except their ranges, and their individual influence on the SNR is unknown. The SNR is a real value that is influenced by noise (thus, for the same input_array applied consecutively, it can have different (but close) values).

What solution(s) can be applied to this problem?

The simplest solution that comes to mind is to perform an
exhaustive search of the parameters domain, but it is no applicable because the time required will be too long.
Initially, I was considering of applying reinforcement learning
algorithms for continuous action spaces, by considering each
parameter a separate action and returning a positive/negative reward
when the SNR increases/decreases (e.g., +/-1). However, I think they
would require too much time; nonetheless, I can stop the learning
process at any time I consider that the input_array produces an
acceptable SNR.
After further thinking, this problem seemed like a search problem,
so I thought that (heuristic) searching algorithms may be
appropriate.

Does anybody have an idea what would be the most appropriate solution to this problem?


texts: Is there a functional programming language with inherent change propagation?

texts:
Change propagation in programming environments is an add-on at the framework level such as React.
There was a lot of work on dataflow virtual machines in the wake of Backus's Turing Award Lecture on formal functional programming.  This is because dataflow programming is one way of thinking about change propagation in functional programming, and people were seriously re-visiting the conflict, going back to the first implementation of LISP, between the concepts of state and pure lambda calculus.
While I recognize that dataflow merely pushes that conflict to the end-points of the dataflow graph, it does seem to have practical merit as evidenced by frameworks attempting to grapple with it.  However, in the decades since then, I've not noticed any functional programming languages that have inherent change propagation.
Am I missing something?


texts: How to show a function is primitive recursive by induction?

texts:
I know, loosely speaking, if we can define a function $f$ in term of
\begin{align}
&f(0,\vec{x})=g(\vec{x})\\
&f(n+1,\vec{x})=h(f(n),n,\vec{x})
\end{align}
where functions $g,h$ are primitive recursive. Then $f$ is primitive recursive.
However, what it means to show a function is primitive recursive by induction?

I had read above explaination on page 93 on book $\textit{Computability}$ by Epstein and Carnielli, but still I'm not sure if I got the idea. Could someone provide some examples about how a inductive definition shows a function is primitive recursive?


texts: Design a DFA that recognizes the following language

texts:
My assignment asked to design a DFA that computes the language:

$L = \{ w \in \{a,b,c\}^\star | \#_a(w) $ is even, $\#_b(w)$ is odd, $\#_c(w)$ is even}

I have been stuck on this question for 2 hours, I draw approximately 20 sketches but still fail. The only thing that I observed so far is we need at least 8 states, or maybe more. And if a non-accept state reads a letter to an accept state, then it must read the same letter back to the non-accept state, or vice versa.(to keep the property of even or odd numbers) But I'm failing to handle all the cases, such like I can handle aabcc, ccbaa, but fail to abcbbca or abcbbac.  Any suggestions?


texts: Can a semi-decidable problem be also decidable?

texts:
As far as I understand, a semi-decidable (recursively enumerable) problem could be:

  decidable (recursive) or
  undecidable (nonrecursively enumerable)

This post made me wonder if this is not conventionally followed. This is my answer to it and as far as I understand it is correct:

  A semidecidable problem (or equivalently a recursively enumerable
  problem) could be:

  Decidable: If the problem and its complement are both semidecidable
  (or recursively enumerable), then the problem is decidable
  (recursive).

  Undecidable: If the problem is semidecidable and its complement is not
  semidecidable (that is, is not recursively enumerable).

  Important note: Remember that a decidable (recursive) problem is also
  semidecidable (recursively enumerable). Conversely, if a problem is
  not recursively enumerable (semidecidable), then is not recursive
  (decidable).

What the Wikipedia entry says is that:

  Partially decidable problems that are not decidable are called
  undecidable.

  In general, a semidecidable problem (recursively enumerable) could be
  decidable (recursive) or undecidable (nonrecursively enumerable).

  Also note that a problem and its complement could both (or just one of
  them) be not even semi-decidable (nonrecursively enumerable). Also
  note that, if a problem is recursive, its complement is also
  recursive.

Is it conventionally (always) understood this way? Is there some literature that presents semi-decidability (partially decidable, recursively enumerable) problem as an equivalent of undecidability?


texts:
I'm trying to show that a special variant of the common 3-SAT is NP-complete by reducing 3-SAT to this special variant.

This special variant works like the normal 3CNF-SAT, except every other clause is conjunctive instead of disjunctive. For example an instance of this variant could be
$(x \vee y \vee z) \wedge (x\wedge w\wedge k) \wedge (y \vee \neg{}z \vee f)$.

EDIT:

Would the following work?
If I want to reduce $from$ 3-SAT, I would propose an instance of the 3-SAT variant, and via an algorithm running in polynomial time, transform every other clause (the conjunctive ones) into 3 new disjunctive clauses like the following example.

Instance of 3-Sat Variance
$(x \vee y \vee z) \wedge (x\wedge w\wedge k) \wedge (y \vee \neg{}z \vee f)$

Transformation/Reduction
$(x \vee y \vee z) \wedge (x\vee x\vee x) \wedge (w \vee w \vee w) \wedge (k \vee k \vee k) \wedge (y \vee \neg{}z \vee f)$

EDIT 2:

Or do you mean I should look at it the other way around?

If I want to prove that this 3-SAT variant is NP-complete, could I for example simply add a new, trival term $z$ not used in the original list of terms (give it TRUE as truth value), and add a clause $(z \wedge z \wedge z)$ inbetween all the original clauses of the original 3-SAT instance?


texts:
I am writing optimization program for unrelated parallel machine scheduling problem on CUDA. Now, the only thing I am missing are some test cases.

Does anyone know where I can find such data? I have been searching for a while but I've only found this: http://people.brunel.ac.uk/~mastjjb/jeb/info.html. Unfortunately there is no test data for UPMS. I know I can easly generate some cases but I just wanted to be sure if optimum is being found correctly.


texts:
I want to decode the following bit stream using Hamming code:
01110110

Once using even parity and once odd parity. I will show my work. For even parity:

$p_{1} \; p_{2} \; 0 \; p_{3} \; 1 \; 1 \; 1 \; p_{4} \; 0 \; 1 \; \; 1 \; 0$

Now, we check:

$p_{1}: p_{1}  \; 0 \; 1 \; 1 \; 0 \; 1 $, since there is an odd number of 1's, $p_{1}=1$

$p_{2}: p_{2}  \; 0 \; 1 \; 1 \; 1 \; 1 $, since there is an even number of 1's, $p_{2}=0$

$p_{4}: p_{3}  \; 1 \; 1 \; 1 \;0 $, since there is an odd number of 1's, $p_{3}=1$

$p_{8}: p_{4}  \; 0 \; 1 \; 1 \;0 $, since there is an even number of 1's, $p_{4}=0$

so the following hamming code is
$$1 \; 0 \; 0 \; 1\; 1 \; 1 \; 1 \; 0 \; 0 \; 1 \; \; 1 \; 0$$

As for odd, the parities will just be the opposite and the code will be

$$0\; 1 \; 0 \; 0 \; 1 \; 1 \; 1 \; 1 \; 0 \; 1 \; \; 1 \; 0$$

Can someone tell me if my work is correct? Because I am a bit confused and would appreciate the help.


texts:
I am given the following grammar:

$
S \rightarrow AabAba
\\
A \rightarrow a | \epsilon
$

and I have to prove it is LL(2).

I know what LL(k) means - one can choose a production based on k characters from the input.

So consider the input $ababa$. Of course we start with $S$, so we apply the production to $AabAba$. Now we see $ab$ in the input, so we choose the production to $\epsilon$ for the first $A$. We get rid of the $ab$ and we have $aba$.

And what now? A while ago, we've chosen $\epsilon$ for $A$, seeing $ab$ in the input. Now we see the same thing, but are supposed to choose $A \rightarrow a$. But, as I understand, we cannot do this, because that would mean nondeterminism.

Is this a counterexample? How is this grammar LL(2)?


texts:
Given I have an initial capital of $10,000 and i want to buy shares in 3 different companies.
Cost of a share in company 1 = $55
Cost of a share in company 2 = $68
Cost of a share in company 3 = $79
And, The trading platform charges me $30 collectively for three purchase transactions above.
And, I want to invest 70% of my capital in company 1, 15% in company 2 and 15% in company 3

What would be non brute force algo to ascertain the total number of shares per company I can buy, that leaves the minimum capital amount after the 3 purchases ?
The problem sounds similar to 0-1 knapsack DP but its not quite that, i believe.


texts:
In the context of database theory, what does semantic closure mean (linguistically speaking, i.e. not the mathematical definition)

If X is the set of attributes of $F$, then the semantic closure $F^+$ of $F$ is defined as follows:
$F^+=\{$ Y $\rightarrow$ Z $\ |\ $ Y $\cup$ Z $\subseteq$ X $\wedge\ F \models$ Y $\rightarrow$ Z $\}$
$F \models $ Y $\rightarrow$ Z means that any database instance that satisfies every functional dependency of $F$ also satisfies Y $\rightarrow$ Z


texts: Prove that $\{1^m+1^n = 1^{m+n}\}$ is not regular using Myhill–Nerode

texts:
Consider the alphabet $Σ = \{1, +, =\}$ and the following language, $PLUS = \{ 1^m + 1^n = 1^{m+n} \mid m, n ∈ ℕ \}$. Prove with Myhill-Nerode that PLUS is not a regular language.

I know how I should use Myhill-Nerode here and how I should show that any two strings in the infinite set $S$ are distinguishable, but I am stuck at defining my infinite set S for this language. I tried $S = \{1^n \mid \text{$n$ is a natural number} \}$ but I don't think it works.


texts: Deterministic and randomized communication complexity of set equality

texts:
Two processors $A, B$ with inputs $a \in  \{0, 1\}^n$ (for $A$) and $b \in  \{0, 1\}^n$
(for $B$) want to decide whether $a = b$. $A$ does not know $B$’s input and vice versa.

A can send a message $m(a) \in  \{0, 1\}^n$ which $B$ can use to decide $a = b$. The communication and computation rules are called a protocol.

Show that every deterministic protocol must satisfy $|m(a)| \ge  n$.
State a randomized protocol that uses only $O(\log_2n)$ Bits. The protocol should always accept if $a = b$ and accept with probability at most $1/n$ otherwise. Prove its correctness.


texts: Grover's search on cryptographic hash functions - how can we build the oracle?

texts:
Let's say I'd like to search a database and I have a function $f$ such that $f(x) = 0$ for all incorrect entries and $f(x) = 1$ for all target entries.

The crux of Grover's search seems to be that there exists a way to construct a quantum operator $\hat{f}$ in a way that it takes a superposition of states as input and adds a phase only to the target elements from the superposition.

What guarantee do we have that such a construction exists? For example, if I take a classical hashing function, how do I go about building the quantum equivalent that is able to simultaneously evaluate multiple inputs and assign the phase only to those inputs that fall below some target threshold?


texts: $2$-sorted array. How to sort it in minimal number of comparisons ?

texts:
It is given array $2$-sorted array $a[1..n]$.  $2$-sorted denotes that $a[1]\le a[3]\le...\le$ and $a[2]\le a[4]\le ..\le$

Obviously we may split array into two sorted arrays and then merge two arrays - it requires $n-2$ comparisons.  However I think about lower bound. I believe that $n-2$ is lower bound number of comparisons, but I can't see a way to prove it.  Can you give me a clue ?


texts: checking whether turing machine passes at least k>2 states before accepting a word

texts:
$L=\{\langle M,k\rangle \mid\exists w\in L(M) \text{ such that $M$ passes at least
 $k>2$ distinct states before accepting $w$}\}$
I try to think of reduction to prove that this language is neither RE nor coRE.
How to approach this problem? Is there a hint, or intuition?
I usually check whether Rice can be used, but the question here is not about the language itself


texts: What algorithm to use for this subset sum problem

texts:
I have a typical subset sum problem and I'm looking to choose the proper algorithm to solve it, the set contains (around) 1000 elements, and elements are constrained to max 22 bits for now.

I have been looking around and looks like the well known O(2^(n/2)) is not an option, and looking into the Dynamic Programming version memory becomes a big concern, because the elements values are pretty balanced

n=1000
s=962,425,151 (Avg=964,452)

Array required: [1000,964452152] =    964,452,152,000 bytes

Even using a bit array, (given I'm estimating the algorithm requirements properly), it will require 112 GB of memory... (964,452,152,000/8 =     120,556,519,000 bytes)

Is there other known subset sum algorithm I could evaluate?

Edit 1: (after Tom reply)

I didn't clarify this in the question:

It must be an exact algorithm (not approximate solutions)
Should be able to output the subset solving s


texts: Transform regular grammar in linear grammar

texts:
My problem is how can I transform a regular grammar into a linear grammar?

I know that a linear grammar has the form

$\begin{align} A &\to w_1Bw_2 \\
               A &\to w \end{align}$

where $A,B \in N$ and $w,w_1,w_2 \in \Sigma^*$.


texts: How to print all pairs of ID numbers such that the corresponding people don't belong to the same socieities

texts:
I want to express the following in relational algebra:

Given a table of

PEOPLE: ID, SocietyName

Where the combination of ID and SocietyName form a key such that we could have the same ID in the table more than once but paired with a different society name.

I would like to be able to output all pairs of people, ID1 and ID2 such that they do not both attend any of the same societies. I am struggling to structure this in my head, I think I will need to rename PEOPLE to p1 and p2 say, then do some kind of join but I am not sure how to refine the output so it is only pairs where none share the same society.


texts: Repeatedly finding and deleting maximal independent sets on a graph: Number of necessary iterations in restricted cases

texts:
I am trying to design a parallel scheduling algorithm based on a constraint graph $G=(V,E)$ in which each node represents a task and each edge $e=(v_1, v_2)$ signifies, that tasks $v_1$ and $v_2$ can not be executed in parallel. Each task is executed exactly once, so the problem is finding "good" independent sets $V_i$, so that
$$
\bigcup_{i=1}^{k} V_i = V\\
$$
with all independent sets $V_i, V_j$ being pairwise disjoint. Since MaxIS is NP-Hard my approach would be solving MIS repeatedly (finding some maximal independent set, removing those vertices and start again until the Graph is empty). I know that in the worst case of $G$ being a clique this approach would yield $n$ iterations, however in my instance i would have the guarantee that the number of neighbors of each node would be upper-bound by $c \ll |V|$.
My question is: Given such a $c$ is there any upper bound on the number of necessary steps $k$?


texts:
Given is an undirected and connected graph. The vertices are persons and the edges between them model their relation. Iff X and Y have an edge (X, Y) the know each other directly. Because the graph is connected each person knows each other at least indirectly. If X knows Z indirectly there must be a person Y so that X knows Y and Y knows Z, what I mean is that every person can know every other person through at most one other person.

Now the task is to seat the people on tables so that on every table every person knows exactly two persons directly. Persons knowing each other directly should sit on opposing sites of the table and persons knowing each other indirectly should sit on the same site.

The question is now how many tables are needed.
I know some graph algorithms like mst, maximum flow, bfs, dfs, dijkstra and so on, but I couldn't come up with an algorithm that solves this problem so please help me.


texts:
I tried this problem from CLRS (Page 39, 2.3-4)

  We can express insertion sort as a recursive procedure as follows. In order to sort A[1... n], we recursively sort A[1... n-1] and then insert A[n] into the sorted array A[1... n-1]. Write a recurrence for the running time of this recursive version of insertion sort.

The recurrence I formed was

$$
T(n) = \begin{cases}\Theta(1) & \textrm{if } n = 1,\\
       T(n-1) + \Theta(n) & \textrm{if } n > 1.
\end{cases}
$$

My reasoning

the base case of $n = 1$ the list is sorted so there is no work hence constant time.
For all other cases the time depends on sorting the sequence A[1...n-1] and then insertion into that sequence. Hence it should be their sum, i.e., $T(n-1) + \Theta(n)$.

I wanted to know whether the recurrence relation is correct. If not what are the mistakes and how to correctly formulate a recurrence relation?


texts: Show that every infinite recursive set has both a nonrecursive r.e. subset and a non-r.e. subset

texts:
My attempt to solve this:

If $\mathcal{A}$ is an arbitrary infinite recursive set then the members of $\mathcal{A}$ can be ordered in ascending order. We can do bijection between $\mathcal{N}$ and $\mathcal{A}$.

Halting problem is $\mathcal{K}\subseteq\mathcal{N}$ and therefore it's also $\mathcal{K}\subseteq\mathcal{A}$. And the same can be said about $\bar{\mathcal{K}}$.

Is my solution correct? Are there any "better" solutions to this problem?


texts: What's the runtime complexity of this algorithm for breaking up string into words?

texts:
I am given a input string $s$ ("bedbathandbeyond") and a set of words {"bed", "bath", "beyond", "bat", "hand", "and"}. I need to divide the input string $s$ into a series of words in the dictionary. In this case, the two allowed outputs would be ["bed", "bath", "and", "beyond"] and ["bed", "bat", "hand", "beyond"]. Both outputs are allowed and none is better than the other.
Here is my recursive solution. On input $s$, it either outputs a decomposition of $s$ into a sequence of words in the dictionary, or Fail.

If the input $s$ is empty, output the empty decomposition.
Otherwise, go over all prefixes of $s$. For each prefix that belongs to the dictionary, recursively try to decompose the corresponding suffix, and if successful, output the corresponding decomposition.
If no decomposition was found, output Fail.

In order to speed up the procedure, I envision using memoization. That is, I maintain a hashtable with answers to previous queries, and on input $s$, I first check whether I already know the answer for $s$. If not, after computing the answer, I put it in the hashtable.
If no memoization is used, the runtime is clearly exponential: we have $O(n)$ branching factor, and $O(n)$ as the depth: $O(n^n)$. With memoization; however, the algorithm seems to be polynomial: the procedure can be called with at most $n$ different inputs, and it then performs a polynomial amount of work on it.
I've been told by a very knowledgeable person that it's still exponential. Could someone explain why? I've been thinking very hard about it and I'm not sure why that's the case. If it matters, I'm implementing this algorithm in python.


texts: Dijkstra and A* Algorithms: Why is A* faster?

texts:
I am learning about Dijkstra's Algorithm and the A* Algorithm and I have manually worked through the graph attached here, which is supposed (I think) to demonstrate that the A* Algorithm is faster than the Dijkstra one. The sequence in which I chose the nodes is indicated by the circled numbers. I can see that the process is fairly simple but there are plenty of possibilities for human error, so please bear with me.

My course book says that the A* will be quicker.

I can't see why this is true. Have I worked through the graph incorrectly?

It seems to me that both methods require that all nodes must be visited so where is the increase in efficiency?

I have read what I can on Stack Overflow about this so please don't point me at earlier posts unless there is a very good reason.


texts: Generate collision resistant identifiers with two-way hashing

texts:
Objective: We want to generate a unique and reproducible identifier for a given slice of bytes and avoid collisions.

High-level idea: Compute $$fK := hash(k_1)\; and\; sK := hash(k_1^{-1})\; where\; k_i^{-1}\; is\; the\; reversed\; bitstring\; k_i$$

We then proceed to set, our identifier to be: $$<value\_of\_fK>\_<value\_of\_sK>$$

Assumption:

For two keys $$k_1\; and\; k_2,\; if\; hash(k_1) = hash(k_2)\; and\; hash(k_1^{-1}) = hashs(k_2^{-1})\; then\; k_1 = k_2$$

where our hash function is FNV1a.

Hypothesis: For any given input bitstring, we will have a unique identifier and no collisions.

I would like to have your input on this


texts: Are Context Sensitive Grammar with Polynomial Complexity Time?

texts:
Accordingly, to the question Chomsky Hierarchy and P vs NP, Context-Sensitive Grammars are on Linear Space.

Assuming a Deterministic Parser is the one which can parse unambiguous grammars in something like linear time complexity, while a NonDeterministic Parser can parse any grammar in some worst time complexity like $O(n^5)$ or exponential.

When something is on Linear Space, it takes Exponential time to be parsed by a Deterministic Parser? (probably space complexity has no relation to its time complexity, maybe something in $NSPACE(n)$ or $PSPACE(n^2)$ can affect time complexity?)
Can any Context Sensitive Grammar be parsed in a Polynomial Complexity Time?


texts: Using a counting semaphore as a binary semaphore

texts:
Are there any methods, so that I can use a counting semaphore as a binary semaphore?

A binary semaphore should have two possible states: 0 and 1.  The operation wait() should atomically look at the state, if the state is > 0, the state should be decremented and the process should continue.  If the state is 0, the process should be atomically placed on a queue of waiters and the process should block.  The operation signal() should atomically look at the state, if the state is 0, and there are processes blocked, exactly one of them should be woken.  If there are no blocked processes the value of the semaphore should be set to 1.

I specifically need a binary semaphore, not a mutex. A mutex assumes ownership: that a processes will first lock and then after a resource is used, the process will unlock the mutex. But in my case there are some processes that will only do semaphore signal() operation, without ever performing a wait() operation.

How can I make sure that the value of the counting semaphore never goes above 1?

I asked a similar question, on Stack Overflow, specifically about solving this problem with the POSIX synchronization APIs, but the suggestion I got there was to use file locking, which is much slower than semaphores, and also seems to have the mutex semantics I can't use.


texts: If I can solve Sudoku, can I solve the Travelling Salesman Problem (TSP)? If so, how?

texts:
Let us say there is a program such that if you give a partially filled Sudoku of any size it gives you corresponding completed Sudoku.

Can you treat this program as a black box and use this to solve TSP? I mean is there a way to represent TSP problem as partially filled Sudoku, so that if I give you the answer of that Sudoku, you can tell the solution for TSP in polynomial time?

If yes, how? how do you represent TSP as a partially filled Sudoku and interpret corresponding filled Sudoku for the result.


texts: Proof By Contradiction - Hamiltonian Paths and Cycles

texts:
Was hoping if anyone had any way to prove the following claim using proof by contradiction

Let $G = (V, E)$ be a simple graph with at least one vertex, and let $G'$ be the graph formed by adding a new vertex $v$ and making it adjacent to every vertex in $V$.
Claim: $G$ has a Hamiltonian Path if and only if $G'$ has a Hamiltonian cycle.

I tried manipulating the definitions of each of the two (path vs. cycle), but didn't find much luck. Any thoughts?
Thanks!


texts: Why do some filesystems have fragmentation and others don't?

texts:
I try to understand why fragmentation is a problem for NTFS and FAT but not when using inodes.
In all cases, files are not necessarily stored in a contiguous fashion so I don't see the problem for the former two.

So where is the crucial difference?


texts: Fast Raytracing Algorithm or Alternative needed

texts:
I have a grid that shows the world and its coastlines. An excerpt from the area around the UK is shown here

From an arbitrary origin point anywhere in the ocean, I want to find those coastline points that are in line of sight of the origin without having to cross another coastline point. For example, if the origin is on the west side of the UK, I would expect to get many coastline points of western Ireland and western UK but not from Denmark as it is "covered" by the UK.
I need advice on a fast algorithm that can "shoot out" rays and detect where those rays cross the first coastline (coastline map is available in binary format).
Alternatively, I could imagine to move along all coastline pixels, build the connecting line between the origin and the coastline point and check if there is no other coastline point on the connecting line. Does any algorithm comes to mind that could accomplish this check of coastline crossing efficiently?
I should add that the map is an array of dimensions 5000x10000 and the coastline is available in binary format (all pixel values are zero except for coastline pixels = 1).
I realize this question is a shot in the blue but maybe there is someone smart who has knowledge in this area. Any help is much appreciated.


texts: Turing machine + time dilation = solve the halting problem?

texts:
There are relativistic spacetimes (e.g. M-H spacetimes; see Hogarth 1994) where a worldline of infinite duration can be contained in the past of a finite observer. This means that a normal observer can have access to an infinite number of a computation steps.

Assuming it's possible for a computer to functional perfectly for an infinite length of time (and I know that's a big ask): one could construct a computer HM which travels along this infinite worldline, computing the halting problem for a given M. If M halts, HM sends a signal to the finite observer. If after an infinite number of steps the observer doesn't get a signal, the observer knows that M loops, solving the halting problem.

So far, this sounds okay to me. My question is: if what I've said so far is correct, how does this alter Turing's proof that the halting problem is undecidable? Why does his proof fail in these spacetimes?


texts:
According to the definition, the productions of a right linear grammar should have the form of $A\to xB$ or $A\to x$,
does $A\to B$ or $A\to xy$ count as productions of a right linear grammar? $A\to B$ can be written as $A\to \epsilon B$ though...


texts: I am learning logic and functional programming and there is a topic called Type checking and their relationship to logic , I am unable to find any source that can help me in understanding this topic. Please help .


texts:
Can we think of NP using a parallelism model instead of using a "checking relation" without loss of generality?

From what I understand from the problem statement given by Stephen Cook,

  The notation NP stands for “nondeterministic polynomial time”, since
  originally NP was defined in terms of nondeterministic machines (that
  is, machines that have more than one possible move from a given
  configuration). However, now it is customary to give an equivalent
  definition using the notion of a checking relation, which is simply a
  binary relation R ⊆ Σ ∗ × Σ ∗ 1 for some finite alphabets Σ and Σ1. We
  associate with each such relation R a language LR over Σ ∪ Σ1 ∪ {#}
  defined by LR = {w#y | R(w, y)} where the symbol # is not in Σ. We say
  that R is polynomial-time iff LR ∈ P. Now we define the class NP of
  languages by the condition that a language L over Σ is in NP iff there
  is k ∈ N and a polynomial-time checking relation R such that for all w
  ∈ Σ ∗ ,w ∈ L ⇐⇒ ∃y(|y| ≤ |w| k and R(w, y)), where |w| and |y| denote
  the lengths of w and y, respectively.

it appears that the definition of NP given here can be derived from the definition of non-deterministic Turing machines. From this lecture document from the University of Illinois:

  Formally, a nondeterministic Turing machine has all the components of
  a standard deterministic Turing machine—a finite tape alphabet Γ that
  contains the input alphabet Σ and a blank symbol ; a finite set Q of
  internal states with special start, accept, and reject states; and a
  transition function δ. However, the transition function now has the
  signature δ: Q × Γ → 2 Q×Γ×{−1,+1} . That is, for each state p and
  tape symbol a, the output δ(p, a) of the transition function is a set
  of triples of the form (q, b,∆) ∈ Q × Γ × {−1,+1}. Whenever the
  machine finds itself in state p reading symbol a, the machine chooses
  an arbitrary triple (q, b,∆) ∈ δ(p, a), and then changes its state to
  q, writes b to the tape, and moves the head by ∆. If the set δ(p, a)
  is empty, the machine moves to the reject state and halts. The set of
  all possible transition sequences of a nondeterministic Turing machine
  N on a given input string w define a rooted tree, called a computation
  tree. The initial configuration (start, w, 0) is the root of the
  computation tree, and the children of any configuration (q, x, i) are
  the configurations that can be reached from (q, x, i) in one
  transition. In particular, any configuration whose state is accept or
  reject is a leaf. For deterministic Turing machines, this computation
  tree is just a single path, since there is at most one valid
  transition from every configuration.

This mentions the notion of a computation tree:

Thus, suppose I were to have a machine that was able to compute all of the non-deterministic branches in parallel such that the bounded running time is $O(poly(n))$. Is this an equivalent of a Turing machine such that a language that is accepted by this machine is within $NP$?

In a sense, we can also see that if a deterministic machine were to choose the "right" branch by chance that it's somewhat equivalent to the notion of an oracle. This seems like it's similar to the "checking relation" in the sense that we need only compute one branch's result in order to determine acceptance of the answer or rejection. Is this intuition right?

And, in addition, can the deterministic machine can simulate the computation of the non-deterministic machine in $O(2^n)$ time?

Edit: If we make the addition that one of the paths are guaranteed to accept, then is the machine now equivalent to NP?


texts: Check if knapsack problem instance is unsolvable

texts:
Is it possible to easily check if an instance of the 0-1 knapsack problem is unsolvable? Example: Assign 10 40-min tasks to 8 employees that have 60 minutes available each. Clearly, this instance is unsolvable as a 0-1 knapsack problem (but solvable as a fractional knapsack problem). I don't want to solve the 01-knapsack problem, but just detect if it is NOT solvable. Thanks in advance!

EDITED PROBLEM 1 - THOROUGH PROBLEM DESCRIPTION

Below is a more thorough problem description.

Tasks

I have a set of tasks with a given duration and a given time window each task has to be performed within (e.g the task duration for a given task could be 20 minutes and it has to be performed in the time interval 08:00-09:00). In addition, each task has a required skill, meaning that the employee carrying out the task needs to have a certain competence level (e.g tasks with required skill equal to 2 can only be carried out by employees with a competence level greater than or equal to 2).

Employees

I have a set of employees that work shifts. E.g an employee work from 08:00 to 13:00. Each employee has a given competence level, described above. The tasks are supposed to be allocated to the employees, and an employee cannot perform more than one task at the same time. E.g the same employee cannot perform BOTH task 1 (duration 10 minutes and time window 08:10-08:20) and task 2 (duration 30 minutes and time window 08:10-08:45). In addition, there are some tasks that a given employee cannot perform due to other reasons.

Problem

I want to check (preferably in polynomial time) a given problem instance (with tasks and employees) is not solvable, meaning that there exists some conflict such that it is impossible to allocate all tasks (see example above in original question formulation). To my understanding, it is NP-hard to solve the problem, but I just want to prove/detect that a given instance is unsolvable. Is it possible to easily check if there does not exist a possible assignment of tasks to employees?

EDIT 2 - BETTER DEFINITION OF THE GOAL

To be clear, I don't want an algorithm that ALLWAYS finds out if an instance is unsolvable or not. I am just looking for a way (an algorithm) that as OFTEN AS POSSIBLE finds out if the instance is unsolvable, and if the algorithm is uncertain (some efficient test did not detect that the instance was unsolvable) then I am fine with the problem instance being either solvable or unsolvable. So the algorithm I am looking for should detect as many "unsolvable instances" as possible, but not all.

Thanks in advance for your answers and contributions!


texts:
If I have a nx2 grid which I need to fill using 2x1 dominoes and L shaped trominoes in any combination, how many different combinations are possible?

I am aware that when only 2x1 dominoes are used then the cell definition using dynamic programming is:
$$
f\left [ 0 \right ]= 0
$$
$$
f\left [ 1 \right ]= 1, i=1
$$
$$
f\left [ 2 \right ]= 2, i=2
$$
$$
f\left [ i \right ]= f\left [ i-2 \right ]+ f\left [ i-1 \right ], \forall i>2
$$

When L shaped trominoes are added to consideration, we (assume) can use them only in pairs since using odd number L shaped trominoes will leave one 1x1 grid unfilled. so when a pair of such trominoes combine it is equivalent to using a single 3x2 rectangular piece. Everytime we use $\ num=\lfloor n/3 \rfloor $ rectangular pieces and the rest are filled with 2x1 dominoes. Also the total number of combinations would be sum of twice the $\ num$, $\ f[i] $ and number of 2x1 domino combinations of the rest of the grid when the 3x2 piece is used. Is this assumption right? This is how far I have gotten through. If any of you have any hints it would be appreciated. Thank You in advance.

Note: Tile Rotations are allowed


texts: Term for a graph decomposition based on a maximum matching

texts:
Let $M$ be a maximum cardinality matching in a bipartite graph $G(X+Y,E)$. Let $X_0$ be the subset of $X$ unmatched by $M$. Define the following sequence:

$Y_1 = $ the neighbors of $X_0$ using edges in $E\setminus M$.
$X_1 = $ the neighbors of $Y_1$ using edges in $M$.
$Y_2 = $ the new neighbors of $X_1$ ("new" = not in $Y_1$) using edges in $E\setminus M$.
etc...

Since the graph is finite, at some point we stop finding new vertices, so the process stops and we have a maximal sequence.

Let $X_S,Y_S$ be the vertices contained in the sequence, and $X_L,Y_L$ the leftover vertices:

We have a decomposition of $X$ and $Y$ into two subsets.
This decompositionhas some nice properties (for example, $X_L$ and $X_S$ are the same regardless of what maximum matching $M$ we start from).

Such a nice decomposition must have a name... what is its name? And what is a standard reference for the decomposition and its properties?


texts: How to apply Hoare Logic to this function

texts:
I would like to apply Hoare Logic to realistic, complex imperative programs that use while loops, if statements, functions, modules, etc. and have side effects (e.g. access the network). In order to get started with using Hoare Logic, I would like to see what it takes for this simple function:

function colorize(integer) {
  var hex = '#'

  if (integer > 1) hex += 'ff'
  else hex += '00'
  if (integer < 100) hex += 'aa'
  else hex += 'bb'
  if (integer > 10) hex += '11'
  else hex += '22'

  return hex
}

My first attempt so far is as follows. I haven't found a resource which describes how to model functions in the Hoare logic, so I just went off the cuff.

\begin{align}
\{hex = \# \land integer = y\}\\
if\ (integer > 1)\ hex += ff\\
\{hex = \#ff \land integer = y\}\\
\\
\{hex = \# \land integer = y\}\\ if\ \neg(integer > 1)\ hex += 00\\ \{hex = \#00 \land integer = y\}\\
\\
\{hex = \#\backslash{d}\backslash{d} \land integer = y\}\\ if\ (integer < 100)\ hex += aa\\ \{hex = \#\backslash{d}\backslash{daa} \land integer = y\}\\
\\
\{hex = \#\backslash{d}\backslash{d} \land integer = y\}\\if\ \neg(integer < 100)\ hex += bb\\ \{hex = \#\backslash{d}\backslash{dbb} \land integer = y\}\\
\\
\{hex = \#\backslash{d}\backslash{d} \land integer = y\}\\ if\ (integer > 10)\ hex += 11\\ \{hex = \#\backslash{d}\backslash{d}\backslash{d}\backslash{d11} \land integer = y\}\\
\\
\{hex = \#\backslash{d}\backslash{d} \land integer = y\}\\ if\ \neg(integer > 10)\ hex += 22\\ \{hex = \#\backslash{d}\backslash{d}\backslash{d}\backslash{d22} \land integer = y\}\\
\\
\{hex = \#\backslash{d}\backslash{d}\backslash{d}\backslash{d}\backslash{d}\backslash{d}\}\\ return\ hex\\ \{?\}\\
\\
\{x\}\\ x := colorize(y)\\ \{x = \#\backslash{d}\backslash{d}\backslash{d}\backslash{d}\backslash{d}\backslash{d} \}\\
\\
\{x\}\\ x := length(colorize(y))\\ \{x = 7\}
\end{align}

Then the question is, if we need to show explicit examples:

$$\{x\}\ x := colorize(0)\ \{x = \#00aa22\}$$

That wouldn't really make sense because then that's unit testing rather than proving.

Finally, the question is, how to prove that colorize returns the correct outputs.

What I don't understand about Hoare Logic so far is:

How to model functions. How to model the "variables are in a certain scope" of the function, as well as calling the function.
Which variables to include in the pre- and post-conditions in the example.
My understanding is these are Hoare triples (assertions). Are these considered rules or are they different than rules. If they aren't rules, wondering if I need to be creating rules as well somehow. Also not sure what I should be including in the Hoare Triples, if I was too-specific.
I saw stuff about partial vs. total correctness. Wondering if I need to somewhere include a proof of termination somehow, or each of these statements.
How to write a proof, given these (or the right) Hoare triples.
How to handle the "patterns" in the hex string. I just used regular expression digit format $\backslash d$.
What counts as a "program" (the middle part of the Hoare Triple). If if (integer > 1) s is one, or does it need to be broken down to the program integer > 1, or is that not a program.

I can follow the explanations of Hoare Triples in introductory presentations, but I am thinking I am a long way from applying it correctly. Looking for help to get over the initial starting complexity, would be helpful to show the specific Hoare Logic statements to define/prove this function, or some of them, so I can build on it.