texts: Checking for intersection of $d$-dimensional spheres

texts:
Is there a simple algorithm to check whether $n$ different balls (of the same radius) in $\mathbb{R}^d$ intersect? That is, coordinates of their centers $x_i$ are given, radius $R$ is given and we need to determine if there exists a point $p$ such that $$\| p - x_i \| \leq R \quad \forall i.$$
In other words, check whether there is a point $p$ that is contained in all $n$ balls.


texts: Is $\epsilon$ always contained in $\Sigma^*$?

texts:
Please correct me on any terminology. For some reason I'm a bit confused.

$\Sigma = \{\epsilon, 0, 1\}$

This means my alphabet, $\Sigma$, contains three symbols ($\epsilon, 0, 1$).

$\Sigma^*$ is the language over $\Sigma$, and it equals $\{\epsilon, 0, 1, 01, 10\}$.

My regular expression for $\Sigma^*$: $\epsilon+0+1+(01)+(10)$.

First question: Does every $\Sigma^*$ include $\epsilon$? I see some with, and some without. I feel like this is a big difference because your regular expression and DFSA will be different.

Second question: At this point, I would have five accepting states in a DFSA? Since the first state is the empty string, is it $\epsilon$? Or is the first state just nothing, which transitions to a second state via $\epsilon$ which contains the empty string?


texts: MST: Prim's algorithm complexity, why not $O(EV \lg V)$?

texts:
According to CLRS, the Prim's algorithms is implemented as below --

  $\mathtt{\text{MST-PRIM}}(G,w,r)$

  for each $u \in V[G]$ do

  $\mathtt{\text{key}}[u] \leftarrow \infty$
  $\pi[u] \leftarrow \mathtt{\text{NIL}}$

  $\mathtt{\text{key}}[r] \leftarrow 0$
  $Q \leftarrow V[G]$
  while $Q \ne \emptyset$ do // ... $O(V)$

  $u$ $\leftarrow$ $\mathtt{\text{EXTRACT-MIN}}(u)$ // ... $O(\lg V)$

  for each $v \in \mathtt{\text{adj}}[u]$ do // ... $O(E)$

  if $v \in Q$ and $w(u,v) \gt \mathtt{\text{key}}[v]$

  then $\pi[v] \leftarrow u$

  $\mathtt{\text{key}} \leftarrow w(u,v)$ // $\mathtt{\text{DECREASE-KEY}}$ ... $O(\lg V)$

The book says the total complexity is $O(V \lg V + E \lg V) \approx O(E \lg V)$. However, what I understood is that the inner for loop with the DECREASE-KEY operation will cost $O(E \lg V)$, and the outer while loop encloses both the EXTRACT-MIN and the inner for loop, so the total complexity should be $O(V (\lg V + E \lg V)) = O(V \lg V + EV \lg V) \approx O(EV \lg V)$.

Why the complexity analysis is not performed as such? and What is wrong with my formulation?


texts: Construct a DAG from given multiple topological orderings

texts:
I need to construct a DAG, from its given topological orderings (i.e. the graph $G$ created must have all the orderings given as its topological orderings). For simplicity, the vertices are labeled as first $n$ natural numbers. (Note that once created, the graph $G$ may have more topological orderings apart from the ones given.)
The following constraints should be met:

The maximum outdegree of every node should be 1
The number of nodes having indegree 0 should be minimum.

There can be multiple solutions, any of them should work.

What I have tried. (Approach 1 which is wrong as it fails one example given in the answer. Please scroll to the second approach, which still I'm not able to find a mistake.)

Approach 1
From all the given orderings, first, create a directed graph by creating a directed edge from every node to its next node. This means if the orderings are:
$$ 1, 3, 2, 5, 4, 6 $$
$$ 3, 1, 5, 2, 4, 6 $$
$$ 1, 5, 3, 2, 4, 6 $$

I will create a directed graph with a directed edge from $1$ to $3, 3$ to $2, 2$ to $5$ and so forth.

This ensures that the number of nodes with indegree 0 remains minimum. Now, I'll remove all the cycles and make sure all the orderings are valid and finally, eliminate all the extra edges any node has. WHile doing so, I'll make sure that if there are two nodes whose edge is coming from the same node, I'll remove the edge from the node having a higher indegree, so that condition 2 is met.
The graph constructed then, should look like:

This DAG created, follows both the constraints, and IMO has the minimum number of nodes of indegree as 0, although, it's not proven.

I have coded the approach and it is giving expected results for the use cases I supply, but I know that it is wrong.
What am I missing here? Can anyone provide an alternative use case, which fails the above approach?

Approach 2
I create a directed graph $G$ by creating an edge from  $a_i $ to $ a_j$ for all $ j > i$ in all the orderings given.
So, for the orderings:
 $$ 1, 2, 3, 4, 5$$
$$ 2, 4, 1, 5, 3$$

I will create the following graph:

The first step after this is to validate all the orderings. Removing cycles separately is not required as they will be removed by this step itself.
For any ordering
$$ a_1, a_2, a_3, a_4, ... a_n $$
I will check if there exists any edge from $a_j$ to $a_i$ where $ j > i$, I'll remove that edge.
Doing so, will give the following graph:

The last step is to remove extra edges from all nodes as maximum outdegree of any node can be $1$ max. I'll remove the outgoing edges such that the number of nodes having indegree $0$ is minimum. First I calculate the indegree of each node. Then for each node which has more than 1 outgoing edges, I'll remove all the edges except the one with the minimum indegree.

The final graph $G$ will look like:

This graph satisfies both the constraints. But I know this approach is wrong! Can anyone help to find why is this wrong?


texts: Why does a RNN network output different based on the training sequence

texts:
I've set up an RNN LSTM network in Java using DL4J as the library.

I currently have 500 examples of positive text, and 500 examples of negative text.

When I fitness the training data by first training all the negatives and then all the positives, my predictions only favor high positive responses even for things that would be considered negative in my training examples.

And if I reverse it and train positive first and then train negative last everything is favored as a negative in high 80 - 90%.

However, when I train in an oscillating pattern such as: Positive, Negative, Positive, Negative and so on, the predictions become accurate again and similar examples of negative text are picked up relatively accurately and vice versa for positive text.

I've only just started studying machine learning in general but I can't quite find any resources explaining why the sequence of training impacted my model so hugely. Is this normally how an LSTM network should behave or is oscillating the training data the correct approach?

Would the classification of a messages negative intent be something an LSTM RNN network should be used for or should I consider another network?


texts: Would increasing system memory speed reduce a Von Neumann Architecture bottleneck?

texts:
A Von Neumann Architecture bottleneck is a limit on the amount of data a computer can process due to limited bandwidth between the CPU and RAM. Possible mitigations to the problem according to Wikipedia are...

Providing a cache between the CPU and the main memory
Providing separate caches or separate access paths for data and instructions
Using branch predictor algorithms and logic
Providing a limited CPU stack or other on-chip scratchpad memory to reduce memory access
Implementing the CPU and the memory hierarchy as a system on chip, providing greater locality of reference and thus reducing latency and increasing throughput between processor registers and main memory.

I know that increasing the number of data lanes between the CPU and RAM would help, but would increasing the system memory speed also help?


texts:
So class P is the class of languages that are decidable in polynomial time on
a deterministic single-tape TM.

I can show that the decider for a language L* runs in polynomial time.

So is it true that this language in class P?
STARCLOSED DFA = { | A is a DFA, and L(A) = L(A)*}


texts: Implement Mathematica's capability of rationalizing machine reals

texts:
If I have a variable x bound to a machine precision real in Mathematica, I can use

 y = FromDigits[RealDigits[x]]

then y is bound to a completely equivalent rational number which has infinite precision.

What are the basic principles behind FromDigits and RealDigits?
How could I implement a similar conversion using common machine operations (fixed-size integers and floating point operations) to coerce a double in a rational, or at least obtain the long integer denominator and numerator of a double?


texts: Constructing a sphere ($S^2$) in HoTT directly?

texts:
(this is a repost of https://stackoverflow.com/questions/29802501/constructing-a-sphere-s2-in-hott-directly, which was voted out of SO)

I understand the construction of $S^2$ as a suspension of $S^1$ in homotopy type theory. I wonder whether one can build $S^2$ in one step as a base point and an open 2-surface. Something like this:

data Sphere where
  base : Sphere
  skin : Id (Id Sphere base base) refl refl

The above is probably something like a sausage with endpoints identified, though.

So my question is: Can an $S^2$ be built as a HIT from a closed 1-ball whose boundary is identified?


texts: Superposition calculus: Elimination of redundant atoms

texts:
Bachmair and Ganzinger (1991), 'Rewrite-Based Equational Theorem Proving With Selection and Simplification', section 5.2, 'Simplification and Deletion Techniques', page 17, 'Elimination of redundant atoms', discusses the question of when, having used one clause to derive another, you can throw away the first clause instead of ending up with both. As discussed in Redundancy elimination in the superposition calculus you cannot do this in the general case, but you can do it in some particular cases, such as when discarding tautologies or subsumed clauses.

"Let C = Γ, u ≈ v → ∆ be a clause in N. If N |= Γ → u ≈ v, ∆, then N |= Γ → ∆, so that C can be simplified to Γ → ∆. A particular case is the elimination of multiple occurrences of atoms in the antecedent. For example, if C = Γ, u ≈ v, u ≈ v → ∆, then the clause Γ, u ≈ v → u ≈ v, ∆ is a tautology and hence trivially implied by N. Redundant atoms in the succedent can be eliminated in a similar way."

Hang on. "elimination of multiple occurrences of atoms in the antecedent", "Redundant atoms in the succedent can be eliminated" - it would certainly be nice if you could do this, but as I understand it, as discussed in https://stackoverflow.com/questions/29164610/why-are-clauses-multisets you have to treat clauses as multisets, not sets, you cannot just throw away multiple occurrences of the same atom. What am I missing?

And "then the clause Γ, u ≈ v → u ≈ v, ∆ is a tautology" - as I understand it, this is true, a clause which contains both an item and its negation is indeed a tautology and you really can promptly discard tautologies, but what does that have to do with multiple occurrences of the same atom with the same polarity? How is that sentence connected to the rest of the paragraph?


texts: How to register an articulated model to noisy predictions?

texts:
Given point sets $Y$ and $M$, I'd like to register articulated $M$ to $Y$ without changing the edge distances of $M$. The point correspondences between $Y$ and $M$ are known and points have a fixed connectivity map.

As you can see from the above sample, the edge distances of $Y$ are corrupted, and I'd like to correct them using $M$ while sacrificing some localization precision.

I know ICP (Iterative Closest Point) and RANSAC (Random Sample Consensus) algorithms, but none of them solve the articulation problem. I'm looking for any kind of algorithms that can solve this articulated body registration problem.


texts: How do you know if a language accepted by a DFA is $Σ^*$?

texts:
I know that a language that is input into a DFA (call it $X$) is regular just by being accepted by it, but given that it is accepted, how can one figure out that $L = Σ^*$? In other words, what does a DFA that accepts anything from $Σ^*$ even look like? When I learnt about DFAs, it was always under the context that $L(X)⊆ Σ^*$.

I get that this must be a DFA that accepts any input from $Σ^*$, but I have trouble wrapping my head around it. This is all of course assuming that $Σ$ is any finite set.


texts:
Which of the following are proper network (not host) addresses?

192.168.23.0/24
193.205.16.132/26
172.16.4.0/20
10.57.13.64/28

How can I tell? What is a proper network address?

Is a proper network address when the IP address is the same as the network address? For example in the first one that is the case.


texts: Average access time in two level cache system

texts:
In a two-level cache system, the level one cache has a hit time of 1 ns (inside the CPU), hit rate of 90%, and a miss penalty of 20 ns. The level two cache has a hit rate of 95% and a miss penalty of 220 ns. What is the average memory access time?

What is a two-level cache system and how to calculate the time required? Since the hit time of level two cache is missing...


texts: Logarithmic vs double logarithmic time complexity

texts:
In real world applications is there a concrete benefit when using $\mathcal{O}(\log(\log(n))$ instead of $\mathcal{O}(\log(n))$ algorithms ?

This is the case when one use for instance van Emde Boas trees instead of more conventional binary search tree implementations.
But for example, if we take $n < 10^6$ then in the best case the double logarithmic algorithm outperforms the logarithmic one by (approximately) a factor of $5$. And also in general the implementation is more tricky and complex.

Given that I personally prefer BST over VEB-trees, what do you think ?

One could easily demonstrate that :

$\qquad \displaystyle \forall n < 10^6.\ \frac{\log n}{\log(\log(n))} < 5.26146$


texts: Applying Ford-Fulkerson to settle a business lunch

texts:
I want to organize a business lunch with two societies $E_1$ (mine) and $E_2$. Each society is made of four people from the Executive management and 6 of the Financial Management. I want to organize this lunch with two tables of ten people with the following constraints :

At least one member of each four department has to be on each table
At most three people of each department can sit together at a table
At least three people of each Executive management department have to be at the table $1$.

I did the following graph :

And applied Ford-Fulkerson (I'm not sure on how to apply it, the itreation are in parenthesis $(number \ of \ the \ iteration)$ ):

The thing is that I'm not able to let everybody sit ... I have only 8 people from society 2. Do I have too much constraints or did I did a mistake ?

What would be the minimum cut ? Is there a minimum cut if I don't have a maximal stream ? Would it verify the Ford-Fulkerson theorem ?


texts:
Am I correct in saying that

traverse(node):
    if node is null, return
    print node
    traverse(node's right subtree)
    traverse(node's left subtree)

would produce output that is the reverse of post-order traversal?

post-order(node):
    if node is null, return
    post-order(node's left subtree)
    post-order(node's right subtree)
    print node

I am mostly interested because if this is true, it greatly simplifies the iterative method for post-order traversal. It "feels" right with a hand-wavey explanation - and with testing on some trees - but how would I prove it?


texts: How to find i largest numbers in unsorted array in O(n) where i <= n^(1/2)

texts:
If we have length $n$ unsorted array such that each element is integer and different, how to find $i$ largest numbers in linear time O(n)? but $i \leq n^{\frac{1}{2}}$.
For example, if we have $A = [11, 6, 8, 1, 9, 100, 88]$ and input $i = 2$, then output is $[100, 88]$ (sorted).


texts: standard sequential algorithm with polylog runtime?

texts:
At the Wikipedia article on time complexity, only a PRAM example is given for polylogarithmic time.

Let $T(n)$ denote the largest number of steps used by a machine to reach a final state on any input with size $n$ bits.

  Is there a program for a standard sequential model of computation (e.g. a Turing machine or a sequential random-access machine), solving some natural problem, so that $T(n) \in \Theta((\log n)^k)$ for some fixed $k>1$?


texts: Does the cpu interface with a memory controller to read the cache? What happens when data is not in the cache, a cache miss, does it automatically fetch the data?


texts: What does superscript + mean in relational algebra?  Suppose $A$ is a subset of attributes of all attributes in a relation $R$.  What does $A^+$ mean?


texts:
Is it true that $FP^{NP[log\cdot n]} = FP^{NP}$ if $P = NP$?

If I understand the polynomial hierarchy correctly, then, if $P = NP$, all complexity classes collapse to one class. Therefore the above two classes should also be equal.


texts:
Main Question

We can represent subsets of a vector using, say, a bit mask. Let's say a nested subset is a pair of masks, for example

A B C D E F
1 0 0 1 0 1
1 0 0 0 0 1

is a nested subset, where the first mask tells us inclusion in the first set and the second mask tells us inclusion in the first. In this case the first set is {A,D,F} and its subset is {A,F}. I am trying to uniformly generate such subset pairs.

Some Thoughts

One could try naively to generate two random masks, use the first for the union, then the second for the intersection where it overlaps. However, this would generate subsets uniform in the initial subset, and not the pair.

Mathematically speaking this can be done by weighting each mask by the number of possible subsets it has (2^n where n is the size of the subset), randomly drawing a subset, then randomly drawing an intersection from it. However this is very challenging/inefficient to implement in practice

My first idea was to find some (efficient) hash function from integers into subset pairs, however I have not had much success with this.  I am wondering if there is a superior way to do this. I don't need code (I don't have implementation issues); I am looking a conceptual approach. Any advice?


texts: How to perform local search to find maximal induced subgraphs?

texts:
I'm looking for efficient ways to perform local search to find maximal induced subgraphs that satisfy certain properties : a tree, a forest or a bipartite subgraph for example.

What I mean by local search is moving from solution to solution by applying local changes, until a solution deemed optimal is found or a time bound is elapsed.


texts: What's the maximum memory address space that the processor can access directly if it connected to a 16-bit memory?

texts:
The question is the following:
3. Given a hypothetical microprocessor which generates a 16-bit address (assume that the program counter and address registers are 16 bits wide) and has a 16 bit data bus.
a) What is the maximum memory address space that the processor can access directly if it connected to a "16-bit memory"?
b) What is the maximum memory address space that the processor can access directly if it is connected to an "8-bit memory"?

It feels like the answer to both would be 2^16, which is equivalent to 24KiB. It also feel natural to say that an 8-bit memory can tranfer 8 bits and a 16 bit memory can transfer 8 or 16 bit words.

But the problem is that the actual answer booklet says the following:
In cases (a) and (b), the microprocessor will be able to access 2^16 = 64K bytes; the only difference is that with an 8-bit memory each access will transfer a byte, while with a 16-bit memory an access may transfer a byte or a 16-byte word.

So 1) 64K? Isn't the unit suppose to be KiB? I am very confused.
2) 16-byte word? Shouldn't it be a 16-bits word?


texts:
I need to find a minimal DFA given the following information:

  $ \{a^nb : n\geq 0\} \cup \{b^na: n \geq 1\}$

Now, maybe I'm not seeing this properly, but I don't see how this is possible: the first one will take 0 or more a's followed by one b, whereas the second one will take a 1 or more b's followed by one a.

Drawing the combined automata only brought me to trap states. Any suggestions?


texts:
I have to cluster a movie dataset of 10000 movies. A movie has attributes like Genres, Actors, Directors, Year. Earlier I thought that we can use a simple clustering algorithm like k-medoids and the distance can be pre-computed between two movies by subtracting genres & actors.

Initialise
d(movie1, movie2) = 0

d(movie1, movie2) -= number of common genres
d(movie1, movie2) -= number of common actors
d(movie1, movie2) -= 1 (if they have a common director)
d(movie1, movie2) -= 1 (if they belong to same decade)

Is this approach correct ? Is k-medoids fast enough to cluster this dataset (I doubt it isn't) ? If it isn't fast enough any better clustering algorithm and strategy to cluster this dataset ?


texts: Unambiguous grammars with different right and left hand derivations

texts: I read recently that for an unambiguous grammar the left hand derivation need not necessarily be equal to the right hand derivation. Can someone give an example of this?


texts: How can a CPU be busy during DMA access with burst mode transfer

texts:
During burst mode in a DMA access, the DMAC has control over the bus for the whole transfer session which includes DATA PREPARATION time as well as DATA transfer time, after the transfer is over, the DMA relinquish the system bus. So in the mean time, the cpu can neither fetch any instruction from the MAIN MEMORY, nor it can fetch any operand, it can atmost complete the instruction it was executing before if that don't include the use of system bus.
In the book I have seen as cpu busy percent is given by
Data preparation time/(data prep time + data transfer time)
How can the cpu be busy during the data preparation time when the bus is not with it.
This can be the concept behind CYCLE STEAL mode, since it gains the bus only during data transfer, but how during burst mode??


texts: Compression of a text that contains only the 5 first letters of the alphabet?

texts:
So the question is: "Imagine the compression of a text written only with the first 5 characters of the alphabet (a, b, c, d, e). Knowing that their apparition's frequency is 1)e, 2)a, 3)c, 4)d, 5)b, code the letters on the minimum bits possible."

so here's how I did start:

We have 5 characters, so 3bits will be enough for the characters (2^3 =8). We can put: e=001, a=010, c=100, d=011, b=110 But I don't see how to use their frequency (we don't have the value of it, they just gave a "scale" of their frequency)


texts: Sorting Algorithm which prevents strings with at least one identical char from being next to each other

texts:
Imagine this Table:

All combinations represented in the table (1,2 ; 1,3 ; 1,4 ; etc.) are stored as strings in an array with a total of  (n^2-n)/2  elements (combinations).

I'm looking for an algorithm that sorts the elements so no number of a combination is next to a combination with the same number in it.

For example a sorted array with n=5: {1,2 ; 3,4 ; 5,1 ; 2,3 ; 5,4 ; 1,3 ; 2,5 ; 4,1 ; 3,5 ; 4,2}

Of course this algorithm would only work with n > 4.


texts: How can can I find out if the two disks intersect in the plane?

texts:
. Imagine two disks on the xy plane. Each disk is represented by
three numbers (the radius, the x coordinate of the center and the y coordinate of the center). All values
for this problem are real numbers. Your task is to determine if the two disks intersect.


texts: How to prove using pumping lemma that language generated by a(b*)c(d*)e is regular?

texts:
I am studying pumping lemma from Introduction to theory of computation by Michael Sipser. I wanted to check if the language generated by regular expression
 a(b*)c(d*)e

can be proved to be regular using pumping lemma. The string generated by this expression are of the form.

abcde
abbcdde...

We can not write these string in the form of $xy^iz$. We can only write it in the form $vx_1^iyx_2^jz$.
So, how can I prove using pumping lemma that the language generated by the expression is regular?


texts: Why did the concept of "write-protecting" not carry over from floppy disks to USB memsticks and especially external USB HDDs?

texts:
Many times, I've wished to plug in my backup hard disks into my PC without the risk of any of the data being deleted, overwritten, or modified in any manner. Purely for "inspection" and copying over certain files from it.
But, unlike on the old floppies, there's just no hardware switch anywhere to enable "read-only" mode, or "write-protected mode". Why?
This very simple, mechanical thing was a thing back then, but later, "we" decided that it was unnecessary?


texts: A tree-like data structure with rights delegation for distributed computing

texts:
Every actor can create a root node and delegate a right to add a child node. Every node contains name of its’ creator or who added it, and value S. Sum of all values S at the same level of the tree must be equal to the sum of all values of the parent level nodes which in turn is equal to the sum of S’s of their parent nodes and so on up to the root.

Original question: Resending an encrypted message so that it’s guaranteed from being changed and is visible only to final receivers

I faced the next rather theoretical problem. Sender sends a message (I, Ch, S), where I is the proper content of the message, Ch is chain of receivers/resenders and S is just a sum. By having received the message Receiver sees all the information (I, Ch and S), next he/she can either accept or decline the message. By accepting it he is in right to resend the message as many times as he wants, adding every time its’ name to Ch, but S of all the resent messages is equal to the S of the original message.

Example. Alice sends <“1st message”, Alice, 500> to Bob, Bob resends <“1st message”, (Alice, Bob), 500> to Daenerys. Daenerys resends <“1st message”, (Alice, Bob, Daenerys), 300> to Jon and <“1st message”, (Alice, Bob, Daenerys), 200> to Tyrion.

The message must be encrypted , firstly, with Bob’s public key, then decrypted with his private key, then encrypted by Daenerys’ public key. But Dany can’t be sure that the content isn’t changed. Jon and Tyrion can’t be sure that the sum of the received messages is equal to the sum of the original message.


texts: Complexity of $T(n) = 4T(n/2) + n^2 \cdot log_2 (n)$

texts:
After constructing the recursion tree i concluded a cost of $n^2\cdot log_2(n)-i\cdot n^2$ per level. So my total cost is:

$$\sum_{i=0}^{log_2(n)}n^2\cdot log_2(n)-i\cdot n^2$$

$$=(log_2(n)+1)\cdot n^2\cdot log_2(n)-\sum_{i=0}^{log_2(n)}i\cdot n^2$$
$$=n^2\cdot log_2^2(n)+n^2\cdot log_2(n)-\sum_{i=0}^{log_2(n)}i\cdot n^2$$

Because $n^2\cdot log_2(n)$ and $\sum_{i=0}^{log_2(n)}i\cdot n^2$ are lower order terms i concluded $T(n) \in \Theta (n^2\cdot log_2^2(n))$

I would appreciate if someone could tell me wether i'm wrong or right.


texts: If h(n) is a perfect heuristic (that is, h(n) = h*(n)), then does it imply that A* will always take linear time complexity?

texts:
That is, if h(n) = h*(n), then A* only expands nodes that lie on an optimal path to the goal. But does this imply that A* will always take a linear time in the solution length to find an optimal solution?

I suspect I may be overthinking this problem, but if h(n) = h*(n) then we are measuring the exact heuristic cost of arriving at a goal node $n$ from x. But I can't see why this would be true, because even though you have a perfect heuristic, it is not monotone, and so you may have a cheaper f-value that may be expanded at a later point in the search, which no longer means the search space is linear.


texts: Base of logarithm in runtime of Prim's and Kruskal's algorithms

texts:
For Prim's and Kruskal's Algorithm there are many implementations which will give different running times. However suppose our implementation of Prim's algorithm has runtime $O(|E| + |V|\cdot \log(|V|))$ and Kruskals's algorithm has runtime $O(|E|\cdot \log(|V|))$.

What is the base of the $\log$?


texts: Given a Turing Machine $M$, if I know $L(M)$ is finite, can I solve the halting problem?

texts:
Say I'm given an oracle that tells me whether or not $L(M)$, the set of words accepted by a Turing Machine $M$, is finite.
By leveraging this oracle, can I solve the halting problem? That is, on an arbitrary input $<M, x>$, can I tell if M is going to halt on $x$ or will it loop forever?
My intuition says no because I don't see a  way to leverage the oracle.
For example, even with a stronger oracle that tells me if $x \in L(M)$, I still don't know, for inputs $x \notin L(M)$, how $M$ is going to behave. It could either reject (and halt), or loop forever.
Hence, I can't seem to solve the problem even with a stronger oracle that computes $L(M)$ explicitly in case it's finite. So, I believe merely knowing $L(M)$ is finite or not doesn't lead to a solution for the  halting problem.
Is my reasoning correct, or am I overlooking something here?


texts: Are there any examples of projects running a program that will take many years to finish its job?

texts:
There are algorithms that are said to be unfeasible to be applied in practice due to their time complexity. In textbooks, it's common to see remarks like "it would take hundreds of years" about using them. Unfortunately, it's often the case an inefficient algorithm is the only proven solution for an interesting problem.
Is there an example of a project running one of those algorithms where the participants know they won't be around to see the results hoping to solve a problem for the next generations?


texts: Image quantization for grayscale images with alpha channel

texts:
I am looking for algorithm that quantize grayscale image that contains alpha to 4-bits (16 colors). I quite like the effect that is used in IrfanView to decrease color depth, however, I dont know the exact algorithm plus the alpha channel is lost.

Currently I am using Wu's Color Quantizer that works with RGB images. I map my grayscale as R = grey, G = grey, B = alpha. However, this approach is not always correct.

I would also like to be able to keep certain grayscale value, that I specify. Currently, I do that manually by increasing number of pixels of this value.


texts: Many-One Reducibility of decision problems for complexity theory?

texts:
A many-one reduction of problem $A$ to problem $B$ is essentially a function that converts a problem instance in problem $A$ to an instance in $B$. This allows you to use a $B-$solver one time to solve this converted instance, in order to solve an $A$-instance.

To show that $A$ is in NP-complete, people use reducibillity arguments to reduce (in polynomial time) an arbitrary problem in NP to $A$, but as far as I know this is not necessarily a many-one reduction.

My question is: How many of these reductions in the context of NP-completeness are many-one reductions? How significantly would the complexity class change if we would require many-one reductions?


texts: What are the best features to identify heads from any angle?

texts:
I want to automatically track heads in CCTV records.

Sometimes I need to re-identify heads because of multiple heads crossing each other. So I continually need to extract features from tracked heads so that I will be able to re-identify them when needed.
Those tracked heads are seen from any angle.

What would be the best features to describe heads?

EDIT: Precisions

I work with multiple cameras (15) in differents positions generally placed from 0.5 to 20 meters to the people. Those cameras are inside a building, the luminosity is quite good (but I also would like to work with IR during the night, but for now working with light), cameras are 2048x1536 @ 20fps with color.
Cameras are barely overlapping
For now, I use https://github.com/Russell91/TensorBox to detect heads accurately from any angle and it works very well (I have almost the same angle and exposition than in TensorBox readme image).
As TensorBox is very slow (20ms->70ms/image on gpu) I use it only when there is motion and only 2times/sec max. I use optical flow (calcOpticalFlowPyrLK from openCV) to follow heads between two head detections.
I don't have any information on people. When there is someone new, I create a new identity. Then I try to follow him on the camera network and save the path he followed.
I am not able to use face detectors for re-identification as cameras do not necessarily see them from the front. But this could improve re-identification.
So there are two different cases to handle with re-identification:

Multiple persons overlap
Person X is moving to another camera

I can easily track persons' heads for now, but I cannot identify them easily because I cannot distinguish them. I think I will need a simple multi-class classifier, but I don't know what would be the best features to describe persons' heads that are moving in any directions.

Thanks for your help!


texts: Why does going from 2's complement (in binary) to the positive value by completing to 1 then adding 1 work?

texts:
I'm studying Computer science and this has confused me for a long time since our professor didn't give any proof.

When changing from 2's complement to the positive value, we can go in reverse (by subtracting 1, then using 1's complement), and that's clear why it works.

But our professor told us another method which is taking the number, using 1's complement, THEN adding 1.

I don't understand why the second method works.


texts:
I came across the following two regular expressions $r_1 = 0^+(10^+0)^∗0^*$ and $r_2 = 0^+(10^+0)^∗$.
I know, in general, proving if two regular expressions are equivalent is hard in terms of time complexity, and that there are several algorithms to determine this. (e.g, convert regex to DFAs.) However, I wanted to know if there is a simpler method for this particular example.
Firstly, they seem to be equivalent.
Intuitively, $r_1$ describes all the words that $r_2$ does since both expressions are the same except for the $0^*$ at the end of $r_1$.
Next, let us rearrange $r_1$ and $r_2$ like so:
$r_1 = 0^+(100^+)^∗0^*$
$r_2 = 0^+(100^+)^∗$
Note that although we changed the order of the expression in the parentheses, it still expresses the same idea, which is zero or more repetitions of one 1 followed by at least two zeroes.
This english description seems to apply even when we append the $0^*$ at the end of $r_1$. Because if we had $m$ zeroes at the end of a word (e.g, 00000100100000), all we would have to do is to use $m$ zeroes for the last repetition of the expression in the parentheses, and just ignore the $0^*$.
This is kind of like my intuition, but I wanted to know if there is any formal proof for this? Or even, I might be wrong, and these regex are not equivalent and there is a counterexample.


texts: Which has a higher order of growth n(n+1) or 2000n^2?

texts: I think they have the same order of growth because both are O(n^2), correct? And even though 2000n^2 has a higher coefficient, they're both the same complexity since O(n) < O(n^2) < O(n^3) is this thinking correct? If not, how can I understand their order of growth better?


texts: Deriving the regular expression for C-style /**/ comments

texts:
I'm working on a parser for a C-style language, and for that parser I need the regular expression that matches C-style /**/ comments. Now, I've found this expression on the web:

/\*([^\*]*\*+[^\*/])*([^\*]*\*+|[^\*]*\*/

However, as you can see, this is a rather messy expression, and I have no idea whether it actually matches exactly what I want it to match.

Is there a different way of (rigorously) defining regular expressions that are easy to check by hand that they are really correct, and are then convertible ('compilable') to the above regular expression?


texts: What are the differences between parse and decision trees?

texts:
I have created a parse tree for the formula: a∧¬(b∨c)∨¬d∧(¬b) successfully.
I am now asked to create a decision tree for the same formula. What are the main differences between a parse tree and a decision tree?


texts: Dynamic programming VS Greedy Algroithms

texts:
I have two True or False questions in my practice test that are related but I am unsure about:

1. If an optimization problem can be solved using a greedy algorithm,
there must be a solution for this optimization problem using dynamic programming as well.

2. If an optimization problem can be solved using dynamic programming,
there must be a solution for this problem using a greedy algorithm as well.

I think the answers are 1. True and 2. False is this correct?


texts: Finding a minimal cover of a subset of a finite cartesian product by cartesian products

texts:
Given a subset of a cartesian product $I \times J$ of two finite sets, I wish to find a minimal cover of it by sets which are cartesian products themselves.

For example, given a product between $I=\{A,B,C\}$ and $J=\{1,2,3\}$, I may observe the subset $\{(A,2), (B,3), (B,2)\}$ and try to cover it with a minimal number of cartesian products.

Two ways to do so are $\{A\} \times \{2\} + B \times \{2,3\}$ and $\{A,B\}\times \{2\} + \{B\}\times \{3\}$, both requiring 2 products. A sub-optimal solution may be breaking it into 3 trivial products.

Can such an optimal cover be found efficiently (e.g., in polynomial time)?


texts: If a poly-time solution exists for an NP-Complete (Decision) problem, then there exists a poly-time solution for the NP-hard (Optimization) flavor?

texts:
This question boils down to: If a polynomial time solution exists for a decision problem, is there also a polynomial time solution for the same problems optimization flavor?
Let's take the Traveling Salesman Problem for example:

TSP Decision Problem (NP-Complete):
Input: Graph G, Budget b
Output: Does a route exist in G with a distance of at most b? (true/false)

TSP Optimization Problem (NP-Hard):
Input: Graph G
Output: What route in G has the shortest distance?

If one could find a polynomial time solution for the TSP Decision Problem wouldn't they also have a polynomial time solution for the TSP Optimization Problem?

Why? Binary search.

You can run your polynomial time solution for the TSP Decision Problem on G over and over with an input for b that increases, e.g. {1, 2, 4, 8, 16, 32, 64, 128, 256, ...}, until the algorithm returns false. Then you decrease b and slowly hone in on the correct answer.
Is this logic correct?


texts: Constructing preorder traversal from postorder of a Binary Search Tree in O(n)

texts:
We are given postorder traversal of a Binary "SEARCH" Tree (in an array) and we want to find (print) its preorder traversal.

A very naive solution is to check from end until we find element less than root so we can find left and right subtree and call the function on them. This is $O(n^2)$. Another way is to generate the BST from its postorder and then generate the preorder from postorder. it is $O$$($$n log n$$)$ because for generating tree we need $O(n log n)$ and for preorder traversal we need $O(n)$ and $O(n + n log n ) = O(n logn)$.

I think we can do it better in $O(n)$ because there is a lot known about the nature of the binary search tree and this extra information must help somehow. but I don't know how to use information we know about BST and implement this problem in $O(n)$.


texts: Why do AI researchers seem to think that consciousness is a computation?

texts:
Disclaimer: I am just an undergraduate student so my exposure to a lot of things is certainly limited.
I am not sure about the actual popularity of the idea that consciousness is a computation but my impression is that it is very widespread. I lost count to how many times I saw, sometimes very serious scientists, claim that we are just decades away from an actually intelligent AI (or AGI).
I also noticed a similar underlying premise with Machine Learning's "Neural Network" which is more or less exactly an implementation of the computational model of consciousness (which as far as I understand it [the model in the next sentence], assumes the Hodgkin-Huxley model to be true even though we don't actually really know that).
Am I wrong? Is it actually not as widely accepted and popular as I think it is?
If not, then why is it this widely accepted as fact?


texts: computing permanent of a 0-1 rectangular matrix

texts:
I need to compute the permanent of a 10*100 matrix. All the entries are either 0 or 1.

All I know is that I can compute the permanent of all 10*10 submatrices and then sum it to get the desired answer. But this involves 100C10=10^13 operations which is too much in my case.

Is there a better algorithm for this task?


texts:
I'm trying to prove the Connected Vertex Cover problem is NP-complete. That is given a graph $G=(V,E)$ and integer $k$, is there a subset $X$ of $V$ such that $|X|≤k$ and that for every edge $(u,v)\in E$ at least one of $u$ and $v$ are in $X$. Furthermore, the subgraph $G[X]$ induced by $X$ must be connected.

I know the structure of an NP-complete proof. But I have no idea what problem to reduce to connected vertex cover and how to go about it.


texts: Compile XPath Abbreviated Query to Unabbreviated version

texts:
The Xpath 3.1 presented by W3C includes the full grammar of the language with both abbreviated and unabbreviated syntax.
I am interested in references (if any) for any formal work done to compile/translate an XPath query in its abbreviated form to its equivalent in fully expanded unabbreviated form. Even work done on versions prior to 3.1 could be helpful.
Reference: https://www.w3.org/TR/xpath-31/#unabbrev https://www.w3.org/TR/xpath-31/#abbrev


texts: How come this turing machine running time is $O(n^{1+\log_2 2006}\cdot \log_2n)$

texts:
Given a deterministic Turing machine with an input tape and a work tape. The work tape is restricted to $\log_2 n+100$ cells ($n$ represents the input length) and its tape alphabet is of size $2006$. Moreover, the Turing machine has $27$  states.

I wonder how come the running time of such machine is $O(n^{1+\log_2 2006}\cdot \log_2n)$ (The answer is the correct choice for this multiple choices question out of an exam I practise)


texts: Compare-and-Swap in an RDBMS for custom locks and lock escalation

texts:
I'm applying the Compare-and-Swap technique to a SQL database to create custom row-level locking in my dataset, allowing for safe READ UNCOMMITTED isolation at the database level.

The Resource table includes a LockOwner GUID and a IsLocked BIT field.  To acquire a lock, a dirty-read query gets the ID, LockOwner, and LockStatus.  If Unlocked, attempt to UPDATE the Resource by (ID, LockOwner) with a newly generated LockOwner and LockStatus of Locked.  Abort and start again if no rows are updated - meaning someone else got there first.  Otherwise, the Lock is held in the READ UNCOMMITTED transaction.  The transaction is needed to allow rollback on client failure/abandon, but the dirty reads avoid locks.

This seems to me to work great for resources that are independent of each other.  But what must I add to account for a new kind of lock, ResourceGroup?

ResourceGroup to Resource is a one-to-many relationship.  Resources can be locked individually, but if the ResourceGroup needs to be locked, then all of the Resources must also be locked.

Locking a ResourceGroup is a far less frequent need than locking a Resource, so the scheme should be optimized for Resource queries, avoiding requiring joins to ResourceGroup if possible.

I am imagining a scenario where locking a ResourceGroup involves marking the member rows with some flag, but I'm not sure what scheme doesn't interfere with the original Resource-only scheme.  Part of the problem comes from the UPDATE of a Resource while it is locked (and therefore already UPDATED in another transaction).  I believe that even if the fields are different within the record, the UPDATE will place an UPDATE LOCK on the row, so any lock on ResourceGroup would introduce blocking that we are trying to avoid.  Even if we could do this, how would the ResourceGroup lock acquisition mechanism know when all of the Resources (which may have had locks in process as we began locking their peers) have been released?

There may be differences in this locking granularity by RDBMS, I'm on MS SQL 2005+.


texts: How does the Vertex Cover algorithm by Chen et al find its tuples?

texts:
I'm still fighting with the aforementioned paper "Improved upper bounds for vertex cover" by Chen, Kanj, Xia (PDF kindly provided by Yuval Filmus).

My current problem is that it's specified that the main vertex cover algorithm VC (page 7/21) has the following header VC(G, T, k), where G is the graph to process, T is a set of tuples and k is the bounding parameter.

My question is: what should the set of tuples contain in the first execution of VC?

It's said multiple times that the algorithm maintains this structure and generates tuples.
This is obvious, given the Reducing subroutine behavior.

What is giving me trouble is that Reducing is called before any further logic in VC and Reducing itself begins with a loop saying for each tuple (S, q) in T, which implies that the set T should be pre-populated.

Should I scan the whole graph for all the structures that would fulfill the criteria for being included in T? This seems a bit drastic, since the operations of Struction and General-Fold will cause the structures in T to be invalidated.

Currently, my best bet is that, given the list of priorities (page 8/21) of certain structures as well as the definition of a good pair (page 5/21, after Observation 3.3) I should search the whole graph for tuples, good pairs and vertices with high degrees and put them into T with appropriate priorities.
The first sentence from section 4. The algorithm VC (page 8/21) seems quite convincing:

  A tuple, a good pair, or a vertex of degree at least seven, will be referred to by the word structure. The algorithm will maintain a list of structures T, and then it will pick a structure and process it.

Can somebody provide some intuition?
Maybe I'm just missing something that's staring at me from the paper itself...

Reading deeper into section updating tuples (page 6/21), one can see the following paragraph:

  Since a tuple imposes certain constraints on the minimum vertex cover sought, one needs to be careful that the
  constraints imposed by the creation of a tuple do not conflict with the conditions imposed by other operations of the algorithm.

  The other operations that do impose constraints on the minimum vertex cover sought are the creation of (other) tuples, the struction operation, and the general folding operation.

  For example, the general folding operation assumes that when we are looking for a minimum vertex cover, we can look for one that either contains the set I or the set N ( I ) in the structure ( I , N ( I )) . This is mainly the reason why the set N ( I ) can be folded.

  If the general folding operation is applied, then this constraint imposed by the operation on the minimum vertex cover might conflict with the constraints
  imposed by a certain tuple. Therefore, to be on the safe side, when we decide to apply the struction or the general folding operations, we will invalidate all the constraints imposed by the tuples. That is, we will basically remove all the tuples.

So, even when I pre-seed T with some structures, they will most likely be removed anyway sooner or later, leaving an empty set and going back to square 1.


texts: data structure admitting top items with prefix

texts:
A trie can answer a query for all items with a certain prefix in $O(m + \log n)$ time, where $m$ is the number of matches and $n$ is the number of items. A trie also supports $O(\log n)$ insertion and deletion and takes $O(n)$ space.

Now suppose each item has a score. I am looking for a data structure that can answer a related query: give me the top $m$ items by score with a certain prefix. Ideally search, insertion, and deletion would have the same time as a trie, up to a constant factor, and space would be $O(n)$ as well. To this end we may assume items are short (of length $O(\log n)$).

This problem can be solved with $O(\log^2 n)$ insertion and deletion and $O(n \log n)$ space by forming a trie where every node contains a sorted set of items with that prefix sorted by score. But this approach uses excess time and space compared to a trie. Can we do better?


texts: Can the Sieve of Eratosthenes be adapted to find twin primes

texts:
The Sieve of Eratosthenes is an algorithm generate the prime numbers, $2,3,5,7,11,13,...$ by drawing a list of numbers crossing out multiples of the smallest number in the list.

Is there anyway to modify this algorithm to search for twin primes up to $N$?

One way would be to, generate the list of primes $p < \sqrt{N}$ and crossing out multiples of those primes should give prime numbers up to $N$.  Then we can check $p \pm 2$ and see if they also appear in the list.

I posted a related question about whether we actually have to generate all primes for this task on cstheory.SE.


texts: DFA for w|w has a length multiple of 2 or 3

texts:
I am trying to create a DFA and a regex for this kind of exercise:

$A = \{w ∈ \{0, 1\}^* |\text{length of w is a multiple of 2 or 3}\}$. I tried to do one for $2$ and one for $3$ and then combine them, but it didn't seem to work cause I miss some cases for example $6,7$ or so. Any help would be gratefully received :D


texts: What's the flaw in the P != NP proof in the article "The Computational Complexity of the Traveling Salesman Problem"

texts:
I am reading through some proof of inequality of P and NP
but they are not accompanied by the flaws in the reasoning so I'm  trying to find them by myself, just to see if I'm getting the logic right. As an example I am currently reading this (very short) proof that P != NP  and for me the lack in the argomentation is the following:
what the author writes about the algorithm is sacrosanct but does not deny in any way the possible existence of algorithms or tricks that would allow to solve the problem in polynomial time.

Am I right on this one?


texts: Kleene positive closure - help in proofing this claim

texts:
I just started a course called 'Automata and Formal Languages'.
I'm having difficulty in proofing\disproofing this equality.

$ (L_{1} \circ L_{2})^{+} = L_{1}^{+} \circ L_{2}^{+}
 $

Where:

$ L_{1} $, $L_{2}$ are Languages.

$\circ$ is the concatenation operation between two languages.

$+$ is the Kleene plus closure defined by $\bigcup  _{i = 1}^{\infty }L^{i} $

I tried finding a counter example and also tried to formally proof but had no luck.
Can someone please point me in the correct direction?


texts: Can we use Convolutional Neural Network for dataset containing numeric data?

texts: I am working on a project of " Fraud detection using deep learning" . For that I have a dataset containing some numerical attributes . Now the task is to use CNN for the above purpose. Please guide me how can we do that as I have observed that it can be used only for image classification. I would appreciate if I get some research paper or blogs related to that.


texts: Scapegoat Trees: Why are they only loosely a-height-balanced?

texts:
From Wikipedia:

  Even a degenerate tree (linked list) satisfies this condition if α=1,
  whereas an α=0.5 would only match almost complete binary trees.

  A binary search tree that is α-weight-balanced must also be
  α-height-balanced, that is

  height(tree) ≤ ⌊log1/α(size(tree))⌋

  By contraposition, a tree that is
  not α-height-balanced is not α-weight-balanced.

  Scapegoat trees are not guaranteed to keep α-weight-balance at all
  times, but are always loosely α-height-balanced in that

  height(scapegoat tree) ≤ ⌊log1/α(size(tree))⌋ + 1.

  Violations of this
  height balance condition can be detected at insertion time, and imply
  that a violation of the weight balance condition must exist.

From Open Data Structures (it uses a = 2/3):

  To implement the add(x) operation, we first increment n and q and then
  use the usual algorithm for adding x to a binary search tree; we
  search for x and then add a new leaf u with u.x=x. At this point, we
  may get lucky and the depth of u might not exceed log3/2q. If so, then
  we leave well enough alone and don't do anything else.

  Unfortunately, it will sometimes happen that depth(u)>log3/2q. In this
  case, we need to reduce the height.

Here's the code sample from Open Data Structures (http://opendatastructures.org/newhtml/ods/latex/scapegoat.html):

  boolean add(T x) {
        // first do basic insertion keeping track of depth
        Node<T> u = newNode(x);
        int d = addWithDepth(u);
        if (d > log32(q)) {
            // depth exceeded, find scapegoat
            Node<T> w = u.parent;
            while (3*size(w) <= 2*size(w.parent))
                w = w.parent;
            rebuild(w.parent);
        }
        return d >= 0;
    }

q is an over-estimate of the number of elements (n) in the tree so (q <= n).
So in the code example, it checks whether depth is greater than

height cannot exceed log1.5(q) per the reference code.

So then we know that:
log1.5(n) <= log1.5 (q)
height <= log1.5 (q) (mandated by the check in the insertion code)

The following inequalities are provided:

q/2≤n≤q
log1.5(q) ≤ log1.5(2n) < log1.5(n)+2

So from the second inequality and the log product rule we can get, log1.5(q) ≤ log1.5(2) + log1.5(n) < log1.5(n) + 2, although I'm not sure whether this would be relevant.

Here's a link to Galperin 1993: http://akira.ruc.dk/~keld/teaching/algoritmedesign_f07/Artikler/03/Galperin93.pdf.

So my question is where the "+ 1" comes from for the loose height balance property of the scapegoat tree? Sorry if it's something obvious
I'm not seeing...


texts: How to calculate the weight between neurons in ANN?

texts: I am currently learning Supervised ANN training using Backpropogation and I am stuck in this exercise. I calculated the δA using the equation at the bottom of the screenshot, however, I am unable to calculate δB because the weight of BD is not given. How do I find the weight of BD?


texts: What is the probability distribution of arrival times in a distributed system?

texts:
I'm going to simulate an asynchronous distributed system. In a distributed system, when a node sends a message, after $\Delta t$ seconds the message reaches to its destination.

My Question: What is the probability distribution of $\Delta t$s?


texts: Alias-resolution: How does "common successor"-heuristic work?

texts:
The "Common successor"-heuristic ist described here: Motamedi et al.: A Survey of Techniques for Internet Topology Discovery, p. 11, 2015
http://ieeexplore.ieee.org/abstract/document/6970764/

From the above named source:

  The “common successor” heuristic suggests which two IP addresses may be aliases. This heuristic relies on the prevalence of routers that respond to traceroute
  probes with the incoming interface. When two traceroute paths merge, the common IP belongs to the second router on the shared path. IP addresses prior to the common IP should belong to different interfaces of a single router and hence would be aliases. Figure 7 shows a partial view of a traceroute measurement from Host1 and Host2 toward Host3 in our toy example. In this example, the black interface succeeds the red interface in one traceroute and succeeds the blue interface in another traceroute. The heuristic suggests that the blue and the red interfaces are aliases.
  This heuristic falsely infers aliases in the presence of layer 2 switches or multiple-access clouds. Figure 8 depicts an alternate topology to Figure 7. The traceroute view in both figures are similar, hence the heuristic infers R26’s red
  interface and R23’s blue interface are aliases.

What I do not understand:
Even if there was no layer 2 switch and R23 and R26 would just route to R21, wouldn't they be regocnized as aliases by this heuristic. I just do not get how you can say two routers must be the same, because the have a common successor. Maybe the paths just start to merge in the "successor".


texts:
One of the conditions for A → α | β to be LL(1) grammar states that

  If β → ε in one or more steps then α doesn't derive any string beginning with a terminal in FOLLOW(A). Likewise If α → ε in one or more steps then β doesn't derive any string beginning with a terminal in FOLLOW(A).

I couldn't understand what is the intuitive meaning of this condition and why this condition should hold? I could easily understand if an example is provided for the answer.


texts: Deciding Recursive/Recursively Enumerable when given Turning machine encoding as a language

texts:
Let $L_{1}$ and $L_{2}$ be two languages defined as follows :
   $L_1 = \{ \langle M\rangle \mid L(M) \neq \emptyset \}$
   $L_2 = \{ \langle M\rangle \mid L(M) = \emptyset \}$
   where $\langle M\rangle$ denotes the encoding of a Turing Machine $M$.
$L_{1}$ is the set of encodings of TMs that accept at least one string (i.e. the with non-empty languages), and $L_{2}$ is the set of encodings of TMs that do not accept any string (i.e. with empty lanugages). By making a language out of such encodings, I am essentially asking a Turing Machine to decide on another Turing machine as to whether the second TM has an empty language or not. This is essentially the halting problem, and so both languages are undecidable.

Now, I am not able to characterize $L_{1}$ and $L_{2}$ from among

not recursively enumerable
recursively enumerable but not recursive
recursive


texts: Strengthening a given attack on discrete log

texts:
I am trying to prove the following claim:

Let $(G,*)$ be a cyclic group of size $m$ with generator $g$. Assume
there exists some adversary $A'$ of size
$T'=\frac{\left(T-O\left(\log m\right)\right)}{2}$, for some
$T$, such that $$\mathbb{P}_{b\gets
 G}\left[A'(b)=\log_{g}(b)\right]>\frac{1}{2}.$$ Show that there exists
an adversary $A$ of size $T$ such that $$\mathbb{P}_{b\gets
 G}\left[A(b)=\log_{g}(b)\right]>\frac{3}{4}.$$
Assume multiplication over $G$ requires $O(1)$ circuit.

How can I prove this claim? Intuitively, since $A$ is bigger than $A'$ in about $O(\log m)$, the construction should be based on dividing the problem into halfs recursively, as in binary search. However, I can't think of any clever way to do that...


texts: Selection type generated by nested loops where initial value is current value of parent loop

texts:
Consider the generator of the selections:

for (i1 = 0;  i1 < 10; i1++)
    for (i2 = i1; i2 < 10; i2++)
        for (i3 = i2; i3 < 10; i3++)
            for (i4 = i3; i4 < 10; i4++)
                printf("%d%d%d%d", i1, i2, i3, i4);

Result:

0000
0001
0002
...
0009
0011 <-- 0010 is skipped
0012
...
0019
0022 <-- 0020 and 0021 are skipped
0023
...
8999
9999

Generated selections have the following property: the order in the selection does not mater, i.e. 0011 0101 1001 1010 1100 are the same.

Basically it is 4-combination of the set { 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, ..., 9, 9, 9, 9}

What do you say to name this type of the selection?

I always get stuck when I say:

4-xxxxxxxx of the set {0, 1, 2, ..., 9}

where xxxxxxxx is the name of this selection.


texts: How were weights chosen in Runge-Kutta (4) method?

texts:
Consider an ODE $\dot y = f(t, y)$. We will approximate the value of $y$ using the 4th-Order Runge-Kutta method. Let $\Delta$ be the step size, then in step $i+1$ we have $~y_{i+1} = y_i + deriv\cdot\Delta~$, where:
\begin{eqnarray*}
  deriv &=& \frac{1}{6}(d_1 + 2d_2 +2d_3 + d_4) \\
    d_1 &=& f(t_i, y_i) \\
    d_2 &=& f(t_i + \frac{\Delta}{2}, y_i + d_1 \frac{\Delta}{2}) \\
    d_3 &=& f(t_i + \frac{\Delta}{2}, y_i + d_2 \frac{\Delta}{2}) \\
    d_4 &=& f(t_i + \Delta, y_i + d_3 \Delta)
\end{eqnarray*}
Why those particular weights were chosen: 2 for $d_2$ and $d_3$, and 1 for $d_1$ and $d_4$? Why not $deriv = \frac{1}{4}(d_1 + d_2 + d_3 + d_4)$? (or any other weights)


texts: Proof that the set of all universal CFGs is co-RE complete

texts:
Let $\Sigma^*\text{CFL} = \{G \mid G \text{ is a CFG; } L(G) = \Sigma_G^*\}$.

Enumerate the r.e. sets by $W_n$.

Let $\text{EMPTY}= \{ n \mid W_n=\emptyset\}$.

On page 4 of these lecture notes, to show $\text{EMPTY}\leq\Sigma^*\text{CFL}$ the author constructs a function $g\colon\mathbb{N}\to\{0,1\}^*$ such that

$$n\in\text{EMPTY}\iff L(g(n))\in\Sigma_n^*.$$

I think we actually want $n\in\text{EMPTY}\iff L(g(n))\in\Sigma_{g(n)}^*$. Is this correct?


texts: How to visualize complex algorithm, like Split Array Largest Sum

texts:
I am trying to do the leetcode question
I got the answer and trying to understand a systematical way to come up with the answer using the DP bottom-up approach, and I am having a hard time to understand it, up to m=2.

What would be the best way to visualized or step by step to come up with this answer??
What is non-after effect property?

The problem statement:
"Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays."
Example to clarify the Question
Given the array [7,2,5,10,8] and split it into 2, there are 4 possible ways to split the array, with a minimum of 1 element in a subarray:

[7][2,5,10,8]  , largestSum 25 = sum(2,5,10,8)

[7,2][5,10,8]  , largestSum 23 = sum(5,10,8)

[7,2,5][10,8]  , largestSum 18 = sum(10,8)

[7,2,5,10][8]  , largestSum 24 = sum(7,2,5,10)
min(largestSums) = 18

Intuition
The problem satisfies the non-aftereffect property. We can try to use dynamic programming to solve it.
The non-aftereffect property means, once the state of a certain stage is determined, it is not affected by the state in the future. In this problem, if we get the largest subarray sum for splitting nums[0..i] into j parts, this value will not be affected by how we split the remaining part of nums.
To know more about non-aftereffect property, this link may be helpful : http://www.programering.com/a/MDOzUzMwATM.html
Basic idea

row is referring to the partition size
col is referring to the array nums

**Visualized **
     7, 2, 5,10, 8
0[0, ∞, ∞, ∞, ∞, ∞]
1[∞, ∞, ∞, ∞, ∞, ∞]
2[∞, ∞, ∞, ∞, ∞, ∞]
3[∞, ∞, ∞, ∞, ∞, ∞]

Here is the working code and output


texts: Understanding Intel's algorithm for reducing a polynomial modulo an irreducible polynomial

texts:
I'm reading this Intel white paper on carry-less multiplication. It describes multiplication of polynomials in $\text{GF}(2^n)$. On a high level, this is performed in two steps: (1) multiplication of polynomials over $\text{GF}(2)$, and (2) reducing the result modulo an irreducible polynomial. We use the "standard" bitstring representation of polynomials, i.e. $x^3+x+1 = [1011]$.

The paper gives an algorithm for calculation of the remainder polynomial on page 16 in Algorithm 3. However, I'm having trouble understanding the reduction algorithm on pages 16-17 (Algorithm 4). Essentially, I think we need Algorithm 4 for larger fields when our or partial results don't fit 128 bits anymore. They give an example for multiplication of two polynomials in $\text{GF}(2^{128})$.

  Where do the "magic constants" 63, 62, and 57 for right shifts, and the "magic constants" 1, 2, and 7 for left shifts come from?

For example, how does one generalize the algorithm for smaller fields, say $\text{GF}(2^{32})$? Would the corresponding shift values then be 15, 14, 9 and 1, 2, 7?

  In the final step 4, the algorithm tells you to "XOR $[E_1:E_0]$, $[F_1:F_0]$, and $[G_1:G_0]$ with each other and $[X_3:D]$".

Why do we do this? As far as I can see, the result of this XOR operation is neither stored anywhere nor used anywhere. Is it somehow used for computing $[H_1 : H_0]$?


texts: Shortest path in graph - upgrade an algorithm

texts:
We are given a graph with $n$ vertices, $m$ edges, and path edge costs of $x$. For vertices without a direct path that are distant exactly one neighbor, we can add new edge with edge cost $y$. Our task is to find shortest path (i.e minimum cost) between the start vertex and all others vertices.

I have developed an algorithm, but I would like to create something faster than adding edges to the graph (via breadth-first search) and Dijkstra's algorithm. Here are a couple examples:

Example 1 Input: For $x=3$, $y=1$

Possible $y$ paths included:

Output: cost of shortest path from start node to node $i$ (assume that from start node to start node is 0)

  1: 0
  2: 2
  3: 2
  4: 1
  5: 1
  6: 3

Example 2 Input: For $x=3, y=2$

Output:

  1: 0
  2: 3
  3: 3
  4: 2
  5: 5


texts: Questions about Seth Lloyd's Programming the Universe?

texts:
I have been interested in Seth Lloyd's cosmological model (which proposes that the universe is a computer: https://en.wikipedia.org/wiki/Programming_the_Universe, https://arxiv.org/abs/quant-ph/0501135) since long ago. While I was "researching" about this topic, I found an interesting article that hungarian author Zoltán Galántai wrote (https://arxiv.org/pdf/1501.01754.pdf)

I was wondering if you would answer a few questions I have about the article. It would be very helpful if any of you could find some time to answer them.

In Zoltán's article he built a table indicating the possible types of computation that could exist. In the type "C3", he says:
"Computing based on different constants - in some cases it is impossible to interpret Lloyd's equations for them"
What does he exactly mean with this? Would Lloyd's cosmological model be compatible with this? Would his model be applicable to a universe with this type of computation?
He also built a table indicating the possible types of computational universes based on the speed of light. In the type 3 (U3) he says that computation is impossible since the speed of light would be 0. But, if that universe had some structure similar to a wormhole or any other kind of instant communication (maybe some kind of teleportation system or some kind of quantum entanglement that would be superluminal), couldn't light be able to transmit information without the need of moving at all? Couldn't that allow computation to occur? Anyways, could Lloyd's model be applied to a static (c=0) universe? I mean, would that model be able to "produce" that type of universe?


texts:
The m-th largest number in a list of n numbers can be found in $O(m \log n)$ using a max-heap. This avoids sorting.

Suppose I'm interested not in the actual numbers, but separation between adjacent numbers (after sorting). Is there an algorithm to find the m-th largest separation without having to sort the numbers? More precisely, the $m$ large separations create $(m+1)$ buckets, and I want to find the bucket each item belongs to (I don't care about the ordering within a bucket).

For example, the largest separation ($m=1$) problem can be solved by creating $(n+1)$ bins of equal size between the min and the max, and finding the bin each item belongs to. By pigeonhole principle, one of the bins will be empty, and this is the position of the largest separation.


texts: How to calculate genus of arbitrary graph? I am interested in any algorithm, even it based on full search.


texts: Uniform Hashing. Understanding space occupancy and choice of functions

texts:
I'm having troubles understanding two things from some notes about Uniform Hashing.
Here's the copy-pasted part of the notes:

Let us first argue by a counting argument why the uniformity property,
we required to good hash functions, is computationally hard to
guarantee. Recall that we are interested in hash functions which map
keys in $U$ to integers in $\{0, 1, ..., m-1\}$. The total number of such
hash functions is $m^{|U|}$, given that each key among the $|U|$ ones can be
mapped into $m$ slots of the hash table. In order to guarantee uniform
distribution of the keys and independence among them, our hash
function should be anyone of those ones. But, in this case, its
representation would need $\Omega(log_2 m^{|U|}) = \Omega(|U| log_2 m)$ bits, which is
really too much in terms of space occupancy and in the terms of
computing time (i.e. it would take at least $\Omega(\frac{|U|log_2 m}{log_2 |U|})$ time to just
read the hash encoding).

The part I put in bold is the first thing is confusing me.
Why the function should be any one of those? Shouldn't you avoid a good part of them, like the ones sending every element from the universe $U$ into the same number and thus not distributing the elements?
The second thing is the last "$\Omega$". Why would it take $\Omega(\frac{|U|log_2 m}{log_2 |U|})$  time just to read the hash encoding?
The numerator is the number of bits needed to index every hash function in the space of such functions, the denominator is the size in bits of a key. Why this ratio gives a lower bound on the time needed to read the encoding? And what hash encoding?


texts:
What are the best arithmetic algorithms out there (addition, subtraction, multiplication, division, power, root)?

I am looking for algorithms that could be easily extended to multiprecision and arbitrary precision settings.


texts: Given a prime power, is it possible to efficiently compute the prime

texts:
Suppose that I am given as input the number $p^i$ for some prime $p$ and some positive integer $i$. I wish to find $p$ and $i$.

Is there an algorithm to do this that works in time polynomial in the number of digits of $p^i$?


texts:
Prove that $L_2 = \{ w \in \{a,b\}^* \mid w = a^ib^j, i \neq j \}$ is not regular.

I was wondering if my intuition holds for proving this language as not regular:

Let $q = \max(i, j) - \min(i, j)$.

Case 1: $i > j$

Let $$L_3 = b^q \Rightarrow L_2 \cdot L_3 = \left \{ a^ib^{j+q} \right \}=\left \{ a^ib^i \mid i \ge 0 \right \}.$$

And then do the same for when $j > i$.

Is this allowed?


texts: Asymptotic running time function's domain

texts:
I am reading CLRS and have uncertainty in asymptotic running time of algorithms. In CLRS, it is said,

The notations we use to describe the asymptotic running time of an algorithm are defined in terms of functions whose domains are the set of natural numbers $N = \{0,1,2,...\}.$ such notations are convenient for describing the worst-case runtime function $T(n)$ which usually is defined only on integer input sizes. We sometimes find it convenient, however, to abuse asymptotic notation in a variety of ways for example we might extend the notation to the domain of real numbers, or alternatively restrict it to subset of the natural numbers

My first question is what is asymptotic running time of an algorithm. Some simply says that it refers to the order of growth of the function, while other describes it using limits. Then, why we take the domain as the natural number and in what cases abuse it, meaning to take the domain as reals. what it gives us to take reals as the function's domain?
I appreciate your answers.


texts: Dijkstra's shortest path algorithm without relaxation

texts:
Although I have found a very similar question to what I want to ask here (https://codereview.stackexchange.com/questions/96064/dijkstras-algorithm-without-relaxation), yet I didn't find a satisfactory answer there, hence comes this question.

So I have done competitive programming for fun for a while, whenever I need to find shortest path, I always implement something like this:

For the sake of brevity, this algorithm only finds shortest path's weight from a vertext s to a vertex d (instead of all vertices) (assuming there is no negative cycle in the graph of course)

1. Create an empty min heap with comparator is the weight
2. Create an empty set (most of the time hash set)
3. Add s to the heap with weight is 0
4. Add s to the set
5. while (heap is not empty)
6.    min = extract min from heap
7.    if (min == d) return min.weight
8.    add min to set
9.    for (v in adj of min)
10.        if (set is not already contains v)
11.           add v to heap with weight is min.weight + weight(min, v)

I have always believed that this is Dijkstra shortest path algorithm until today when I saw a video of lecture on Dijkstra algorithm from MIT. I realized that I never had the relaxation step in my Dijkstra algorithm.

So I'm really not sure if it is or just a variant of Dijkstra or not even Dijkstra (maybe A*? I'm not sure)?
Also, I have used this algorithm in programming contests many times, it always worked, but now I doubt about its correctness?

Yet, half of me still thinks this algorithm is correct because this not very formal proof:

At a given time, there could be multiple paths to v with different
weights in the heap, but once we extract first path to v from the
heap (calls it min_path), it has to be smallest weight path to v
in all the paths.
For all the other paths to v which haven't been
added to the heap, they have to have weight more than min_path's
weight because: when they are added to the heap, they can only be
added after extracting some other paths which have bigger weight than
min_path's weight, so their weights are bigger than min_path's
weight.

If my algorithm is correct, then I think the running time would be O(ElogV) and O(E) of space because:

The heap can have at most E elements at a given time

extract min costs log(E) < log(V^2) = 2log(V) = log(V)
same goes to adding an elmenet to the heap

In total, O(ElogV) for running time.

So in the end, I believe my algorithm has same running time with standard Dijkstra that has relaxation and decrease key step (that costs logV), only downside is my algorithm costs O(E) for space. Is this correct?

UPDATE1: Java sample code

public class Test30 {
    public static void main(String[] args) {
        List<int[]>[] map = new List[4];
        map[0] = Arrays.asList(new int[]{1, 2}, new int[]{2, 2});
        map[1] = Arrays.asList(new int[]{3, 9});
        map[2] = Arrays.asList(new int[]{3, 1});
        System.out.println(dijkstra(map, 4, 0, 3));
    }

    public static int dijkstra(List<int[]>[] map, int n, int src, int dst) {
        boolean[] been = new boolean[n];
        // 0: vertex, 1: weight
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        been[src] = true;
        pq.add(new int[]{src, 0});
        while (!pq.isEmpty()) {
            int[] pop = pq.remove();
            int v = pop[0];
            int weight = pop[1];

            if (v == dst) return weight;

            for (int[] i : map[v]) {
                if (been[i[0]]) continue;
                pq.add(new int[]{i[0], weight + i[1]});
            }
        }
        return -1; // impossible
    }
}


texts: Show that the following construction is not a correct proof for Context Free Grammars

texts:
Give a counterexample to show that the following constructions are not correct proofs for the star operation:
Given a CFG $G = (V,Σ,R,S)$, add the new rule  i) $ S → SS$ or ii) $S → SS|ε$.

For i), I basically said that this rule is an infinite loop and doesn't contain an epsilon, so can't be the star operation.
For ii) I'm stuck and can't see why it's not equivalent to the star operation
I know the real star operation is $S'→SS'|ε$ but cant seem to see find out why ii) is not the case. I can't find a counterexample.
Any help is hugely appreciated.


texts: Random restarts for unsatisfiable instances

texts:
In the worst case, Boolean satisfiability (assuming P!=NP) takes exponential time. Nonetheless, modern SAT solvers using variants of DPLL, are able to solve enough instances to be useful in practice.

One technique used, that has shown good results in practice, is random restart. Intuitively, randomly restarting means there is a chance of getting luckier with guessing the right variable assignments that would lead to a quick solution.

The same intuition suggests this should be much more effective when the problem instance is in fact satisfiable (so you only need to guess a set of variable assignments that constitute a solution) than if it is not (so in principle you have to check all possible assignments anyway, modulo sections of the search space that can be skipped via techniques like unit propagation and non-chronological backtracking, which are at least not obviously sensitive to the initial guesses).

Is the second intuition correct? Are random restarts in fact much more effective, on average, in cases where the problem instance is in fact satisfiable?


texts: Problems that feel exponential but are P

texts:
I'm trying to build a list of algorithms/problems that are "exceptionally useful", as in, solving problems that 'seem' very exponential in nature, but have some particularly clever algorithm that ultimately solves them. Examples of what I mean:

Linear Programming (The simplex algorithm is exponential time; it took a long time to find a polynomial time solution!)
More generally, Semidefinite Programming
Primality testing
2-SAT and HORNSAT
Computing determinants (if this doesn't sound difficult, consider the permanent)
Finding perfect matchings
A variety of hard group theoretic problems that can be accomplished using the Classification of Finite Simple Groups
A variety of hard graph problems that can be accomplished using complicated Forbidden Minor characterizations (embeddability on an arbitrary surface; bounding of treewidth and branchwidth; Delta-Wye reducible graphs)
Computing exponentials in a bounded group (i.e. computing $a^b \mod k$ in $\log b$ steps, as accomplished by repeated squaring)
Computations relying on the LLL algorithm. (As a special case: Euclidean algorithm. As a more general case: PSLQ or HJLS algorithms.)
Constraint problems without Taylor terms (?). I admit I don't fully understand this, but it sounds like it probably subsumes the 2-SAT / HORNSAT cases above, and any linear algebra over finite fields. See here for a longer post
Problems computable via holographic reductions.

As a honorable mention, I would also mention Graph Isomorphism, because it's still awfully easy ($n^{\log^2 n}$), and equivalent to so many other isomorphism problems:

Digraphs/multigraphs/hypergraphs (a sort of 'harder' problem)
Finite automata/CFGs

Obviously there's a range of difficulty in these, but all leave at least some people with some sense of 'surprise' in the sense that the problem can sound difficult but turn out tractable. LP might sound relatively straightforward, but took people quite a while to build an actual solution to. Repeated squaring or solving 2-SAT is something an undergraduate could possibly come up with on their own, but if you had only learned about NP-Complete problems without having seen HORNSAT, it might sound like a natural candidate for NP-Completeness. Solving the CFSG or having a polynomial way to check for Delta-Wye reducability are no mean feats.

I hope this makes sense; there are obviously lots of subjective attributes here, but I'm curious to hear what other people find to be efficient solutions to "obviously hard" problems.


texts:
I've been trying to solve the below problem the entire day but couldn't come up with a solution. I have the suspicion that it could by solved by a graph algorithm (or maybe some greedy approach?) but couldn't find something. Thanks for the help!
You have n baskets and m cats (m >> n). The cats don't like each other, H_{ij} denotes how much cat i hates cat j (H_{ji} = H_{ij}). Each basket b has a capacity C_b and each cat c needs space C_c.
How can you minimize the sum over the H_{ij} of all cat pairs (i,j) that are assigned to the same basket? Every cat needs to be assigned to a basket.


texts: Prove that $\#k-colouring$ graph problem is $\#P-complete$

texts:
I need to prove, that the $\#k-colouring$ graph problem is $\#P-complete$. I want to construct the reduction from $\#3SAT$ problem, so $\#3SAT \leq \#k-colouring$. The reduction between the counting problems consists of two parts. The first one maps instances of the first problem to the instance of the second problem (the same as within the reduction at decision problem) and the second part has to recover the number of solutions between the relevant problems.

For counting problems, there is a special type of reductions, called parsimonious reduction, where is the number of solutions identical. I read that for all known natural NP-complete problems, there is a parsimonious reduction from $3SAT$. However, consider $ 3-colouring $ graph problem, then the solutions come in groups of 6 since you can always permute the individual colours.

Will be the reduction $\#3SAT \leq \#k-colouring$ parsimonious or not? If yes, how to construct such reduction to prove that the number of solutions is identical and if not, how is the relationship between the number of solutions within both counting problems with respect to the $k$?


texts:
Question:The set of all first names given to children born in New Zealand in 1996

I think this language is regular because every element in the set can be a accept state

How can I prove if the language is regular?


texts: Struggling to understand the thought process required to come up with some recurrences for Dynamic Programming problems

texts:
I was doing a few dynamic programming problems and I am struggling to understand the thought process required to come up with recurrences.

The first problem I solved was longest palindromic substring and I managed to solve it successfully using the following logic: I have a function f(i,j) which returns the longest palindromic substring between characters at positions i,j in the string. I came up with the following recurrence:

f(i,j) = true // if(s[i] = s[j])
f(i,j) = true // if(i>j)
f(i,j) = true // if(s[i] = s[j] and f(i+1, j-1) == true)
f(i,j) = false // otherwise

Using this recurrence I managed to solve the problem successfully.

The second problem I wanted to solve was Longest valid parentheses (which I want to do using DP not stacks). The question is: Given a string containing just the characters '(' and ')', find the length of the longest valid parentheses substring.

My initial thought process was that this was similar to the longest palindromic substring problem that I already solved. So I defined f(i,j) as a function that returns longest valid parenthesis between elements i,j. The recurrence I came up with is as follows - here I use -1 to indicate that f(i,j) does not form a valid parenthesis:

f(i,j) = -1 // if i == j
f(i,j) = -1 // if j=i+1 and ! (s[i] = '(' and s[j] = ')')
f(i,j) = 2 // if j = i+1 and s[i] = '(' and s[j] = ')'
f(i,j) = 2 + f(i+1, j-1) if s[i] = '(' and s[j] = ')' and f(i+1, j-1) > 0;
f(i,j) = -1 // otherwise

My code (written in java) for the top-down version of the above is (note: dp[][] was initialized to -2 indicating state i,j is not processed yet):

private int topDown(String s, int i, int j, int[][] dp) {
    if(dp[i][j] != -2)
        return dp[i][j];

    if(i == j)
        dp[i][j] = -1;
    else if(j == i+1 && (s.charAt(i) != '(' || s.charAt(j) != ')' ) )
        dp[i][j] = -1;
    else if(j == i+1 && (s.charAt(i) == '(' && s.charAt(j) == ')' ) )
        dp[i][j] = 2;
    else if(s.charAt(i) == '(' && s.charAt(j) == ')' && topDown(s, i+1, j-1, dp) > -1)
        dp[i][j] = 2 + topDown(s, i+1, j-1, dp);
    else
        dp[i][j] = -1;

    return dp[i][j];
}

This does not work for inputs like ()() as it will return 2 instead of 4.

I was unable to come up with a solution of my own so I looked it up online. I found a solution here.

In this case the author defines f(i) as the length of the longest longest valid, balanced parentheses substring which begins at index i. He then describes the recurrence as follows:

f(i) = 2 + f(i+2)   // if s[i] = "(" and s[i+1] = ")"
f(i) = f(i+1) + f(i + f(i+1) + 2)   // s[i]="(" AND s[i+1]="(" AND s[i+f(i+1)+1]=")"
f(i) = 0    // otherwise

I have not written/tested the code for the recurrence but I assume it is correct.

My questions are as follows:

When I was solving the problem initially I had not thought of writing it as a function of f(i). I only thought of it as a function of f(i,j) and that turned out to be wrong. So is there an easy way to tell just by looking at a problem what states should be computed? For example why can't I solve the longest palindromic substring problem as a function of f(i)? similarly why can't I solve the longest parenthesis problem as a function of f(i,j)?
Is there a way to solve the longest valid parenthesis problem as a function of f(i,j) where f(i,j) represents the length of longest valid parenthesis between i and j? It is ok if the runtime complexity is higher I am just curious about this.

Thanks.


texts: Min-plus matrix and Shortest path variation

texts:
I was solving a problem in which given a directed weighted graph with no self loops (adjacency matrix),I had to find minimum path of length at least K between ever pair of nodes.
One  method is :
let say we want path from $u$ to $v$, let $w$ be the vertex in which we are after exactly $k$ edges. If the walk is shortest, we must get from $u$ to $w$ using a shortest walk with exactly $k$ edges (compute $D^k$ using Min-plus matrix multiplication) and then from $w$ to $v$ using Floyd-Warshall algorithm to compute all pair shortest distance.
Other method is what I don't understand and needed help with:
Calculate all pair shortest distance matrix using Floyd-Warshall algorithm and then compute $D^k$ using Min-plus matrix multiplication from that matrix, and every entry of it corresponds to the least path of length atleast $k$.
Needed some hints regarding correctness of second method also is doing such thing is a well known algorithm/method?
Thanks.


texts: Approach to find minimum set in one table consisting of all items in second table

texts:
wondering if you can help me with the following problem.

I have one table consisting of items in each person's bag:

name  |  item1  |  item2  |  item3
____________________________________
jack  | pen     | pencil  | eraser
____________________________________
jane  | phone   | pen     | camera
____________________________________
leia  | pencil  | eraser  | glasses

I have another list with all items that can be in a bag:

pen
pencil
eraser
phone
camera
glasses

What is the best approach to find the minimum list of names who have all the items in the list? For example, in this toy example, the output would be {jane,leia}.

Your help is much appreciated. Please also let me know if I should formulate the problem differently.


texts:
Hey guys in a turing machine can a state go to itself by reading a letter. For example,

q2 reading a 'c' to go to itself. Is that possible?

Or does it need to read a tape alphabet, such as $ to read that c and then go back to q2?


texts: Recover an array from its insertion indices

texts:
An array is built starting with an empty array, and then a sequence of insertions:

insert $a_1$ at index $z_1=1$
insert $a_2$ at index $z_2$
insert $a_3$ at index $z_3$
...

and so on.  When we insert element $a_i$ and index $z_i$ the result is that $a_i$ is now at index $z_i$, whereas everything before index $z_i$ is unchanged and everything after has its index increased by 1. (With one-based indexing) E.g., the sequence
$(3,1), (5,2), (1,2)$ gives $[3]$ then $[3,5]$ then  $[3,1,5]$. All of the instructions will make sense, i.e., $1 \leq z_i\leq i$.

My question is about how to calculate the final array. The naive approach would be to start with an empty array, and literally obey the instructions;  but in the language I program, insertions have a worst case time complexity of $O(\# $elements shifted$)$; if, for example, all the insertion indices were $1$, this would result in $O(N^2)$ time.

Supposing we have access to all the instructions simultaneously, how can we calculate the final array in faster than $O(N^2)$ time? I would be happy with a name if this problem is well studied. I did make the following (family of) observations:

the element which ends up at index 1 was the last one which arrived with index 1.
the element which ends up at index 2 arrived with index 1 or 2. If it arrived with index 2, then none came after it with either index 1 or 2. If it arrived with index 1, then exactly one came after it with index 1, after which came none with index 2.
the element which ends up at index 3 arrived with index 1, 2, or 3. If it arrived with index 3, then none came after it with index 1, 2 or 3. If it arrived with index 2, then exactly one element with index 1 or 2 followed it, then none after that with index 1, 2, or 3. If it arrived with index 1, then it was followed by one with index 1, then one with index 1 or 2, and then none after that with index 1, 2, or 3.

... and so on.
However I can't think of the algorithms or data structures that would make this information useful.

Update: There are two $O(n\log n)$ solutions below: the first one, which I accepted, that uses an AVL tree, and one which I learned of afterward that uses a semgent tree, and is somewhat simpler.


texts: Benefit of Backward Pass at compile time

texts:
We collect most of the information about possible compiler optimizations during forward pass. Is it possible to utilize the information collected in forward pass in a backward pass so as to perform better optimizations ?

Note: I have been going through the patent Compiler with cache utilization optimizations by Roch G. Archambault et al. (2004) and was wondering what kind of information might have been utilized in their backward pass.


texts: Automatic Downcasting by Inferring the Type

texts:
In java, you must explicitly cast in order to downcast a variable

public class Fruit{}  // parent class
public class Apple extends Fruit{}  // child class

public static void main(String args[]) {
    // An implicit upcast
    Fruit parent = new Apple();
    // An explicit downcast to Apple
    Apple child = (Apple)parent;
}

Is there any reason for this requirement, aside from the fact that java doesn't do any type inference?

Are there any "gotchas" with implementing automatic downcasting in a new language?

For instance:

Apple child = parent; // no cast required


texts: Decomposition of a directed graph into Hamiltonian paths

texts:
I was wondering if anyone knew of an algorithm that when given a directed graph will split it up into separate Hamiltonian paths. I don't really mind about nodes that can't be added to a path but as few paths as possible should be made to include the most nodes.

Any ideas would be greatly appreciated.


texts: ILP and number of variables in constraints

texts:
This question is about the time impact of the length (i.e. number of variables) of the constraints in an Integer Linear Programming formulation.
Most people try to reach the minimum number of constraints/variables, but I couldn't find anything that considers the size of the constraints.

In more concrete terms, I have some maximization problem for which I can make two different formulations $A$ and $B$.  Both have $O(n^2)$ variables, $n$ being the size of the input.

Formulation $A$ has $O(n^3)$ constraints, each having a constant number of variables (say each constraint is a summation over four variables).

Formulation $B$ has $O(n^2)$ constraints, but many constraints are of linear size - i.e. they include summations over $O(n)$ variables.

In terms of performance, does $B$ have an advantage over $A$ ?


texts: How does the Earley parser accept the input string as syntactically correct?

texts:
https://en.wikipedia.org/wiki/Earley_parser

An input string of length $n$ is syntactically correct if at least one $(S \rightarrow X_1 ... X_m • 0)$ is in $E_n$. Why is this the case ? The part before the dot (•) represents the subpart of the rule that derives a substring of the input string starting at position $i + 1$. Shouldn't the statement be:

An input string of length $n$ is syntactically correct if at least one $(S \rightarrow X_1 ... X_m • n)$ is in $E_n$ since I have parsed all the words before ? I.e, $n$ instead of 0.


texts: Why is SAT so important in theoretical computer science?

texts:
In my Computability and Complexity class, we are focusing on P, NP,
NP-complete, and NP-hard problems and the one thing that keeps coming up
is the SAT problem, in the context of reduction from one complexity to
another or to explain certain concepts.
Why is SAT so ubiquitous in theoretical computer science?


texts: What is the difference between directed graph and bidirectional graph?

texts: Is the graph above bidirectional? The image in wikipedia confused me a lot, before I heard about something called as bidirectional graph, I would say the above one a directed graph, but I am not sure now.


texts: Differences between the OS and DB buffer pool?

texts: How does the DB manage a pool of buffers when the operating system ends up controlling what's really in memory? For example, couldn't the operating system decide to evict a page frame from a DB's buffer?


texts: How to properly reduce a set of TMs to the halting problem?

texts:
Consider a standard enumeration of Turing machines ($T_0, T_1, T_2$, ...).

Then, let language A be defined as $A = \{n \in\mathbb N | T_n(\lambda) \downarrow\}$.

I need to reduce it to the halting problem (let's call it $K$). So, I want $K \leq_m A$ (mapping reduction).

I know that mapping reduction is based on the idea that $w \in K$ if and only if $f(w) \in A$. Also, $f(w)$ must be computable. I don't know how to reduce properly.


texts: Given list of numbers find for each number in the list the next distinct number

texts:
Given a sequence of numbers $l_1, \ldots, l_n$, I want to find for each index $i$ the next possible number to the right of $l_i$ (if any) that is different from $l_i$. What is the best time and space optimal solution to do this?

The numbers may be repeating and are in no particular order.


texts:
I'm dealing with this recurrence equation:

$\qquad\displaystyle T(m, n) = T(m/2, n/2) + T(m, n/2) + O(1)$.

Any idea how to solve this? I've looked in to few advanced resources but the literature on two dimensional recurrence equation seems to be very thin.


texts: Check if a linear function or an affine function can be a pseudo random function

texts:
Let $G = \{0, \cdots , p-1 \}$ be a field. Let $K = G^{m \times n}$ and $F:K \times G^n \to G^m$ be a family of functions.
For $A \in G^{m \times n}$ and $x \in G^n$ we have $F(A,x) = Ax$.
I need to check if $F$ is a secure pseudo random function.
We say that PRF $H: K \times X \to Y$ is $(T, \epsilon)$-secure if for every algorithm $B: X \to \{0,1\}$ of size $T$ it follows:
$$|P(B^{H_k()} = 1) - (B^{R()} = 1)| \le \epsilon$$
where $H_k(x) = H(k,x)$, $R:X \to Y$ is a random function, and $B^{S()}$ means $B$ has oracle access to the function $S$.
Now, back to the question, I tried to describe the following adversary B:
on input $x \in G^m$ and access to oracle $Z()$, $B$ will take $n$ base elements of $G^m$ and run $Z()$ on them.
Then, $B$ will check if $ x \in span\{Z(e_1), \cdots , Z(e_n) \}$ and return 1 if it is.
This way I get that $P(B^{H_k()} = 1) = 1$ and if $ m > n$ then $P(B^{R()} = 1) \le \frac{1}{p^{m-n}}$, which proves that $H$ is not secure.
The only problem is when $n \ge m$, since I am not sure how to get a good bound on $P(B^{R()} = 1)$ in this case.
Help would be very appreciated!
There is also the same question but with $K = G^{m \times n} \times G^m$ and $F:K \times G^n \to G^m$, $F((A,b), x) = Ax+b$.


texts: Efficient way to find degree of edge in induced subgraph?

texts: Let G(V,E) be a graph and H(V',E') be some induced subgraph of G. Let v be a vertex from V'. Is there an efficient way to calculate the degree of v in the subgraph H if we have some representation of G? (Preferably it should be O(1))


texts: Using DCEL to represent "simple geometric objects"

texts:
Many algorithms in computational geometry assume to have as input a complex data structure to represent a geometric object. The most common I know is the Doubly connected edge list, but there're also the halfdge data structure, winged edge etc... I was wondering if such data structure is also used to represent simple object. I know for example there's no need to represent a vertex or a line segment using a DCEL, however in practical implementations this would probably make the interface reusable, and therefore the whole algorithm implemented (unless we want to use some wrapper but I'm assuming I'm not).

So my question is, how can both points and segments be represented using a DCEL?

I would initialize the half_edge_incident field to be NIL and I would keep the  list_< HalfEdge* >  empty, same as the list< Face* >?

For the segment case I would just have two vertices entries not empty, two half edges entries not empty, the faces list would be empty.

Does this representation work?


texts: How much space an ascii character really takes on a 64 bit word addressable memory?

texts:
I know that an ASCII character needs 1 byte of memory for storage, but if a computer uses a 64-bit word addressable memory does it mean that the character actually takes 8 bytes even when only 1 byte was needed?
Does being a 64-Bit word addressable memory mean the same as being a 64-Bit machine?


texts: Can BPP be bounded around any constant other than 1/2?

texts:
A language $L$ is in BPP if there exists a randomised TM such that it outputs a correct answer with probability at least $1/2+1/p(n)$ for some polynomial $p(n)$, where $n$ is the length of the input. This probability can be amplified to $1-2^{q(n)}$, for some polynomial $q(n)$ by repeating the algorithm polynomially many times and taking the majority.

I was wondering if it is necessary to have this bound around the constant $1/2$? Can we have a randomised algorithm that answers correctly with probability $c+1/p(n)$ for some $c<1/2$ and still amplify the probability in polynomial time?

The proof for the case of $1/2 + 1/p(n)$ uses Chernoff bound on lower tail that requires $0 < \delta <1$. $\delta= 1-1/2p$ in that case which means $p$ should be greater than $1/2$. Proof here.

However here is a proof that weak BPP = Strong BPP where strong BPP is BPP as we know it and weak BPP is when if $x\in L,$ $P(TM\ accepts\  x) \geq s(n)+1/p(n)$, and if $x \not\in L, P(TM\ accepts\ x ) \leq s(n)$, where $p(n)$ is any polynomial and $s(n)$ is any polynomial time computable function.


texts: Finding a minimal width strip which encloses a set of points in the plane

texts:
Problem: Consider a set of $n$ points in the plane, how could we find a strip of minimal vertical distance that contains all points?

Definitions: A strip is defined by two parallel lines and the vertical distance is defined as the distance between their intersection points with the $y$ axis.

3 variables solution: In the plane itself, this could be solved using a linear program of three variables, $m$, $a$ and $b$ where we look for $y=m\cdot x+a$ and $y=m\cdot x+b$.

Duality: If we move to the dual plane, we get a set on $n$ lines which can be transformed to $n$ upper half-planes or $n$ bottom half-planes. Denote $C_1$ to be the intersection of all upper half-planes intersection and $C_2$ of the bottom ones. The strip in the dual problem is represented by the two ends of the shortest vertical segment crossing the $C_1$ and $C_2$.

My question is - can we express the problem in the dual plane using a linear program of two variables?