texts: Is there a known worst start configuration for Ford-Johnson sorting algorithm?

texts:
By this I mean a permutation of the $n$ input items to be sorted such that the number of comparisons taken to produce the correct order is maximal over all of the possible permutations of $n$ items.

Is there a pattern like all input ascending is worst case, or even some class of input permutations that have been proved to lead to worse performance than others?


texts: Grover's Algorithm result when the desired element is not present

texts: What does Grover's algorithm output when the desired element is absent from the database? Since there will be no phase inversion, how exactly will the probabilities work?


texts: Finding a node in a binary tree by looking at the path between it and the root

texts: There is a directed binary tree as shown in the picture (all edges are diercted from higher- to lower-level nodes). In that tree there is some specific unknown node $s$. All nodes in the $(s, root)$ path are marked somehow (yellow nodes in the picture) so we can check using a $check$ operation if a node belongs to the path. The total length of the path (number of the edges) is $l$ and its value is unknown (in the picture $l=2$). The task is to find the node $s$ using a randomized algorithm such that it is expected to use $check$ operation at most $\frac{3}{2}l$ times.


texts: What simple arguments and insights can I observe that running both BFS and DFS can be achieved in O(|V| + |E|)?

texts:
BFS and DFS can be achieved in O(|V| + |E|). I understand the proof but it seems a bit lengthy.

Can I argue O(|V| + |E|) in a very simply way? e.g. checking each edge at most once?
Also what does O(|V| + |E|) imply?

I know Dijstrka algorithm and many other algorithm is somewhat like BFS. Does it imply automatically they can be run in |V| + |E| is the lower bound?


texts: Count number of ways in which atomic operation(s) of n different processes can be interleaved

texts:
PROBLEM: Count the number of ways in which atomic operation(s) of n different processes can be interleaved. A process may crash mid way before completion.
Suppose there are a total of n different processes - P1, P2, P3 .... , Pn.
Each process can have a variable number of atomic operation(s) that constitutes that process, but it should have at least one operation.

EXAMPLE

Consider two processes, P1 and P2

P1: 1o1; 1o2; 1o3; 1o4; 1o5; 1o6;
P2: 2o1; 2o2; 2o3;

where 1o1 denotes first operation of process P1.

Attempt:
Fix position of all operations of process P1, then count the number of ways in which the operations of process P2 can be placed in empty positions( __ ) created between operations of process P1, as shown below:

__ 1o1 __ 1o2 __ 1o3 __ 1o4 __ 1o5 __ 1o6 __
There are seven empty positions numbered 1 to 7.

Counting: (Note that the numbers below (like 1 2 3) denote the empty position number.)
> Case1: When all three operations of P2 are placed in consecutive empty positions.

  1 2 3

  2 3 4

  3 4 5

  4 5 6

  5 6 7

  We have a total of 5 ordering possible for empty positions.

> Case2: When operations of P2 are placed in two consecutive empty positions taken together.

  1 2 3   2 3 4   3 4 5   4 5 6   5 6 7

  1 2 4   2 3 5   3 4 6   4 5 7

  1 2 5   2 3 6   3 4 7

  1 2 6   2 3 7

  1 2 7

  First cell in every column has already been counted in previous case. We have a total
  of (5 - 1) + (4 - 1) + (3 - 1) + (2 - 1) + (1 - 1) = 10 ordering possible for empty
  positions.

  A similar argument can be made for last two consecutive empty positions taken together,
  that gives us a total of another 10 ordering possible for empty positions.

> Case3: These are those cases that do not have empty positions numbered 8 and 9 for them.

  6 7 8

  7 8 9

> Case4: When operations may crash mid way before completion.
  An 'x' denotes position where a crash is possible and process (here P2) terminates.

  1x 2x 3

  2x 3x 4

  3x 4x 5

  4x 5x 6

  5x 6x 7

  6x 7x 8

  7x 8x 9

  There is a total of 14 'x's possible.

  Note: I have not put a cross after last empty position number because I am assuming that
  a process will complete at this stage. You may correct my assumption if this is
  wrong and should not be assumed in the first place.

Adding all 4 cases: 5 + 2*10 + 2 + 14 = 41. There are 41 possible ways to interleave operations processes P1 and P2.

As you can see, counting like this is cumbersome and error prone. I have missed cases.
How can this counting problem be generalised? Please see the problem statement at the top of the question.


texts: How to efficiently code Dynamic Time Warping algorithm with a locality constrain?

texts:
For given two lists $[s_1, s_2, ... s_n]$ and $[t_1, t_2, ..., t_m]$

I need to implement DTW algorithm with one extra constraint:

If $s_i$ is matched with $t_j$ then the next element $s_{i+1}$ has to be matched with some $t_{j+k}$ close enough to $t_j$ (i.e. $0 \le k \le W$ for some fixed window size $W$).

This constraint has to hold for each $s_i$.

1) Does there exist $O(nm)$ solution to such problem?

2) If an efficient algorithm does not exist, what would be a good practical solution?

(Note that locality constraint mentioned in the DTW link above is different from the constraint I need).


texts: Find the largest number of independent subarrays given an array

texts:
We are given an array and numerous subarrays. What we can do is add or multiply some element to all elements of a subarray. The subarrays are given as start index and the end index. We have to find the largest number of independent subarrays from the subarrays given to us. For example:

If we have the array as given below :

$\qquad A = [a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,\dots]$

Now we are given numerous subarrays as :

$\qquad\begin{align*}
  S_1 &= (a_1, \dots, a_6) \\
  S_2 &= (a_1, \dots, a_8) \\
  S_3 &= (a_7, \dots, a_8)
\end{align*}$

So in this case all manipulations that can be done by the subarray $S_2$ is actually captured by the subarrays $S_1$ and $S_3$, i.e we want to add $7$ to all elements in $S_2$ then we can do it by adding $7$ to all elements in $S_1$ and $S_3$. So $S_2$ can be removed. In this similar way we need to find out the maximum number of independent subarrays possible.

Independence here means that if any subarray can be expressed as a combination of two or more subarrays then any changes that can be made to the subarray like adding a specific element to all elements in the subarray can also be make  by applying the same operation to all the subarrays which make up the given  subarray. For example if we have an array of size n. Then we have a given subarray from A11(11th element) to A20(20th element) and there are two more subarrays given from A11 to A15 and A16 to A20. Then if we want to add 5 to all elements from A11 to A20. Then we can add 5 to subarray from A11 to A15 and also A16 to A20. Hence A11 to A20 is not important.

Here we just need to find the total number of independent subarrays.


texts: What category of AI would a 2048 bot be considered?

texts:
I have just delved into the realm of AI and from what I can tell its a very vast field of study. I am a game programmer, so AI in games is particularly interesting to me. My question is, what type of AI would a bot that can beat 2048 fall under?

I learned the basics of machine learning, but I wasn't sure if this is how you could apply machine learning. I want to know what category this falls under so I know what to research and learn to make my own bot. Also, if you don't know what 2048 is, check it out here.


texts: What sorting algorithm should be used for this array?

texts:
I am given an array {1, 2, 3, 5, 4, 6} and I am asked

  What sorting algorithm might you want to use to sort the given list, and why?

Initially I think using Bubble sort would be the best option due to it's best case linear ($O(n)$) complexity and due to the fact that you'd only need to use 1 swap. However, the more I look at the problem I am starting to think that Insertion Sort may also be efficient in this situation.

Insertion sort and Bubble sort both have the same best, average, and worst case time complexities as well as the same space complexities. Are neither one of these algorithms the proper one to be used on this array? If not, why not?


texts: Are you allowed to change the specifications of a problem when doing reductions?

texts:
I'm doing a polynomial time reduction from problem A (known graph problem) to problem B (funky and specific longest path problem). There is a lot of demands on how problem B is supposed to be solved. However, the input of problem A does not give me enough information to be able carry out all of these demands that problem B require.

My reduction will look something like this:

**A**(G(V, E), K) =
     a = V
     b = E
     P = **B**(a, b, K)
     if(P)
         return true

My question is if it is okay to ignore some of these demands and simply change the B problem to a simpler one which then would allow me to find a reduction which satisfies both problems?

I'm sorry for being so vague, it is a homework problem and I would like to not publish the details.


texts: Intuition behind the condition |xy| ≤ p in pumping lemma for regular languages

texts:
When I take a look at the proofs for pumping lemma, I have a feeling that I am often missing the intuition behind the condition |xy| ≤ p.

What exactly is the reason behind this condition? All the literature I have taken a look at are either silent (no proof, no discussion, only a statement) about this point, or state that we want the first repetition to occur not too far from the start.

But when there is an inequality involved, with very precise symbols and operators, don't we expect there to be a clear proof where we ultimately reach this condition?

What I am looking for are,

Mathematical proof for the condition, |xy| ≤ p.
Intuition behind the same condition.

To make the strings sufficiently long we have the condition string size at least p. My specific issue is why it is needed that |xy| ≤ p? And what does it break if |xy| ≤ p is not true?

(What's the reason for the second condition of the pumping lemma(s)?, does not exacly answer my question. The question is perhaps alright, but the answers only give some examples without much deep intuition.)


texts: Algorithm for building a suffix array in time $O(n \log^2 n)$

texts:
I've been working with suffix arrays lately, and I can't find an efficient algorithm for building a suffix array which is easy to understand.  I have seen in many sites that there is an $O(n \log^2 n)$ algorithm, but I can't understand it, as many important details are omitted.  There's an example at Top Coder.

Could someone introduce me an efficient algorithm for suffix array construction, which is easy to comprehend?


texts: Finding undirected cycles in linear time (triangulating graphs while minimizing degree)

texts:
In the article ["Triangulating Planar Graphs While Minimizing the Maximum Degree"] by Kant and Bodlaender [1], Section 4 briefly mentions the extraction of elementary cycles (no repeating edges) from what I assume is an undirected graph $H$. It has the following to say:

$H$ is planar and bipartite.
...using a simple modification of Euler's technique to find an Eulerian cycle in a graph, we can extract the elementary cycles $C_\mathrm{elem}$ from $H$.
Thus $H - C_\mathrm{elem}$ consists of paths $P$ with disjoint begin- and endpoints.

In the proof section it mentions that extracting elementary cycles and disjoint paths can be executed in linear time, allowing the triangulation algorithm as a whole to do the same.
From what I understand, there are no algorithms that compute the simple cycles of an undirected graph in linear time, raising the following questions:

Which algorithm does "Euler's technique to find an Eulerian cycle" refer to? There seem to be several algorithms with varying performance.
What is the "simple modification" in question? The paper doesn't say, and I haven't been able to find anything on the net.

[1] G. Kant and H. Bodlaender, "Triangulating Planar Graphs While Minimizing the Maximum Degree". Information and Computation, 135:1(1–14), 1997. (Science Direct)


texts: Is there a relationship between visitor pattern and DeMorgan's Law?

texts:
Visitor Pattern enables mimicking sum types with product types. Where does the "sum"-iness come from?
For example, in OCaml one could define type my_bool = True | False
Or encode with visitor pattern:
type 'a bool_visitor = {
  case_true: unit -> 'a;
  case_false: unit -> 'a;
}

let t visitor = visitor.case_true ()
let f visitor = visitor.case_false ()

let visitor = {
  case_true = (fun () -> "true");
  case_false = (fun () -> "true");
}

let () = print_endline (t visitor) (* prints "true" *)

What's the best way of explaining the sum-type-to-visitor-pattern transformation? Is it:

Of course + and * are interdefinable, what did I expect?
Or is it that the left side of -> is the "negative" position and that this leads to a DeMorgan-law-like flip of sum and product?

I also wonder if this question is related to how one can use universally-quantified types to mimic existential types.


texts: Smallest set of balls under hamming distance that covers all $n$-bit strings

texts:
Suppose we defined a set $S = \{x\mid0 \leq x \leq 2^n-1\}$. Notice that all element in $S$ can be represented with a $n$-bit binary string. Now consider subset $S_i$ such that,

$$S_{y_i} = \{y \in S\mid d(y,y_i) \leq t\},$$

where $y_i$ is the $i$th element of $S$ and $d(y_j,y_i)$ is the hamming distance between the binary representation of $y_j$ and $y_i$ and $t < n$.  Obviously, $S_{y_i} \subset S$.

Consider the family ${\Phi = \{S_0, S_1, \ldots, S_{2^n-1}\}}$. Find ${\phi \subset \Phi}$ with smallest cardinality, so that the union of the all elements in $\phi$ is equal to original set $S$ (notice that, each element of $\phi$ is a subset of $S$).

I was not be able to solve. However, I believe it is possible to find $\phi$ with an efficient algorithm rather than using an exhaustive search.

Edit: An example-

Assume $n =3$ and $t = 1$

Then $S = \{0, 1, 2, 3, 4, 5, 6, 7\}$

So, $S_0 = \{y \in S\ |\ d(y,0) \leq 1;\} = \{0, 1, 2, 4\}$

Similarly, $S_1 = \{0, 1, 3, 5\}$; $S_2 = \{0, 2, 3, 6\}$; $S_3 = \{1, 2, 3, 7\}$; $S_4 = \{0, 4, 5, 6\}$; $S_5 = \{1, 4, 5, 7\}$; $S_6 = \{3, 4, 6, 7\}$; $S_7 = \{3, 5, 6, 7\}$;

So, $\Phi = \{S_0, S_1, S_2, S_3, S_4, S_5, S_6, S_7\}$;
Now, for this case the $\phi = \{S_2, S_5\}$ as $S_2 \cup S_5 = S$


texts: How to prove that the reduction relation is not symmetric

texts:
I know that the reduction relation is not symmetric. Writing formal proofs is the main core of the course I take on Theory of Computation. So I'm trying to prove that theorem. For that I need to show two languages $L_{1},L_{2}$ so $L_{1}\leq L_{2}$ and $L_{2}\not\leq L_{1}$. My textbook suggests to use $L_{1}\triangleq\Sigma^{*}$ and $L_{2}\triangleq HP$ and show that $L_{1}\leq L_{2}$ and $L_{2}\not\leq L_{1}$.
So I need to split the proof into two sections:

Prove $L_{1}\leq L_{2}$ - Stuck. Not sure how to prove it formally.
Prove $L_{2}\not\leq L_{1}$. I want to use that $HP\not \in R$. So lets assume by contradiction that $HP\leq\Sigma^{*}$. This means there such function $f\,:\,\Sigma^{*}\to\Sigma^{*}$ between $HP$ and $\Sigma^*$. How to continue?

The definition of reduction: Given two languages $L_1$ and $L_2$, we say that there is reduction from $L_1$ to $L_2$ (and mark $L_1\leq L_2$) if there is a function $f\,:\,\Sigma^{*}\to\Sigma^{*}$ so:

$f$ is full - for each $x\in \Sigma^*$ there is one $y\in \Sigma^*$ so $f(x)=y$.
$f$ can be computed - there is a Turing machine that can compute $f$.
fulfils: $x\in L_1$ iff $f(x)\in L_2$.

As formality is important, how do I fill the blank spaces up to the full proof?


texts: Number Partitioning targeting a Ratio of subset sums?

texts:
I have a problem, which appears to be similar to number partitioning:
a set of numbers partitioned (two-way), such that the sum of the numbers in each subset are as close as possible to a targeted ratio (instead of having the minimum difference, as in the number partitioning problem). Can I use the same algorithms? How would I modify them? Is another approach more suitable?

Context:

I am implementing a load-balancing algorithm, for a work conserving Group Weighted Round Robin (GWRR) scheduler. In some corner-case (some groups have less tasks than CPUs in the system), I want to partition the weighted groups and assign them to the subsets of a partitioning of the set of CPUs, so that the ratio of the sums of (predicted) CPU idle times, in the subsets of the CPU partition, is as close as possible to the ratio of the weight sums, in the subsets of the group partition. The group partition splits the groups, using a normal number partitioning algorithm (CKK), so that group weight sums, in each subset, have the minimum possible difference (but they are unlikely to match, in the general case).

Any ideas?


texts: Why is the complement of a language that is not regular also not regular?

texts:
In my lecture notes I we were given two languages and were shown that each of the two languages were not regular. The second was the complement of the first language. To show the second was not regular, he wrote that it follows from the fact that the second language was the complement of the first, which we had already proved was not regular.

I was wondering if anyone could explain why this is the case?


texts:
With the recurrence relation:
$$ T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log(n)}$$

The "sum for all levels" in the recurrence tree is:
     $$ \sum_{i=0}^{\log n -1} \frac{n}{\log n - i} =  \sum_{i=1}^{\log n} \frac{n}{i} = n \sum_{i=1}^{\log n} \frac{1}{i}$$

Inside the analysis of the recurrence, $\sum 1/i$ appears and then bounded by $\Theta(\log\log n)$. Why is this?


texts: Deriving epsilon with a context free grammar with epsilon rules

texts:
The below problem is from my Formal Languages class. The professor suggested drawing derivation trees for the language until we reach epsilon in all the leaves, and that it should begin to look like a geometric series. But I'm still having trouble getting started.

The way it was explained: if a context free grammar G contains epsilon rules and can reach epsilon, then show that it does so in N replacements, where N is <= the sum of a geometric series. What's the proof for showing an implication like this?


texts: Has the notion of "non-cheating" quines been formalised?

texts:
Informally, it is often said that some quines "cheat", such as those that read their own source code from memory, or the case where a program consisting of the empty string happens to output the empty string.

Quines that are considerd to be "non-cheating" always seem to have the same structure. There is some data structure (usually, but not always, a string) which contains some representation of the source code. This structure is read twice, once to reformat it into the code part of the final output, and a second time where it's copied verbatim to reproduce the data part. For example, the following Python example (which I just invented) has this structure:

x = """x = {0}{1}{0}
print x.format(chr(34)*3,x)"""
print x.format(chr(34)*3,x)

The string 'x' is referred to twice in the last line, once to reformat it, and a second time to paste it verbatim into the reformatted string.

My question is whether this notion of "cheating" or "non-cheating" quines has been, or can be, formalised. That is to say, if we are given a formal specification of a language and its semantics, and we are also given an example of a quine in that language, is there a well-defined way to say, in principle, whether that quine is "cheating" or not? Or is this notion of "cheating" inherently too vague to admit a formal definition?

If this notion can be formally defined, is it possible to have a language that only admits "non-cheating" quines, and is an example of such a language known?


texts:
I am trying to understand Pattern Databases for designing heuristics. I am reading Richard E. Korf's book Heuristic Search. One of its paragraphs says

  The obvious heuristic for Rubik's Cube is a three dimensional version of the Manhattan distance. For each cubie, compute the minimum number of moves required to correctly position and orient it, and sum these values over all cubies.Unfortunately, to be admissible, this value has to be divided by 8, since every twist moves 8 cubies. A better heuristic is to take the maximum of the sum of Manhattan distances of the corner cubies, divided by four, and the maximum of the sum of edge cubies divided by 4. The expected value of the Manhattan distance of the edge cubies is 22/4=5.5, while the corresponding values for the corner cubies is 12.333/4 that's approximately equal to 3.08 partly because there are 12 edge cubies, but only eight corner cubes.

My question is why taking the maximum of the sum of Manhattan distances for corner cubies divided by four and the maximum of the sum of Manhattan distances for edge cubies divided by four is better heuristic than taking the sum of Manhattan distances divided by eight?

Besides, how do they get the expected values of 5.5 and 3.08?


texts: Alternative proof of the fact that heapify can be linear-time

texts:
As an exercise, I'm trying to prove by myself that constructing a binary heap from an array in-place can be $O(N)$. I've come up with an idea, but I'm not sure about its correctness.

Firstly, I define the following procedure (pseudocode):

process_node():
    if the node has children:
        select the child node with the maximum value
        if the selected node's value is greater than the value of current node:
            swap current node with the selected node

Then I run this procedure on all non-leaf nodes going down level by level in the binary tree view of the array. So the root is processed first, then comes the first level etc. After doing this, a half of leaf nodes become smaller than all of their ancestors. Another run of the procedure on the same nodes settles the other half of the leaves. Thus, they have been put in place in the heap and can be removed from the processing.

The number of leaves is halved, and so is the number of non-leaf nodes. The procedure is run again on new non-leaves, and the process is repeated until all the elements of the array are processed.

The number of nodes on which the procedure is run starts with $N/2$ and later is halved. We get a decreasing geometric series with the sum being $O(N)$.

Are there any mistakes in my reasoning?

EDIT.

An example with 7 elements. The number of levels $L = 3$.

       1
    /    \
   2      3
  / \    / \
 4   5  6   7

Step 1. The root node is processed with process_node().

       3
    /    \
   2      1
  / \    / \
 4   5  6   7

Step 2. The nodes in the level 1 are processed. The total number of levels processed in this way is $L' = L - 1$.

       3
    /    \
   5      7
  / \    / \
 4   2  6   1

The processing of each node sifts the smallest value in the node and its direct descendants one level down. Each node thus "generates" the smallest value for its children. After steps 1 and 2 are completed, the values "2" and "1" are on their correct places. It is a half of the leaf nodes.

Step 3. Repeat steps 1 and 2. The lowest level is completely filled and can be excluded from further processing. The second lowest level can be thought of as the new "leaves".

       7
    /    \
   5      6
  / \    / \
 4   2  3   1

The heap is now fully built, but it seems to be an accident that it is constructed this early. So,

Step 4. Do steps 1 and 2 for the first $L' = L' - 1$ levels. Repeat until $L' = 0$.


texts: 1/r attractive force by cellular automaton

texts:
Does there exist a cellular automaton (in 2D) which simulates a $1/r$ force between particles?

More specifically, I would like to know whether it is possible, with strictly local update rules, to have two objects (defined within the model) attract each other with a $1/r$ force, where $r$ is the distance separating the objects.  This would in particular entail an acceleration of the object (particles) as they get closer together.

More generally, can long range attractive forces between objects (blobs) be simulated in a cellular automaton setting with strictly local rules?


texts:
Michael Sipser offers the definition:
The pumping lemma says that every regular language has a pumping length p, such that every string in the language can be pumped if it has length p or more. If p is a pumping length for language A, so is any length p′ ≥ p. The minimum pumping length for A is the smallest p that is a pumping length for A.
Now, (01)* in set notation is {€, 01,0101,010101....}
Taking minimum pumping length = 1, according to the definition, we have the statement if a string in the language has length 1 or more, it can be pumped.
This statement is true for all elements of the above mentioned set, so can the minimum pumping length be 1?
p.s. the minimum pumping length for (01)* has been asked here before but it doesn't answer my doubt that since the condition holds for minimum pumping length = 1, why is it not the answer?


texts:
i have the following CFG

E -> ABC
A-> a|Cb|epsilon
B-> c|xA|epsilon
C-> y|z

and the First of the Non-Terminal :

First(E) = {a,y,z,epsilon}
Frist(A) = { a,y,z,epsilon}
First(B) = { c,x,epsilon }
First(C) = {y,z}

the follow of Non-Terminal :

follow(E)={$}
follow(A)={c,x,y,z}
follow(B)={y,z}
follow(C)={b,$}

my problem is how to construct the parsing table , i constructed the table and i got the following , but i think there is something missing/mistake in the table

    x    a    b    c    y    z    $
------------------------------------
E       ABC            ABC  ABC  epsilon
A eps.   a        eps. Cb   Cb
B  xA              c   eps.  eps.
C                       y     z

i hope the table is clear ,

Note : in the row A i got epsilon with both Cb in y And Cb in z , but i did not write it in the table , is that mean the grammer is not LL(1) ??

thank you!


texts: Does weak consistency allow reordering of events?

texts:
I am on studying a consistency model: weak consistency. weak consistency
This model was first defined by Dubois et al. (1986), by saying that it has three properties:

Accesses to synchronization variables are sequentially consistent.
No access to a synchronization variable is allowed to be performed until all previous writes have completed everywhere.
No data access (read or write) is allowed to be performed until all previous accesses to synchronization variables have been performed.

And there is an example saying that the following sequence is weak consistent :

Here, S represents accessing synchronization variables.

But how is this possible ? I don't understand how can the event R(x)2 happens before R(x)1 of processor P3 while W(x) 1 happens before W(x)2 on processor P1.


texts: Distributed predicate computation on event stream

texts:
My question is actually a request for papers, articles, texts or books on the problem that I'm trying to solve on my work.
I'm working on a program that computes a predicate value (true or false) for a given object in a distributed system in which there is a stream of events that can change the object's attributes and, consequentially, the predicate value. Whenever the predicate value changes, the program must send a notification about this change.
For example, consider that there is an object A which has an attribute called name and consider that there is a predicate P which is true when the object's name is equal to Jhon.
Each event in the stream has a timestamp and a value for the attribute name. So consider the following sequence of events:
e1 = { name: Jhon, timestamp: 1 }
e2 = { name: Jhon, timestamp: 2 }
e3 = { name: Peter, timestamp: 3 }
e4 = { name: Doug, timestamp: 4 }
e5 = { name: Jhon, timestamp: 5 }

In this problem the events have a total order relation: If you have two events you always can say which one is the oldest of them.
Now, the events don't necessarily show up in the stream in the correct order according to its timestamp. Each event is unique to its timestamp, so there are no two or more events with the same timestamp for the same object. Also, the timestamps don't necessarily form a sequence that always increase by one: if we see e1 with timestamp 1 and e3 with timestamp 3, it doesn't imply the existence of e2 with timestamp 2.
There is no guarantee that all events will be received or when they will be received. It's part of the problem that we only know about the existence of the events that we see in the stream.
The real scenario is even worse: there are multiple computers parallelly processing this stream of events. However, for simplicity, I'll go further in this example considering only one computer.
If the events arrive and are processed in the order described above, then the notifications sent should be:
P(A) = true when e1 arrives
P(A) = false when e3 arrives
P(A) = true when e5 arrives.

That is the correct sequence of notifications because it respects the timestamp order.
Now, imagine that the computer receives the events in the following order:
e1, e5, e2, e4, e3

A naive algorithm which doesn't consider the event's timestamp would send an incorrect sequence of notifications:
P(A) = true when e1 arrives
P(A) = false when e4 arrives

The algorithm that I'm working on considers the timestamps and infers when a notification should have been sent but was not. So when e3 arrives it will notice that the notification P(A) = true for e5 was not sent.
This feels a bit like reinventing the wheel, though I'm not aware of any reading about this problem.
I would like some references to this problem or to something similar, like some papers dealing with this kind of problem.
The real problem is quite more complex since it involves storing the predicate $\times$ object state in a database that works as a shared state between the computers processing the stream and I'm talking about thousands of events arriving per second so it's not possible to keep all events stored in some database.
Is there any literature about the problem that I have described? if so, could you give me links to it?
I would like to see a paper or a text that explains an algorithm that solves this problem and it would be even better if such paper provides proofs about the algorithm (e.g. correctness).
If such paper doesn't exist (I actually think that is the case), I would accept an answer that describes an algorithm and provides an argument or a proof about its correctness.
For this algorithm to be correct, it should always send the correct sequence of notifications no matter what order that events arrives.
And the algorithm shouldn't keep all the received events in memory, because the real problem deals with too many events to save in memory or to store in a DB.
It would be reasonable to keep some events in memory, preferably a fixed amount.


texts: HashTable open-addressing is used for main array or buckets

texts:
I am trying to understand the HashTable open-addressing technique. I see there are three approaches: linear, quadratic and double hashing. I'm wondering are these techniques used:

to find an index of the main array and no bucketing is involved
or used when our buckets are arrays too and we are trying to add it to the bucket and we are not sure where to add.

Thanks in advance.


texts: Finding the half with greatest elements in a set

texts: Given an array with $2n$ elements, we want to select the greatest $n$ elements, i.e. obtain new array with these elements, no matter of the ordering (it's not necessary to be sorted). Can we do this in $O(n)$ time?


texts:
Ok, I've found a good example
But it doesn't really answer my question.
Simple Example
We have a 8 two-word blocks. So we have an offset of 1 bit.
Say we  have two references 33 and 32.
Ref His/Miss  Addrs        Tag       Index
33   miss     0001 0001    0010      000
32   ???      0010 0000    0010      000

what happens at 32 ????
we have the exact same tag and index so we have a hit. But it's not the same reference? I'm confused.


texts: Find shortest paths in a weighed unipathic graph

texts:
A directed graph is said to be unipathic if for any two vertices $u$ and $v$ in
the graph $G=(V,E)$, there is at most one simple path from $u$ to $v$.

Suppose I am given a unipathic graph $G$ such that each edge has a positive or negative weight, but contains no negative weight cycles.

From this I want to find a $O(|V|)$ algorithm that finds all the the shortest paths to all nodes from a source node $s$.

I am not sure how I would go about approaching this problem. I am trying to see how I could use the fact that it contains no negative weight cycles and of course at most one simple path between any node $u$ to $v$.


texts: Prove that the language is not regular without using Pumping Lemma

texts:
I am practising problems on Regular Languages and I came across this question:

  Prove that the language $$\{a^m b^n : m ≥ 0, n ≥ 0, m \ne n\}$$ is not
  regular. (Using the pumping lemma for this one is a bit tricky. You
  can avoid using the pumping lemma by combining results about the
  closure under regular operations.)

I have tried to prove it using pumping lemma in the following way:
Let p be a sufficiently large integer, then we construct the string:
$$s = a^pb^{p + p!}$$
Now by pumping lemma conditions, the string $s$ can be written as $xyz$ where $|xy| \le p$. Hence $xy$ contains only $a$'s.
If we choose any substring $y$ of length $k \le p$ from $xy$, we can always find a $C$ such that
$$p+C*k = p + p!$$

We can also prove it if we choose $s$ to be just the single character string $a$ and then we pump down.

Q1. Please let me know if there is a flaw in the above proofs.
Q2. How can closure properties be applied to prove the above? Till now I have applied closure properties to prove regularity, but never the converse.


texts: Give a Context Free Language, is the complement of this language always recursive(REC)?

texts:
I have seen some people make an argument that given the fact that Context Free Languages are proper subset of REC which is closed under complementation thus complement of a CFL must be in REC. I cannot wrap my head around this argument.

What I know about a CFL(say L) is that the complement of this CFL(say L') need not necessarily be a CFL. This creates fair bit of skepticism about nature of such a complement in my head and makes me feel that there is a possibility this complement L' could fly off anywhere in Chomsky Hierarchy as long as it is not a CFL. Why would it be restricted to REC?

In my head, I find myself coming up with arguments like following:
"Every CFL is in RE and complement of an RE need not necessarily be RE and thus need not necessarily be REC! Thus there could be CFLs whose complements are not in REC.
"
or
"Complement of a CFL may fall under RE and there are RE languages which are NOT REC. Thus there is a possibility that a certain complement may not be in REC"

Thread like : What is complement of Context-free languages?
did not answer my question.


texts: Calculating attributes' values in the semantic analysis stage

texts:
I'm reading through the book : "Compiler Construction: Principles and Practice". In chapter 6 : semantic analysis, an example about attribute grammars is given. The example is of a simple integer arithmetic expressions (I posted a picture because different fonts means different things as you may know):

where the bold Courier font is a token and the Times New Roman is grammar.

Now this parse tree represents the expression: (34-3)*42 which is 1302. I know that every attribute rule corresponds with a grammar rule, and we're actually starting with the rule exp->term because it is what it fits the given expression, but I just don't understand how did the compiler know the value in the first place? When was the value computed? How does the compiler start implementing the semantic analysis? did it start from the bottom where the number token is? I hope I made it clear.


texts: Understanding an example of an EXP-SPACE Problem

texts:
I am trying to understand the example given here of an EXP-SPACE time decision problem.

They write :

  An example of an EXPSPACE-complete problem is the problem of
  recognizing whether two regular expressions represent different
  languages, where the expressions are limited to four operators: union,
  concatenation, the Kleene star (zero or more copies of an expression),
  and squaring (two copies of an expression)

Here is what I understand. Supposing I have some alphabet $\Sigma = \{a,b,c...,z\}$, then a regular expression
is a pattern in order to specify the set of strings that belong to some language.

So for instance if I have two regular expressions, say

$aa+a^{*}+bb^2$ then any string that satisfies this expression is in $L_1$ (language 1),

$abc$         then any string that satisfies this expression is in $L_2$

Why does determining if these languages are the same in the worst case take exponential space. Further what is the size of the input ? I imagine it could be the sum of lengths of the two reg-expressions, but I am not sure.

Edit: If the Kleene star criterion is dropped, then I could see that we could simply create a set with all possible strings (the power set), and then compare the two sets, not sure about the input size however.


texts: Definition of liveness property in model checking

texts:
A property $P$ is simply a set of sequences of states and a certain program is characterized by its set of sequences of states, let's call it $T$. A program is compliant to a specific property P if $T\subseteq P$.

Intuitively, a specific liveness property LP1 is the set of traces (sequences of states ) in each of which "something good" will happen, based on the specific property LP1 (for example "termination"). This means that if a program it's compliant with LP1 in each of its traces the "good thing" will happen, that is the program will terminate.

However, I don't understand how the formal definition of liveness property contains what was said, can you explain me? This definition to me makes no sense (i know all the terminology)...

$\forall t\in S^{*}\,(\exists t'\in S^{\omega }:t\leq t^{'}\wedge t^{'}\in LP1)$


texts: Traveling Salesman Problem with profit and time limit as ILP formulation

texts:
How to formulate the following problem?

The salesman gains a profit $p_{i}$ when visiting a city i, trip between city i and city j costs $c_{ij}$ and takes $t_{ij}$ time. The trip must not exceed a time limit T. The difference between profit and costs must be maximized.

I've formulated this problem as follows:

maximize $\sum _{i=1}^{n} \sum _{j=1}^{n}p_{ij}x_{ij}- \sum _{i=1}^{n} \sum _{j=1}^{n}c_{ij}x_{ij}$

can i formulate trip time as $\sum _{i=1}^{n} \sum _{j=1}^{n}t_{ij}x_{ij}$ and add the constraint $\sum _{i=1}^{n} \sum _{j=1}^{n}t_{ij}x_{ij} \leqslant T$?

I've read also about the Time Dependent TSP (TDTSP), but i'm not sure it's my case...


texts: Seems like NP cannot equal coNP by the definition of NP

texts:
A yes answer to an NP problem must be deterministically verifiable in polynomial time. The complement is that the no answer must be similarly verifiable. If the problem is NP-complete, there will generally be an intractable number of possibilities. How can it be possible to deterministically verify the no answer  for all possibilities in polynomial time?

As an example, would it not be necessary to address every non-empty subset to verify a no answer for the subset sum problem?


texts: Construct non-recursive predictive parser for grammar $S \to Aa \mid b A c \mid Bc \mid bBa, A \to d, B \to d$

texts:
In the grammar for S production two bodies have same starting symbol

$ S \to Aa \mid b A c \mid Bc \mid bBa $

So i removed the left factoring from those two productions

$ S \to bC$

$ C \to Ac  Bc$

Then I calculated first and follow for all of them. Then i constructed parse table, but for the entry on state S when input symbol is d there are two possible productions

$ A \to d$

$ B \to d$

I don't have much knowledge about what to do when there is a conflict in the entry for this table, if I'm completely wrong please help me to find solution


texts: Can reducing NP problems to subset NP Problems leed to faster calculation of NP problems

texts:
Integers can be represented with a pair of smaller numbers. To achieve this I use 2 integer sequences.

Integer Sequence 1

1,1,2,1,2,3,1,2,3,4...

And Integer Sequence 2

1,2,1,3,2,1,4,3,2,1...

This gives me a unique pair of smaller integers for every given integer N
Like So

1={1,1},2={1,2},3={2,1},4={1,3},5={2,2},6={3,1}..

I've noticed that when reducing 3-Sat to Clique problems you can make 2 simpler 3-sat problems that combine to resolve the main problem.
for example..

3 Sat Problem 1.
(x1 or !x2 or x3) ^ (x1 or x3 or !x4) ^ (!x1 or !x2 or x4)

is equivalent to

3 Sat Problem 2a and 2b

(x1 or !x1 or x2) ^ (x1 or x2 or !x1) ^ (!x1 or !x1 or x1)

and
(x1 or !x2 or x1) ^ (x1 or x1 or !x3) ^ (!x1 or !x2 or x3)

If you reduce problems 2a and 2b into 2 clique problems then overlay the two solutions onto a clique reduction of the first problem they match up.

Not only that but you can keep reducing till your only working with 2 x  variables in any given problem subset.

So you could reduce the problem further to 4 subset problems.

Is it possible any of these findings might speed up NP problem solving.
to re-phrase the question.

If I break what I am preposing down into 2 parts the time it takes to convert the 3 sat problem with lots of variables into 2 variable problems and what compute space finding any cliques in a 2 variable 3 sat takes at most.
I can already estimate quite well how long it's going to take to get the roughly 2*Log[2,n] output 2 variable 3sat problems.

So what I really want to know is how quickly can you computer 2 variable only 3sat problems or where I might find the latest big O or what compute space it's in.


texts:
I have a following problem:

Given a set $S$ consisting $N$ triangles (possibly overlapping). Answer queries (online) of the form: given a point $P$ is there a triangle $T$ in $S$, such that $P$ lies inside $T$?

I am interested in solution (data structure) which:

$*$ Answer query faster than $O(N)$ (worst case)

$*$ Preprocesses triangles faster that $O(N^2)$ (worst case)

Problem looks classic, but I am new to computational geometry.


texts: Reduction of SUBSET-SUM to SET-PARTITION

texts:
There is a similar question that has been asked, but my question addresses particular detail of an answer.

I am trying to reduce SUBSET-SUM to SET-PARTITION. I found the following description:

SUBSET-SUM is defined as follows: Given a set X of integers and a target number t, find a subset Y from X such that the members of Y add up to exactly t. Let s be the sum of members of X. Feed X' = X U {s - 2t} into SET-PARTITION. Accept if and only if SET-PARTITION accepts.

What does "X' = X U {s - 2t}" (union?) and "Feed X' = X U {s - 2t} into SET-PARTITION" mean? How does this prove that SUBSET-SUM can be reduced to SET-PARTITION?


texts:
I have seen in some ML tutorial that functions of the form $f(\vec x) = \vec x^T A \vec x$ ($\vec x \in \mathbb{R}^n$ and $A$ is an $n\times n$ real matrix) can be PAC learned.

Can anyone point me to a reference to this fact?


texts: Is there a guaranteed min-cut algorithm for weighted graph or weighted cyclical digraph?

texts:
I'm looking for find the min-cut of a fully-connected directed graph (with cycles), or an undirected graph.

Karger's works but is not guaranteed to produce the correct solution. Is there a guaranteed algorithm?

I came across max-flow algorithms. Do these only work if the graph is acyclic?

Thanks.


texts: When there's no memory, should malloc or read/write fail?

texts:
To my surprise, I recently found out that Windows would fail a large memory allocation even if little of said memory is to actually be used, e.g. even if you don't want the swap, you better not disable it.  http://brandonlive.com/2010/02/21/measuring-memory-usage-in-windows-7/  (Basically, in Windows 7, Windows Task Manager, Performance, System, Commit, -- the sum of the physical memory plus the swap file is depicted, and a mere allocation of 2GB will immediately grow the figure by 2GB, unless such growth is restricted (e.g. if the page file is disabled), then the whole allocation would fail.)

I recall that it's also the case with OpenVZ virtualisation, which behaves the same way, thus being incompatible with Java, for example.  However, I never really heard of anything like that in regards to the virtual memory of other operating systems, like FreeBSD, OpenBSD or non-OpenVZ Linux (which doesn't necessarily mean that they don't behave the same).

What's the history behind such behaviour, and how the popular systems generally behave in such situation?  I mean, isn't virtual memory supposed to be unlimited on any system?


texts:
I'm taking a course on Coursera about approximation algorithms for fun and one of the modules uses probability to analyze the cost of a linear program with randomized rounding solution to the set cover problem.

One of the techniques employed is Wald's equation for dependent decrements, described in Neal Young's Notes on algorithms.

For Alice's coin-flipping example, can somebody please describe to me how $\delta$ is increasing if it's chosen to be $\delta(n_t) = \frac{1}{2} \lceil n_t \rceil$? As the number of coins left decreases doesn't $\delta(n_t)$ also decrease?

Clearly there's something missing in my understanding of how this works.


texts: Correctness proof for greedy algorithm based on ratio

texts:
I've an issue stated as follows:

  We have 10000 jobs to do, each with some length $l_i$ and weight
  (importance) $w_i$. Our goal is to arrange the schedule of doing these
  jobs (in other words, the order of doing jobs) in such way that
  minimizes the weighted sum of completion times

For this, I'm using the ratio greedy algorithm, that is ratio weight/length to order the jobs, and it is working fine. But now I've to do its correctness proof and I'm stuck with it.


texts: Dana Angluin's L* algorithm - Hypothesis inconsistent

texts:
is it possible for the Dana Angluin's L* algorithm that a hypothesis is inconsistent?

So assume we have a closded observation table for a regular language L. Now after creating the hypothesis we will get a counterexample w.

The Question is: Can the counterexample w be chosen in the hypothesis, so that I have two times the same counterexample?

Unfortunetaly I could not find any language and counterexample where it will work.


texts: What is the fastest way to bytewise examine the contetnt of quadword

texts:
I have the following byte: 0x0A and I need to test if a quadword contains it or no using standard bitwise operarion (or, nor, xor). For instance:

0x1689FFBB768922AC ---> false
0x106489320A792399 ---> true

Unfortunately I cannot use intel SSE2 extension because this will make the code heavily depndent on the platform.

Can we find some bitmask to bitwise or with? Or maybe something else...?


texts: Why use $\mu$-calculus and not LTL,CTL,CTL*?

texts:
It is known that the temporal logics LTL,CTL,CTL* can be translated/embedded into the $\mu$-calculus. In other words, the (modal) $\mu$-calculus subsumes these logics,
(i.e. it is more expressive.)

Could you please explain/point me to papers/books that elaborate on this matter.
In particular, are there concrete fairness, liveness, etc. properties not expressible in the temporal logics but in the $\mu$-calculus?


texts: Online bipartite edge-cover problem with requirements

texts:
I have $N$ nodes $v_1,\ldots,v_N$ in one partition $X$ and $M \leq N$ nodes $u_1,\ldots,u_M$ in a different partition $Y$. I want to connect nodes in $X$ to nodes in $Y$ with edges under the following constraints:

Each node in $X$ must be connected to at most $k$ nodes in $Y$
For each node $v_t$ there is a node $u_{f(v_t)}$ that it can not be connected to.
I want to do it in an online fashion: I will get a stream of nodes from $X$ and then immediately connect that node to a node in $Y$. This edge can not be removed.
After processing each node in the stream, then the difference between the maximum degree of nodes in $Y$ and the minimum degree of nodes in $Y$ should be as small as possible.

In a simple case of the problem, assume that $N = M$ and that $f(v_t)=t$.

Doing this in trivial ways lead to situations where I can end up with a difference of 2 in degrees for small examples.

Edits to address comments:

Comment: I don't understand what the inputs are and in what order they are presented. What does it mean to "get a node"? What information is provided along with that node? Also, what do you mean by "After ..., the difference should be as small as possible"? Does this mean that there are two phases: the first phase is to find edges that provide at least kk-connectivity; the second phase is to add more edges to minimize the difference in degrees? If so, this seems like it should be split into two separate questions, as those phases seem independent.

By "getting a node", it means you are given an index $i$ of referring to the node $v_i$ in $X$. "After" refers to when the stream of nodes ends. It was not clear in my original question that in this stream of nodes, each node $v_i$ will appear exactly $k$ times. For $N=3$ and $k=2$, this might look like $v_1,v_3,v_1,v_2,v_2,v_3$.

Comment: It might be interesting to describe these trivial ways you're talking about.

Sure. Say that our algorithm for selecting which node in $Y$ to connect a node (in $X$) to is the following: Take the node in $Y$ which has the lowest degree. If there is a tie, take the one with the lowest index ($u_1$ before $u_2$ for example).

Let $N=3$, $M=3$ and $k=1$ and the stream of nodes/indices be $v_1,v_2,v_3$. Let $f(v_t)=t$. For the first node $v_1$, we connect it to $u_2$ (since $v_1$ can't be connected to $u_{f(v_1)} = u_1$, all edges have degree 0 and since we tie-break by lowest index). Next $v_2$ gets connected to $u_1$ (since it can't be connected to $u_2$ and since $u_1$ and $u_3$ have degree 0 and $u_1$ has the lowest index). Finally $v_3$ gets connected to $u_1$ since it can't be connected to $u_3$, and since $u_1$ and $u_2$ both have degree 1.

In this case, we end up with $\text{degree}(u_1)=2$, $\text{degree}(u_2)=1$ and $\text{degree}(u_3)=0$. A better strategy would have been to connect $v_1$ to $u_2$, $v_2$ to $u_3$ and $v_3$ to $u_1$.


texts: Universal hashing - insert / search / delete

texts:
I don't understand the highlighted text below in CLRS 3rd Ed.:

I'm not sure I even understand what the sentence is trying to say. For example:

What do they mean by "... operations containing $\mathcal{O}(m)$ INSERT operations"?  Which operations contain which?
If the (total) expected time is $\Theta(n)$ how can any of these operations contain other $\mathcal{O}(m)$ operations?


texts:
I was recently going through the Wiki page List of unsolved Problems in Computer Science.

There was a problem which I do not understand

  Do one-way functions exist ? [Is public-key cryptography possible ?]

A one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input.

A one-way function that comes to mind is a Cryptographic hash function which is used to create message digests. Where size of the message digest is relatively small as compared to the size of the message and hence it becomes very hard to reconstruct message from the message digest.

So, why does the above problem say that these functions do not exist?


texts: Why do Google Deepmind images always look the same?

texts: There is a certain sameness to google deep mind images. Why do they always look like a bad tool album cover?


texts: Why does arithmetic left shift of negative number leads to positive number?

texts:
According to this Wikipedia article, when arithmetic left shift operation is applied to a signed number, the number is multiplied by 2. But there are certain situations where a negative number becomes a positive number when an arithmetic left shift is applied.

Eg.: Take a 2's complement signed integer -5 and 5 bits are used to represent it.

11011 ==> -5
10110 ==> -10 (-5x2)
01100 ==> +12 (?)

So after two arithmetic left shifts -5 became 24. I expected -20. Why is this the case?


texts: When can the coinduction hypothesis be used?

texts:
We can use the induction hypothesis when we are proving a property for a structure that is well-ordered. I am aware that there is a proof for this.

When it comes to coinduction, I'm confused.

One of the answers to another question "What is coinduction?" mentions that there is a notion of a corecursive definition to be well-formed.

A lot of things I (try to) read related to coinduction mostly talk about bisimulation and equivalence. But to the best of my knowledge, those are trying to prove some relationship for two coinductive data structures. For example, they prove that two streams are equivalent. And the coinductive hypothesis is somehow derived from one of the bisimulation's hypothesis. Even so, I think I'm still lost on the requirements of what constitutes well-formedness in the coinductive world.

I can somehow see that the coinduction hypothesis works when proving those kinds of propositions, but I'm still unclear when they can be used to prove more general propositions such as the one mentioned in What is coinduction?. In that link, the proposition states that "something is infinite". This seems like a more generic form of statement one would be interested in proving.

A possibly related question is whether any proposition can be converted and re-stated as a proposition of equivalence or not.

Is there some simple informal reasoning that talks why co-induction works for some well-formedness requirement?

I'm hoping for an explanation like if possible: https://math.stackexchange.com/questions/432293/well-ordering-and-mathematical-induction/432302#432302.


texts: Let $G = (V, E, W)$ be a weighted graph with positive and negative weights. I would like to find the set of vertices $V^\prime$ such that the sum of the weights of the edges that they share is the maximum you can get from $G$. I suspect that this is an NP-complete problem, so my question is whether this can be reduced to a known NP-complete problem. Since $V^\prime$ does not necessarily have to be the minimum subset that satisfies the constraint, I think I can't use the solutions for the vertex/set cover problems, so any ideas would be welcome.


texts: Prove that every undirected connected graph with $|V | > 2$ results in a connected graph if two vertices removed..

texts:
How do I go about proving this?

Prove that every undirected connected graph with $|V | > 2$ has at least two vertices such that if one or both are removed (along with their incident edges) the resulting graph is still connected, and describe an efficient algorithm to find two such vertices.


texts: Prove Recursive formula (Dynamic programming) N(C,i)

texts:
I've been asked to prove the correctness of the following recursive formula. The formula is trying to define, how many ways you can spend your money C on the i amount of beers. I did the following recursive formula where you either bought a beer and losing $P-i$ money, or passed the beer and went for the next in the array $i-1$. You cannot buy the same type of beer twice.

$$N(C,i)=\begin{cases}
    0       & \quad \text{if } C<0\;||\; i<0 \\
    1       & \quad \text{if }  C=0\\
    N(C,i-1)+N(C-P_i,i-1)  & \quad otherwise
  \end{cases}
$$

I'm not certain how to prove the correctness of the algorithm. Especially because the assignment is about dynamic programming, and I can't find any repeated subproblems. The amount of money you will have will differ unless some of the different beers cost the same. I asked a fellow student who said the problem will always give overlapping subproblems.

The problem has also been talked about here (Making a recursive formula for finding amount of ways to spend money on beer), but I think my recursive formula is correct.

Sorry, if the question is unclear, or if I've done something wrong. It's the first time on stackexchange, and I think, this is the place to ask the question and not the mathmatics site.


texts: Showing that a binary linear code $C$ is self-dual

texts:
Let $C*$ be the length 8 binary code obtained by adding a parity check symbol to each word in $C$. (so a word $c_1, c_2, c_3, c_4, c_5, c_6, c_7$ is extended to  the word $c_1, c_2, c_3, c_4, c_5, c_6, c_7, c_8$ for which $\sum_{i=0}^8 c_i =0$. Show that $C*$ is self dual (I.e show that $C*=C*^{\bot}$.

Where $C*^{\bot}$ is the orthogonal complement of $C*$

I am given the generator matrix for $C$:

$$G= \begin{bmatrix}
    1 & 1 & 0 & 1 & 0 & 0 & 0 \\
    0 & 1 & 1 & 0 & 1 & 0 & 0  \\
    0 & 0 & 1 & 1 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 & 1 & 0 & 1
\end{bmatrix}$$

So I think $C*$ is given by:

$$G*= \begin{bmatrix}
    1 & 1 & 0 & 1 & 0 & 0 & 0 & 1\\
    0 & 1 & 1 & 0 & 1 & 0 & 0  & 1\\
    0 & 0 & 1 & 1 & 0 & 1 & 0 & 1\\
0 & 0 & 0 & 1 & 1 & 0 & 1 &1
\end{bmatrix}$$

I can show  $C*$ and $C*^{\bot}$ have the same dimensions but don't know what to do from here.


texts: Find 8 numbers whose sum is closest to a defined value

texts:
I have a file that has a number (a positive integer) on each row.

Given a number $q$, I want to find a value that's a sum of some 8 numbers in the file, and is as close to $q$ as possible.

So, supposing that I have a file that looks like this:

  345
  3
  2
  3453
  1234
  6
  7
  34
  12
  1111
  48
  413

If the given number is 526 I would like to get a solution like:  3+2+6+7+34+12+48+413 = 525. So those are the 8 numbers that best fit our condition.

Is there an efficient algorithm with a low complexity?

The file can have >1000 rows and the numbers won't be bigger than 10k.


texts:
My teacher told us that when the ram runs out of space it will push a program in the cache, i argued that the program should go to the swap space in the hard drive, plus the memory cache cannot hold instructions because instructions and data have different access patterns, it can only hold data frequently accessed.
So i am asking the experts, can the memory cache hold instructions ?
Edit : what i mean by memory cache is the L1 memory cache


texts: Problems Implementing Closures in Non-functional Settings

texts:
In programming languages, closures are a popular and often desired feature. Wikipedia says (emphasis mine):

  In computer science, a closure (...) is a function together with a referencing environment for the non-local variables of that function. A closure allows a function to access variables outside its immediate lexical scope.

So a closure is essentially a (anonymous?) function value which can use variables outside of its own scope. In my experience, this means it can access variables that are in scope at its definition point.

In practice, the concept seems to be diverging, though, at least outside of functional programming. Different languages implement different semantics, there even seem to be wars of opinons on. Many programmers do not seem to know what closures are, viewing them as little more than anonymous functions.

Also, there seem to exist major hurdles when implementing closures. Most notable, Java 7 was supposed to include them but the feature was pushed back to a future release.

Why are closures so hard (to understand and) to realise? This is too broad and vague a question, so let me focus it more with these interconnected questions:

Are there problems with expressing closures in common semantic formalisms (small-step, big-step, ...)?
Are existing type systems not suited for closures and can not be extended easily?
Is it problematic to bring closures in line with a traditional, stack-based procedure translation?

Note that the question relates mostly to procedural, object-oriented and scripting languages in general. As far as I know, functional languages do not have any problems.


texts: How can an approximation ratio be less than 1?

texts:
A question in my algorithms text-book requires that we,

  Describe an efficient $(1 - \frac{1}{k})$ -approximation algorithm for this
  problem.

It is my understanding that $(1 - \frac{1}{k})$ being $p(n)$ is the approximation ratio and that an approximate solution differs from an optimal solution by a factor of $p(n)$. In that case, if $p(n)< 1$ wouldn't the approximation be better than optimal?

How can the approximation ratio be less than $1$?


texts: Finding a source of a directed acyclic graph in linear time

texts:
Given a directed acyclic graph $D = (V,A)$, a vertex $v \in V$ is a source if its indegree is zero, meaning that it has only outgoing arcs.

Does there exist a linear time algorithm to find a source in a given directed acyclic graph?

Follow-up question:  Can one in linear time find all sources?


texts:
I'm supposed to write grammar for this language: $$L=\{a^{i+1}b^{i}c^{2j}d^je^{2j}\mid i,j>0\}$$
This is what I have so far:
$$\begin{align}
S &\to aXbY \; \\
X &\to aXb \;|\; a \\
Y &\to ccYdE \;|\; ccdE \\
Ed &\to dE \; \\
dE &\to dee \; \\
eE &\to eee \; \\
\end{align}$$
Edit:
Thank you for answers, I looked at the https://en.wikipedia.org/wiki/Noncontracting_grammar#Example and edited my grammar:
Is this correct? Is it necessary to do
$$\begin{align}
Ed &\to dE \; \\
dE &\to dee \; \\
eE &\to eee \; \\
\end{align}$$
or can I just do
$$\begin{align}
Ed &\to dee \; \\
E &\to ee \; \\
\end{align}$$


texts: What is the correct way to determine the width and depth of a count-min sketch?

texts:
The width (number of registers) and depth (number of hash functions) of a Count-Min sketch determine the accuracy of counts retrieved.

I've found two different methods for calculating the width ($w$) and depth ($d$).

First Method

The clearest example I've found is from a 2011 paper by the original Count-Min authors:

  Suppose we want an $\mathrm{error}$ of at most $0.1%$ (of the sum of all frequencies), with $99.9%$ $\mathrm{certainty}$. Then we want $2/w = 1/1000$, we set $w = 2000$, and $(1/2)^d = 0.001$, i.e. $d = \log 0.001/ \log 0.5 ≤ 10$.

From which I deduce that:

$w = \lceil 2/\mathrm{error}\rceil$

$d = \lceil \ln(1-\mathrm{certainty})/\ln(1/2) \rceil$

The description of Count-Min in Real-time Analytics (page 357) states:

  In the original Count-Min paper, the authors show that the probability that the estimate of an element is between its true value $x$ and an upper bound $x + em$, where $m$ is the number of elements entered into a [Count-Min Sketch], is larger than $1-d$ under two conditions. The first condition is that the width of the sketch is $2/e$. The second condition is that the depth of the sketch is $(\log 1/d)/\log 2$. So, a Count-Min sketch where the estimate is within $5$ percent of the sum with a $99$ percent probability would have a width of $40$ and a depth of $7$. A depth of $8$ with a width of $128$ would have a relative error of approximately $1.5$ percent with a probability of approximately $99.6$ percent.

From which I deduce that (with $\mathrm{error}$ and $\mathrm{certainty}$ defined as above):

$w = \lceil 2/\mathrm{error} \rceil$

$d = \lceil \ln(1/(1-\mathrm{certainty}))/\ln(2) \rceil$

Which is equivalent to the first method, merely being a rearrangement of the logarithms.

And, for what it's worth, the implementation of Count-Min within stream-lib also uses an equivalent method:

$w = \lceil 2/\mathrm{error} \rceil$

$d = \lceil -\ln(1-\mathrm{certainty})/\ln(2) \rceil$

Second Method

Wikipedia, however, gives the following:

  The parameters $w$ and $d$ can be chosen by setting $w = ⌈e/ε⌉$ and $d = ⌈\ln 1/δ⌉$, where the error in answering a query is within a factor of $ε$ with probability $δ$.

Which is seemingly extracted from a 2009 paper by one of the original Count-Min authors (Theorem 1, on page 2).

From this I deduce that (with $\mathrm{error}$ and $\mathrm{certainty}$ again defined as above):

$w = \lceil e/\mathrm{error} \rceil$

$d = \lceil \ln(1/(1-\mathrm{certainty})) \rceil$

This does not seem to be equivalent to the first method (and gives different results if I implement it).

Due to the volume of evidence I'm guessing that the first method is the correct one, but is it? Are there subtle differences between them that I'm not understanding?


texts:
Today at lunch, I brought up this issue with my colleagues, and to my surprise, Jeff E.'s argument that the problem is decidable did not convince them (here's a closely related post on mathoverflow). A problem statement that is easier to explain ("is P = NP?") is also decidable: either yes or no, and so one of the two TMs that always output those answers decides the problem. Formally, we can decide the set $S :=\{|\{P, NP\}|\}$: either the machine that outputs $1$ only for input $1$ and otherwise $0$ decides it, or the machine that does so for input $2$.

One of them boiled it down to basically this objection: if that's how weak the criterion of decidability is - which implies that every question which we can formalize as a language that we can show to be finite is decidable - then we should formalize a criterion that doesn't render any problem with finitely many possible answers that's formalizable in this way decidable. While the following is possibly a stronger criterion, I suggested that maybe this could be made precise by requiring that decidability should depend on being able to show a TM, basically proposing an intuitionist view of the matter (which I don't incline towards - nor do any of my colleagues, all of them accept the law of excluded middle).

Have people formalized and possibly studied a constructive theory of decidability?


texts: Sorting tuples with respect to multiple criteria

texts:
Given $n$ rows with $k$ columns, is there a storage mechanism/data-structure and/or algorithm that enables dynamic restructuring such that I can get the top $t=\mathcal{O}(1)$ results efficiently?

Example strategy 0

$$k_0 \le k_1 \le \cdots \le k_{n-2} \le k_{n-1}$$

Example strategy 1

$$k_{n-1} \le k_{n-2} \le \cdots \le k_1 \le k_0$$

Given [ [0,1] [2,3] [1,2] ] strategy 0 returns: [ [0,1], [1,2] ], where $t=2$.

Restructuring with strategy 1 returns: [ [2,3], [1,2] ]. New strategies can be provided "at runtime".

Given a data-structure solution, here are the methods that it should expose:

insert_row (*row) -> inserts a row of $k$ elements into the structure
delete_row (*row) -> delete the precisely specified row from structure
new_strategy(*k_prioritisation) -> rebalances the structure given the specified strategy
top_rows() -> provides top rows after a strategy has been "installed". Number of rows to return is specified at compile time (as a source-code constant).

PS: Bonus points if you can enables strategies like $k_0 \le [\text{all other } k \text{ except } k_0]$, with embedded strategies of much the same.


texts: Implementing Deterministic Turing Machine

texts:
If i want to implement a Deterministic Turing Machine from a Non-deterministic Turing machine is always suggested to use the Breadth-first algorithm ?
If yes, why ?


texts: Can the shortest simple cycle between two given nodes be found in polynomial time?

texts: Given an undirected simple graph $G$ and two nodes $s$ and $t$, the question asks for an algorithm to find the shortest simple cycle (no edge or vertex reuse) that contains the two. As far as I know, the problem is NP-complete if the two constraint were changed to arbitrary, but what if the number is given?


texts: As part of my continual improvement plans, I'm reviewing algorithm analysis and I've hit a roadblock. I cannot figure out how to determine the Big O complexity of $\log(n+7)^{\log(n)}$. I've spent the last few days rolling this over in my head and I still haven't made any progress in solving it. Could someone tell me what the Big O of this algorithm is, and explain how you solved it?


texts: Prove that { ⟨M⟩ ∣ ⟨M⟩ ∉ L(M) } is undecidable

texts:
Prove that $L = \{\langle M \rangle \mid \langle M \rangle \notin L(M)\}$ is undecidable. Hint: If there were a decider TM DL for L, what would happen if we gave DL its own description as input?

Here's what I've got so far:

$\mathrm{ATM} ≤_M M$ (with $\leq_M$ being mapping reducible)

Find a map : $f: \langle M \rangle \to \langle DL \rangle$
such that DL doesn't recognize w if and only of x is M's own description.

DL(w):
 if w != description:
    run on M(w)
    if M(w) accepts:
       return accept

I couldn't figure out how to relate DL to ATM to prove that L is unrecognizable. My answer might be partially wrong, but I tried my best.
Any help is appreciated.


texts: If 3SAT reduces to its complement then PH=NP

texts:
In Chapter 5 of the Arora–Barak complexity theory textbook we are asked to prove the following statement:

  If 3SAT is polynomial-time reducible to its complement then PH=NP.
  How do I prove this statement?


texts:
Some of the MIPS processors like 5kc, 5kf have "limited dual issue". Searching online it seems that this means that the processor allows for a dual issue in only some selected cases, but it is not clear which ones these precisely are. Can someone elaborate on what "limited dual issue" exactly means ?

Further, came across another terminology around limited dual issue - asymmetric and symmetric. What does asymmetric limited dual issue mean ?


texts: Do lossless compression algorithms reduce entropy?

texts:
According to Wikipedia:

  Shannon's entropy measures the information contained in a message as opposed to the portion of the message that is determined (or predictable). Examples of the latter include redundancy in language structure or statistical properties relating to the occurrence frequencies of letter or word pairs, triplets etc.

So entropy is a measure of the amount of information contained in a message. Entropy coders are used to losslessy compress such a message to the minimum number of bits needed to represent it (entropy). To me this looks like a perfect entropy encoder would be all that is needed to losslessy compress a message as much as possible.

Many compression algorithms however use steps before entropy coding to supposedly reduce the entropy of the message.

According to german Wikipedia

  Entropiekodierer werden häufig mit anderen Kodierern kombiniert. Dabei dienen vorgeschaltete Verfahren dazu, die Entropie der Daten zu verringern.

In english:

  Entropy coders are frequently combined with other encoders. Previous steps serve to reduce the entropy of the data.

i.e. bzip2 uses the Burrows-Wheeler-Transform followed by a Move-To-Front-Transform before applying entropy coding (Huffman coding in this case).

Do these steps really reduce the entropy of the message, which would imply reducing the amount of information contained in the message? This seems contradictory to me, since that would mean that information was lost during compression, preventing lossless decompression. Or do they merely transform the message to improve the efficiency of the entropy coding algorithm? Or does entropy not correspond directly to the amount of information in the message?


texts: Assignment problem for compute mininum weight cycle cover?

texts:
I've read in multiple articles and books that the computation of a cycle cover
for a given graph is possible in polynomial time, since this problem can be
viewed as the assignment problem, which is a special type of matching problem.
It's written in the Algorithmic Aspects of Bioinformatics (Spring-2007) and in the Minimum-weight Cycle Covers and Their Approximability by Bodo Manthey.
I failed to find any article, page or book explaining how is it possible to view the computation of cycle cover as an assignment problem. It seems impossible to me, since the assignment problem is about bipartite graphs, and the cycle cover is about finding a spanning subgraph in a complete graph.


texts: Is there a data structure for efficiently searching a string that contains a given substring?

texts:
This question arose from a practical problem: given a set of texts, find one, which contains a given string (not word).

Let $S$ be a set of $n$ strings, and $l$ the length of the longest string in $S$. What will be the best data structure to efficiently search a string that contains a substring of length $k$ in $S$?

Sequential scan with Knuth–Morris–Pratt algorithm yields $O(n(l+k))$ searching complexity.
I thought maybe something similar to tries exists.


texts: Superset of another language and recognizability of turing machines

texts:
$L_1$ = $\{\langle M \rangle \mid M$ is a turing machine and $M$ halts on some string$\}$

$L_2$ = $\{\langle M \rangle \mid M$ is a turing machine and $M$ halts on all strings $\}$

a) Is $L_2$ a superset of $L_1$ ?

b) Is $L_2$ not co-recognizable and not recognizable ?

(without formally proving)

my attempt

$a)$ $L_2$ is a superset of $L_1$ since all strings are in $L_2$ whereas $L_1$ is some string

$(b)$ $L_2$ is not recognizable because, out of the infinite enumerations of strings, a single one could not halt disproving it from being recognizable.

For not co-recognizable: It can be written like this

$\bar{L_2} = \{ \langle M \rangle \mid M$ is a turing machine and $M$ loops on some string $\}$.

It's not possible to make a recognizer for loops so its instantly not co-recognizable. This is because looping means it never stops so to come up with a recognizer for anything to prove it loops is impossible since we are working with infinite combinations.

Not sure about it being a superset or not and my explanation for co-recognizable


texts: How to produce nonzero absolute differences between neighboring numbers on a circle as long as possible?

texts:
I apologize for the lack of an even better title. The main reason I couldn't find a better one is because I have a problem that I cannot find reference anywhere. I am pretty sure it has a name, but I'm afraid I simply don't know it.
I'm given an algorithm that starts with four numbers $a$, $b$, $c$ and $d$ which can be chosen freely.
After each iteration, the numbers are recalculated as shown in the following images. $a_{n+1}=|a_n-b_n|\ $, $b_{n+1}=|b_n-c_n|\ $, $c_{n+1}=|c_n-d_n|\ $, $d_{n+1}=|d_n-a_n|\ $ for all $n\gt0$.

After a certain amount of time, this algorithm always results in all four columns ending and remaining at 0. Or so it appears. You can quickly try it out by replicating it in Excel or any other spreadsheet program.
The goal is to choose the four starting numbers a, b, c and d in such a way, that the columns all jump to 0 after the 50th iteration or later.
I have difficulties understanding how one can outsmart this algorithm, i.e., to make this algorithm compute as many rounds as possible before reaching all 0's. I've tried a brute force method by simple giving a, b, c and d random numbers with maximum lengths of 30 digits. And then seeing how far I can get. I let my computer try that for eight hours last night and the best I came up with was 17 several times - so obviously pure random brute force will not work and I will need a more thoughtful approach.
I'd be glad about any ideas!


texts: When was the terminology *tracing collector* introduced to denote both mark-and-sweep and copy collectors

texts:
Automatic storage reclamation, aka garbage collection, comes in two
main families, sometimes cooperating: the reference count collectors
and the tracing collectors. I may develop specifics of each family if
there is demand for it but my question is about tracing collectors.

Tracing collectors, in their simpler form can be divided into
mark-and-sweep (possibly with compaction) and copy collectors (that
compact naturally). Historically, they seem to have been
considered distinct families in the first 10 or 20 years of the
development of garbage collection technology.

I am wondering when they started to become known as tracing collectors
forming a single family. When was the expression tracing collectors
first used to denote both mark-and-sweep and copy collection, and
possibly collectors mixing both technologies (as is often the case with
generational collectors).

Ideally, a reference to a paper introducing the terminology would be
the best form for an answer. Reference to a book is good too, if you can give the printing where it first appears, as books often evolve with successive printings. Specifying the page or giving a quote would be nice too.

Added after accepting the answer.

I am accepting the answer given by Pseudonym, as it is a very clear
answer, that seems to be as good as it will ever get (but who
knows?). What I mean is that it seems unlikely that an earlier date
will be found, sinve the Paul Wilson's 1992 survey is pretty
thorough. As I recall, the previous survey by Cohen in 1981 does not
allude to tracing or unification of copy and mark-and-sweep.

An interesting trivia is that the introduction of this concept is
exactly half-way between the first garbage collection paper in 1960 (as
far as I know) and now (early 2015), which give a kind of time measure
of conceptual evolution.

This first GC papers, to my knowledge, used reference counting and
were published in 1960. According to wikipedia, which cites  Jones,
Richard; Lins, Rafael (1996), Garbage collection: algorithms for
automatic dynamic memory management, Wiley, p. 40, ISBN
9780471941484:

  The first, though cumbersome and error-prone, reference counting technique was described by J. Gelertner, J.R. Hansen, and C.L. Gerberich [Gelernter et al, 1960] but the standard reference counting algorithm is due to George Collins [Collins, 1960].

To my knowledge, the first tracing GC is a mark-and-sweep
implementation for LISP published in 1964 in, Notes on implementing
LISP for the M-460 Computer, Timothy P. Hart and Thomas G. Evans,
pp. 191-203 in The Programming Language LISP, its Operation and
Applications, March 1964, published by Information International, and
reprinted by MIT press (though they seemed to have lost all memory of
it when I asked, a long time ago). It does use the name "garbage collector", but I do not
know whether that is the first occurrence in the computer literature.


texts: Where can I find an original reference for this integer square root algorithm

texts:
As an exercise, I converted an old method I learned for calculating square roots on a rotary decimal hand calculator to binary.

I'm sure this is not original; can anyone provide a reference?

// All arithmetic is truncating unsigned integer arithmetic
// Actual implementation uses bit shifts
// Indention level defines statement scope

def sqrt(r)                         // r is an unsigned integer
    residue = r                     // residue will be the 'remainder'
    root = 0                        // root will be the integer square root (floor(r**0.5))
    onebit = 2**(bitlength(r)-2)    // onebit is a moving 'bitpicker'
    while onebit > r
        onebit = onebit / 4         // find highest bitpicker less than r
    while onebit > 0
        x = root + onebit           // Current root plus onebit
        if residue >= x             // Room to subtract?
            residue = residue - x   // Yes - deduct from residue
            root = x + onebit       // and step root
        root = root / 2             // Slide evolving root 1 bit down the residue
        onebit = onebit / 4         // Slide the bitpick 1 bit down the root
    assert(root**2 + residue == r)
    assert((root+1)**2 > r)
    return root, residue


texts: Affine transformations for twisting and pinching

texts: In image processing we can use affine transformations for translation, rotation, shear and scaling of pixels. But what kind of transformations are used for twisting and pinching of image pixels? Or what is mathematical definition for this kinds of transforms?


texts: Micro-optimisation for edit distance computation: is it valid?

texts:
On Wikipedia, an implementation for the bottom-up dynamic programming scheme for the edit distance is given. It does not follow the definition completely; inner cells are computed thus:

if s[i] = t[j] then
  d[i, j] := d[i-1, j-1]       // no operation required
else
  d[i, j] := minimum
             (
               d[i-1, j] + 1,  // a deletion
               d[i, j-1] + 1,  // an insertion
               d[i-1, j-1] + 1 // a substitution
             )
}

As you can see, the algorithm always chooses the value from the upper-left neighbour if there is a match, saving some memory accesses, ALU operations and comparisons.

However, deletion (or insertion) may result in a smaller value, thus the algorithm is locally incorrect, i.e. it breaks with the optimality criterion. But maybe the mistake does not change the end result -- it might be cancelled out.

Is this micro-optimisation valid, and why (not)?


texts: How to prove coNP is closed under reverse Karp Reduction?

texts:
Is it true that $A \leq_k B \land B \in \mathsf{coNP} \implies A \in \mathsf{coNP}$?

If so, how would you go about proving it?


texts: Looking for an algorithm or similar mathematical problem for trading ownerships in shared property

texts:
Suppose there is $N$ property. Each property is owned by multiple person. (they have shared ownership) For example: $Person_1$ owns 22% of $Property_1$, $Person_2$ owns 35% of $Property_1$ and $Person_3$ owns 43% of $Property_1$. Also every person has shared ownership in multiple property. The number of persons is $M$.

The following rules has to be fulfilled:

Shared ownership's can be traded between two person.
All trade must be fair. The same amount of ownership can be traded E.g: If $Person_1$ wants to trade 22% of his ownership from $Property_1$ he must get the same amount from $Person_x$ $Property_x$
Partial trades are allowed. E.g: $Person_1$ has 35% of ownership in $Property_1$ but he can only trade 22% from it, with $Person_x$ the 22% is transferred to $Person_x$ but the rest 13% is still owned by $Person_1$
The sum of the shared ownership for each person must be constant. Nobody get rich or poor.

The goal is to concentrate all of the ownerships in the smallest amount of properties with the least amount of trades executed. Every trade execution has a fee, so finding the optimum amount of trades while maximizing the ownership in a single property.

What I'm looking for is a starting algorithm (dosen't matter if it's greedy) or some similar mathematical problem where I can start to work on my own solution.

So far I was able to represent my problem in a matrix with some test data, but I stucked here.

Every column is a property $Property_1$ ... $Property_n$

Every row is a person $Person_1$ ... $Person_m$

The values in the matrix is the ownership for each person and property between $0..1$


texts: How to count all integers less than a given integer and having two contigous digits as $y$?

texts:
Suppose i have been given a number 54432 .How to count all numbers less than 54432 and having last two digits as 1 ? i.e all the numbers of form xxx11 and xxx11 < 54432 .Here x can be any digits but xxx11 < 54432 should hold.

What is count of all the numbers of form x11xx and x11xx < 54432 ?

How to solve this in general and fast way i.e any number other than 1 , say y and arbitrary position of two contiguous digits as y and count of all such numbers less than a given integer.

can we solve this problem using strings ?

Like for 54411 , total count is 545 . Just remove 11 part and add 1.
for 54112 ,total count is 543 , just remove 11 part .


texts:
For example, in the proof of lemma 6.4.1 in the HoTT book, a function inductively defined over a function is simply applied on paths loop and refl, and then a path between loop and refl is used (presumably by congruence via f) to construct a path between f loop and f refl:

  Suppose that loop = refl base. [...] with x : A
  and p : x = x, there is a function f : S1 → A defined by f(base) :≡ x and f(loop) := p, we have

p = f(loop) = f(refl base) = refl x.

But in a cubical setting, things are not so clear-cut. f(loop) is not well-typed, only f(loop i) is, for some i : I. But then that above proof becomes

p = <i> f (loop i) = <i> f (refl base i) = refl x

but doesn't that need some kind of "interval extensionality" in the middle   step? What exactly is the justification of the middle step in cubical type theory? I can see how to prove ∀ i → f (loop i) = f (refl base i), but how does one "lift" that to <i> f (loop i) = <i> f (refl base i)?


texts: Scheduling problem with performance based selection

texts:
I would like to solve a scheduling problem where, I am able to maximize the number of consecutive shifts a employee may have, therefore minimizing the likelihood of them not showing up for a single, short shift on an odd day. However, I want to preferentially give shifts to better performers - where 'performance' is an arbitrary score. It is okay for some employees to get a low number of or 0 shifts.

The approach I believe I need to take is to tier each employee by to give them a maximum and minimum number of hours for the algorithm to try to achieve, however I would prefer to only have maximum hours and for the algorithm to always select a better performer over a worse performer.

Is anyone able to suggest an alternative approach?


texts:
The ACM Contest Problem 102 (HTML or PDF) can be paraphrased as:

  Given 3 bins each containing possibly different number of bottles of 3 colors, move the bottles so that there is one color per bin, minimizing the number of bottle movements.

Specifically, we wish to decide on an allocation of colors to bins so that moving from the initial position to the "sorted" position requires the least number of bottle moves.  The bins are assumed to have infinite capacity.

For the problem as stated, one can brute-force check all $3! = 6$ permutations to see which has the fewest number of bottle movements.  However, for $N > 3$ colors of glass, $N!$ grows very large. Is there a way to solve this problem for general $N$ that runs in polynomial time?


texts: Is there a special name for a queue that works with groups of elements

texts: I have a data type that accepts and returns byte arrays. However, the input is from a network callback or loading a huge file in piecemeal and the output is CRLF-terminated lines. The internal storage isn’t groups of bytes, but a single packet of bytes where the partitions extracted don’t have to match the ones inserted. Is there a existing special name for this? Otherwise I’ll call it something like “parsing queue.”


texts:
I am starting to learn recurrence relations in class and I am having issue with this example:

T(N) = 2N - 1 + T(N-1)

I am bit confused as to get the base case.
I'm sorry if this seems elementary, but I am having a difficult time grasping this concept.

Thank you for your help!


texts: Proving that if L is regular. Then L′ = {ww : w ∈ L} is regular

texts:
I believe this statement to be true. And here's my reasoning:

  Based on regular languages properties, the concatenation of two regular languages is regular. And since L′ = L · L, it follows that L′ must also be regular.

Do you think my reasoning is valid?


texts:
I'm trying to write some little code (POC for the selection/mutation operators) that uses a genetic algorithm to solve a global maximum for a function.

f(x_1...x_n) = M - (x_1 - a_1)^2 - (x_2 - a_2)^2 - ... - (x_n - a_n)^2

M a_i are constants. I have to find x_i such that f(x_i) = max(f) = M

My selection method is truncation (I select the top 100 fittest of a population of 500).
My crossover method is average. there is a 80% chance for crossover, other wise one of the parents is passed on.
My elite count is 5 (1% of the population)
There is a 3% chance for a mutation for an individual, the range of the mutation is [-0.3, 0.3]

My fitness function is f it self and my stopping condition is ABS(previous best fitness - current best fitness) <= 10^(-21)

You can find the code I wrote here.

The problem is that it converges before it reaches even an approximate solution.

What can I change in the solution approach so that the algorithm would converge on the maximum(f)?
(This is not my algorithm, it's a reduction of a problem I have at work.)


texts: Function notation/mapping for this type of functions?

texts:
In short, what is the proper function notation/mapping for this type of functions?
From Wikipedia regarding maps:

In the communities surrounding programming languages that treat functions as first-class citizens, a map is often referred to as the binary higher-order function that takes a function $f$ and a list $[v_0, v_1, \dots, v_n]$ as arguments and returns $[f(v_0), f(v_1), ..., f(v_n)]$ (where $n \geq 0$).

In mathematics we use the function and mapping notation
\begin{align}
f&:\mathbb R^n\rightarrow \mathbb R^n \tag 1   \\
x&\mapsto (f_1(x), \dots, f_n(x)) \tag 2
\end{align}
Where $x=(x_1,\dots, x_n)$ and we often write
$$
f(x_1,\dots, x_n)=(
f_1(x_1,\dots, x_n),
\dots,
f_n(x_1,\dots, x_n)
)
\tag 3
$$
Question:
According Wikipedia we have the variable $v=(v_0,\dots, v_n)$ and a function of the form
\begin{align}
f(v_0,\dots, v_n)=
(f(v_1), f(v_2), \dots, f(v_n))
\tag 4
\end{align}
But this form doesn't correlate with the notation in $(1)-(3)$. What is the proper function/mapping notation for $(4)$?


texts:
I'm having serious issues fining an unambiguous version of a particular grammar. I've looked online for help for this particular problem and for general methods for finding unambiguous versions of grammars, and though I understand the concept, I can't seem to figure this out. Any help/advice? I keep getting really close then finding something that doesn't fit. Here is the grammar in question:

S -> aS | bS | Sa | Sb | aa


texts: How can one reduce 3-CNF-SAT and k-CNF-SAT to each other?

texts:
I am studying for NP problems.
To prove k-CNF-SAT is NP-hard, there must exists something that can be reduced to k-CNF-SAT. So what I thought is to reduce 3-CNF-SAT to k-CNF-SAT and reduce k-CNF-SAT to 3-CNF-SAT both proves that it is NP-hard.

I know that 3-CNF-SAT is NP-Complete, because of its number of literals, but this property seems dedicate no effect to proof.
Thanks for any suggestion.

Note: k-CNF-SAT is a conjunctive normal form which k > 3.
And my question is same as the title, I have no idea about this question, since I just only know 3-SAT is a special case of k-SAT.


texts: Faster RCNN: how to translate coordinates

texts:
I'm trying to understand and use the Faster R-CNN algorithm on my own data.

My question is about ROI coordinates: what we have as labels, and what we want in the end, are ROI coordinates in the input image. However, if I understand it correctly, anchor boxes are given in the convolutional feature map, then the ROI regression gives ROI coordinates relatively to an anchor box (so easily translatable to coordinates in conv feature map coordinates), and then the Fast-RCNN part does the ROI pooling using the coordinates in the convolutional feature map, and itself (classifies and) regresses the bounding box coordinates.

Considering that between the raw image and the convolutional features, some convolutions and poolings occured, possibly with strides >1 (subsampling), how do we associate coordinates in the raw images to coordinates in feature space (in both ways) ?

How are we supposed to give anchor boxes sizes: relatively to the input image size, or to the convolutional feature map ?

How is the bounding box regressed by Fast-RCNN expressed ?
(I would  guess: relatively to the ROI proposal, similarly to the encoding of the proposal relatively to the anchor box; but I'm not sure)


texts: Do we need regular expression first or finite state automata in lexical anlysing?

texts:
I'm a bit confused about the concept of finite state automata (FSA) and regular expression (RE) in lexical analysis. I have reading some books about compiler construction. At the part of tokenization, all the books I read talk  about the regular expression first to recognize the tokens. For example, the regex below is to recognize the identifier:

([a-zA -Z] | _ | $ )([a-zA -Z0 -9] | _ | $)*

Then, they jumped to explain another technique which is finite state automata (FSA). As a result, some questions have come to my mind which are:

1- What part I should learn first? RE or FSA?.

2- Programmatically, which part should be converted to other to build the lexer? RE ==> FSA or FSA to RE.
3-Since all tokens can be recognized by regular expression, then, why we need finite state automata?.

Sorry for the to many questions, but I really can't figure out how to start. many thanks in advance.


texts:
The Strassen algorithm is developed for multiplying the matrices faster. It enables us to reduce O(n^3) time complexity to O(n^2.81).

However, this algorithm is applied for the matrices which are square and the dimension of the matrices must be a power of 2.

Assume that the matrices are called A and B.

Problem 1: A = 3x3 B = 3x3

Problem 2: A = 2x3 B = 3x1

How can we apply Strassen algorithm to multiplication of these matrices ?
The only thing which comes to mind is enlarging the matrices to convert them into square non matrices by adding zeros, which is called padding operation. However, I am not sure whether this method is proper or not.

Is there another method ?

Is my notion correct ?


texts: Making sure the Branch Target Buffer stays accurate

texts:
As i've been told , a Branch Target Buffer (BTB) acts a lot like a cache for Branches , keeping a map of where branches are in the address space.

If implemented well , it should allow the processor to detect branches before even decoding them , redirecting the PC to the presumed target ( with the help of the branch predictor proper).

But the BTB is presumed to be accurate about where the branches are. You don't want the processor to jump when encountering an ADD instruction for example , meaning the instruction PC has to be an exact match with what is in the BTB.

Here's my question :

Most Processors support self modifying code (for better or for worse). This means that a branch instruction in main memory has the potential to be overwritten by data or another instruction.
If said branch is already present in the BTB , this could result in BTB information being stale. In such a case , the processor might jump in response to a non-existent branch , resulting in an incorrect program result.

My initial solution to this was to just compare every memory write against what is present in the BTB. But this would be inefficient (requiring additional ports and potentially slowing down the machine) and most memory writes to not overwrite branch instructions or instructions at all for that matter.

Is there a better way to do this? something i've missed ?

I've looked around already , but couldn't find any information .


texts: Does #$P$-Completeness imply approximation hardness?

texts:
Let $\Pi$ be some counting problem which is known to be #$P$-Complete.

Does it imply that $\Pi$ is $APX$-hard (i.e. no PTAS for the problem exists unless $P=NP$)?


texts: What are some problems in $\mathrm{P}$ with time complexity of high-degree polynomial?

texts: What are some problems that are in $\mathrm{P}$ but the best known algorithm has a high-degree polynomial ($\ge 3$) time complexity?


texts:
In the book The Annotated Turing, Charles Pezold writes:

  Because Turing Machines are entirely defined by a Description Number, it might be possible to create a Turing Machine that analyzes these Description Numbers to determine whether a particular machine is satisfactory or unsatisfactory. Turing proves this is not the case. There is no general process to determine whether a a Turing Machine is satisfactory. The only way one Turing Machine can analyze another is to trace through the operation of the machine to determine what it is going to do.

Now I intuitively understand this has something to do with the Halting Problem, but I'm having trouble expressing why this is the case in this situation. (Ie I understood Turing's Paper to be about the impossibility of a general algorithm to solve Diophantine equations in a knowable number of steps).

My question is: How did Turing prove that there is no general process to determine whether a Turing Machine is unsatisfactory?