texts: Advantages of knowing foreign languages for natural language processing

texts:
I wonder about cases in which knowing several languages can lead a researcher to  interesting results in natural language processing.

For example, knowledge of foreign languages can without doubt contribute to better machine translation, it's the most obvious example.

In what other fields of NLP can a researcher benefit from knowing several languages?


texts: Connecting an unconnected forest of subtrees in a graph?

texts:
If I have a weighted graph $G=(V,E)$ and three subgraphs $T_1$, $T_2$ and $T_3$ in $G$ which are trees and all unconnected from each other.

What is the best way to connect these three trees such that the resultant connected tree is of minimal cost?

If it helps, I have already used the floyd-warshall algorithm to calculate the total distance matrix of $G$.

I was thinking of just iterating over all pairs of vertices $(T_1,T_2)$, $(T_1,T_3)$ and $(T_2,T_3)$ in the distance matrix and find two values from two of those groups that sum to the least. But that feels like it would be very inefficient.

essentially iterating over every vertex almost twice to get the distance values, and then iterating over those values twice again to find the smallest sum. Ending up with a complexity of like $\mathcal{O}(V^3)$ or $\mathcal{O}(V^4)$ or something (forgive me, its been a few years since i did any complexity theory)

Is there a simpler, more efficient solution that I am missing?

EDIT:
I have previously worked out a solution (not necessarily very efficient), to the problem if there are only two trees. Using the distance matrix, I iterate over every pair of vertices in $T_1$ and $T_2$, and then use dijkstra's algorithm to find the shortest path that joins the pair of vertices with the lowest value in the distance matrix.

Am I on the right track at least for the instance where there are only 2 trees? This method seems to get a lot trickier and much less efficient when there are more than 2 trees.

CLARIFICATION:
There seems to have been a bit of confusion (in a subsequently deleted comment) about what I am asking, so I will be more explicit.

The subgraphs $T_1$, $T_2$ and $T_3$ are trees in $G$, but are not connected to eachother.

here is an example:

I am trying to work out a good method of connecting all three trees such that it results in the smallest total cost

From the example I have given, it is pretty trivial to connect $T_2$ and $T_3$, just find an MST over the union of their two vertex sets because they share a single edge. However my problem stems from trying to connect $T_1$ to the rest; there are a lot of ways in which I can draw a path from $T_1$ to the other two, but I want to find the shortest one.

The only way I have thought of so far is to iterate over all the vertices in $T_1$ and see which one is closest to the vertices in $T_2$ and $T_3$ and then use dijkstra to find the shortest path. But this becomes pretty inefficient with very large scale graphs.

So I am looking for a more efficient method of doing this.

I hope that is more clear.

UPDATE:
In response to @D.W.'s answer to my related question here on solving a simplified version of this problem with only two vertex sets.

In order to extend that solution to this, more complicated, instance of the problem with three distinct vertex sets. Do I just need to create 3 dummy vertices $\{t_1,t_2,t_3\}$in $G$ with edge lengths 0 that link to $T_1$, $T_2$ and $T_3$ respectively, and then run dijkstra 3 times: $t_1 \rightarrow t_2$, $t_1 \rightarrow t_3$ and $t_2 \rightarrow t_3$, to find the minimum path $p_1$ that joins two of the three vertex sets; then if, say, the shortest path lay between $t_2$ and $t_3$ then run dijkstra again to find the shortest path $t_1 \rightarrow t_4$ where $t_4$ is a dummy vertex with 0 edge cost linking to the set $\{T_2 \cup T_3 \cup p_1\}$?

Or is that making things too complicated?


texts: Tennis Tournament Divide and Conquer for arbitrary number of players

texts:
I'm struggling with a divide and conquer algorithm for the Tennis Tournament (or Round Robin tournament).

I can successfully build a timetable if $N$ (number of players) is $2^k=N$, but Brassard-Bratley, Fundamentals of Algorithmics suggests that is possible to build a divide and conquer algorithm for an arbitrary number of players.

However, I can't find a rule to build such timetables.

For example, an N=4 is very easy to schedule. Divide by two, do tournaments, then merge each one on the left with each one on the right:

|1|2|3|4|
|-------|
|1-2|3-4|
|-------|
|1-3 2-4|
|1-4 2-3|

With N=5, I have problems because the parts of the division by two have different sizes

|1|2|3|4|5|
|---------|
|1-2|3-4  |
| - |3-5  |
| - |4-5  |
|---------|
|1-5 2-4  |
|1-3 2-5  |

And of course in the empty spaces, you could put 1-4 and 2-3, but I don't know how to generalize this.

And if N=7, there are no empty spaces and just fills perfectly.

|1|2|3|4|5|6|7|
|-------------|
|1-2  |4-5|6-7|
|     |-------|
|2-3  |4-6|5-7|
|1-3  |4-7|5-6|
|-------------|
|1-4 2-5 3-6  |
|1-5 2-6 3-7  |
|1-6 2-7 3-4  |
|1-7 2-4 3-5  |

So, what's the general rule to follow in a divide and conquer approach to the tennis tournament?


texts: Finding Smallest Frontier for Graphs of bounded pathwidth

texts:
Let $G$ be a graph and $X=x_1,x_2,...,x_n$ be an permutation/ordering of the vertex set of $G$. We then let $S_i = \{x_j:j\le i\}$, and $F_i$ be the number vertices $v\in S_i$ that are adjacent to some vertex $u \not\in S_i$. (where $u$ may depend on $v$ and $i$) We finally define $F$ to be a list of values $F_i$ sorted from largest to smallest. e.g. if $F_1=2,F_2=1,F_3=6, F_4=2$ we’d have $F = 6,2,2,1$ (we caution that in reality $F_{i+1}-F_i\le 1$ so the sequence features in the example could not occur)
In general, finding $X$ such that $F$ is lexicographically minimal is a task which I’d assume is NP-Hard. However, I am curious if there exists a polynomial algorithm to do this for graphs with bounded pathwidth.


texts: How might I express a sequence of operations in formal terms?

texts:
I want to be able to represent a set of operations in sequential order such that they will represent what is traditionally called a "function" (which is not always the mathematical definition of a "function"). However, I'm trying to define more primitive terms:

object - Anything that can be manipulated throughout the course of a program; that is, they can be read and set.

place - A container that can hold value. (e.g. variables)
value - A value. (e.g. 2+2 is a value but not a variable).

procedure - A sequence of operations.

I want to be able to define procedure in more definite terms. Note that I will be starting without the definitions of operations, as I want to be able to define basic operations as procedures.

I know that I may want to introduce the sense of "time" and "space" for programs, time being necessary due to the definition of "sequence" that I put forth. Is there a better way to define it? Is there already work out there that explores this?

How would you formally define a procedure or operation at its most basic level?


texts: How to show that f(x) is primitive recursive?

texts:
Let

  $$f(x)=\begin{cases} x \quad \text{if Goldbach's conjecture is true
 }\\ 0 \quad \text{otherwise}\end{cases}$$

  Show that f(x) is primitive recursive.

I know a primitive recursive function is obtained by composition or recursion, but I don't know what should I do about this problem.


texts: Applying the graph mining algorithm Leap Search in an unlabeled setting

texts:
I am reading Mining Significant Graph Patterns by Leap Search (Yan et al., 2008), and I am unclear on how their technique translates to the unlabeled setting, since $p$ and $q$ (the frequency functions for positive and negative examples, respectively) are omnipresent.

On page 436 however, the authors clearly state that "In the following presentation, we are going to use the second setting (Figure 3) to illustrate the main idea. Nevertheless, the proposed technique can also be applied to the 1st [unlabeled] setting."


texts: Finding lower bounds for data structures with non-standard interfaces

texts:
Consider the problem of designing a data structure that provides the interface functions  $\rm{pop}, \rm{push}, \rm{findmin}$, all running in constant time. This problem may be solved by (e.g.) having the $\rm{push}$ method compute the new minimum as well, and place it on the stack together with the pushed element.

Is there any systematic approach to determining lower bounds (of time and space complexity) for data structures exposing a given set of interfaces? E.g. $\rm{push,pop,sort, insertAtIndex}$? Can you provide links to relevant literature?


texts: PDA pushing nothing given an input and the current stack top

texts:
If we had a language $$\sum = \{a,b,c\}$$
for a pushdown automata, and the transition
$$a;A/AA$$
means "If you read in an a and A is at the top of the stack, push A", then would you be able to push nothing if you encounter an a and A is at the top of the stack with the transition:
$$a;A/\epsilon \space C$$
I am new to this notation so I am unsure of if I am doing it correctly.


texts: Why not just use FSTs for combining syntactic and semantic analysis?

texts:
I've just found the finite state transducer.

Since the FST processes two tapes: one for input, one for output,

shouldn't it be possible to use FST to "pack together" some compiler stages, such as Syntactic Analysis and Semantic Analysis.

The FST could take in tokens and output semantically analysed code.


texts:
Note that I had asked this question in GIS forum, although it
  has gotten many up-votes, still has not received any answer. Hope you can
  break the silence, some collaboration :)

Consider a region (2D) filled with lines randomly (following Figure). We are interested in filling the empty spaces between lines including four boundary edges in a way:

0- maximizing the size of parcels;
1- shape of filling parcels is square aligned horizontally or vertically;
2- shape of filling parcels is square, i.e., relaxed alignment;
3-  shape of filling parcels is any quadrangle. our original question

So for now there are three different scenarios.
Note that the lines are of the form [x1,y1,x2,y2] point set, real numbers.

[* * *] Ideas of possible solutions/algorithms/code snippets/etc are more than welcome.

For the first case i.e., horizontally/vertically aligned squares, our proposal as a solution is:
1- rasterising input lines into bitmap (matrix) using e.g., Bresenham's algorithm
2- searching nearby cells for each cell of desired colour (i.e., the same colour) with an objective function to maximize the associated area i.e., the number of pixels.

We assumed that the reader is familiar with the concept of space-filling-tiling. You may follow this link for inspiration. However, note that our problem is different. As we do not fill the empty space randomly and we do not choose the size of filler shapes randomly. The solution should be iterative, starting from largest to smallest permitted. The size boundary can be defined, for example, according to our explanation below for a particular study (our interest). For all the cases, there is no limit on the number of parcel being fitted. Indeed, it is up to user to limit the iteration number, by choosing a minimum area for parcels, for example. This is obvious in the example given above in which we discretised lines into pixels with specified size. That is, the procedure should run until entire empty area is filled respecting the criterion e.g., the maximum area of parcels.

A mathematical view for the problem can be stated as follows:
2D: Find all rectangles that could be extracted from a given 2D region with some lines optimized for larger rectangle size as possible.
3D: Find all rectangular cubes that could be extracted from a given 3D region with some sub-planes (better: polygons) optimized for larger block size as possible.

- Application:
One application is to find out the distribution of extractable intact 'rock' blocks in a heavily fractured 'mine'. This could be very helpful for many aspects including drilling design, financial evaluation and so on.

-- Details:
For a mine of decorative rock (stone) the products which are the blocks of intact rocks cut as rectangular cubes the price is closely dependent to the size of the block.  Extraction of a block from a suitable area i.e., with no major fracture will be desired if the amount of remaining parts is small as possible. Usually, the small pieces of rocks have no economic value relatively and are considered so as waste.
The question in this post investigates solutions for this kind of problem.

Size Constrains:
You may put some restrictions on the solution for the ultimate question, although, we believe it is always possible to add more later.  For example, follow these:
{2D case}
The best size of a block (economically optimum rectangle) to be extracted under the conditions mentioned above, is 1x1 m given 10x10 m for the region in the example. This is one constraint defined based on economical value. The minimum workable size for cutting etc, let be 0.15x0.15 m; so this the second size limit.

The figure above shows the economic value function depending to the block size. So for this particular case every rock piece smaller than 0.15x0.15 m is just waste. There will be no block size larger than 1.7x1.7 m due to operation limits.


texts: Why is $NP \subseteq P \implies NP^A \subseteq P^A$ false?

texts:
My question is about why does the result of Baker-Gill-Solovay not prove that $P \neq NP$. There have been several questions on this forum about this topic perhaps but I couldn't find my specific question amongst them.

Context: This is what I had in mind when I first saw the Baker-Gill-Solovay result (there exists an oracle $A$ such that $P^A \neq NP^A$): I will try to give a proof for $P \neq NP$. Suppose $P=NP$ then $P^A = NP^A$ for all oracles $A$. By Baker-Gill-Solovay result we arrive at a contradiction. When I asked my prof about this he said that the implication $P=NP \implies P^A = NP^A$ is wrong. So I wanted to check why (and where) does it fail.

I think it is correct that $P \subseteq NP \implies P^A \subseteq NP^A$ for all oracles $A$ because any poly-time TM with oracle access to $A$, is also a poly-time NDTM with oracle access to $A$.

My question is: Why (if $NP \subseteq P$ then for any oracle $A$, $NP^A \subseteq P^A$) is false?

My reasoning would go as follows: $NP \subseteq P$ means that given any NDTM (which involves a guessing sequence, followed by a poly-time verification), I can replace the guessing sequence with some poly-time TM. But given a NDTM with oracle access to $A$, I cannot directly replace the guessing sequence with some poly-time TM (as per the hypothesis), because in this NDTM, the guessing sequence might involve the access to oracle $A$.

Following that, I want to argue why isn't it so, that given a NDTM with oracle access to $A$, I can move all these calls to oracle $A$, after the guessing sequence? That is to say - why couldn't I, using non-determinism, guess the answers to my oracle queries and in the final step, verify these particular guesses using actual oracle queries?

More precisely, can I not re-define the definition of $L \in NP^A$ as follows: there exists a poly-time TM $M$ and a polynomial $p$ such that $x \in L \iff \exists w$ such that $|w| \leq p(|x|)$ and $M^A(x,w) = 1$?

Apologies for being too vague in my arguments above but I have just started learning Complexity Theory.

Edit1: Changed the question from
given a oracle $A$, if $NP \subseteq P$ then $NP^A \subseteq P^A$ to if $NP \subseteq P$ then for any oracle $A$, $NP^A \subseteq P^A$

Edit2: My definitions are: $P^A$ is the set of languages decided by a poly-time TM with oracle access to $A$ and $NP^A$ is the set of languages decided by a poly-time NDTM with oracle access to $A$

Edit3: Added more context to the problem.


texts: When does the nearest neighbor heuristic fail for the Traveling Salesperson?

texts:
Can you provide an example of NN algorithm failure on the Euclidean traveling salesman problem?

I was trying to construct a specific example of this for my friends and was failing.


texts: Reference request: proof that if $L \in DCFL$, then $L \Sigma^* \in DCFL$

texts:
So, it's fairly easy to prove that if $L \in DCFL$, then $L \Sigma^* \in DCFL$. Basically, you take the DPDA accepting $L$. You remove all transitions on final states, and then for each $a \in \Sigma$ and each final state $q$, you add a transition looping from $q$ to $q$ on $a$.

I'm using this in a paper, and I'd love to not have to actually prove this construction is valid. It's easy, but it's about a half-page long. Since DPDAs have been studied almost exhaustively, I was wondering, does anybody know of a paper that proves this property?


texts: Time complexity - Head stay transition - Turing Machine

texts:
I'm checking time complexity in a turing machine.
There is a transition that doesn't move the head, it justs stays (not right nor left movement) .
Should I count that state transition to calculate the complexity, -even though- the head doesn't move?
I understand that it should be counted as that step would take a time unit anyway, but i'm not sure really.
Thanks!
Sorry for my english!


texts: Is every Turing complete set for EXPSPACE autoreducible?

texts:
I'm reading about autoreducibility, which is the following notion:

  A set $L$ is autoreducible
  if there is a polynomial-time oracle Turing machine $M$
  that accepts $L$ using $L$ as an oracle, with the caveat
  that $M(x)$ may not query whether $x \in L$.

I encountered some results that are confusing me. In  Using autoreducibility to separate complexity classes,  Buhrman et al. showed that every polynomial-time Turing-complete set for EXPSPACE is autoreducible (Theorem 4.1). In Diagonalization, a survey by Fortnow, there is a theorem stating that if every Turing-complete set for EXPSPACE is autoreducible then $NL \neq NP$ (Theorem 3.1). So using both theorems together, we have $NP \neq NL$! I want to know where is my fault.


texts: Problem regarding Turing Machine notation

texts:
Here I have a Turing Machine (sorry for awful drawing):

So, I have a question regarding the usage of a here. It is treated as a variable here. But since it doesn't alter input tape in any way, shouldn't it be stored in an implicit storage? My question is if this implicit storage (tell me if I am wrong) is in conflict with the fact that a Turing Machine only has a single input tape.

My hunch is that it is syntactic sugar and it can be explicitly defined with less-intuitive notation (another input tape?), but I am not sure.


texts:
Let's say I have an alphabet
$$\Sigma = \{A, B, C, D, E\}$$

with probabilities
$$P(A) = P(B) = P(C) = 0.25 \text{ and } P(D)=P(E) = 0.125.$$

I know that the entropy then is:
$$H(\Sigma) = 3 \cdot 0.25 \cdot \log 4 + 2 \cdot 0.125 \cdot \log 8 = 2.25.$$

My question now is: What does this mean in relation to the lower limit of compression? How many bits will I at least need to compress a text that consists of the above alphabet?


texts: How to reduce Untyped λ-Calculus to Normal Form?

texts:
I have an assignment to do which involves reducing an Untyped λ-Calculus expression to Normal Form. I am struggling to come to terms with Lambda Calculus though.

For example, one small part of the expression is:

((λ n f x . n f (f x)) (λ f x . x))

Does this mean that we substitute (λ f x . x) in for every n, f and x? Giving us the following:

((λ n f x . (λ f x . x) (λ f x . x) ((λ f x . x) (λ f x . x))))

If so, can this be reduced further? I know I am probably way off with this, but I just do not understand it; any help would be appreciated.


texts: All pair shortest path in a tripartite graph

texts:
I have a tri-partite graph with three sets of vertices source, bridge and destination nodes. I want to find the shortest path between every vertex in the source set to every vertex in the destination vertex. Also, all vertices in the source set are connected to all vertices in the bridge set, and all the vertices in destination set are connected to all the vertices in the bridge set.

Let $n$ be the cardinality of both the source and the destination set, and $m$ be the cardinality of the bridge set.

A naive algorithm can compute these in $\mathcal{O}(n^{2}m)$ comparisons.
On the other hand, since we are computing $n^{2}$ quantities, so the complexity will be at least $\mathcal{O}(n^{2})$.

My guess is that it can be done in $\mathcal{O}(n^{2}\log m)$ using priority-queue.
So question is, whether my guess is correct and if not, then what is the complexity of solving this problem?

Edit:

Note that shortest path between a vertex in the source set to any vertex in the bridge set is the direct link, and same holds for the shortest path between the bridge and destination set.


texts:
I have recently been interested in low level computer science (as a hobby), and I have just learned about the way a computer organizes and stores information on a hard drive. I have learned the basics of how a filesystem works. I understand that in the case of Unix, an inode entry is created for each file in the inode table near the beginning of your drive, and each inode has a preallocated block for storing direct and indirect pointers to fragments of the file.

I have a few questions regarding this:

If the block pointers are stored in order (which I'm assuming they are), how does the computer handle deleting or modifying from the middle of a file? As I've understood so far, filesystems were designed because storing files in order on the drive is messy and modifying/removing files in the middle of the drive would mean everything else would have to be shifted around. But don't inodes create this same issue on a smaller scale? When deleting or modifying the middle of a file, if the computer reads from the block pointers in order, you would need to shift every pointer back one space, even in the indirect pointers, because there would be a new empty space in the inode table for a block pointer, assuming you deleted/modified more than the size of the block its pointing to. How does the filesystem handle this?
The same question applies to the actual inode table itself. When removing a file indexed somewhere between other inodes, are all the following inodes just shifted back? I would think if this is how the filesystem truly operates, it would slow down your computer a lot.
How is empty space in each block dealt with? Say the size of each block being pointed to is 4K on this particular system. What if I delete 2K of data from the center of the file? Is the remaining 2K zeroed over and left unused? What about the end of the file? If this is the case how does the CPU know how much free space is at the end of each block when loading a file into RAM? And wouldn't this leave a lot of wasted storage space on your drive?

If someone could clear these questions up for me that would be great. I have a curious mind. Thank you.


texts: Is the language of TMs that halt on some string recognizable?

texts:
I would like to show that the following language is recognizable:
$$L:= \{ \langle M \rangle \mid M \text{ is a TM that halts on some string}\}.$$

How do I go about showing that this language is recognizable? I know that all recognizable languages are reducible to $HALT_\epsilon$, so I figure if I can show that this language reduces to $HALT_\epsilon$, then I am all set. I am defining $HALT_\epsilon$ as follows:

$$HALT_\epsilon:= \{ \langle M \rangle \mid M \text{ is a TM that halts on } \epsilon \},$$

where $\epsilon$ is the empty string. We can reduce $HALT$ on $x$ to $HALT_\epsilon$ by a reduction $F(\langle M, x\rangle) = \langle M' \rangle $, where $M'(y) = M(x)$. For this reduction, we just ignore the input string $y$, which we know will be $\epsilon$ and just run $M$ on $x$ instead. Here, $HALT$ is defined as

$$HALT:= \{ \langle M,x \rangle \mid M \text{ is a TM that halts on } x \}.$$

I tried leveraging a similar technique to show that $L$ is recognizable, but I could not come up with anything better than this (somewhat crazy) TM that has a $HALT_\epsilon$ oracle:

$ D^{HALT_\epsilon} =$ On input $\langle M \rangle:$

Construct $N = $ "On input $x:$

Run $M$ in parallel on all inputs $y\in \Sigma^*$.
If $M$ halts on any $y$ then accept, otherwise loop."

Query the oracle to determine whether $\langle N \rangle \in HALT_\epsilon$.
If the oracle answers YES, accept; if NO, reject.

Note: My notation for TM algorithms is based on "Theory of Computation" by Sipser. Step 2 for the definition of $N$ is a bit redundant, but in this type of context, is it okay to say something like "If $M$ halts on any $y$, then halt?"

I think all I have shown here is that $L$ is decidable relative to $HALT_\epsilon$. I don't know if this implies that $L$ is recognizable. Can a Turing reduction be used in this manner to show that a language is recognizable? I'm confused as to what it means for a language to be recognizable. The task seems obvious if we go back to the definition: If some TM $R$ accepts strings in $L$, then $R$ recognizes $L$. So what if $R=D^{HALT_\epsilon}$, and in the body of $D^{HALT_\epsilon}$ we use some crazy reduction like $N$?

In general, to show recognizability, can we just come up with a reduction like $N$ that may or may not halt? Is it a problem that $N$ will never halt if $\langle M \rangle \notin L$?


texts:
A Go-back-N sender just receives an ACK packet with sequence number . Before this
ACK is received, sender’s window is [,  +  − 1] where  is the window size.
Suppose  > , packets may be lost or corrupted but will not be reordered. What is
the smallest possible value of ?
Can I know why is the answer for this k-1 instead of k? Can't really figure this out and will be grateful if someone can enlighten me on this. Thanks!


texts: Number of logic gates for "reasonable" Turing completeness

texts:
Somewhere on stackexchage, I, or someone else asked what was the proper term for Turing completeness minus the infinite memory (e.g. a Turing machine that one can actually build, no bigger than your typical data center).  Answer was inconclusive.

Also, someone else asked somewhere else on stackexchange about the number of gates for a Turing machine, but that got sidetracked into the useless infinite definition (that many quanta do not exist in the known universe).

So using the non-infinite Turing machine definition (*), whatever that is, is there a known lower bound on the number of 2-input binary gates needed to produce a Turing complete computer?  Or a reasonable guess or a minimum among known current published existing example implementations?

(* If necessary assume the "tape" is external to the logic gate count, the gates just drive the tape read/write/move mechanism).


texts: Leftist Tree initialization in O(n) time

texts:
In the book Handbook of Data Structures and Applications, section 5.2.5, (copy of the relevant section available here) about leftist queues, the author(s) state the following:

  For the complexity analysis of of the initialization operation, assume, for simplicity, that n is a power of 2. The first n/2 melds involve max HBLTs with one element each, the next n/4 melds involve max HBLTs with two elements each; the next n/8 melds are with trees that have four elements each; and so on. The time needed to meld two leftist trees with 2 i elements each is $\mathcal{O}$(i + 1), and so the total time for the initialization is
  $$\mathcal{O}(n/2 + 2 (n/4) + 3(n/8) + \ldots) = \mathcal{O}(n\sum \frac{i}{2^i}) = \mathcal{O}(n)$$

However, it seems to me that the summation iterates from i = 0 to $\log(n)$: $\sum_{i=0}^{\log(n)}$. This means it varies based on n, which in turn means the algorithm doesn't achieve $\mathcal{O}$(n) time as claimed but instead $\mathcal{O}(n \sum_{i=0}^{\log(n)} \frac{i}{2^i})$ time.

Am I misunderstanding something? I've found other explanations online stating $\mathcal{O}$(n) time for this sort of mass initialization is possible, but this is the only proof I've found so far.


texts: Applications affected by memory performance

texts:
I'm writing a paper on the topic of applications affected more by memory performance than processor performance. I've got a lot written regarding the gap between the two, however I can't seem to find anything about the applications that might benefit more from memory performance.

I suppose these are applications that make a large amount of memory references, but I have no idea what kind of applications would make such large number of references to make it stand out?

Can you please give me any pointers on how to proceed, some links?


texts: Request for examples regarding PAC learnability

texts:
I am searching for 2 examples.
At the bottom I give definitions I am using.

An example for H that is PAC learnable (according to 3.1) but not Agnostic PAC learnable (according to 3.3). We learned that such should exist. I saw in another post a comment that 3.1 and 3.3 are equivalent but i can't comment there (permissions) and don't see why - any way if you know such example or have a proof there is no, i'll be glad to read.
An example of H with 2 different non trivial loss functions (if one of them can be the 0-1 loss it will be great), which give as according to definition 3.4 that H is Agnostic PAC Learnable with one but not with the other.

  definition 2.1 (The Realizability Assumption) There exists $h* \in H$ s.t.
  $L_{(D,f)}(h*) = 0.$. Note that this assumption implies that with probability 1 over
  random samples, S, where the instances of S are sampled according to D and
  are labeled by f, we have $L_S(h*) = 0$.
  $$$$
  Definition 3.1 (PAC Learnability) A hypothesis class H is PAC learnable
  if there exist a function $m_H\colon(0,1)^2 \mapsto N$ and a learning algorithm with the
  following property: For every $\varepsilon, \delta \in (0,1)$, for every distribution $D$ over $X$, and
  for every labeling function $f \colon X \mapsto  \{0,1\}$,  if the realizability assumption holds
  with respect to $H,D,f$, then when running the learning algorithm on $m \geq m_H(\varepsilon, \delta)$ i.i.d. samples generated by $D$ and labeled by $f$, the algorithm returns
  a hypothesis $h$ such that, with probability of at least $1 - \delta$ (over the choice of the examples), $$L_{(D,f)}(h) \leq \varepsilon.$$

  Definition 3.3 (Agnostic PAC Learnability) A hypothesis class $H$ is agnostic
  PAC learnable if there exist a function $m_H\colon(0,1)^2 \mapsto N$ and a learning algorithm
  with the following property: For every $\varepsilon, \delta \in (0,1)$, for every distribution $D$
  over $X\times Y$, when running the learning algorithm on $m \geq m_H(\varepsilon, \delta)$ i.i.d. samples
  generated by $D$, the algorithm returns a hypothesis $h$ such that, with probability
  of at least $1 - \delta$ (over the choice of the $m$ training examples),
  $$L_D(h) \leq \min_{h' \in H}
L_D(h') + \varepsilon.
$$

  Definition 3.4 (Agnostic PAC Learnability for General Loss Functions) A
  hypothesis class H is agnostic PAC learnable with respect to a set Z=$X \times Y$ and a
  loss function $l : H \times Z \mapsto R_+$, if there exist a function $m_H\colon(0,1)^2 \mapsto N$
  and a learning algorithm with the following property: For every $\varepsilon, \delta \in (0,1)$
  and for every distribution D over Z, when running the learning algorithm on
  $m \geq m_H(\varepsilon, \delta)$ i.i.d. examples generated by D, the algorithm returns $h \in H$
  such that, with probability of at least $1 - \delta$ (over the choice of the m training
  examples),
  $L_D(h) \leq \min_{h' \in H}
L_D(h') + \varepsilon.$
  where $L_D(h) = E_{z \sim D}[l(h,z)]$.

Thank you!


texts: Is there a TM that halts on all inputs but that property is not provable?

texts:
Does there exist a Turing machine that halts on all inputs but that property is not provable for some reason?

I am wondering if this question has been studied. Note, "unprovable" could mean a "limited" proof system (which in the weak sense think the answer must be yes). I am of course interested in the strongest possible answer, i.e. one that is not provable to halt on all inputs in say ZFC set theory or whatever.

It occurred to me this could be true of the Ackermann function but I am hazy on the details. It doesn't seem like Wikipedia describes this aspect clearly.


texts:
Can the number of cycles in a graph (undirected/directed) be exponential in the number of edges/vertices?

I'm looking for a polynomial algorithm for finding all cycles in a graph and was wondering if it's even possible.


texts: Neural network game players and incremental updates

texts:
Neural networks in recent years have been successfully used for gameplaying. A difference between games and e.g. image processing is that the game boards get updated incrementally. Do any neural network implementations optimize for this fact?

For example, there are 361 squares on a Go board; in a typical turn, only one of those squares will change value. On the face of it, a program like AlphaGo could save time by not redoing the calculations from the other 360 squares each time it looks at a new board position.

On the other hand, if the calculations are being done on a GPU, this optimization involves moving away from the straight vector arithmetic that GPU's do so well, which would offset the efficiency gain.

On the third hand, the potential efficiency gain would become larger as you move to more complex games; how many variables are there in StarCraft?

Has anyone ever done this optimization, or studied it and given reasons for not doing it?


texts:
I came across the following problem. Given a set of $n$ positive integers $A$ and an integer $k$. Let $S$ be the set of integers that are the sum of $k$ distinct integers in $A$. Mathematically speaking
$$S = \{s ; \text{ there exists } P \in {A\choose k} \text{ such that } s = \sum_{a \in P} a\}.$$
The object of the problem is to compute $S$ and for each integer $s \in S$, we have to find how many subsets of $A$ of size $k$ there are that sum up to $s$.

The constraints: $k$ is very small (can be considered constant) and I am looking for something subquadratic in $n$.

I tried to formulate the problem as a polynomial multiplication problem and solve it using FFT. So I built the polynomial $\rho$ as follows. I started with $\rho = 0$ and For each element $a \in A$, I added $x^a$ to $\rho$. Now for each exponent $r$ in $\rho^k$, the coefficient represents the number of combinations of $k$ elements in $A$ that sum up to $r$. However, these combinations include using the same element more than one time and count reorderings of the same subset.

I have been trying the following ideas:

Rebuilding my polynomial to count better.
Build and multiply different polynomials each representing a part of the problem (with some kind of divide and conquer technique).
Edit the polynomial resulting from the multiplication with some combinatorial argument (Subtract the numbers resulting from counting twice etc.). This helps when $\rho^2$ but could not make it work for higher values of $k$.

I appreciate any thoughts or hints about the problem :)


texts: Check if a tree is formed by 3 subtrees with given number of nodes

texts:
I have run into a  contest problem (ACM like) that sounds like this:

Input: a tree of $N$ nodes; integers $X,Y,Z$ such that $X+Y+Z=N$
Question: Can the tree be partitioned into three trees of $X,Y,Z$ nodes by removing only two edges?

I am promised that $N \le 10^5$.  My code must finish within 200ms.

The brute-force method of generating all possible partitions of X, all possible partitions of Y, and all possible partitions of Z and checking if they form the tree is too slow. This got me thinking about dynamic programming. The only thing I see here to help me form a DP algorithm is counting how many children does a node have (treating the current node as a root of a tree).  However, checking between the nodes themselves for X, Y, Z would still take $O(N^3)$ time, which is too much.

So do you see any other algorithm for this task?

Example: We're given a tree of 8 nodes and X = 3, Y = 3, Z = 2 and the following edges:
2-3; 4-2; 2-1; 1-5; 1-8; 5-6; 5-7. The answer is yes because you can
delete edges 1-2 and 1-5 to form 3 partitions like this {1,8} (Z) and {2,3,4}/{5,6,7} (X/Y).

This problem is from a preparation stage of a local competition that happend a while back.


texts:
As we know that average access time is given by

t=p*(tc)+(1-p)*(tc+tm)

where t represent the average time, p is the hit ratio , tc is the time to access the data from the cache and tm is time to retrieve data from main memory.
I was wondering wouldn't it be possible to decrease this time to

t=p*(tc)+(1-p)*(tm)

if we search for the data in both the cache and the main memory in parallel?


texts: Object recognition - given an image, does it contain a particular 3D object of interest?

texts:
I have in mind a particular 3D object.  Given an image taken by a camera, I want to check whether that image contains an instance of my object.

For instance, let's say that the object is a bathroom sink.  There are many kinds of bathroom sinks, but they tend to share some common elements (e.g., shape, size, color, function).  There can also be significant variation in lighting and pose.  Given an image, I want to know whether the image contains a bathroom sink.

How do I do that?  What technique/algorithm would be appropriate?  Is there research on this topic?

Of course, it is easy to use Google Images to obtain many example images that are known to contain a bathroom sink (or whatever the object I'm looking for might be), which could be used for training some sort of machine learning algorithm.  This suggests to me that maybe some combination of computer vision plus machine learning might be a promising approach, but I'm not sure exactly what the specifics might look like.


texts:
An elevator with a capacity of N people in a building with E floors works in a pretty unusual way.

The elevator starts at the first floor and it goes to the top floor before returning to the first floor.

It stops at every floor that is a destination of a person in the elevator.

It also stops when 1) there is someone at the current floor who wants to travel in the same direction as the elevator is currently traveling and 2) there is still room in the elevator.

At least how many round trips to the top and back are necessary to carry every person to their destination?

I assume that some kind of Greedy algorithm can give a good algorithm to solve this problem, but I still have no idea how to write a pseudocode for it.


texts: Get all factors of a word in linear time or constant time

texts:
I have the following problem :

I have an algorithm which takes a word $w$ as entry. The problem is that my algorithm is doing a lot of things on the factors of $w$ and I am representing $w$ as an array of char. So if I want to get the factor $w_i...w_j$ of $w$ I need to do a loop that begin at $i$ all the way to up $j$., so it basically takes$O(j-i)$ times. Yet I am doing this operation on a lot of couples $(i,j)$ so at the end it becomes heavy in time complexity.

So one idea is to first calculate all factors of $w$ and put them in a double array of size $\mid w  \mid^2$, I guess it takes $O(\mid w \mid^2)$ to fill this array.

Now I am wondering if we can improve this complexity ? Like for example get all factors of $w$ in linear time ? Maybe it's possible to use at first a different data structures to stack $w$ (so not array) that will allowed me to get any factors of $w$ in constant time ?

Thank you !


texts: How does one heuristically determine if an algorithm has an exponential time complexity?

texts:
How does one easily determine if an algorithm has an exponential time complexity? The Word Break naive solution is known to have a time complexity of O(2n) but most people think its O(n!) because of the decreasing subsets as you go down the stack depth.

  Word Break Problem:
  Given an input string and a dictionary of words, find out if the input
  string can be segmented into a space-separated sequence of dictionary
  words.

The brute-force/naive solution to this is:

def wordBreak(self, s, wordDict):
    queue = [0]
    dictionary_set = set(wordDict)
    for left in queue:
        for right in range(left,len(s)):
            if s[left:right+1] in dictionary_set:
                if right == len(s)-1:
                    return True
                queue.append(right+1)
    return False

With the worst case inputs of:

s = 'aab'
wordDict = ['a','aa','aaa']

Results in a O(2n) time complexity of 23 ≈ 7:

Let me caveat this question with:

I'm not looking for a performant solution so just ignore why the implementation is the way it is. There is a known O(n2) dynamic programming solution.
I know there are similar questions asked on stackexchange, but none of them gave an easy to understand answer to this problem. I would like a clear answer with examples using preferably the Word Break example.
I can definitely figure the complexity by counting every computation in the code, or using recurrence relation substitution/tree methods but what I'm aiming for in this question is how do you know when you look at this algorithm quickly that it has a O(2n) time complexity? An approximation heuristic similar to looking at nested for loops and knowing that it has a O(n2) time complexity. Is there some mathematical theory/pattern here with decreasing subsets that easily answers this?


texts: Counterexample to this modified Dijkstra's

texts:
In class, we were given the following problem:

  We are given a directed graph G = (V, E) on which each edge (u, v) ∈ E has an associated
  value r(u, v) which is a real number in the range 0 ≤ r(u, v) ≤ 1 that represents the reliability
  of a communication channel from vertex u to vertex v. We interpret r(u, v) as the probability
  that the channel from u to v will not fail, and we assume that these probabilities are
  independent.
  Give an efficient algorithm to find the most reliable path between two given vertices.

My answer was to run Dijkstra's shortest path algorithm taking (1 / r(u,v) ) as the weight for each edge, which is wrong. The standard solution to this problem is to take the -log(r(u,v)) when running Dijkstra's algorithm. I understand why the standard solution is correct as it exploits the log's property where: log(a*b) = log(a) + log(b) to convert the problem from maximizing the product to minimizing the sum of the logs. However, what is an example of a graph where taking the inverse of the reliability would not produce the optimal result? My thinking was that any function that maps smaller fractions to bigger numbers could be used.


texts:
There are $n \leq 10^6$ kinds of cake layers, and for each kind we have a machine capable of baking it in one unit of time and nothing more. Now, a cake is a sequence of layers, more specificly a permutation of numbers $\{1,2,...,n\}$, and before doing one of layers in a cake all previous ones must have been done.

Given two cakes we want to find the shortest time sufficient for baking them both. Of course one machine can work only on one layer at a time, but different machines can work simultaneously. From this constraints we obtain that this time is between $n$ (at each moment the maximum number of two machines at work) and $2n$ (each layer done separately).

Let's take an example. We're given cakes $\{1,2,3\}$ and $\{3,2,1\}$. Baking them is possible in $4$ units of time - first we bake first layers from both cakes, next the middle layer of the first cake, then the middle layer of the second cake and the last of the first one, and lastly the one remaining layer. However, it's not possible to bake those cakes in time $3$, thus the desired answer is $3$.

What I tried was some dynamic programming, which leads to $O(n^2)$ solution. Then I tried expressing this problem as some kind of bipartie graph problem, which would be something like "how many edges can a bipartie graph of $n$ vertices on both sides have, if no two edges can cross, and also we're given some set of $n$ forbidden edges?". I could not go any further with this approach though. Also, I thought of transforming our two cakes in such a way that the first one is just $\{1,2,...,n\}$ - which is easy. Then, our problem can be thought as looking for some special subsequence in the second cake (after transformation), and then I tried to reduce it to longest increasing subsequence, but failed here as well.

What I ask for are hints for solving this problem in complexity around $O(n \log n)$.


texts:
I have these grammar rules defined as follows,

FDL -> FDEF FDL | ε
FDEF -> #feature #: FEXP
FEXP -> #op #( FLIST #)
FLIST -> FEXP #, FEXP | #feature

I know how to derive the derivative tree for a given string from this, but how do I draw a NFA for this string {#feature #: #op #( #feature #)}*.
I have seen many examples which they draw the NFA from a regular expression, if so can I consider this string as a regular expression? If not how can I draw it?


texts: Explanation of proof of why connectedness is not conjunctively local of any order $k$

texts:
I was reading Minsky's and Papert's book on perceptrons and I was reading theorem 0.6.1 and I was having a hard time understanding it. The theorem was about proving that the property "connected" was not a local property i.e. that you somehow had to see the whole picture to know if something was connected or not. In particular their prove shows that "connected" is not a conjunctively local property of any order (for definition of conjunctively local see appendix at the end of this question).

In particular goes as follows:

Suppose that $\psi_{CONNECTED}$ has order K. Then to distinguish between these two $k+1$-wide figures:

there must be some $\varphi_0$ such that $\varphi_0(X_0) = 0$, because $X_0$ is not connected. All $\varphi$'s have value 1 on $X_1$, which is connected. Now $ \varphi_0$ can depend on at most $k$ points, so there must be at least one middle square, say $S_j$, that does not contain one of these points.

This last sentence is the one that does not make sense to me. Why does there must be at least one middle square that does not contain one of these points? I don't understand this. When it says "these points" what does that mean? Why are we talking about the middle points? Why does that matter? Also, the sentence as a whole doesn't make sense to me nor its purpose.

Like the first two properties make sense:

of course there must exist a $\varphi_0$ that rejects $X_0$, since $\psi_{CONNECTED}$ can only work properly if all of its predicates say YES if and only if the shape is connected. Since $X_0$ is not connected then some predicate must reject it. That is clear.
For a similar reason its obvious that all the predicates say YES on $X_1$ since its connected. More precisely, that is the definition of connected according to $\psi_{CONNECTED}$, that all its predicates say YES. Since $X_1$ is connected then all its predicates must say YES.
Last part that does make sense before my brain gets confused is that of course $\varphi_0$ can depend on at most $k$ points. This is obvious from the definition of $\psi_{CONNECTED}$. i.e. we assume $\psi_{CONNECTED}$ is conjunctively local of order $k$ so all of the predicates $\varphi$ can only see $k$ points.

however, the existence of $S_j$ doesn't make sense to me and thus, the remaining of the proof remains a mystery to me. If anyone can clarify that and the remains of the proof that would be fantastic!

Also, for completion, the whole proof is provided in the appendix2.

Appendix::

Recall the definition of Conjunctively local:

A predicate $\psi$ is conjunctively local of order k if it can be computed by independently computing a set of functions $\varphi_1(X)$...$\varphi_n(X)$ and then combined by the results of another function $\Omega$ of n argument by a set $\Phi $ of predicates $\varphi$ such that each $\varphi$ depends no more than $k$ points on a 2D Euclidean plane $R$ and:
$$
\psi(X) = \begin{cases}
1 \text{ if } \varphi(X) = 1 \text{ for every } \varphi \text{ in } \Phi \\
0 \text{ otherwise. }
\end{cases}
$$

or directly from Minsky's and Papert's book:

Appendix 2:

Proof of theorem 0.6.1


texts: Sum of k smallest values of affine functions

texts:
Assume we have a fixed number of $n$ one-dimensional affine functions of the form $f_i(x) = a_i x + b_i$ for $i \in N = \{1,\ldots,n\}$.

Consider some fixed value $k \in \{0,\ldots,n\}$. Let $S_k : \mathbb{R} \mapsto 2^N$ (power set) denote a function mapping some value $x \in \mathbb{R}$ to the set of indices of the $k$ smallest functions at $x$, so for all $x \in \mathbb{R}$, it holds that $|S_k(x)| = k$ and $f_i(x) \leq f_j(x)$ if $i \in S_k(x)$ and $j \notin S_k(x)$.

The question is: If we hold $f_1,\dots,f_n,k$ fixed and allow $x$ to vary, how many different sets can $S_k$ map to? In other words, which cardinality can the image of $S_k$ have?

For $k=0$ or $k=n$, there is only one possible set for all $x$ (either $\emptyset$ or $N$). Similarly, for $k=1$ or $k=n-1$, there are $n$ different sets each (since this is equal to the maximum or minimum element, which can change $n$ times while x increases).

But is there a general formula for arbitrary values of $k$? It seems that the maximum is attained at $k = \frac{n}{2}$.

Note that an upper bound is given by $O(n^2)$ since this is the maximum number of intersection points of the involved functions, which, thus, bounds the number of orderings. However, I think this bound is too rough. In computational experiments I have never seen a value of $2n$ or more.


texts: What are system clock and CPU clock; and what are their functions?

texts:
While reading a book, I came across a paragraph given below:

  In order to synchronize all of a computer’s operations, a system clock—a small quartz
  crystal located on the motherboard—is used. The system clock sends out a signal on a regular basis to all other computer components.

And another paragraph:

  Many personal computers today have system clocks that run at 200 MHz, and all devices (such as CPUs) that are synchronized with these system clocks run at either the system clock speed or at a multiple of or a fraction of the system clock speed.

Can anyone kindly tell:

What is the function of the system clock? And what is meant by “synchronize” in the first paragraph?
Is there any difference between “system clock” and “CPU clock”? If yes, then what is the function of the CPU clock?


texts: Interpretability of feature weights from Gaussian process classifier

texts:
Suppose I trained a Gaussian process classifier with a linear kernel (using GPML toolbox) and got some feature weights for each input feature.

My question is then:

Does it/When does it make sense to interpret the weights to indicate the real-life importance of each feature or interpret at group level the average over the weights of a group of features?


texts: For some $n$, how can we check whether there exists $a,b \in \mathbb{N}$ such that $a^b = n$ in polynomial time?

texts: For some given $n$, how can we check whether there exists $a,b \in \mathbb{N}$ ($b > 0$) such that $a^b = n$ in polynomial time with respect to the number of digits in $n$?


texts: $NC$ and $FNC$ oracles low for functional and Stockemeyer classes respectively?

texts: We know $P^{NC}=P$ and $FP^{FNC}=FP$ hold. Do $FP^{NC}=FP$ and $P^{FNC}=P$ hold?


texts: Relationship between flow and resource consumption in VNFs (Middleboxes)

texts:
A middlebox consumes some resources (CPU ticks, RAM, etc.) to process a traffic, e.g., a IDS consume 50% CPU and 20% RAM to process a 100M bps flow.

Here is the problem. 100M bps flow may consume more resource if the flow is processed by a lot computationally expensive rules.

Therefore, my question is that are there any publications (paper, book, etc.) that study about the problem I just mentioned.

Any suggestions will be appreciated.


texts: Multi modal learning from separate modal datasets

texts:
Let's say I'm trying to learn emotion given multi-modal sources. In this case, video and audio. However, I only have one dataset for video emotions and one dataset for audio. Is it possible to train a Deep Learning classifier on each dataset separately? One way I can imagine doing this is creating some sort of shared hidden units, similar to the figure below:

However, in the publication this is taken from, these weights are trained simultaneously.

Are there examples of this type of multi-modal learning in the literature? I'm not sure what to look up and all I can come up with myself is "something-something Deep Belief Network".


texts: How to estimate the complexity of sequential algorithm given that we know the complexity of each step?

texts:
First case:
I was stumble upon a two step sequential algorithm where the big O complexity of each step is $O(N^9)$.
Second case:
Also if the algorithm have three steps where the complexity of step 1 is $O(N^2)$, the complexity of step 2 is $O(N^3)$ and the complexity of step 3 is $O(N^9)$
What would be the complexity of the first case and second case ?


texts: Help me understand this Turing-machine Problem concerning $A_{TM}$

texts:
I'm a Physics/C.S. student and have been struggling with this particular problem for a few days now.
So the task is as following:

Consider the following languages:
$\hspace{20pt} L_1 = \{\langle M \rangle \, | \, L(M) = A_{TM}\} \\
\hspace{20pt} L_2 = \{\langle M \rangle \, | \, L(M) = \overline{A_{TM}}\}$
Are these decidable? Prove your decision.
$A_{TM}$ is defined as $\{\langle M , w\rangle \, | \,\text{M is a TM and M accepts w}\}$

So first off I'm trying to understand the first language $L_1$.
What exactly would it mean for $L_1$ to be decidable? I understand why $A_{TM}$ isn't decidable, but what would a TM that decides $L_1$ actually do?
I feel like I already know the solution to the second problem but would like to know whether my gut instinct is right. So since $\overline{A_{TM}}$ isn't Turing-recognizable it means that $M$ with $L(M) = \overline{A_{TM}}$ doesn't exist/is empty. Thus $L_2 = \emptyset$ and that's easily decidable.


texts: Are there any RE-complete languages w.r.t. polynomial reduction?

texts:
I need to decide if there exists $L\in RE$ so that for every $L'\in RE$ we have $L' \leqslant_p L $, meaning a polynomial-time reduction.

I've tried to use $L=A_{TM}$ (the accepting problem), but got stuck when for the other language $L'$, I needed the turing machine that accepts it. But how could I summon this machine in polynomal time?


texts: Proof that the regular languages are closed under string homomorphism

texts: Where can I find a proof of this? Thanks!


texts: Hash function, $h(k) = \lfloor km \rfloor$ is simple uniform for real $k$ independently, uniformly distributed in the range $0 \leq k < 1$

texts:
I was going through the text Introduction to Algorithms by Cormen et. al. where I came across the following statement:

If the keys are known to be random real numbers $k$ independently and uniformly distributed in the range $0 \leq k < 1$ , the hash function
$$h(k) = \lfloor km \rfloor$$
satisfies the condition of simple uniform hashing.

Now what I can understand that they are probably considering uniform disturbution in the "continuous" sense and not in the discrete sense. Had it been in the discrete sense then suppose for $n$ keys the probabity mass function (p.m.f) shall be constant and equal to $1/n$ and so it shall be equally likely for each key to be used in the hashing there-by yeilding the desired result.
But we seem sort of in trouble if the distribution being referred to is continuous (I feel so because of the line: "uniformly distributed in the range $0 \leq k < 1$")
Let $f(x)$ be the associated probability density function (p.d.f) and from the given information we have $f(x)=1$,(which is quite easily found, integrating $f(x)$ in the range $0$ to $1$ and equating it with $1$ and noting that in uniform distribution the p.d.f is a constant).
Now though the p.d.f is a constant but p.d.f is not the probability. Rather probability at a spectrum point is $0$. Now how to use this result to get to the claim of the authors.
Or am I entirely at fault considering the distribution to be continuous?
(There is an answer here, but it does not go into this detail as the question there is different after all).


texts:
How do I calculate RTT, do I start to measure the time from the beginning of the segment transmition or from the moment all the segment had been transmitted?

The end time is the moment the sender gets the "ACK".


texts: Language of lists of words, not all of which are different, is not context-free

texts:
How do I prove that the following language isn't context-free using the pumping lemma?
$$
L=\{w_1\#w_2\#\dots\#w_k \colon k ≥ 2, w_i \in \{0,1\}^*, w_i = w_j \text{ for some } i \ne j\}
$$
I am having trouble choosing the string to use for the proof. I know that I have to choose a string such that at least two substrings separated by the # are equal to each other but am unsure of how to approach this. If someone could please help me with this, I would appreciate it.


texts: Set of points partitioned into max subsets of size N with no intersecting edges

texts:
Question

Given a set of X kd (k-dimensional) points, find the maximum number of closed subsets of these points such that no subsets (each forming a convex hull) overlap or intersect, that each subset is exactly of size N, and that the distance from each vertex to the center of its subset (average center of all points in subset) is maximally D. Furthermore, each vertex may only belong to at most one subset. The solution should be precise, but can be a good approximation if precise is way too expensive. The set of subsets should be calculated, not how many subsets belong to the set.

By overlap, this means that there are no edge, face, etc intersections and that one subset can't have another subset inside of it. If you were to have closed subsets on a 2D cartesian coordinate system, then the closed subsets would form shapes and none of these shapes would be allowed to overlap.

Let it be known that I'm not very proficient with graph theory.

My current methodology is to convert the points into a near triangulation graph. From there, I have no idea where to go. Of course, my entire starting point may be wrong as well.

Idea 1

Calculate center point of graph. From the farthest vertices, select N - 1 closest vertices such that their inclusion keeps the set valid and remove them from the graph.

Idea 2

Starting from vertices with the fewest reachable vertices (distance <= 2R), create valid subsets using reachable vertices with maximum reachable vertices, or are closest, or have minimum (I've tried all three, and all three failed).

Idea 3

Start with triangles that share minimal vertices and expand them, always working off of triangles that have as few vertices as possible (bad things can happen towards the center of the graph, giving an incorrect solution).

There are also problems with near triangulation. What happens if N is 2? It would turn into pairs. I guess the algorithm could have a special case for N = 0, N = 1, and N = 2, and then actually go into a general algorithm for N >= 3.

Another way to think about the problem is that, from a set of points, it is trying to build a maximal list of polygons with N faces. I've been working it from a 2D standpoint, but I also understand that what the problem changes a bit when going to 3D and beyond. For example, a 2D shape in 3D has undefined faces, so how then would the general algorithm make sure that the plane doesn't intersect any other planes or volumes?

Ideally, I'd want this to work for any dimension >= 2. I also may want to draw the 2D/3D stuff down the road. The 4D stuff may be interesting to simulate.

I'm really looking for an optimal solution here. I am starting to think that this problem may be NP-Hard.

This problem is for an ability in a game that I've wanted to do for years.


texts:
I have this very simple "proof" for NP = CoNP and I think I did something wrongly somewhere, but I cannot find what is wrong. Can someone help me out?

Let A be some problem in NP, and let M be the decider for A. Let B be the complement, i.e. B is in CoNP. Since M is a decider, you can use it to decide B as well (just flip the answer). Doesn't that mean that we solve both NP and CoNP problems with the same M?

To put it more concretely.

Let A be some NP-complete problem, and let M be decider for A. Consider any problem B in CoNP. We consider its complement not-B, which is in NP, and then get a polynomial reduction to A. Then we run our decider M and flip our answer. We thus obtain a decider for B. This implies B is in NP as well.

May I know what is wrong with my reasoning?


texts:
It might just be a stupid question but I simply see no obvious reason why dependent sum type is a generalized form of product type. Concretely, the sigma type $\Sigma(x:S)T$ degenerates to a product type if $T$ does not depend on $x$ and is expressed to be $S\times T$ in this case.

Where the SUM part in dependent sum type is coming from? Also, the type of dependent functions is called dependent PRODUCT type. Might I ask why it's called product type as well? I kind of sense that it has something to do with algebraic data type but I can't get through it.


texts: What Happened to "Top" in Denotational Semantics?

texts:
Has "top" ($\top$) been removed from or relegated to a much more minor role in denotational semantics? If so, when and why?

I see older papers and books talking about both "top" and "bottom" ("bot", $\bot$), but it seems like newer work only refers to bot. I vaguely recall seeing a reference somewhere that said that top wasn't used anymore or wasn't necessary, but I don't know where that was and I don't know anything about the transition away.

I'm reading a paper from 1979 about applying denotational semantics to databases and null values ("Null Values in Data Base Management: a Denotational Semantics Approach" by Yannis Vassiliou) that makes heavy use of both bot and top, and I'd like to understand what a more modern take on that might be. Any relevant references on that angle would also be greatly appreciated.


texts:
I'm a newbie in machine learning field. And I need to choose the best model for my classification model, so i use "learning curve" from sk-learn to make selection. I train and plot learning curve on models such:

Logistic Regression
KNN
Gaussian Naive Bayes
Decision Tree
Random forest
Stochastic Gradient Descent
Perceptron
SVM
Linear SVC

Here is detail graphs:

So I don't know how to conclude from above pictures:

How bias vs variance on each model (underestimate/over estimate) ?
Which models need more data to train or need to increase the complex ( increase degree,...)
Which models is good to apply?
Which modes is the best to select?

Please help me clarify these answers relate to these learning curves.

Thanks a lot


texts: What are the sufficient conditions for a grammar to be unambiguous?

texts:
There is no algorithm that, given an arbitrary grammar, decides if it's ambiguous or not. However, Are there any sufficient conditions that make it easier to tell that a grammar is unambiguous?

For example, if I'm not mistaken, it can be algorithmically checked if a grammar contains no conflicts under LR(1), LALR(1) or LL(1); if so, is there any  implication like "If the grammar has no conflicts under LL(1) then it is unambiguous" or something like that?


texts: What exactly is the semantic difference between set and type?

texts:
EDIT: I've now asked a similar question about the difference between categories and sets.

Every time I read about type theory (which admittedly is rather informal), I can't really understand how it differs from set theory, concretely.

I understand that there is a conceptual difference between saying "x belongs to a set X" and "x is of type X", because intuitively, a set is just a collection of objects, while a type has certain "properties". Nevertheless, sets are often defined according to properties as well, and if they are, then I am having trouble understanding how this distinction matters in any way.

So in the most concrete way possible, what exactly does it imply about $x$ to say that it is of type $T$, compared to saying that it is an element in the set $S$?

(You may pick any type and set that makes the comparison most clarifying).


texts:
I am trying to solve a problem- Longest repeated substring in a string. Firstly, I built a suffix tree that takes O(n) time and then I traversed the suffix tree to find the deepest internal node. I am not sure whether traversing in a suffix tree would be O(n) or not?

These are the properties of a suffix tree-

A suffix tree will contain n leaves which are numbered from 1 to n.
Each internal node (except root) should have at least 2 children.

If each internal node can have more than 2 children,How can I say that number of nodes in a suffix tree is O(n)? So, How will the complexity be O(n)?

Here is the code that I have written for traversal. I am aware that this platform is language independent so I have added the relevant comments along with my code.

struct StNode
{
    string str;
    StNode* child[256];
};
void lrs(StNode* t,string s,string &res)
{
    if(leafNode(t)){    //leafNode means no child
        string str=t->str;
        s.erase(s.length()-str.length());   //erasing the leafNode's string
        int k=s.length();
        if(k>res.length())   res=s;
        return;
    }
    for(int i=0;i<256;i++){     //traversing through all childs
        if(t->child[i]!=NULL){
            string str=t->child[i]->str;
            lrs(t->child[i],s+str,res);
        }
    }
}


texts:
A graph with $C_3$ + 3 "ears" is called a net graph.

In general, $C_n$ + $n$ pendant vertices are called sunlet graphs.

Is there a name for 4-sunlet graph minus two pendant vertices?


texts: Finding a $g(n)$ so that $f(n) = O(g(n))$

texts:
I am having trouble on the following algorithms question:
Given $f(n) = \sum^n_{y{=}1} (n^5\cdot y^{22})$, I am trying to find a $g(n)$ such that $f(n) = O(g(n))$.
I know that this means I need to find constants $c,n_{0}$ so that $f(n) \leq g(n)$ for all $n > n_{0}$.
I began by considering the expansion of $f(n) = n^{5}\cdot1^{22} + n^{5}\cdot2^{22} + ... + n^{5}\cdot(n-1)^{22} + n^{5}\cdot n^{22}$.
This gave me two ideas for a solution:
First, I thought to set $g(n) = c \cdot n^{27}$ (given that this is the largest exponential term of $f(n)$), but where I am stuck is picking the right $c$.  I had the idea of picking $(n-1)n^{5}$ (there are $n-1$ other terms and the largest exponential of each term is $n^{5}$), but I'm stuck for two reasons:

Can $c$ be dependent on $n$?  By definition it seems like the answer is no since $c$ is a constant.

The choice of $c = (n-1)n^{5}$ is dubious.  Consider the term $(n-1)^{22}n^{5}$, the largest portion is $(n-1)^{23}$, not $n^{5}$.

My second idea is to let $g(n) = c \cdot n^{5} + n^{27}$, and let $c = \sum^{n-1}_{y{=}1} (y^{22})$, but again this seems incorrect because $c$ depends on $n$.
I would love some feedback on these attempts, thanks!


texts:
I would like to encode a binary tree where every node has either 0 or 2 kids into a binary word.

I was thinking about marking every left edge with a "0" and every right edge with a "1"
and then use every path from root to a leaf concatenated to encode the tree, but I'm not sure if this results in a unique code for every tree?

I thought about it for quite some time but I can not figure out... maybe you know?


texts: Is linked list a preferable underlying basic DS for a collection mutable through an iterator

texts:
I need to implement a collection DS that exposes an iterator which can be used to iterate an underlying collection and possibly remove the current item. I can use either a vector (dynamic array) or a linked list as an underlying DS. I'm inclined toward toward linked list because of the easiness of operations. Is it a good decision? What other things I need to consider?

Thanks


texts: Divide directed weighted graph into two parts

texts:
I have a directed, weighted graph $G = (E,V)$. For example, one might be $|E| = 74000, |G| = 725$.

I want to divide this graph into two parts/clusters/communities, taking the edge weights into account.

I researched several methods, but the problem is that either they automatically detect the number of parts (communities), e.g. the Louvain method, or they only work for undirected graphs, e.g. k-MST.
I also considered computing a minimum cut, but my network does not have source and sink.

Which other methods are there?


texts: How to find the optimum solution of Weighted set cover in O(2^n)

texts:
A weighted set cover problem is:

  Given a universe $U=\{1,2,...,n\}$ and a collection of subsets of $U$, $\mathcal S=\{S_1,S_2,...,S_m\}$, and a cost function $c:\mathcal S\to Q^+$ , find a minimum cost subcollection of $\mathcal S$ that covers all elements of $U$.

How to design a deterministic algorithm to solve weighted set cover in $O(2^n)$ (just find the optimum solution)?

If I simply use exhaust searching to look through all possible cover (which is actually equals to $2^m$) and find the one with minimum weight, it will cost $O(2^m)$ but not $O(2^n)$.


texts: Proof of $f(n) + ο(f(n)) = \Theta(f(n))$

texts: Can you please help me prove this? I am trying to set $o(f(n))= g(n)$ and then try to solve the equation $f(n) + g(n) = \Theta(f(n))$ but I don't know if it is the correct way, and if it is I don't know how to continue my solution. Thank you


texts: Self study materials for computational complexity theory

texts: I will be taking a computational complexity theory course in about a year, and as the reference material will be Computational Complexity A Modern Approach I am more than confident that without a proper preparation that course will eat me alive. The book seems to have excellent practise problems in the sense that it will build up my CS toolbox. But I am going to need extra material to help me to get to a level where I can confidently self study the book in quetion. Therefore I was wondering that does there exist a solution manual for the book or are conference papers my only option to check how the quality of my proofs/work as a hint when I am stuck?


texts:
Given a bipartite graph $G(X+Y,E)$, how can I find a non-empty subset $Y'\subseteq Y$, such that $|N(Y')| \leq |Y'|$ (where $N$ is the set of neighbors)?

If $|Y|\geq |X|$ then the problem is easy - $Y'=Y$ satisfies the requirements. The interesting case is $|Y| < |X|$. In this case a solution might not exist, for example here:

$$
x_1 - y_1
\\
x_2 - y_1
$$

the only subset of $Y$ that satisfies the requirement is $\emptyset$. Is there an efficient algorithm for deciding whether a solution exists, and if so, find one?

A possible first step is to find a maximum matching in the graph. If its size is less than $|Y|$, then by Hall's theorem there exists a $Y'\subseteq Y$ with $|N(Y')|< |Y'|$, and it can be found efficiently, so we are done.

But if the size of the matching is $|Y|$, then... I am stuck.

RELATED PROBLEMS:

Finding a subset in bipartite graph violating Hall's condition: there, the problem is to find a subset with $|N(Y')|< |Y'|$; here, the problem is to find a non-empty subset with $|N(Y')|\leq |Y'|$.
In bipartite expansion, the goal is to find a subset $Y'$  containing a fraction $\beta$ of the vertices of $Y$ which minimizes the size of $N(Y')$. The problem is hard to approximate. However, our problem is possibly easier, since we  only require $Y'$ to be non-empty, and only require $|N(Y')|$ to be at most $|Y'|$ - we do not try to minimize it.
In union minimization, we are given a set-system and an integer $k$, and the goal is to find $k$ sets such that their union is minimized. We can view the set-system as a bipartite graph with sets on one side and elements on the other side; then, the goal is to find a $Y'$ of size $k$, such that $|N(Y')|$ is minimized. This is hard to approximate, but again our problem is potentially easier since it does not insist on $k$ and does not require minimization.

So, can the problem be solved in polynomial time?


texts: Removing conflicts of LR(1) parsing tables

texts:
S' -> S $

S -> I ; S
S -> return E ; S
S -> return I ; S
S -> ''

I -> id
I -> id = E
I -> id = I

E -> C && C
E -> C || C
E -> ! C
E -> C

C -> A > A
C -> A < A
C -> A >= A
C -> A <= A
C -> A == A
C -> A

A -> T A'
A'-> + T A'
A'-> - T A'
A'->''

T -> F T'
T'-> * F T'
T'-> / F T'
T'->''

F -> id
F -> const
F -> ( A )

This is supposed to be a LR(1) grammar, but its LR(1) parsing table have a conflict on the ; symbol column: it has both a shift and a reduction transition. How this conflict can be removed?


texts: Model disjunction in a $\{0,1\}$ integer linear program

texts:
How can I model logical OR as an integer linear program?

$$(y_3 + y_4 + y_5 + y_6 = 2) \lor (y_2  = 1)$$

where $y_i \in \{0, 1\}$, $1$ = True and $0$ = False.


texts: Shortest Minimax Path via Floyd-Warshall

texts:
I am trying to modify the Floyd-Warshall algorithm to find all-pairs minimax paths in a graph. (That is, the shortest length paths such that the maximum edge weight along a path is minimized.)

Floyd-Warshall algorithm contains the following loop to enhance the distance (ds) and the next vertex (ns) matrices at each iteration.

for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (ds[i][k] != inf && ds[k][j] != inf) {
                final int d = ds[i][k] + ds[k][j];
                if (d < ds[i][j]) {
                    ds[i][j] = d;
                    ns[i][j] = k;
                }
            }

I replaced ds with two new matrices: ws (weights) and ls (lengths). Further, updated the iteration step as follows:

for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (ws[i][k] != inf && ws[k][j] != inf) {
                final int w = Math.max(ws[i][k], ws[k][j]);
                final int l = ls[i][k] + ls[k][j];
                if (w < ws[i][j] || (w == ws[i][j] && l < ls[i][j])) {
                    ws[i][j] = w;
                    ls[i][j] = l;
                    ns[i][j] = k;
                }
            }

However, the modified algorithm finds paths with loops, that is, paths such as 1-3-2-3-4. While the maximum edge weight of the paths 1-3-2-3-4 and 1-3-4 are identical, the latter has a shorter path length and supposed to be returned by the enhanced Floyd-Warshall. Any ideas?

A working Java version of both algorithms and a test case which produces a path with loop can be found here.

Edit: Since no solutions were presented yet, I implemented my own shortest minimax path algorithm using incremental link removal method. Java sources to the solutions can be accessed from the above link.


texts: Is there an algorithm that given a PDA $M$ decides if there exists a string in $L(M)$ with a suitable decomposition?

texts: I am looking for an algorithm that given a PDA $M$ decides whether there exists $w \in L(M)$ for which there exists a decomposition $w = uvxyz$ that satisfies $|vy| \geq 1$ and $uv^ixy^iz \in L(M)$ for every $i \geq 0$.


texts: Estimating the number of distinct elements

texts:
Need to understand "intuition" part. It does not make sense to me why $log(d)$ is a good approximation.

We have a stream $\sigma = \{a_1, ..., a_n\}$, with each $n \in [n]$, and this implicitly defines a frequency vector $F = {f_1, ..., f_n}$. Let $d = |\{j : f_j > 0$}| be the number of distinct elements that appear in $\sigma$.
For an integer $p > 0$, let $zeros(p)$ denote the number of zeros that the binary representation of $p$ ends with. Formally,
$zeros(p) = max\{i : 2^{i}$ divides $p\}$
Algorithm:
Initialize:

Choose a random hash function $h$: $[n] \mapsto [n]$ from a 2-universal family;

z $\leftarrow $ 0;

Process $j$:
3. if $zeros(h(j)) > z$ then $z \leftarrow zeros(h(j))$
Output: $2^{z+\frac{1}{2}}$
The basic intuition here is that we expect $1$ out of $d$ distinct tokens to hit $zeros(h(j)) \geq log(d)$, and we don't expect any tokens to hit $zeros(h(j)) >> log(d)$. Thus the max value of $zeros(h(j))$ over the stream - which is what we maintain in $z$ - should give us a good approximation to $log(d)$.


texts: Program Transformation to Disintermediate Isomorphic Representation Transforms

texts:
Given two representations of the same abstract data type, any optimal program that incorporates one representation has a corresponding optimal program that incorporates the other.

What is the field of computer science that studies program transformation between two such optimal programs?

If necessary, posit the practically restrictive, but analytically convenient, case that the representations are isomorphic rather than homomorphic.


texts: Constructing languages in NPI other than through Ladner's Theorem

texts: I have seen proofs of Ladner's theorem which detail the construction of languages in NPI assuming P $\neq$ NP.  However, I was wondering if there are any other constructions using the fact that sparse sets cannot be NP-complete assuming P $\neq$ NP (Mahaney's Theorem).  Specifically, is it definite (assuming P $\neq$ NP) that the intersection of an infinite decidable sparse set and an NP-complete language lies in NPI? It seems to me that it cannot be in P, but I don't know how to prove it. (Note: I am asking about taking a given NP-complete language and its intersection with a sparse set, not about $\textsf{NPC} \cap \textsf{SPARSE}$ which must be empty, again by Mahaney's Theorem.)


texts:
$(0+1)^*.1.(0+1) + (0+1)^*.1.(0+1)$ and  $(((0^*.1^*)+1)^*(0+1)^*)^*$

I have studied Arden's theorem $R=Q+RP$ has a unique solution $R=QP^*$
and some identities like $E+RR=R$ and $E.R=R$.

I have tried something on equation (factorizing) but I'm not sure that I had the correct solution.


texts: Proving a factor 2 performance guarantee for a greedy minimum cardinality vertex cover algorithm (Exercise)

texts:
Exercise 1.3 from Vijay Vazirani - 'Approximation Algorithms' asks:

Consider the following factor $2$ approximation algorithm
for the cardinality vertex cover problem. Find a depth first search tree
in the given graph, $G$, and output the set, say S, of all the nonleaf vertices
of this tree. Show that S is indeed a vertex cover for $G$ and $|S| ≤ 2$ · $OPT$.
Hint: Show that $G$ has a matching of size $|S|/2$.

$EDIT$: the hint originally reads as follows: 'Show that G has a matching of size |S|'. A counterexample to this is when G is a path of length $4$ - then the DFS tree $T = D$, and a maximum matching is of size $2$. I took this to be a misprint and assumed that $|S|/2$ is the number the hint meant to refer to. Now after reading fade2black's comment, he also has a counter example in which $S$ is not a cover of $G$. After thinking about this for a while, I now cannot see for what reason $|S|$ should always be a cover of $G$. What I thought was proof of this statement (my attempt at the first part of the question below), is actually proof that $S$ is always a cover of $T$. Any ideas? Am I missing something? Is this a misprint, or is this just a poorly formulated question?

My attempt:

Showing $S$ is a vertex cover of $G$: Assume not. Then there is at least one vertex $v \in G-S$, $s.t.$ $v$ is a leaf and not adjacent to any vertex in $S$. Then either $v$ is disconnected in $G$, or $v$ is adjacent to some other leaf in $G$. If $v$ is adjacent to some other leaf in $G$, this implies that $G = K_2$, in which case $S = \emptyset$ and selecting either of the two vertices on its own gives a vertex cover. Therefore, if $G \neq K_2$ and $G$ is connected, $v$ must be connected to some $w \in S$.

Showing that $|S| \leq 2 \cdot OPT$: Consider a $2$-colouring of the vertices in $S$. At least one of the colours will have been used to colour at least half of the vertices in $S$. Pick that  colour, and for each vertex coloured by it, match exactly one of its incident edges. It follows that $G$ admits a matching of size $|S|/2$.
Let $M$ be a maximal matching in $G$. Then $|S|/2 \leq |M|$. We know that the minimum cardinality vertex cover of $G$ can be bounded from below by $|M|$, i.e. $|M| \leq OPT$. Together this gives $|S|/2 \leq |M| \leq OPT$, which implies that $|S|/2 \leq OPT \implies |S| \leq 2 \cdot OPT$.

Im pretty happy with the logic behind my solution to the second part of the exercise (showing that $|S| \leq 2 \cdot OPT$), but I'm not sure if the first part is quite there - I think the logic needs a bit of work. Any suggestions?


texts: Complexity of computing symmetries of a polynomial

texts: Given a polynomial $f\in\mathbb{F}[x_1,\ldots,x_n]$ what is the computational complexity of computing a generating set of the automorphism group of $f$? On first look this seems like a hard problem (at the least NP-hard). Is the complexity of the above problem studied earlier?


texts: Number of edges required to guarantee $K_3$ as subgraph

texts:
I am trying to solve a given problem: Find an algorithm to determine if a graph has a clique of size 3 in $O(n^{2.81})$ steps. The hint given is that $2.81 > \log 7$. In order to solve this I came up with a conjecture: if $m > n^{\log 7}$ then the graph has $K_3$ as a subgraph. This will easily solve the problem if the conjecture is true.

I am trying to argue by contradiction: Let $m > n^{\log 7}$ and assume there does not exist a $K_3$ subgraph. Then for any set of three vertices there are exactly 7 choices for how to connect them. However, I am stuck as to how to progress from here.

Does anyone see a way to prove this, or if the conjecture is even true. I'm also interested to see if the conjecture can be extended, i.e. if $m > n^{\log 2^k -1})$ does there exist a $K_k$ subgraph?


texts: Does this imply checking a candidate Hamiltonian Path solution can be done in logspace?

texts:
Assume vertices are integers base 2.

Smallest vertex is 1.

There are n vertices.

Our input is: the number of vertices (n expressed in log(n) bits - 0s and 1s)
followed by 2 (as a separator)
followed by an edge list of n*(n-1) bits (whether or not i->j is a directed edge)
followed by a list n vertices (each vertex expressed in log(n) bits)

In terms of n, there are log(n) (n representation) + 1 (separator) + n*(n-1) + n*log(n) = m bits. Our input length is m, which is a polynomial of n.

If there is no separator, reject. We need one bit to keep track of whether or not we’ve found the separator. Accept if separator reached. Reject if end of input reached without first reaching the separator. (This probably assumes an end-of-input symbol.)

If there’s more than 1 separator, reject. We need one bit to keep track of whether or not we’ve found the separator. Accept if end-of-input reached and separator found. Reject if separator reached after already finding one.

Computing log(n) can be done in log space. Increment a counter by 1 until the separator is reached.

Subtracting 1 can be done in logspace.

Adding can be done in logspace. Can take 3 counters: Initialize a counter to 0. Subtract 1 from the first number (second counter) and add 1 to the first counter until the first number is 0. Do the same to the second number (third counter).

Multiplying can be done in logspace (Can be done with 5 log(n) counters). We need to add a number to itself n times. Four log counters are needed to do the adding (the product will be a single 2*log(n) counter). A fifth log counter is needed to count the number of additions.

Once finding the separator, confirm end of input is reached in exactly n*(n-1) + log(n)*n bits. If not, reject. We need to multiply, add, subtract 1, and know log(n), all of which is log space.

Given two integers, p and q, we can determine whether or directed edge p->q edge exists by checking the corresponding bit. We need to first compute what bit to check. Move to the separator (takes constant bits of space). Compute r = (p-1)*n + q. Go to that bit (move, decrement r by 1; stop when r is 0). It takes logspace to do this.

To process the first two vertices, first move to the separator. Then compute n*(n-1). Decrement that by 1 and move. This way we skip the edge list. Now you will be on the first vertex pair. The next 2*log(n) bits are the first two vertices, p and q. See if directed edge p->q exists.

Do this for the next two vertices (move to n*(n-1)+log(n)*offset after the separator).

We’ll need a log(n) counter to keep track of the offset (how many vertices on the path we’ve checked).

If p->q for some offset does not exist, reject.

if offset = n-1, accept.

Check that vertices are unique. Check that all vertices after the current vertex are not equal to the current vertex. Do this for each vertex. Can be done with two offset counters. (Thanks, Yuval Filmus for pointing this out!)

Because of the input length m, if all edges in the n-1 length path are valid, then it's a path of length n - a Hamiltonian path.

Is this algorithm correct? Does it verify a candidate Hamiltonian path?

Is this algorithm logspace?


texts: Simulating Turing Machine with writing only on non-input fields on read-only Turing machine

texts:
Can you show me how to simulate Turing Machine with writing only on non-input fields on read-only Turing machine ?

I tried to do it be using internal states, but it provides me to infinitely many states, what is not allowed.
Any ideas ?

Edit
I consider standard Turing machines - one leftly-infinite tape.
read-only Turing machine is for me Turing machine such that it can't write on tape.
non-input fields - I mean part of tape where input is given. For example,
abcd#####...., machine can't overwrite abcd but it can overwrite each #.  However, readonly can  only read this tape, so no changes.

Edit II
I am searching for solution in which we use functions and Myhill-Nerode theorem. Can anyone provide this kind of solution ?


texts: Does the process exiting from critical section will always call signal instruction?

texts:
I have seen many solutions to critical section problems in process synchronization chapter . Many of them first acquire resources , execute critical section and leave . My Question is a process exiting from the critical section should always call $V(S)$ (or release/signal/ up ) instruction ? Can any process exit from critical solution by calling wait instruction ? If so give an example and explain how it works .

For example , all the problems regarding semaphore are executed in the following manner . Where $P(s) $ and $V(s)$ has usual meaning .( up and down operator )

s=1
P(s)
< Critical Section >
V(S)

I have never seen an solution like this

s=0
V(s)
< Critical Section >
P(S)

Does any critical section problems could be solved like this ? if so please explain me how it would works .


texts: Origin of tFAW (Four Activation Window) in DRAM timing constraint

texts:
In DRAM timing constraints, tFAW means length of a rolling window that allows up to four row activations in same Rank. This constraint is mainly due to power budget of each rank.

However, I am curious why 4 is the magic number？Would it be wrong if we use Eight Activation Window and double the value or use Two Activation Window and halve the value?


texts: Is a 2 address machine more likely to follow a RISC or CISC design?

texts:
The Problem: If I have a 3 address machine, is my machine more likely to follow RISC or CISC design?  2 addresses?  1 address?  0 address.

To solve this problem I first looked up the different terms.

RISC is a microprocessor architecture that has smaller/simpler set of instructions
CISC is a microprocessor architecture that has larger/more complex set of instructions
3, 2, 1 address machines just mean how many addresses are in an instruction

When first investigating the relationship between RISC vs CISC and n-address machines, with the help of the slide below, I was able to quickly associate 3 address with CISC and 0 address with RISC.

I saw that 3 address instructions were much more complicated than 0 address and therefore would make sense for CISC design. Similar reasoning for 0 address machine and RISC design. How would you make the distinguish for CISC and RISC with the address sizes in the middle - 1 and 2?


texts: Listing all maximal cliques with mean edge weight at least k in a weighted complete graph

texts:
Given a weighted undirected complete graph G = (V,E). I am interested in finding all maximal cliques that have mean edge weight (mean of weights of all edges in the clique) at least k.

Most of the approaches that I have found so far solve clique problem in an unweighted graph. I am wondering if there are any algorithms known to solve this problem.


texts: What is the correct algorithm to see whether N points lie on the same side of a line?

texts: What I tried first was to find the equation of the line and then compare its y-intercepts with the y-intercepts of each point. I just need the proper approach to this algorithm.


texts: Find string that minimizes the sum of the edit distances to all other strings in set

texts:
I have a set of strings $S$ and I am using the edit-distance (Levenshtein) to measure the distance between all pairs.

Is there an algorithm for finding the string $x$ which minimizes the sum of the distances to all strings in $S$, that is

$\arg_x \min \sum_{s \in S} \text{edit-distance}(x,s)$

It seems like there should, but I can't find the right reference.


texts: How many thresholds and distance matrix are in Eigenface?

texts:
I edited my question trying to make it as short and precise.

I am developing a prototype of a facial recognition system for my Graduation Project. I use Eigenface and my main source is the document Turk and Pentland. It is available here: http://www.face-rec.org/algorithms/PCA/jcn.pdf.

My doubts focus on step 4 and 5.

I can not correctly interpret the number of thresholds: If two types of thresholds, or only one (Notice that the text speaks of two types but uses the same symbol). And again, my question is whether this (or these) threshold(s) is unique and global for all person or if each person has their own default.

I understand the steps to be calculated until an matrix O() of classes with weights or weighted. So this matrix O() is of dimension M'x P. Since M' equal to the amount of eigenfaces chosen and P the number of people.

What follows and confuses me. He speaks of two distances: the distance of a class against another, and also from a distance of one face to another. I call it D1 and D2 respectively. NOTE: In the training set there are M images in total, with F = M / P the number of images per person.

I understand that threshold(s) should be chosen empirically. But there must be a way to approximate. I was initially designing a matrix of distances D1() of dimension PxP. Where the row vector D(i) has the distances from the vector average class O(i) to each O(j), j = 1..P. Ie a "all vs all."

Until I came here, and what follows depends on whether I should actually choose a single global threshold for all. Or if I should be chosen for each individual value. Also not if they are 2 types: one for distance classes, and one for distance faces.

I have a theory as could proceed but not so supported by the concepts of Turk:

Stage Pre-Test:

Gender two matrices of distances D1 and D2: In D1 would be stored distances between classes, and in D2 distances between faces. This basis of the matrices W and A respectively.

Then, as indeed in the training set are P people, taking the F vectors columns D1 for each person and estimate a threshold T1 was in range [Min, Max]. Thus I will have a T1(i), i = 1..P

Separately have a T2 based on the range [Min, Max] out of all the matrix D2. This define is a face or not.

Step Test:

Buid a test set of image with a 1 image for each known person Itest = {Itest(1) ... Itest(P)}

For every image Itest(i) test:

Calculate the space face Atest = Itest - Imean

Calculate the weight vector Otest = UT * Atest

Calculating distances:

dist1(j) = distance(Otest, O (j)), j = 1..P

Af = project(Otest, U)

dist2 = distance(Atest, Af)

Evaluate recognition:

MinDist = Min(dist1)

For each j = 1..P

If dist2 > T2 then "not is face" else:

If MinDist <= T1(j) then "Subject identified as j" else "subject unidentified"

Then I take account of TFA and TFR and repeat the test process with different threshold values until I find the best approach gives to each person.

Already defined thresholds can put the system into operation unknown images. The algorithm is similar to the test.

I know I get out of "script" of the official documentation but at least this reasoning is the most logical place my head. I wondered if I could give guidance.

EDIT:

i No more to say that has not already been said and that may help clarify things.

Could anyone tell me if I'm okay tackled with my "theory"? I'm moving into my project, and if this is not the right way would appreciate some guidance and does not work and you wrong.


texts: prove that there is a complete language in $L \cup \{A_{TM}\}$

texts:
$A_{TM} = \{\langle M,w\rangle\mid w\in L(M)\}$

$L$ = complexity class containing decision problems that can be solved by a deterministic Turing machine using logarithmic space

Given the language $L \cup \{A_{TM}\}$,

we will say that $A$ is complete in $L \cup \{A_{TM}\}$ if:

$A \in L\cup\{A_{TM}\}$
For every $B\in L \cup \{A_{TM}\} \implies B\le_LA$

Is there a complete language in $L \cup \{A_{TM}\}$?


texts: What do the terms 'Sample' and 'Sampling' mean in the discussion of Pattern Recognition and Machine Learning?

texts:
The tag sampling tells me that,

  Creating samples from a well-specified population using a
  probabilistic method and/or producing random numbers from a specified
  distribution.

Now, the question becomes: what is population then?

Suppose, I am implementing a classifier.

I have a set of training data in the file train.txt, and a set of test data in the file test.txt.

What element can be termed as 'Sample', and what activity can be termed as 'Sampling' in this case?


texts: On a semiconductor chip, what state (on/off or read/write) corresponds to conducting or insulating behavior?

texts:
My textbook has a brief explanation of how semiconductors are used in modern computer chips because they can be made to conduct (by applying enough voltage to excite electrons across the band gap) or to insulate (by dropping the voltage to a lower level or shutting it off entirely) and this conditional, binary state can be used as an 'on/off' logic gate.

In modern computer systems, which state is "on" and which is "off"? In other words, is it the case that when we increase the voltage to cause conductance in the semiconductor that we have a "1" value and that when we drop the voltage down, we have a "0" value, or is it the other way around?

Or is it more appropriate to say "read" vs "write"?

Does the on/off or read/write state vary from one manufacturer to another? Or from one type of memory to another? I.e. does DDR SDRAM use conducting as "on" and insulating as "off" while other forms do it the other way around?

P.S. If comp sci isn't the right SE, please could you advise a better SE for this question?


texts: Finding largest disjoint subtrees spanning nodes

texts:
I have a taxonomy (tree) of product categories. To each leaf product category, I have assigned a shop department where the products of a given category can be found.
Now for each department, I would like to find the smallest number of the largest subtrees in the taxonomy.
For instance, in the example below leaf nodes have been assigned one of two departments $A$ and $B$.

The expected solution would be: $A$ has two subtrees, namely $x_2$ and $x_7$, $B$ has one subtree $x_4$.
The solution where $A$ has $x_1$ subtree is wrong because $x_1$ is the ancestor of nodes that belong to another department.
The solution where $A$ has $x_3$ and $x_7$ subtrees is wrong because we want the biggest subtrees possible.
Is it a known problem?
Is there a solution for it?


texts: Why don't we scale the cost of memory access when analyzing runtime of algorithms?

texts:
Runtime for many programming languages is typically analyzed either assuming each operation takes a constant amount of time, or assuming each operation takes a logarithmic amount of time in the size the the data being manipulated. From a practical perspective, this is reasonable since modern computers have essentially constant time memory access (albeit for a fixed amount of memory).

However, from a theoretical perspective, it seems to me that this is a bad assumption.

Since bits can't be stored denser than the Planck scale (which we are fast approaching), the number of bits we can store in a certain volume of space can grow at most linearly as volume grows. Further, since the speed of memory retrieval and storage is bounded by the speed of light, it makes a lot of sense to say that as the size of the data we store grows, the cost for storing and accessing it should grow. For instance, one could assume that storing and accessing the $n$th bit of data requires $\sqrt[3]{n}$ time. (Since space is 3-dimensional).

Presumably this has been discussed in the literature somewhere. Could anyone point me to some references? Have algorithms been analyzed using this model?


texts: A question of congruence modulo concept. (Optimization Required)

texts:
I have an arr[] of M integers. He has to find all integers K such that :

1)  K > 1
2) arr[1]%K = arr[2]%K = arr[3]%K = ... = arr[M]%K where '%' is a modulus operator

with following constraints :
- 2<= M <=100
- 1< value of each integer <109
- All integers will be distinct

I have written an algorithm and program for this problem. Here is my code: `

 int main()
 {

  std::ios::sync_with_stdio(false);

  int M;
  cin>>M;
  long long int arr[M];
  long long int max = LLONG_MIN;
  for(int i=0; i<M; i++)
  {
    cin>>arr[i];
    if(max<arr[i])
    {
        max=arr[i];
    }
 }
 vector<long long int> vec;
 for(int k=2; k<max/2; k++)
 {
    bool flag = true;
    int result = arr[0]%k;
    for(int j=1; j<M; j++)
    {
        if(result != arr[j]%k)
        {
            flag = false;
            break;
        }
    }

    if(flag == true)
    {
        vec.push_back(k);
    }
 }

 for(int i=0; i<vec.size(); i++)
 {
    cout<<vec[i]<<" ";
 }
 return 0;

}

But in worst case my code will run in O(n^2) which is having quadratic time complexity. Please suggest some of the optimization which I can do.