texts:
In my thesis I am working on a problem connected with sequence alignment, in particular, I deal with the Dynamic Time Warping (DTW) algorithm (see this for more), which is used to evaluate the distance between two time series. It is very similar to the Needleman–Wunsch algorithm for aligning protein sequences, the difference is: NW finds a maximum score alignment, whereas DTW finds a minimum distance alignment; and DTW does not penalise gaps.

The question I am having is the following one. Given two sequences S and T, what is the maximum DTW distance between them if points along S can be skipped. I tried adjusting the standard DTW dynamic programming algorithm, but this problem may not be as trivial as it seems. For example, finding the minimum DTW distance between S and T if points along S can be skipped is easy, we just need to extend the recurrence relation from the original alignment algorithm; but this trick does not seem to be working with the problem I have.

I would be very grateful for any ideas on how to tackle this problem or any links to relevant literature.

More formally, DTW distance is defined via the following recurrence relation:
$$d_{DTW}(\langle\rangle,\langle\rangle)=0,$$
$$d_{DTW}(S,\langle\rangle)=\infty,$$
$$d_{DTW}(\langle\rangle,T)=\infty,$$
$$d_{DTW}(S,T)=\delta(S_n,T_m)+\min\{d_{DTW}(S_{1:n-1},T_{1:m-1}),d_{DTW}(S_{1:n-1},T_{1:m}),d_{DTW}(S_{1:n},T_{1:m-1})\},$$
where $\delta$ is the local distance function (usually $L_1$ or $L_2$ metric) and $|S|=n$ and $|T|=m$. What I am looking for is a subsequence $S'$ of $S$, such that is $$\arg\max_{S'}d_{DTW}(S',T).$$


texts:
this is related to the following question:

Generalised 3SUM (k-SUM) problem?

Without loss of generality, let's only consider even $k$, or just $k=4$.

My question is, after summing all pairs of numbers, is it necessary to sort the list of sums? I understand we could use two pointers from left and right to sandwich the two pairs in $O(n^2)$ time, but the sorting requires $O(n^2\log(n))$ time.

If we use a hashmap to store the sums as key and their corresponding index pairs as value, then all operations can run in $O(n^2)$ time.

Am I missing something in that post or is it true for even $k$, $k$-sum can run in $O(n^{k/2})$ time?

Thanks!


texts: Operating System code suffers more cache misses than user code

texts:
I was going through the text of the book Computer Architecture: A Quantitative Approach. It has a section in Chapter 5 where it discusses the fact that OS code undergoes more cache misses as compared to user code. Here is the text:

  Although the user code executes more instructions, the behavior of the operating
  system can cause more cache misses than the user processes for two reasons
  beyond larger code size and lack of locality. First, the kernel initializes all pages
  before allocating them to a user, which significantly increases the compulsory
  component of the kernel’s miss rate. Second, the kernel actually shares data and
  thus has a nontrivial coherence miss rate. In contrast, user processes cause coherence
  misses only when the process is scheduled on a different processor, and this
  component of the miss rate is small. This is a major difference between a multiprogrammed
  workload and one like the OLTP workload.

What is the first argument trying to explain?
My doubt is that although the kernel has to initialize the pages for allocation to a user, it(the kernel) is not required to retrieve data from those pages into cache. That is the user code's responsibility. Hence, the argument seems confusing.


texts: would complexity of constrained optimization problem bound the constraint satisfaction problem?

texts:
For an optimization problem $x^* =\text{argmax}_xf(x)$ s.t. $x \in Y$ satisfy to some constraint $Y$.
Can I argue that if there is a polynomial algorithm for this optimization problem. Then there must exist a polynomial algorithm checking if $x$ satisfy constraint $Y$?


texts: Prove correctness of recursive multiplication algorithm

texts:
I'm in a first year discrete math course and we started algorithms. I created a recursive algorithm to multiply two numbers together:

function multiply($n, $r) {
    if($n == 1)
 return $r;
    else if($r == 1)
 return $n;
    else
        return $r + multiply($n - 1, $r);
}

How do I prove my algorithm is correct?

A quick google search tells me I have to prove that it works for $n + 1$ and I have to prove that it terminates. Unfortunately I'm still incredibly new to this and haven't the faintest clue as to where to start for proving my algorithm correct, so I would really appreciate some help here. I think maybe I have to do some sort of proof by induction but as this is an algorithm, I wouldn't know where to start.


texts:
From what I know,

a problem can be transformed to a yes/no answer, which can be
described by a decision tree.
Solution to a problem also can be represented by a set of strings (a language), which means the problem can be regarded as a membership problem.
This set of strings can
also be represented by an automaton, although how it is done is still
vague in my mind.

My questions are:

What is the relationship between a decision tree and an automaton?

How to convert a decision tree to an automaton?

I have tried to read some articles related to this, and somehow 'know' these concepts are related with each other, but still feel that I don't quite understand the relation and how to convert them to each other.


texts:
I understand that in programming languages in general, function routines have what I can generally name a parameter set (or "list"), usually symbolized with parenthesis and if it is not empty, it is also utilized in function calls.

In JavaScript:

function myFunction (passed_parameter_1, passed_parameter_2) {
    // Some code...
}

myFunction(corresponding_passed_argument_1, corresponding_passed_argument_2);

My problem

I never learned in programming courses:

What is the name of that feature
why, in programming languages in general, a user must have this feature, even if the parameter set in routine and the corresponding argument set in call, are both empty.
Why not let a user define a group of parameters (or not) per need, only inside a routine's scope instead

Interim note

One could claim it is needed for a compiler to know what is a function but a keyword such as function reinforce the opinion that it isn't.
One can claim it is needed for separation of internal implementation and external interface but such separation could be done as two different sub-scopes of the main scope ({}), for example:

function myFunction {
    par myPar1
    par myPar2

    // some code

}

myFunction {1,2}

My question

Why, in programming languages in general, must function declarations be followed by a parameter set, external to the sub-routine scope?


texts: Transition and configuration of Turing machine

texts: In my lecture I have examples about 0 -> R (which means if it's 0, move Right) or 0 -> x, R (replace 0 with x and move Right) but I don't quite understand about the 0, 0 -> R expression. What is the configuration of Turing machine btw


texts: Algorithm for Minimum Subset Needed to Satisfy all Constraints

texts:
I was wondering what is the most efficient algorithm to solve something like the following:

You have $P$ people.

You have $T$ tasks, each of which is a set of sets that represent all of the possible sets of people that could be used to complete the task.

What is the minimum set of people required to complete all of the tasks?

For example:

You have $8$ people (call them $1, 2, ...$) and $2$ tasks.

$$T_1 = \{\{1,2\},\{4,5,6\}\}$$
$$T_2 = \{\{7,8\},\{4,5,6\}\}$$

Then the desired result is $\{4,5,6\}$.

I have been trying to think of a few solutions to this, but I'm not convinced any of them are the most efficient way of going about it.

The test case presented above shows that a greedy solution in which the smallest subset in each task is selected does not work as it would result in the set $\{1,2,7,8\}$.

Another possibility is to do a breadth-first search in which you maintain all possible valid subsets while traversing through all of the tasks. But the time complexity of this type of solution would be rather large as you cannot efficiently prune huge valid subsets (such as one containing all $P$ people).


texts:
Suppose I have the array:

[2, 3, 4, 5, 6, 7, 8, 9]

Now based on few parameters:

current_item - currently selected item.
select_size - selection size, always odd.

I want to get a sublist of the list that follows the conditions:

current_item should be in middle of sublist if that is possible.
In case when there is not enough elements on left/right of the list, use the ones from right/left.

Examples:

list: [2, 3, 4, 5, 6, 7, 8, 9]
current_item: 5
select_size: 3

result: [4, 5, 6]

list: [2, 3, 4, 5, 6, 7, 8, 9]
current_item: 2
select_size: 5

result: [2, 3, 4, 5, 6]

list: [2, 3, 4, 5, 6, 7, 8, 9]
current_item: 8
select_size: 5

result: [5, 6, 7, 8, 9]


texts: Constrain certain variables in CNF to unique satisfying assignments

texts:
[Reposted because the original question was deleted by the poster.]

I'm looking for a way to add additional clauses (and maybe additional variables) to an already existing SAT instance so that solutions with non-unique assignments for certain variables are invalidated.

Currently I enumerate all the original solutions, and filter out the bad solutions having duplicate partial assignments on specific variables. But this becomes impractical when there are many solutions to the original instance, compared to a very small number of good solutions.

If the SAT solver had information within the CNF that duplicate partial assignments on certain variables invalidate any solution that contains those partial assignments, it would speed up the search significantly.

Here's an example with 16 variables: 90 original solutions, 42 filtered solutions. https://gist.github.com/re-curse/7b1c970768400ef5d0fe

This example instance generates 90 solutions, but 48 solutions are bad because they duplicate assignments for variables 1-8 or variables 8-16. I need to add clauses to the CNF to filter out those bad 48 solutions while the solver searches instead of retroactively filtering after enumerating all original solutions.

An example of two bad solutions for this instance are (00110110 00110110) and (00110110 00111001) because variables 1-8 have an assignment [ie. 00110110] that shows up more than once in the 90 original solutions.


texts: All the references about Pure Type Systems I know consider only systems that allow to recover natural deduction systems with additive rules. Is there any variant that allows it to recover natural deduction systems with multiplicative rules? Otherwise, is it just by tradition or by inclination that such a Pure Type System is never considered, or is there any good and deep reason why it is not considered?


texts: Vectorized Algorithm for finding the Shortest Path in a Graph

texts:
I know that you can calculate the shortest path in a vectorized fashion using Floyd-Warshall, e.g. like proposed by Han and Kang, however I want the matrix, they call "via", the actual route taken through the graph.

Is it possible to retrieve this "via" matrix from a similar vectorized algorithm?

Actually I do not need all-pairs shortest path, but have two nodes, that I just wish to calculate the distance between, however I want to do it vectorized. I cannot seem to find algorithms, that allow me to get the actual path, and not just the distance, when doing it vectorized.

Is it at all possible?


texts: Maximal number of rounds we can do distributing 64 diners on 8 groups in different ways if they can't meet each other more than once?

texts:
N=64 hungry diners come to a buffet.
We sit them at 8 different (s=8 people at each table) tables so that they get to know each other while they eat.

After a while we distribute them over the tables so that no one will ever match another person with whom they have eaten before.
We keep on redistributing them with different while they eat.

What is the maximal number of rounds each person can do?

Intuitively I would say the solution is rounds=(N-1)/(s-1)=9 but I don't know if it applies always nor if take into account all restrictions.

The same problem can be thought as a group of poker players playing against each other.
If the problem were smaller, 16 people in groups of 4 the solution would be 5 rounds:

a1 a2 a3 a4 - b1 b2 b3 b4 - c1 c2 c3 c4 - d1 d2 d3 d4
a1 b1 c1 d1 - a2 b2 c2 d2 - a3 b3 c3 d3 - a4 b4 c4 d4
a1 b2 c3 d4 - b1 a2 d3 c4 - c1 d2 a3 b4 - d1 c2 b3 a4
d1 b2 a3 c4 - b1 d2 c3 a4 - c1 a2 b3 d4 - a1 c2 d3 b4
a1 d2 b3 c4 - b1 c2 a3 d4 - c1 b2 d3 a4 - d1 a2 c3 b4

But I don't know how to do it for a larger problem apart from bruteforce, at least for the simpler case N=s^2.

Here
Game tournament program, NP complete?
a solution is given just for the case of subroups of 4.

How would you address this problem computationally?
How would you do it theoretically in a simple way?


texts:
I am looking to generate a heat map from some data. I have a value and a location (longitude and latitude). I understand generating a colour from the value, however I'm not sure how I would go about generating the matrix to use for this.

I figure it's best to place the location points into buckets essentially (so that I have the same number of buckets as pixels in my map) but I'm not sure how to calculate the values for the buckets where I don't have any readings.

Has anyone got any experience with this?

Thanks!


texts: Sieve of Eratosthenes vs. Sieve of Sundaram

texts:
Relevant Information:
Sieve of Eratosthenes
Sieve of Sundaram

Suppose I want to generate all primes in [2,n], and I have both of these algorithms at my disposal to get the job done. Which is preferable under what conditions?

I read that Sundaram runs in O(n log n) time, whereas Eratosthenes runs in O(n log log n) time, so it seems that Eratosthenes is preferable. However, that is just a very superficial evaluation. Are there other factors (aside from ease of implementation) to be considered? Which is the 'better' algorithm?


texts: Set Difference of Two RE Languages - An Intuitive Idea of Why It's Not Closed

texts:
I'm new to studying formal languages, so apologies if I get a lot of basic stuff wrong, but I'm trying to get an intuitive understanding of why the difference between two Recursively Enumerable languages (A and B, say) is not itself RE? I.e. why for A-B = Z, Z is not RE?

The basic set notation and maths I understand, but I've added a more textual description as I'm looking for an intuitive answer: let C = complement of B.

Some of the words C contains in its set would cause a TM for B to reject, others would cause it to never halt. So C is not RE.

Now, A-B = A n C, by basic set operations. The theory I've read now says that the intersection of an RE (A) and a non-RE (C) cannot be RE, which is why the original A-B = a non-RE. I accept this logic, but am struggling to understand intuitively how this is true, in terms of picturing a Turing Machine that halts or loops, given the input of words from A n C.

My First Attempt at an Intuitive Explanation:

My guess is that I've missunderstood something fundamental about TMs, and what their acceptance/rejection/looping on words of a language really means, but here we go:

Imagine a TM for the RE lang A. Every word in A will cause TM to accept. Now, isn't A-B just a subset of the words from the language A? Therefore, wouldn't all the words in A-B cause our TM to also accept? By this logic then, wouldn't the difference between two RE's, A-B, be an RE language, too?

My Final Thought:

I tried to picture this in different ways, with say having the condition be that you test your newly outputted language (A-B in this case), on a TM that accepts on each of the initial languages (A, B), and if the new language accepts on all those TMs, it must be RE? But that didn't hold for things like A u B.

So, I'm stuck as for an intuitive understanding as to why A - B is not RE, when A - B is just a subset of words of A, and A will accept on its TM?
Further, what's the rule for how your new language (be it A-B, A u B, A* n B, etc) should accept in relation to TMs that accept on the initial languages?

Thanks very much for your help.


texts:
Let's say we have a card game, like poker. Inputs are board cards and an array of cards strength(that is calculated based on the board cards and game rules).
For example for 3 ranks(A, K, Q) /2 suits(h,s) simplified poker(Leduc) with Qs on board as input we will have a strength array [2, 2, 1, 1, -1, 3]  indexes are [As, Ah, Ks, Kh, Qs, Qh]. The highest strength has Qh because pair wins, then aces and kings. -1 means that Qs is impossible because it is on board already.
We need to sample vectors of player ranges - probabilities that player holds each possible hand. We are using this vectors to train some machine learning algorithm to play with this cards.
On the average for the example above we should sample Qh with the same probability as As + Ah and Ks + Kh. For this example, it is ideally to get [1/6, 1/6, 1/6, 1/6, 0, 1/8] as a result.
So we need to split input array onto the strength "clusters" and split probability between them and then divide each cluster probability by the number of elements in that cluster.  But how to define such clusters?  What algorithm can you suggest for this task?

Update:
Here the procedure that is used by Alberta University for the "generating pseudo-random ranges that attempt to cover the space of possible ranges"
We used a recursive procedure R(S, p), that assigns probabilities to the hands in the set S that sum to probability p, according to the following procedure.

If |S| = 1, then Pr(s) = p.
Otherwise,
(a) Choose p1 uniformly at
random from the interval (0, p), and let p2 = p − p1.
(b) Let S1 ⊂ S and S2 = S \ S1 such that |S1| = |S|/2 and all of the
hands in S1 have a hand strength no greater than hands in S2. Hand
strength is the probability of a hand beating a uniformly selected
random hand from the current public state.
(c) Use R(S1, p1) and R(S2, p2) to assign probabilities to hands in S
= S1 ∪ S2.

Also, I have looked at their implementation one note is that if we have an odd number of cards middle card goes to randomly to the left or right subsets.
But the real results of this algorithm looks strange: For the example above average cars sampling probability: [0.185,0.189,0.185,0.220,0, 0.219]
For the empty board: [0.19,0.12,0.19,0.19,0.12, 0.19] = [3/8, 1/8, 3/8, 3/8, 1/8, 3/8]. Not uniform because of an odd number of cards(6/2 = 3) on the second iteration. The results look not very good and accurate. Is this a best that we can achieve?


texts: Are neural networks inherently imperfect because they mimic an imperfect machine (human)?

texts:
Neural networks are the base for all(most?) of the machine learning / deep learning algorithms/programs.

Humans don't have fixed algorithms to decide or do something. Initially, we don't know how a snake is supposed to look. We learn that from experience. But our learning is never perfect. Once in a while, we mistake a black wire lying on the floor for a snake. Or we mistake the snake for a wire.

Given that neural networks are using the same technique as humans, are they inherently imperfect? Surely, we can make the self-driving network much better than best human, but that is because it got much more experience(24x7) than the human. But can we guarantee it's perfectness?(mathematically, or at least by testing, enough to make people trust in the programs)

I have this question because of the moral implications ML programs bring. I guess this will cause a lot of problem in adopting these technologies, especially when human life is at stake(eg. surgeon, self-driving cars, self-flying jets) as humans would rather rely on an imperfect human than a lesser imperfect AI.


texts:
I was searching through Google and I couldn't find anything.

Can a Post machine have more than one accepting state?


texts: Ordering elements so that some elements don't come between others

texts:
Given an integer $n$ and set of triplets of distinct integers
$$S \subseteq \{(i, j, k) \mid 1\le i,j,k \le n, i \neq j, j \neq k, i \neq k\},$$
find an algorithm which either finds a permutation $\pi$ of the set $\{1, 2, \dots, n\}$ such that
$$(i,j,k) \in S \implies (\pi(j)<\pi(i)<\pi(k)) ~\lor~ (\pi(i)<\pi(k)<\pi(j))$$
or correctly determines that no such permutation exists.  Less formally, we want to reorder the numbers 1 through $n$; each triple $(i,j,k)$ in $S$ indicates that $i$ must appear before $k$ in the new order, but $j$ must not appear between $i$ and $k$.

Example 1

Suppose $n=5$ and $S = \{(1,2,3), (2,3,4)\}$.  Then

$\pi = (5, 4, 3, 2, 1)$ is not a valid permutation, because $(1, 2, 3)\in S$, but $\pi(1) > \pi(3)$.
$\pi = (1, 2, 4, 5, 3)$ is not a valid permutation, because $(1, 2, 3) \in S$ but $\pi(1) < \pi(3) < \pi(5)$.
$(2, 4, 1, 3, 5)$ is a valid permutation.

Example 2

If $n=5$ and $S = \{(1, 2, 3), (2, 1, 3)\}$, there is no valid permutation.  Similarly, there is no valid permutation if $n=5$ and $S = \{(1,2,3), (3,4,5), (2,5,3), (2,1,4)\}$  (I think; may have made a mistake here).

Bonus: What properties of $S$ determine whether a feasible solution exists?


texts: Are vector clocks useful in centralized systems?

texts:
Vectors clocks seem to be a common way to synchronize the partial ordering of events in a distributed, peer-to-peer, system across all clients.

Is there any benefit to using them in a centralized system, where one node in the system has the power to order all events anyway, to order events? If one computer can decide the order anyway, there would be no need for vector clocks, right?


texts: How to solve this Planning Domain Definition Language (PDDL) question?

texts:
These are 5 action descriptions with conditional effects:

Action(A, Precond:{X}, Effect:{when P : ~X), Z})
Action(B, Precond:{Y}, Effect:{when Z : ~P), ~Y,~Z,X})
Action(C, Precond:{~Z}, Effect:{when P : ~X), Y})
Action(D, Precond:{~X}, Effect:{when Q : X)})
Action(E, Precond:{Z}, Effect:{when Q : ~Z)})

What state would result from executing the action sequence [E,D,A,B,C] in the state {P,Q,Y,Z}?
I know the answer but I really don't know how to achieve it. Anyone please shed some light? (Please include workings)


texts:
I am confused how to check if an algorithm I made is asymptotically optimal.

At the very least, the running time is constant at O(4). This is because you will need to check at least 4 names.

At the very most, the running time is linear at O(n).
This is from n + n + n/2 + n/2 + n/4 + n/4 + .... = 2n * (1 + 1/2 +...) < 2n. As we ignore constants its just O(n).

I checked on Wiki and it said that the algorithm should perform at worst a constant factor of the best algorithm. But if you invented an algorithm then how do I figure this out?


texts:
In the Dubins TSP (DTSP for short), one needs to visit a set of given points in the plane, and return to the starting point, minimizing the distance of such a trajectory. The difference with the Euclidean TSP (ETSP for short) however is that the visiting entity is curvature constrained by some $r$, meaning the vehicle can, at any moment in time, either go straight, or move on the edge of some circle of radius $r'\geq r$.

Consider the following theorem, by Le Ny et al. (Theorem 2 in http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.84.982&rep=rep1&type=pdf) which we will call Theorem 1 in this post :

  A trajectory based on an ETSP optimal visit order, is not necessarily an optimal trajectory for the DTSP.

(I changed the wording of their theorem to suit this post)

Suppose the next theorem, Theorem 2 :

  There exists instances for which the optimal DTSP visit order creates a crossing ETSP trajectory.

My question is : Does Theorem 2 imply Theorem 1 ?
The idea is as follows. Since some instances have the optimal DTSP visit order creating a crossing ETSP trajectory $T$, this ETSP trajectory $T$ is not optimal (due to the triangle inequality). This in turn implies that some optimal ETSP trajectory $T*$ on these instances (or their corresponding optimal ETSP visit order) cannot be adapted and optimized to obtain the optimal DTSP trajectory. If it could, then $T = T*$, which is a contradiction, since $T$ admits a crossing trajectory.


texts: Understanding the closed form derivation on the function f(n/3) + n^2 +3

texts:
I have the function:

$$ f(n) =
\begin {cases}
4 & , n = 1 \\
f(\frac{n}{3}) + n^2 -3 & , n \ge2
\end {cases}
$$

The given solutions shows the unwinding of the function as follows:

Assuming $ n \ge 2$

$$f(n) = f\bigg(\frac{n}{3}\bigg) + n^2 - 3$$
$$ = \bigg[f\bigg(\frac{n}{3}\bigg) + \bigg(\frac{n}{3}\bigg)^2 -3\bigg] + n^2 -3$$
$$ = f\bigg(\frac{n}{3^2}\bigg) + n^2 \bigg(\frac{1}{9} + 1\bigg) -6$$
$$ = \bigg[f\bigg(\frac{n}{3^3}\bigg) + \bigg(\frac{n}{3}\bigg)^3 -3\bigg] + n^2\bigg(\frac{1}{9} + 1\bigg) -6$$
$$ = f\bigg(\frac{n}{3^3}\bigg) + n^2 \bigg(\frac{1}{81} + \frac{1}{9} + 1\bigg) -6$$

Where I get lost are the last two lines of the unwinding because I do not understand where the $(\frac{n}{3})^3$ becomes to $n^2(\frac{1}{81} + \frac{1}{9} + 1)$.

Question is taken from UofT CSC236 Tutorial 6


texts: Reducible from vertex cover for only some inputs

texts:
Suppose I have an NP problem, $\text{PROBLEM}(n)$, such that for certain values of $n$ I can get a reduction from vertex cover with $n$ vertices, and for others such a reduction is not possible (if $\mathbf{P}\neq\mathbf{NP}$).

More precisely, there exists an infinite set $M\subseteq\mathbb{N}$ such that for $m\in M$ we can obtain a reduction from vertex cover with $m$ vertices to $\text{PROBLEM}(m)$, while for others PROBLEM can be solved in "polynomial" time. (More precisely, there exists a polynomial $p$ such that for all $n \in \mathbb{N} \setminus M$, $\text{PROBLEM}(n)$ is solvable in under $p(n)$ steps.) $M$ is infinite, but can be arbitrarily sparse.

I'm at a loss as to what we can say about the complexity of the problem. If $\mathbf{P}\neq \mathbf{NP}$, there is no polynomial $q$ dominating the running time of PROBLEM because we can always pick a sufficiently large $m\in M$ that will exceed $q(m)$; however, neither do I see any way to show NP-completeness. The naive approach of taking an instance of vertex cover with $n$ vertices and padding it up to $m\in M$ does not work because we might not be able to reach $m$ in a polynomial number of steps due to the sparsity of $M$. Is this an example of a problem that's neither in $\mathbf{P}$ nor NP-hard?


texts: Looking for an "intuitive" regular expression for $\{ w \in \Sigma^{\ast} \mid 2|w|_1 + |w|_0 \equiv 0 \pmod{3} \}$

texts:
Let $L \subseteq \Sigma^{\ast}$ with $\Sigma = \{0,1\}$ be the language such that two times the number of $1$'s in a word in $L$ plus the number of $0$'s is divisible by $3$, i.e. if we denote by $|w|_1$ the number the symbol $1$ occurs in $w$ and by $|w|_0$ the number the symbols $0$ occurs, then
$$
 L = \{ w \in \Sigma^{\ast} \mid 2|w|_1 + |w|_0 \equiv 0 \pmod{3} \}.
$$
I know this language to be regular, as it is quite easy to give an automaton for it. I also got a (quite complicated) regular expression for it using an algorithm going from the automaton. But is there any regular expression that is easy in the sense that it gives some insight into why it is a regular expression for the language?

Not that for example for the language $\{ w \mid |w|_0 \equiv 0 \pmod{3} \}$ it is quite easy to give a regular expression, it would be $1^{\ast}(01^{\ast}01^{\ast}01^{\ast})^{\ast}$, or for $\{ w \mid |w| \equiv 0 \pmod{3} \}$ as it would be $(\Sigma\Sigma\Sigma)^{\ast}$. But the above language somehow combines these conditions.


texts: Expected value of next CPU burst using exponential averaging

texts:
The burst time is needed for Shortest Job First (SJF) and Shortest Run Time First (SRTF) scheduling. To get the approximate burst time, we use the equation
$$\tau_{n + 1} = t_n + (1 - \alpha)\tau_n$$

I want to ask whether $\tau_{n + 1}$ is the predicted burst time of the $n + 1$ th process or it is the predicted burst time of some process say p which is demanding the CPU for the $n + 1$ th time.


texts:
I am trying to execute the following algorithm shown in the image from my course slide.  I am trying to get the table shown in the image:

1st Iteration
L2: 1:CS=A, SL = A, NSL = A
L3: while NSL!=[]: true
L4:
L6:no children: false
L17:NSL =BCDA
L18:CS:=B
L19:SL=BA
L20, L21
2nd Iteration
L3:While NSL (true)
L4:
L6:no children: false
L17: NSL=EFBCDA
L18: CS:=E
L19:SL:= EBA
L20, L21
3rd Iteration
L3:while NSL (true)
L4:
L6:no children: false
L17:NSL= HIEFBCDA
L18: CS:= H
L19:SL:=HEBA
L20, L21
At this point its fine but when there are no more children of current node, it has to backtrack, so it should execute the while loop, at that point I am losing the track:
L3:while NSL(true)
L4:
L6:no children: true
L7:begin
L8:while SL is not empty (true) and CS:=H
L9: DE=H
L10:SL=EBA
L11:NSL=IEFBCDA
L12:CS=I
L14:SL= IEBA
Now it should keep traversing the while loop but I am having problem with this. Somebody please correct this algorithm or guide me a better backtracking algorithm which has the contents of table.
Zulfi.


texts:
Problem statement:

  Given an undirected graph $G = (V, E)$ with edge $e_i$ having two associated positive values $c_1, c_2$. Find a spanning tree $ST$ such that (ratio of the spanning tree): $$\frac{\sum{c_1}}{\sum{c_2}}$$
  is minimum.

Motivation: competitive programming problem http://acm.timus.ru/problem.aspx?space=1&num=1447

This problem is solved as follows:

Choose any ratio $x$.
Assign weight $w(e) = c_1 - x \cdot c_2$ to each edge $e$.
Find MST with any known algorithm (with respect to costs $w$).
Assign ratio of this spanning tree to $x$. That is, $x \leftarrow ratio(MST)$.
Output ratio if it hasn't changed compared to previous iteration; go to step 2 otherwise.

Could you please help me prove this solution by providing some hints? I don't understand why the ratio converges and what is the rate of convergence. Empirically, I know that convergence rate is logarithmic or faster as one can search ratio with binary search.

About the binary search solution. One should choose the first half of search range if sum of $w(e)$ in $ST$ is negative. The answer is found if this sum is zero. I also don't understand why this function is monotone.

I searched for some articles online but there aren't any free available.


texts:
I am given an exercise unfortunately I didn't succeed by myself.

  There is a set of rectangles $R_{1}..R_{n}$ and a rectangle $R_{0}$. Using plane sweeping algorithm determine if $R_{0}$ is completely covered by the set of $R_{1}..R_{n}$.

For more details about the principle of sweep line algorithms see here.

Let's start from the beginning. Initially we know sweep line algorithm as the algorithm for finding line segment intersectionswhich requires two data structures:

a set $Q$ of event points (it stores endpoints of segments and intersections points)
a status $T$ (dynamic structure for the set of segments the sweep line intersecting)

The General Idea: assume that sweep line $l$ is a vertical line that starts approaching the set of rectangles from the left. Sort all $x$ coordinates of rectangles and store them in $Q$ in increasing order - should take $O(n\log n)$. Start from the first event point, for every point determine the set of rectangles that intersect at given $x$ coordinate, identify continuous segments of intersection rectangles and check if they cover $R_{0}$ completely at current $x$ coordinate. With $T$ as a binary tree it's gonna take $O(\log n)$. If any part of $R_{0}$ remains uncovered that $R_{0}$ is not completely covered.

Details: The idea of segment intersection algorithm was that only adjacent segments intersect. Based on this fact we built status $T$ and maintained it throughout the algorithm. I tried to find a similar idea in this case and so far with no success, the only thing I can say is two rectangles intersect if their corresponding $x$ and $y$ coordinates overlap.

The problem is how to build and maintain $T$, and what the complexity of building and maintain $T$ is. I assume that R trees can be very useful in this case, but as I found it's very difficult to determine the minimum bounding rectangle using R trees.

Do you have any idea about how to solve this problem, and particularly how to build $T$?


texts: Minimize number of circles to cover set of points

texts:
I'd like to minimize the number of circles $C$ to cover a set of points $P$ in 2D.

There is no fixed radius however each circle must contain exactly $N$ points. The circles may overlap. A point may be covered by multiple circles. All coordinates are floats.

Problem size: $|P| \leq 1000$, $5 < N < 15$

My current approach: I limited the possible center points of the circles to the set of points and just take the center point which covers the most uncovered points as long as there are uncovered points.

Good example with $N=3, |P|=9, |C|=3$ (optimal because $|C| = \lceil|P|/N\rceil$):

Non-optimal but valid example with $N=3, |P|=9, |C|=4$ (using my current approach, numbers indicates step):

I'm aware the problem might be a bit vague. Any hint on how to approach the problem is appreciated. I'm not necessarily interested in an optimal solution. An approximate/heuristic algorithm is totally fine.


texts: How do you obtain transition relation of a PDA?

texts:
I know how to figure out the start state, accepting state, input alphabet, and all that stuff. But how do you develop the transition relation of a PDA? For an FSM, (q0,a),q1) means if you start at q0 and get an a, you transition to q1. But what does (S,a,e),(S,a) mean? (S is start state and e is epsilon)

Here's a picture if that helps. I want to understand the circled part. I will be extremely appreciative of any help.


texts: How to do supervised learning without knowing the target

texts:
I'm working on an optimization algorithm that I think could be considered machine learning, but I'm not sure.  Basically I have a model that I want to optimize by adjusting its parameters.  I don't have any target data to compare the output of my model to, so I don't know the loss factor.  However, I'm able to generate information on whether increasing or decreasing a parameter will improve my model.

This information consists of a sum of positive and negative numbers that I'll call votes, and they are very noisy.  I know I should increase the parameter if the average vote is positive and decrease it otherwise.  I can generate as many votes as I like if I invest the computational resources, and I need to generate a sufficient number to over come the noise.  I only know I've optimized the parameters if the average votes are zero.

I'm having a hard time optimizing my algorithm.  Basically it's hard to decide how many votes I should take before shifting the parameters, and then how much I should shift them.  I believe the optimal amounts depend very much on the circumstances.  I'm wondering if my algorithm falls under a class of optimization algorithms that have a literature I could research.  Or if anyone knows any literature that my be useful to what I'm working on.


texts: NFA recognizing strings in $\{0,1\}^*$ that have two zeros separated $4i$ characters, for some $i\geq1$

texts:
I am trying to design a nondeterministic finite automaton that recognizes the language of strings in $ \{0,1\}^{\ast}$ that have two zeros separated by a string of length 4i, for some $i \geq 1$.
Let $A = \{w \mid w \in \{0,1\}^{\ast}$ have two zeros separated by a string of length $4i$, for $i \geq 1\}$. Then we design a NFA that recognizes A
Let  $M = (Q, \Sigma, \delta, q_{0}, F)$ , where
$Q = \{q_{0}, q_{1}, q_{2}, q_{3}, q_{4}, q_{5}, q_{6}\}$,
$\Sigma = \{0, 1\}$
for any $q \in Q$ and $a \in \Sigma$
$\delta(q, a) =
   \begin{cases}
     \{q_{0}\} & q = q_{0},\ a = 1\\
     \{q_{0}, q_{1}\} & q = q_{0},\ a = 0\\
     \{q_{2}\} & q = q_{1},\ a = 0\ or\ a = 1\\
     \{q_{3}\} & q = q_{2},\ a = 0\ or\ a = 1\\
     \{q_{4}\} & q = q_{3},\ a = 0\ or\ a = 1\\
     \{q_{5}\} & q = q_{4},\ a = 0\ or\ a = 1\\
     \{q_{2}\} & q = q_{5},\ a = 1\\
     \{q_{2}, q_{6}\} & q = q_{5},\ a = 0\\
     \{q_{6}\} & q = q_{6},\ a = 0\ or\ a = 1\\
   \end{cases}$
$q_{0}$ is the start state, and
$F = \{q_{6}\}$
The state diagram is as follows:

I am not quite sure it is totally correct. Does $q_{0}$ should be a final state?


texts: In a 'self-stabilized' distributed system, where a fault occurs?

texts:
Consider a self-stabilized distributed system based on shared memory and the processor $p_{i}$ be connected to the processor $p_{j}$. Suppose we are going to solve a problem like finding a maximal independent set or minimal dominating set and we need to break symmetry. For breaking symmetry, we use id of processors.

My Question: When $p_{i}$ reads the id of $p_{j}$, a failure can occurs in this operation?


texts: Locally finite graph without an optimal path

texts:
If I have a locally finite graph (every node has finite number of neighbors) with positive edge weights, is it possible for there to be a path between some start node and goal node but no shortest path between them?

I think that it can only happen if the goal node is somewhere in the infinity, but then we wouldn't be saying that the goal node actually exists, right?

Could anyone help me on this?


texts: VC dimensions: Let ${x_1, \ldots, x_N}$ be $N$ labelled points on $\mathbb{R}$, then there exists a sinusoid that separates these points

texts:
(Proposition, pg 26): Let ${x_1, \ldots, x_N}$ be $N$ points on $\mathbb{R}$, $N \in \mathbb{Z}$, labelled either $+1$ or $-1$ , then there exists a function from the set $\{t \mapsto \sin(\omega t)| \omega \in \mathbb{R}\}$ that separates these points into two sets, one with all labels ${+1}$, and one with all labels ${-1}$

Does anyone see how to prove this proposition?
Right now I am using induction, however, I cannot see how it can extend to the $N$ point case.
It is also difficult to picture how this works for the $N$ point case.


texts: is the intersection of a context free language and a regular language a two way street?

texts:
I wasn't sure how to word it correctly, hence the 'two way street' in the title. My question is:
The intersection of a context-free language and a regular language always results in a context free language, but does this also mean that if I have a language L1 and a regular language L2 that when L1 intersected with L2 is context free that L1 is also context free?


texts:
Can a running interrupt handler be pre-empted by another interrupt handler?
If this is possible, in which scenarios is this safe, and in which scenarios is it not?
If this is not possible, why?


texts: Preventing multiple threads from racing on a queue while not wastefully polling its size

texts:
I have a queue with 50 ints in it, and I have 3 threads that want to race at the queue to print the values in it, with a 2 second delay before trying to get the next int.

The queue is not thread safe, and the semaphore protecting is is decoupled from the number of items inside the queue(the number of items in the queue are checked by calling .size() for the queue, but the lock is obtained by blocking on the semaphore until its owner unlocks it.

I am trying to understand how to prevent the three threads from accessing the queue at the same time, but at the same time not trying to access the queue if the queue is empty.

If the queue is empty, but unlocked, i will have a bunch of threads locking the queue, checking its size, and unlocking it, until something is added to the queue. This seems silly and wasteful; Is there a solution to this?


texts: If A is reducible to B and B is reducible to A, and A is NPC, is B also NPC?

texts: I was thinking about the max-clique problem and the k-independent set problem. You can show that k-independent set is reducible to max-clique easily and you can show that max-clique is reducible to k-independent set (with a simple for loop). And k-independent set is NPC, so wouldn't that mean max-clique is also NPC, but it's not because we can't create a verifier, so I'm terribly confused. What wrong assumption am I making?


texts: The running time of algorithm is at most $O(n^2)$

texts:
The problem is that if an algorithm is $O(n^2)$ then it is also $O(n^3)$ and $O(n^4), O(n^n), \ldots$ and the phrase 'at most' does not make sense in this situation.
For this reason, I am not sure whether this statement is correct or not.


texts: Can I use infinite numbers in a reduction?

texts:
I have to reduce $L_\text{empty}$ to $L_\text{inf}$

where

$\qquad L_\text{empty} = \{e \mid |L(P_e)| = 0 \}$ and
$\qquad L_\text{inf}= \{e \mid |L(P_e)| = \infty \}$.

where $P_e$ is the program with Gödel number $e$, and $L(P_e)$ the language it accepts.

So can I define a program $P$ like this

input n
Run Pe on 1...n for n steps
if Pe accepts any number then
  enter an infinite loop and start accepting infinite number
if Pe does not accept any number then
  accept 1

Now if I can define program P like above then asking the question whether the index of $P$ is in $L_\text{inf}$ will tell me whether the language accepted by $P_e$ is empty or not.


texts: I'm quite confused about the convergence of pix2pix cGAN, how can we tell whether my model is well trained?

texts: Usually we will see decreasing loss for regular CNN model, but for GAN, it seems to be not that simple. How can we tell whether my model is well trained?


texts: Placing a tripod in a plane such that it partition a given set of points (with pic)

texts:
I would appreciate if anyone could help me with the following problem:

Given a set of 3n points in the plane with n > 0, is it possible to find a placement of a tripod such that each region contains at most n of the points?

If it is possible, then can we prove that a valid placement always exists?

If it is not possible, then can anyone provide me a set of 3n points (with n > 0) and a tripod T and prove that there is no placement of T which has the required properties.

Here, I am considering the points in general position, i.e. no three points are collinear. Also by my understanding, tripod is a point (say p) with three rays emanating from p such that the angle between two consecutive rays is 2π/3 (120 degree). Also the tripod can partition the plane into three regions(i.e. cones).


texts: Does immutability in functional programming really exist?

texts:
Although I work as a programmer in my daily life and use all the trendy languages (Python, Java, C, etc) I still have no clear view of what functional programming is. From what I've read, one property of functionally languages is that data structures are immutable. For me this alone raises a lot of questions. But first I will write a bit of what I understand of immutability and if I'm wrong, feel free to correct me.

My understanding of immutability:

When a program starts it has fixed data structures with fixed data
One can't add new data to these structures
There are no variables in the code
You can merely "copy" from the already data or currently calculated data
Because of all above, immutability adds huge space complexity to a program

My questions:

If data structures are supposed to remain as they are (immutable), how the hell does someone add a new item in a list?
What is the point in having a program that can't get new data? Say you have a sensor attached to your computer that wants to feed data to the program. Would that mean that we can't store the incoming data anywhere?
How is functional programming good for machine learning in that case? Since machine learning builds from the assumption of updating the program's "perception" of things - thus storing new data.


texts: lambda expressions, parenthesis, and order of application

texts:
I am building a lambda applicator in Java, and I have uncovered a bit of misunderstanding.  Either my question at the bottom is what I am asking, or something in the build-up below is wrong.  Either way, I'd appreciate any insight.

So, NOT can be defined as

λb.b (λxy.y) (λuv.u)

If we allow

A1 = λb.b
B1 = (λxy.y)
C1 = (λuv.u)

Now NOT is (A1 B1 C1)

By order of operations, B1 will be applied before C1
So let Not1 = (A1 B1)

NOT can now be rewritten as (Not1 B1) or ((A1 B1) C1).

When we apply the expression

TRUE = (λdw.d)

to NOT, we have

((A1 B1) C1) TRUE

Which, because A1 is the identity function, is supposed to get us

((TRUE B1) C1)

... but why wouldn't we apply B1 to A1 first?


texts: Find the maximum number of contiguous occurrences of smaller string s in a larger string l

texts:
Say we have two strings s and l, and they only have characters 'a' through 'z' (lowercase English alphabet characters). The task is to find the maximum number of consecutive occurrences of s in l.
Ex.
s = "ab"
l = "defgababajklabe"
The answer here would be 2, because there is "abab" which would be 2 consecutive occurrences of string s in l.
My initial thought was to go through each character in l, and try to match the substring starting at that position with s, if it matched we would increment our count and keep track of some global maximum. We would also set the value of our next starting point to one position after the end of this matched portion.
If at any point there is a mismatch, then we wouldn't have to re-check all the previous characters, we would just go to one position after the start point, that would be our new start point.
For example, when processing the given example, we would eventually set start to index 4 (0 based index), and match ab, then set it to index 6 and match ab again, then set index to 8. At that point there would be a mismatch, and we would just start matching again at index 9. There is no need to start over from index 5.
This is my guess, and it appears to work, but I can't seem to prove why this works. Can someone help me understand why this works? Or doesn't work?


texts: What is the complexity of Array[n] and Object.value

texts:
I faced a great doubt about the Complexity of two ways of calling a information.

First I have an Array, if I call an array in a program like this:

print array[0]

This process will be O(1) as I understand.

But what is the complexity of something like this:

class Obj:
    value = 1
print Obj.value

Is this complexity is the same of callin and array by Index? If we ignore the process to create the object.


texts:
I want to implement efficiently "streaming Knapsack" problem in java.

The problem is I have a stream input of integer data coming continuously for example -1, 2, 9, 5, 5, 11, 1 -3,...

The question is to find the first "k" elements in which their sum is "n>0". for example k=3 and n=12,
then the solution is: ...,2,...,5, 5.

I found an answer in http://programmingpraxis.com/2012/05/15/streaming-knapsack/2/
as: (It is mainly for positive Integer Values)

But looking for simpler one! Any Ideas?


texts: Understanding lemma found in proof of quotient construction for DFAs

texts:
Lemma 13.6    $p \in F \Longleftrightarrow [p] \in F'$
Proof. The direction $\Rightarrow$ is immediate from the definition of $F'$. For the direction $\Leftarrow$, we need to show that if $p \approx q$ and $p \in F$, then $q \in F$. In other words, every $\approx$-equivalence class is either a subset of $F$ or disjoint from $F$. This follows immediately by taking $x = \epsilon$ in the definition of $p \approx q$. $\quad\square$

The excerpt above found in Dexter C. Kozen's Automata and Computability.  This lemma is found in a proof of the Quotient Construction for DFA.
I do not understand how the author concludes that if one wants to show $[p] \in F' \implies p \in F$ (1), then it is equivalent to showing that $p≈q$ and $p \in F \implies q \in F$ (2). Can someone please provide as detailed as possible an explanation of why if we want to show (1) it is equivalent to show (2)? Any idea on why the author does not feel the need to justify this?


texts:
I'm searching an hash function for integer set equality that must be fast.
It must support update (adding an element already in the set must not change the hash) and union.
MinHash has these 2 properties but it is too expensive and I do not need all the feature of MinHash, in fact I don't need set similarity but only equality.
Do you know something that can satisfy my needs?
Thanks :)

P.S. I have to implement it in C for an high performance software


texts:
I'm reading Multithreading (computer architecture) - Wiki, aka hardware threading, and I'm trying to understand the second paragraph:

  (p2): Where multiprocessing systems include multiple complete processing units in one or more cores, multithreading aims to increase utilization of a single core by using thread-level parallelism, as well as instruction-level parallelism.

while the link to thread-level parallelism says:

  (Link): Thread-level parallelism (TLP) is the parallelism inherent in an application that runs multiple threads at once. This type of parallelism is found largely in applications written for commercial servers such as ...

which is not so useful... So I read task parallelism above, since I guess TLP is a subtype of it:

  Task parallelism (also known as function parallelism and control parallelism) is a form of parallelization of computer code across multiple processors in parallel computing environments. Task parallelism focuses on distributing tasks—concurrently performed by processes or threads—across different processors.

Question: If thread-level parallelism is task parallelism, and task parallelism is for parallelization across multiple processors, how increase utilization of a single core by thread-level parallelism work?

Guessing: I guess for TLP, it should mean across multiple logical processors, i.e. hardware threads in the perspective of OS, correct?

Another minor issue is that for my first link, Multithreading:

  In computer architecture, multithreading is the ability of a central processing unit (CPU) (or a single core in a multi-core processor) to execute multiple processes or threads concurrently, supported by the operating system.

And in (p2) it aim to increase utilization of a single core by using thread-level parallelism? What a contradiction.


texts: Options for approaching stable marriage problem with unequally sized sets of elements/preferences

texts:
I am looking for an algorithm/code that will provide stable matching for two unequally sized sets of elements (clubs and students) with an unequal set of preferences. There is a large pool of students looking to join a club, and a comparatively small pool of clubs for those students to join. Each student ranks only the clubs they wish to join in order of preference. In other words, each student will not be required to rank every club available. At the same time, each club has a maximum amount of students they can accept and this number differs across each club. Therefore, both pools for the algorithm are unequally sized, and each element within those pools (i.e. every individual club and student) could have a different number of preferences.

I have looked into the Gale-Shapley algorithm and envy-free matching, but I have not found any code that provides a stable match when there is so much variation in the elements/preferences. Does anyone know of any code that can accomplish this (preferably in something like Python or Java)?


texts: Does minimumm spanning tree always include the node with highest degree?

texts:
I want to know why the distances between nodes in a minimum spanning tree seems to be rooted to the node with highest degree.
A bit of context here:
I have spatial explicit weighted network that describes the physical growth pattern of a fungal colony. Most of the nodes in this network have either degree = 1 or degree =3 (degree=2 is not possible because of biological reasons). Degree >4 are not possible except for only one (and only one) case: the center of the colony, where all edges orginally radiate.
Using the observed network, I obtained the MST (taking into account edge weights. BTW I using the mst function in igraph for R). I did this because I wanted to know how much the fungal colony differs from a MST pattern. However, I noticed that the resulting MST is essentially made up of the shortests paths between the center of the colony (that is, the only node with degree > 4) and any other node in the network. I am a biologist diving into network science, so I am now curious why is that so? why I do not get a shorthest path that does not include the node with hightest degree in the MST?


texts: Why this greedy algorithm does not return the optimal solution to this NP-hard problem?

texts:
Problem:
In the generalized assignment problem with unit-value items, there are $m$ bins of capacity $C$ each. There are $n$ items where each item $i$ has weight $w_{ij}$ with bin $j$. The objective is to assign the items to the bins (while respecting the bins capacities) such that the number of assigned items is maximum. I know that this problem is NP-hard.

Question: why the following algorithm is not optimal?

Algorithm:

For each bin $j$, assign the maximum. Here, assign the maximum means to iterate the items such that $w_{1j}\leq w_{2j}\leq\cdots\leq w_{nj}$ and add to bin $j$ the items in that order until the capacity $C$ is filled.
Take the union. This means that, if bin $j$ is assigned a set $S_j$ of items, then the result would be: $\bigcup_j S_j$.

So for example if I have this instance: $C=4$ and $m=3$ and $n=7$. The weights are given by:
$$\begin{pmatrix}
2 & 4 & 4\\
2 & 1 & 4\\
4 & 1 & 2\\
4 & 1 & 4\\
4 & 1 & 4\\
4 & 4 & 4\\
4 & 4 & 2
\end{pmatrix}.$$

So the algorithm gives the following assignment:

bin 1: items 1 & 2,
bin 2: items 2, 3, 4, & 5
bin 3: items 3 & 7

Finally, we choose the following assignment:

bin 1: items 1 & 2,
bin 2: items 3, 4, & 5
bin 3: item 7

Maybe I choose the bad example, can you show me how this algorithm fails?


texts: Optimization over convex combinations in a circle

texts:
Consider the following situation: given a triangle $ABC$ inscribed in a circle, define $f$ as the product

$$f(P) = d(P, A) \; d(P,B) \; d(P,C)$$

where $P$ is a point on the circle and $d$ are distances between points.

Now, every point $D$ in the interior of the circle can be written as a convex combination of points $D_i$ on the circle:

$$D = d_1 D_1 + d_2 D_2 + d_3 D_3$$
where each $d_i > 0$ and $d_1+d_2+d_3=1$. Then we define $F$ as

$$F(D) = d_1 f(D_1) + d_2 f(D_2) + d_3 f(D_3).$$

The problem I am interested in is: find the choice of points $\{D_1,D_2,D_3\}$ which minimizes $F$ for a given $D$.

However, since the optimization is performed over all possible choices of $\{D_1,D_2,D_3\}$, it is in general very difficult. Could this perhaps correspond to a more manageable optimization problem that can be computed?

Note that if one was to remove the restriction that points $D_i$ lie on the circle and define $f$ in the same way for every point in the interior, the minimization problem would correspond exactly to finding the convex hull (convex envelope) of the function $f$. This would provide a lower bound for the original problem, but I am not sure if the computation of this quantity is in any way easier.

I would appreciate any pointers with regards to computing the minimum.


texts: is a deterministic algorithm for breadth-first traversal possible (binary heap)

texts:
Imagine I have a binary heap, traversed in a breadth first manner like so:

                  0
       1          |           2
  3    |    4     |    5      |     6
7 | 8  |  9 | 10  |  11 | 12  |  13 | 14

To the left of root (0) is 1, to the right is 2, to the left of 1 is 3 to it's right is 4 etc.

So node 13 corresponds to the following pattern (right right, left, (or 0,0,1, perhaps)).

The question is, is there an equation, function, or algorithm that will produce the pattern to get to any node without actually producing the entire tree and traversing it?

Say I didn't create the tree in memory (it's just a virtual tree). How would I know that in order to get to 8 I need to start at root and go: left,left, right (1,1,0)?

Is this computable without creating the tree, and traversing it? If so what is the pattern for 42? is it easily calculable (is it linear) ?

I'm sorry for not knowing all the CS terms (I'm not a cs major, but I want to know if there's a deterministic algorithm to produce a path to any node, if so, whats it's computational efficiency) ?


texts: Computing the longest common substring of two strings using suffix arrays

texts:
After I learned how to build a suffix array in $O(N)$ complexity, I am interested in discovering the applications of the suffix arrays. One of these is finding the longest common substring between two strings, in $O(N)$ time. I found on the internet the following algorithm:

merge the two strings $A$ and $B$ into one string $AB$
compute the suffix array of $AB$
compute the $LCP$(longest common prefix) array
the answer is the largest value $LCP[i]$

I tried to implement it, but as many implementation details were not said(i.e. when concatenating the strings, should I put a special character between them($AcB$)?), my code failed on many test cases. Could someone elaborate more on this algorithm?

Thanks in advance.

Note: I do not guarantee the correctness of this algorithm; I found it on a blog, and I'm not sure it is working. If you think it is incorrect, please suggest another algorithm.


texts: Counting substrings with a given number of different characters in O(N)

texts:
Given a string $S$ of length $n$, and a number $k$, count the number of substrings (regardless of their length) that contain exactly $k$ different characters.

The obvious solution takes $O(n^2)$ time (fix substring start point, and move its end point while keeping track of the set of seen characters).

Is there a way to do that in $O(n)$ time? Or at least in $O(n c)$ time, where $c$ is the number  of unique characters in the string $S$?

I tried to keep track of two pointers (start and end) and move only one of them forward at each step, while updating the hash table with character counts. But counting substrings became really messy.


texts: Get the previous and next values of a string in lexicographic order

texts:
I'm working with a noSQL database and for certain reasons I can't use equality filtering in my queries

e.g

select all from database where id = 10

is NOT allowed

but inequality filtering is allowed

e.g

select all from database where id > 1

My ID's are UNIQUE strings (emails) and I need to use equality filtering so I thought to convert inequality statements to equality statements (e.g where id = 10 could be written as Where id > 9 AND < 11).

If my ids were numbers I would use code such as this to get my key:

function(id)
{

    //assuming no id can be 0 and no id can be larger than 2^53-1. This will return the row with id = 10
    var result = sendToDatabaseQuery('SELECT * FROM database where id > ' + (id-1) + ' AND ' id < ' (i+1)');

}

With numbers it would be very easy to do this, but with Strings I have found it to be more challenging. If I have an email such as mysuperfakeemail.gmail.com how could I get the previous and next lexicographic string (I am assuming they are mysuperfakeemail.gmail.col and mysuperfakeemail.gmail.con respectively)? Is there an established algorithm for this type of function already? I am writing this on a nodejs server with UTF-8 characters.


texts:
You have an Array of length n. If you pick a sub-array from the array, it must contain at least one unique element. The sub-array could be of any length but must contain consecutive/successive elements.

The question is what is the minimum number of characters you need to ensure that your array has the property mentioned and how should those elements be placed in the array? the answer needs to be in terms of n.

For Instance,

Let n be 10. Then you can place n different characters in it.

a, b, c, d, e, f, g, h, i, j

such that any sub-array would contain all unique elements. In this case the answer is n. But, of course this is not optimal as you need only one unique element in the sub-array.

In the same example of to pick 2 elements a and b and place them as

a, b, a, b, a, b, a, b, a, b

and you pick a sub-array of the first 4 elements a, b, a, b then you do not have any unique element. In this case the answer is 2 but is Incorrect.

So, what is the minimum number of unique element (and their placement in the array) you need to ensure your array has the property mentioned.


texts: Finding preferences for G-S algorithm (Algorithm Design Chapter 1 exercise 7)

texts:
I'm working on Algorithm Design (Kleinberg-Tardos) Chapter 1 exercise 7:

Some of your friends are working for CluNet, a builder of large
communication networks, and they are looking at algorithms for
switching in a particular type of input/output crossbar. Here is the
setup. There are n input wires and n output wires, each directed from
a source to a terminus. Each input wire meets each output wire in
exactly one distinct point, at a special piece of hardware called a
junction box. Points on the wire are naturally ordered in the
direction from source to terminus; for two distinct points x and y on
the same wire, we say that x is upstream from y if x is closer to the
source than y, and otherwise we say x is downstream from y. The order
in which one input wire meets the output wires is not necessarily the
same as the order in which another input wire meets the output wires.
(And similarly for the orders in which output wires meet input wires.)
Figure 1.8 gives an example of such a collection of input and output
wires. Now, here’s the switching component of this situation. Each
input wire is carrying a distinct data stream, and this data stream
must be switched onto one of the output wires. If the stream of Input
i is switched onto Output j, at junction box B, then this stream
passes through all junction boxes upstream from B on Input i, then
through B, then through all junction boxes downstream from B on Output
j. It does not matter which input data stream gets switched onto which
output wire, but each input data stream must be switched onto a
different output wire. Furthermore—and this is the tricky
constraint—no two data streams can pass through the same junction box
following the switching operation. Finally, here’s the problem. Show
that for any specified pattern in which the input wires and output
wires meet each other (each pair meeting exactly once), a valid
switching of the data streams can always be found—one in which each
input data stream is switched onto a different output, and no two of
the resulting streams pass through the same junction box.
Additionally, give an algorithm to find such a valid switching.

This is the algorithm I've came up with so far:

Input wires prefer output wires in the order the signal meets each output wire from source to terminus.
Output wires prefer the source input wires of downstream junctions to source input wires of upstream junctions.
Let M be the matchings after applying the G-S algorithm using the input wires, output wires, and associated preferences
Return the set M of input-to-output wire matchings

I'm having trouble proofing or disproving this algorithm correctly solves the problem. My goal is to show that if 2 data streams meet at the same junction then it leads to an instability in  the matchings. I started by assuming the data streams meet on some arbitrary output wire and a downstream junction exists, but I haven't made any progress past that in showing an instability. The 2 source input wires will prefer this arbitrary output wire over their terminus wire, but there is always a place on this arbirary wire to place a junction such that the arbirary output wire prefers it over the other two junctions - then no instability can exist.


texts: Maximum amount of memory that can be allocated to a process

texts:
DISCLAIMER: The following scenario was taken from an assignment I got in a OS course I'm taking, and it arose a lot of question marks in my head. However non of the questions asked by myself here reflects a question that I'm supposed to answer (alone) as part of the assignment. What I mean is: I'm not asking you to do my HW I'm just asking for help to better understand the concepts.

Given the following scenario:
A system using paging for memory management.
Physical memory size is 128MB
There are 4K frames in physical memory and each frame has 8K words.
Page table of a single process has at most 1024 entries
Virtual memory is not used.

I know from the above that a WORD in such a system must be 4 Bytes long.

Since virtual memory is not being used, I think it is possible that a process can get all the 4K frames if it requests them (assuming obviously that they're available for it when it's loaded) thus it can be allocated all of the available physical memory (128MB). However if Virtual Memory is used then the maximum amount it can get is 32MB because of the structure of the page table (1K entries, each entry has 8K words and each word = 4 Bytes). Is my conclusion correct or not? I reached it while reading Silberschatz, Galvin & Gane book (Operating System Concepts).


texts:
From Simon Peyton Jones (recent Royal Society member) we read the paper: Implementing lazy functional languages on stock hardware: the Spineless Tagless G-Machine.

Now this paper is part of how they made Haskell a lazy language when they were implementing it, and solved some problems they had at the time.

The only comparable paper seems to be: Compiling Lazy Functional Programs Based on the Spineless Tagless G-machine for the Java Virtual Machine but there doesn't appear to be an implementation available.

One tangentially related is: Compiling Haskell to Java. However in this approach they leave the implementation of the Spineless Tagless G-Machine in GHC and just read the output.

My question is: Are there any implementations of the spineless tagless G-machine other than in GHC?


texts: Minimum number of strings to cover entire space within Hamming distance

texts:
Given $(n, k)$:

What is the minimum number $x$ of (binary) strings such that all $n$-bit (binary) strings are within $k$ Hamming distance of some string?

Is there an asymptotic expansion or lower bound, at least?
A somewhat-trivial lower bound is as follows:

There's $\sum_{i=0}^{k} {n \choose i}$ strings within distance $k$ of a given string.
There's $2^{n}$ strings total.
Each string can be counted no less than once.
So we have a lower bound of: $$x \ge \frac{2^{n}}{\sum_{i=0}^{k} {n \choose i}}$$

Is there an explicit formula that maps an index $1..k$ (or $0..(k-1)$) to these strings? (I am aware that this is likely not unique.)

This is closely related to error-correcting codes, but ultimately distinct. (In an error correcting code you (usually) want to have every string within distance $k$  (or $k/2$, etc, etc) of no more than one codeword, whereas here you want to have every string within distance $k$ of at least one codeword.)


texts: Proving algorithm for removing nodes from a complete graph with two kinds of edges

texts:
Lets say $G$ is complete undirected graph with a set of edges coloured either black or red. The problem is to find an algorithm answering if it is possible to remove a subset of nodes from $G$ in a way such that all black edges are gone, but for any two nodes in the set of removed nodes there was no red edge between them.

I think I found a solution: If the graph has more than one black strongly connected components, then the answer is "no", because then there are two black edges $E_1$ and $E_2$ with no common nodes, and for every black edge at least one of its nodes should be removed to remove that edge from graph, and for any pair of nodes of $E_1$ and $E_2$ we choose to remove, there is a red edge between them, so we fail. Otherwise, we can sort all nodes by the number of linked black edges in descending order and then iterate this list node by node removing them from graph. If for current node there is a linked red edge, then mark the node on other end as "dangerous", and if we come across such node before all black edges are gone, then answer is "no". Otherwise, when there is no black edges, stop and answer "yes".

But now I want to prove this algorithm is correct. I think the case of more than one black SCCs is simple and doesn't require anything more rigorous, but the other case is more complicated and I'm not even entirely sure it's correct. Currently this is where I got:

Lets say the strategy of always removing a node with more linked black edges first is incorrect. Then it means, such strategy can make algorithm answer "no" when there was an other way to choose nodes which would make algorithm answer "yes". Then there is a step where some max-black-edges node $X$ is improperly chosen. Lets take a look at set of its black-adjacent nodes $S$. If all of them have the same number of linked black edges as $X$, then all other choices are symmetric and we will fail anyway, otherwise, there are nodes with less linked black edges than $X$ which means there are at least two nodes in $S$ which have a red edge between them. And to remove all black edges that make nodes in $S$ black-adjacent to $X$, we should remove all these nodes, so we will remove two with that red edge, so such strategies are incorrect and max-black-edges nodes should always be removed first.

I think this proof is somewhat naive and vague (especially in the end) and maybe even incorrect, so I'm seeking suggestions to make a better one. Not necessarily super-formal, but at least something which is sufficiently strict and believable.


texts: Iterative Byzantine consensus in directed graphs with unbounded malicious nodes

texts:
I've found many articles describing iterative procedures to reach Byzantine agreement on a graph (for instance http://www.crhc.illinois.edu/wireless/papers/icdcn14-vaidya.pdf or http://arxiv.org/pdf/1203.1888v1.pdf) but they all assume that a fraction of the peers aren't faulty or malicious.

Are there procedures to reach consensus among honest peers when there is an unbounded amount of faulty peers, but such faulty peers are only very sparsely connected to the cluster of honest peers?

A typical example would be a web of trust where it is trivial for an attacker to create millions of peers, but hard to receive trust from the main cluster.

I realize that, as such, the problem isn't very well defined. The honest cluster may have sub clusters, and it's unclear why they should be able to influence each other's consensus, while clusters of dishonest nodes may not. Typically, a solution would exhibit a threshold effect depending on connectedness.


texts:
Basically, you have $n$ integers. The data structure is for your choice, it is ok to do polynomial time preprocessing on them. Then you have multiple questions "Is an integer $k$ in the set?"

My question is about the best way we know in terms of time/space to answer this query. Ultimately, the time should be guaranteed (not randomized) and the space must be polynomial of $n$.

Firstly, one can use let's say 2-3 Trees or another type of search trees to do this in $O(log n)$ time and $O(n)$ space.

Secondly, one might say that it can be done in $O(1)$ with hashing, however I should note that this time is random and we are looking only for deterministic algorithms. Universal hashing requires a lot of space.

So, one way to approach the main question is to answer if there is a perfect hashing constructable in poly-time and poly-space?

Another approaches are also appreciated. Thanks.


texts:
I got this question:

  Let $A \oplus B = (A\cap \bar{B})\cup(\bar{A}\cap B)$.

  Proof that $NP = coNP$ if and only if $A,B\in NP$ and $A \oplus B\in NP$.

But I don't know how to proof the direction that if $A,B\in NP$ and $A \oplus B\in NP$ then $NP = coNP$.

I have tried to build the non-deterministic machines for $\bar{A}$ and $\bar B$, but I don't know how.

What that I tried: Say I want to build the non-deterministic machine for $\bar{A}$. I know that if $w\in A \oplus B$ and $w\in B$, then for sure $w \in \bar A$. My problem is with the condition if $w\notin A \oplus B$ and $w\notin B$ then $w \in \bar A$, because I don't know if $w\notin A \oplus B$ and $w\notin B$ since I don't know that $NP = coNP$.

So how can I show non deterministic machines for $\bar{A}$ and $\bar B$ when I don't know how to decide if "word is not in ..."?


texts: Can all regular tree types be expressed as $\mu$ types?

texts:
In "Types and Programming Languages", Pierce gives a translation from recursive types ($\mu$ types) to types expressed as regular trees: possibly infinite trees, but with finitely many distinct subtrees.

I'm wondering, is the converse true? Can every regular tree type be expressed using the $\mu$ fixpoint notation? It seems obvious that this can be done if you have mutually recursive types: you have a type for each subtree of the regular tree type. But can it be done with singly recursive types?


texts: Show that (2,3)-satisfability is np-complete

texts:
First of all, I introduce (2,3)-satisfability:
Formulas are in CNF form, the special property is that each clause has $2$ or $3$ literals. Formula is satisfied iff only and only if there exists valuation such that:

clauses with two literals are treated normally - it sufficient to
satisfy one literal (also $2$ literals can be satisfied).
clauses    with three literals are treated specially - there are must
be    satisfied exactly $2/3$ of literals (no more, no less)

Show that checking if such formula is (2,3)-satisfable is np-complete.
I have no idea how to do it. Obviously, it is easy to show that it is in np,  but hardness doesn't seem that easy to show.


texts: How to efficiently determine whether a relation is total?

texts:
I have a set $S$ of pairs $(x_1,x_2)$ with $x_1,x_2 \in X$ for some set $X$.

I want to know whether this defines a total relation on $X$. In other words, whether:

If $(a,b)$ in $S$ and $(b,c)$ in $S$, then $(a,c)$ in $S$. (transitivity)
Exactly one of $(a,b)$ and $(b,a)$ is in $S$ unless $a=b$, in which case they are both an element of $S$. (totality and antisymmetry)

Brute-force would take $O(|X|^3|S|)$ steps (I think), because there are $|X|^3$ triples $(a,b,c)$ and looking up whether something is an element of an array costs $O(|S|)$.


texts: Randomized Algorithm for determining items with rank $\geq n/16$

texts:
Problem: We say that an item $x$ is of rank $m$ if there are $m$ items in the set less than $x$. Design a randomized algorithm to find all of the items in a set of size $n$ with rank greater than $\frac{n}{16}$ with probability of failure $\frac{1}{1024}$.

I had this problem on my final yesterday and it completely stumped me. I don't even know how to begin. Any hints would be appreciated.


texts: Class of languages recognised by a Forgetful Turing Machine

texts:
A Forgetful Turing Machine (FTM) operates just like a normal Turing machine except that, in every instruction (i.e., transition), the letter written in the tape cell is always the letter $a$, regardless of the current state and the current letter (although the read/write head is still allowed to move either Left or Right, according to the instruction). What class of languages is recognised by FTMs?

Is the language non-empty with only the letter $a$? Does this mean that it is regular since it can be represented by $aa^*$?


texts: Which pass do you look at for Radix Sort stability?

texts:
I know this is a fairly poorly worded question, but I can't think of a better way to phrase it in the title.

So in Radix Sort, you go digit by digit from least significant to most significant, and along the way you are swapping elements around. When considering the case where two digits are the same, do you look at the original array to decide which should come first, or do you look at the previous iteration?

In one case you would have to store the original to look back on, so my guess is it's not that, but I can't tell which provides the correct result by my own examples. Let me know if I need to describe my question better and I will try.


texts: Is there such a thing as an "or" case in a dependency graph?

texts:
Suppose $A$ depends on $B$ or $C$, but not necessarily exclusively. Is it possible to model this in a dependency graph?

Can we just link $A$ to $B$ and $C$ via a diamond (like in UML) (though I don't see how this can be represented mathematically)? Or do we have to condense $B$ and $C$ to a single node $D$?


texts:
Theoretically, is it possible to convert the processing power of the CPU into several tens of bits of memory?

My question is unusual, but it's very interesting. I'm looking for a way to create a small (64 bit) memory department that the user could not access.


texts:
My question relates to a video I watched on YouTube.

The pipeline is a 5-stage pipeline which include fetch, decode, ALU, Mem (data), and Write.

It mentions that nothing is fetched until we're sure what to fetch. How can that be though? Won't you need to fetch and decode an instruction first to know what to fetch?

He mentions that the ADDI instruction gets fetched, but then goes in a bubble since it's not a branch. I really do not understand what is happening here and why the CPI for each instruction are ADDI=2, ADD=2, and BNEZ=3.

Can any explain to me what's going on here? Maybe a table with cycle iteration would be helpful.

Here's the video link: Branch Prediction question


texts: How to get the expected time complexity of while loop?

texts:
How to get the expected time complexity of while loop below?
While infinity:
  case1: Return 0 with a probability of p(1 - p)
  case2: Return 1 with a probability of p(1 - p)
  case3: otherwise repeat this loop until return 0 or 1

I can understand the probability that this loop runs only one time is $2p(1 - p)$. But I cannot understand how much the expected run time of this is. Can anyone let me know it and why?


texts: "Combinational" Decision Graph - Cheapest search algorithm

texts:
I have a special kind of decision graph, where Multiple decisions must be made in combination, to accomplish the path. Not sure if Multiobjective or Combinational is the right term here, let me know if there is a better one.
Picture better then words:

We have:

Joining Nodes (e.g. "Start") which joins decisions or costs nodes together - meaning solution path MUST cover all edges of joining nodes.
Decision Nodes (e.g. D1,D2,...) and Decision Edges (aka "local solution" - e.g. D1-1, D1-2,...) each solution path may cover only one of the edge of a decision.
Costs Nodes - (e.g. 3,7,5...) that have cost/reward applied to the Paths that cover it. Technically any node even decision or joining can have costs associated. COSTS MAY BE NEGATIVE.
Solution Path - goes from a starting node and must cover all edges of connected joining nodes and only one edge of each decision node it meets

Green is the cheapest Path for this example (D1-2,D2-1,D3-1) that you can calculate yourself empirically or combining all possible combinations and sorting by total costs. Total costs of Green path is $5.

Constraints:

Costs may be negative - in this case it's a reward.
Cycles are possible - they must be resolved as invalid path.
Decisions are NOT binary

Goal:

Find the best (BigO runTime) algorithm to find cheapest path covering this kind of graphs (without iterating all possible combinations and calculating its costs)? Pseudo code would help. Also what is the name of such type of decision graph?


texts: Proof that regular languages are closed against taking the even-length subset

texts:
This question is on the GRE Computer Science test booklet (not homework). I tried applying closure properties of regular languages but no success.

Suppose $L$ is a regular language over $\Sigma = \{0, 1\}$. Show that the language

$\qquad L' = \{w \in L \mid |w| \in 2\mathbb{N}\}$

is also regular.

What I find surprising is that the booklet mentions that the language $\{w \in L \mid |w| = 2^k, k \in \mathbb{N}\}$ is not necessarily a regular language.


texts:
NOTE:  This is for a project I'm working on for fun, NOT production code.

So I'm working on a pet project that involves reading data in from a sensor and summing it up.  The values are mostly floating point number mostly in the range (+/-)1 -  (+/-)10 and the program is expected to run for at least 2-3 hours, and it collects around 1000 datapoints a second.  The goal is to keep an accurate track of their sum, but after 3 hours or so there will be some drift in the calculation (which I would like to minimize).

So my main concern is that since the numbers can be positive and negative there will be too much cancellation that will ruin it, so what I was thinking of trying is to keep 2 kahan summations running, one for positive inputs and one for negative.

So for long runs can I expect this to lead to an increase in precision?


texts:
I am told A(B ∩ C) ≠ AB ∩ AC
I am unsure as to why they are not equal. Using examples and following them I am unable to show that they are not.

e.g Let A = {m} B = {s, p} C = {p, r}

A(B ∩ C) = A{p} = {mp}

AB ∩ AC = {ms, mp} ∩ {mp, mr} = {mp}

Have I made a mistake here?


texts: Finding paths of certain length in trees

texts:
In a graph tree, is there any "smart/existing/efficient" algorithm to find linear segments of defined length?

For example given a tree graph:

g = {1 -> 2, 2 -> 4, 3 -> 6, 4 -> 8, 6 -> 12, 1 -> 3, 2 -> 5, 3 -> 7,
   4 -> 9};
TreePlot[g, VertexLabeling -> True]

How can one find all linear segments of length 4. In this example this would be

1 2 4 8
1 2 4 9
1 3 6 12
2 1 3 7
2 1 3 6
9 4 2 5
...

This is probably a common problem, but I guess I have not yet found the right keywords for google. The naive implementation would be to visit every node, then recursively try to get four nodes away and delete all duplicated segments at the end...


texts: Create PDA for the alphabet {a,b} starting and ending with the same symbol

texts:
I have to design PDA accepting language: set of strings over ∑ {a, b} starting and ending with the same symbol.
From that moment i think good way is to remember only first element because the last one should be the same, but how make push and pop properly to achieve the final state.


texts: Proof that $A^* - \{x\} = A^+$ such that $A=\{a,b\}$ and $x \in \{a,b\}^*$

texts:
Exercise 1.1 (2) from Problem Solving in Automata, Languages, and Complexity by Du and Ko. P.7. the question is as following:

  Let A be a langauge over {a,b} and $x \in {a,b}^*$. Find necessary and sufficient conditions in terms of x and A for the equation:
  $$A^* - \{x\} = A^+$$

thus, by substation:
$$\{a,b\}^* - \{\{a,b\}^*\} = \{a,b\}^+$$

Now this the LHS should equal to $\{a,b\}^*$ because if we have two sets A and B, then $A \cap B = \phi$, then $A-B=A$. Now where is wrong?!!

I'm also trying to prove from RHS since this is equality to proof should be from both direction.


texts: Prove complement a^nb^nc^n is contextfree

texts:
So the complement of L1 = {$a^{n}b^{n}c^{n}$ | n $\geq$ 1} would be L2 = {a,b,c}* \ {$a^{n}b^{n}c^{n}$ | n $\geq$ 1}.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


texts:
Afternoon All,
Perhaps an easy one for many, but am new to Lambda calculus:
Is the below list, Ni, a representation of the Church numerals? I think it is but how do I prove it...if not, what is it...?
The terms Ni and N'i for each natural number i are defined as follows.
(n and c are variables while i stands for a number.)
          N'0 = n
          N'i = c i N'i−1 for i > 0
          Ni = λc.λn.N'i for any i

any help much appreciated...
Kind Regards


texts: Efficient algorithm for conversion of hexadecimal fraction to decimal fraction

texts:
Let's say I have some very long hex fraction like this:

0.3F30A21306AEFCBADE3230A593EFAEB395A39E

What are some algorithms with an acceptable complexity to convert it to the associated decimal string:

0.246835...

?


texts: Distributed push relabel with changing graph topology

texts:
There is at least one (1) distributed version propsosed for the push-relabel maximum-flow algorithm. I wonder if and how this algorithm can cope with nodes leaving or enterig the graph during runtime. Is there any work about this?

1 Andrew V Goldberg and Robert E Tarjan. A new approach to the
maximum-flow problem. Journal of the ACM (JACM), 35(4):921–940,
1988. google scholar


texts:
I started reading more and more language research papers. I find it very interesting and a good way to learn more about programming in general. However, there usually comes a section where I always struggle with (take for instance part three of this) since I lack the theoretical background in computer science: Type Rules.

Are there any good books or online resources available to get started in this area? Wikipedia is incredibly vague and doesn't really help a beginner.


texts: How to prove P = NP if problem Π ϵ NP-complete and Problem complement Πc ϵ NP?

texts:
How to prove if P = NP if problem Π ϵ  NP-complete and Problem complement Πc ϵ NP?
OR
P = NP if NPC intersects with Co-NPC


texts: Algorithm to convert undirected connected graph with no bridges to strongly connected directed graph

texts: I am not sure how to go about this exactly. My attempt is find the pick an arbitrary node and run DFS, ordering each node by order of discovery. After this, You can orient each of edges so it pointing from lower order to higher order. Now I know this will create a path from one node to another, but doesn't guarantee a path from the other back to the initial. Is there any way to modify my algorithm so that it it would strongly connected and not just connected.


texts: Transitions needed for dividing two fixed integers

texts:
Let $Q$ be the set of states of the Turing Machine, $\Sigma$ be the alphabet, and $\{L,R,S\}$ be the left shift, right shift, and stay respectively.

A transition is an element of $Q \times \Sigma \times Q \times \Sigma \times \{L,R,S\}$ which can be read as current state, current symbol, next state, next symbol, movement direction.

For a Turing Machine I'm looking to understand how many transitions, or states since they are linearly related, are needed so that when I give integer $i \ge 0$ on the tape it outputs the $i^\text{th}$ digit after the decimal point(zero indexed) of $\frac{p}{q}$ for which $p$,$q$ are coprime. Assume it is in base $c$ and you only have the characters $0,1,\dots,c-1$ and blank. I imagine this is possible to do in $O(c\log q)$ states, but my best attempts(outlined below) only give me $O(cq)$. An example where $c=2$ and $\frac{p}{q}=\frac{1}{3}$ would be I want a binary Turing machine such that when given $10$ on the tape would output the $3^\text{rd}$ digit after the decimal point of $\frac{1}{3}$ which is $0$ and when given $110111$ would output the $56^\text{th}$ digit which is $1$.

Here is my way of doing it. For the purpose of this $\text{nt}(c,q)$ is the length of the non-terminating portion length of $\frac{p}{q}$ in base $c$, this is easily verified to be the same for all coprime $p$,$q$. Also define $\text{per}(c,q)$ as the length of the periodic portion of $\frac{p}{q}$ in base $c$

My basic idea was you check if it is less than $\text{nt}(c,q)$ and if so output that digit and halt, this takes $O(c\,\text{nt}(c,q))$ transitions. If it's not smaller subtract out $\text{nt}(c,q)$ which takes $O(c\lfloor \log \text{nt}(c,q) \rfloor)$ transitions. Then test for what the result is modulo $\text{per}(c,q)$ and output the appropriate digit. This takes $O(c\,\text{per}(c,q))$ transitions. Now remember that the worst case of $\text{per}(c,q)+\text{nt}(c,q)$ is $q-1$. Therefore the final transition complexity is $O(cq)$

A second idea I had was Newton's algorithm which I think would take $O(c\log q)$ transitions. The basic idea would be to output $p$,$q$,$.1$ to the tape in base $c$, convert to unary which takes $O(c)$ transitions then do multiplication and subtraction in unary which takes $O(1)$ transitions. Would this work?


texts: Why aren't computables used for numerical calculations?

texts:
In programming languages like Haskell you can use lazy evaluation to delay calculations.

Why isn't a similar approach being used for numerical methods (I understand that there would be memory implications).

The approach would be that non-integer values would be stored as how they are calculated, so that the next digit can be found when requested.

This kind of approach should allow every value to be calculated to the correct number of significant figures.

Sorry that this is slightly garbled.


texts: Why is the reduction $\textbf{SAT} \leq_P \textbf{3SAT}$ possible, but $\textbf{SAT} \leq_P \textbf{2SAT}$ not possible, given, that $\textbf{SAT}$ is $\textbf{NP}$-complete, $\textbf{2SAT} \in \textbf{NP}$ and $\textbf{3SAT} \in \textbf{NP}$?


texts: How to prove this obvious theorem in type theory (LEAN prover)

texts:
I have the following code:

constant B:Type
constant A:Type
constant P:B → A → Prop
definition F:Type := B → A

axiom a1: ∀b:B, ∃a:A, P b a
theorem thrm1: ∀b:B, ∀a:A, (P b a) → ∃f:F, (f b = a) ∧ ∀bb:B, P bb (f bb) :=
    λ b:B, λ a:A,
    assume h: P b a,

sorry

It should be almost trivial to prove this, yet I'm not sure how to do it in type theory. Perhaps my intuition is implicitly based on some axiom from classical logic?

The informal argument is as follows: If for a particular $b$ and $a$ the property $P \; b\;  a$ holds, then we can consider the equivalence class of functions $f:B \to A$ for which $f \; b= a$. Moreover, since for any $b\in B$, there is an $a\in A$ such that $P \; b \; a$ holds, we can simply pick from this the function $f$ which also assigns for every other $b$ some $a$ such that $P\; b\; a$ holds. Such a function must always exist, since we can freely adjust the output for each input independently.

But how do we formalize this argument in type theory?


texts: How do you implement a language with greater capabilities using subordinate languages?

texts:
I've heard that C++ and Python where implemented using C. How can someone make an object oriented language out of something that doesn't support objects?

I've read in the book "Math You Can`t Use - Patents, Copyright and Software" that code is considered an equivalent of mathematics because it will eventualy be ran on cirquits that work and interact based on mathematical logic.

If a limited tool like C can produce a tool with further capabilities like C++, does that mean that mathematics can be used to create "better" mathematics? That seems to contradict Gödel's incompleteness theorem.

What is the essence of this trancedance from simple procedural to object oriented? Is there some code written in C that C++ and Python use or are they written in a completely different paradigm from the ground up?


texts:
I have recently become extremely interested in understanding and proving aspects of (functional) programming languages.

However as I dive deeper in, things like $\lambda$ calculus, category theory, and denotational semantics are a little difficult to grok without proper explanation.

I read SICP (quite an enlightening book) but I'm looking to dive deeper into the theory of functional programming. Are there any books/blogs/sites/you-name-it that would discuss the theory of functional programming languages from the ground up?


texts:
I'm just beginning self-studying a course on computability and automata; my textbook, describing a generic Turing Machine, lists two following halt conditions:

A TM halts, if for a particular state $q \in Q$, $\delta(q, a) = (q, a, HALT)$ for all $a$ in the alphabet and this $q$ is called a halt state;
A TM also halts, when the TM reads $a$ while being in $q$, and $\delta(q, a) = (q, a, HALT)$ is true only for this particular $a$.

I have no problems comprehending the first one, but I'm a little frustrated by the second one, that is, I don't understand, why the exclusivity of $a$ is of any importance. Won't the machine halt if we have several $a, a'$, for both of which it's supposed to halt?

And in general, are there any other halting conditions possible?


texts: Is there a binary tree structure with fast access to recently accessed elements and worst $O \left( \log n \right )$ complexity?

texts:
The idea of splay trees is very nice as they move frequently accessed elements to the top, which can gain a considerable speed up in many applications. The drawback is that in the worst case an operation can have $O(n)$ complexity.
(Although amortized bounds are $O(n\log n)$ if we perform at least $n$ operations.)

Is there a self-adjusting search tree structure that has both? Favoring recently accessed elements and with worst $O(\log n)$ complexity for a single operation?


texts:
Can anyone let me know, why 2PC is blocking when the coordinator fails? Is it because the cohorts don't employ timeout concept in 2PC?

Good reference: Analysis and Verification of Two-Phase Commit & Three-Phase Commit Protocols, by Muhammad Atif,

Elaboration of the question:

Let’s say, a coordinator sends 1st message (PREPARE-COMMIT). At this point assuming all cohorts are reachable, there are two possible outcomes- either all cohorts reply YES or at least one cohort replies NO. In either way, let’s assume the coordinator crashes before it can send the 2nd message (COMMIT/ABORT).
Since 2PC uses only 2 messages, in order to keep the cohorts consistent, the cohorts can never apply a commit without explicitly receiving a COMMIT message. So, when a coordinator crashes, the cohorts can either (1) apply a ABORT using a timeout or (2) can remain in waiting state indefinitely. It is hard to believe that a 2PC would employ option (2) i.e. waiting indefinitely. Therefore, if option (1) is chosen, then why do we tag 2PC as blocking when a coordinator dies?


texts: How strong is an countable infinity large circult?

texts:
To give a clear definition:

1) No wire delay

2) Any number of bits(including infinity) doing NAND(and therefore all the lead-out logics) operation cost O(1) time

3) There are only finite layers(so you can't find a logic chain longer than a fixed value)

4) There may be an input of countable infinity size

To define calculate: You are allowed to say, for i in N(0 to infinity), or maybe a few for's, (a,f(i))->(c,g(i)), where a<c, and f and g are functions with plus, minus and merge(packing two integers into one). The expression should be finite.

E.g. Increase a binary number a[inf]..a[0] by 1:

f[i] = a[i] xor (a[i-1] and a[i-2] and ... and a[0])

E.g.2 Add two binary numbers a[inf..0] and b[inf..0]:

u[i] = a[i] or b[i]

t[i] = a[i] and b[i]

s[i][j] = u[i-1] and u[i-2] and ... and u[i-j]

c[i] = t[i-1] or (t[i-2] and s[i][1]) or (t[i-3] and s[i][2]) or ... or (t[0] and s[i][i-1])

f[i] = c[i] xor a[i] xor b[i]

E.g.3 Adding two real numbers: Get (0.a[0]a[1]a[2]...+0.b[0]b[1]b[2]...)mod 1

f[i] = a[i] xor b[i] xor ((a[i+1] and b[i+1]) or ((a[i+1] or b[i+1]) and (a[i+2] and b[i+2])) or ((a[i+1] or b[i+1]) and (a[i+2] or b[i+2]) and (a[i+3] and b[i+3]))...)


texts: Is "Feral Concurrency Control" a disparaging description?

texts:
The paper Feral Concurrency Control:
An Empirical Investigation of Modern Application Integrity uses the term "feral" in a way I have never seen before.

  Rails has developed a range of concurrency control strategies,
  two of which operate external to the database, at the application
  level, which we term feral concurrency control mechanisms.

The paper shows that various application-level data validations are less reliable than database-level checks.

The only usage of "feral" I'd seen previously applied to untamed animals - eg, "feral cats".

Are the authors using the term disparagingly, or does "feral" mean something different in this context?


texts: Halting problem vs. automated theorem proving?

texts: In the Theory of Computation tutorial offered by Complexity Tree (I just began the 2nd video), it talks about how the Halting problem was developed to show that mathematics could not be automated.  Lately, I've heard quite a bit about automated/automatic theorem proving--some people are even positing that some day mathematicians will be replaced by machines.  My question is: Do we need to find a flaw in the reasoning of the Halting problem to prove that mathematics can be automated?  (Or is the Halting problem, in the age of Machine Learning, reduced to a nice historical account of the past...)