texts: There exists an algorithm to find grammar of complement of a function?

texts:
I'm wondering if there exists an algorithm to solve the following problem:

  Given a grammar $S$ of a context-free language $\mathcal{L}$, find a grammar
  $S'$ such as $L(S) = L(S')^c $.

I note that the complement of a context-free language is also a context-free language, so the questions is well stated.


texts: What is the name for the comparison used in C's memcmp?

texts:
The C memcmp function (and strcmp) does a comparison similar to the function below for comparing integers:

int compare(const int a, const int b) {
     if (a > b) return 1;
     if (b > a) return -1;
     return 0;
}

Microsoft information for their strcmp says:

  The strcmp function performs an ordinal comparison of string1 and string2 and returns a value that indicates their relationship.

The manual of GNU's libc describes the comparison in this way:

  Your comparison function should return a value the way strcmp does: negative if the first argument is "less" than the second, zero if they are "equal", and positive if the first argument is "greater".

But doesn't define any name for this comparison type.

What is the name for this comparison algorithm?

And why doesn't memcmp simply return say 0 if a and b the same and 1 otherwise?


texts: Is it possible to calculate the propagation delay if only the length of the link is known & not the speed at which a bit travels into the link?

texts:
Consider a $10^7$ bps link that is $400$ km long, with a queue large
  enough to hold $2000$ packets.Assume that the packets arrive at the
  queue with an average rate of $4000$ packets per second and that the
  average packet length is $2000$ bits.Find the average number of
  packets in the queue.

I am getting Average Queue length = 0.

In this question is it possible to calculate Propagation delay?
How can we calculate the propagation delay until we don't know about the speed at which a bit travels in the link?


texts: If I'm just trying to show something is NP-hard (as opposed to NP-complete) does my reduction need to be completed in polynomial time?

texts: I have a problem that I believe is NP-hard. If I reduce a NP-complete problem to it in exponential time (and not polynomial time), does that prove the problem is NP-hard?


texts: Complete proof of PAC learning of axis-aligned rectangles

texts:
I have already read PAC learning of axis-aligned rectangles and understand every other part of the example.
From Foundations of Machine Learning by Mohri, 2nd ed., p. 13 (book) or p. 30 (PDF), I am struggling to understand the following sentence of Example 2.4, which is apparently the result of a contrapositive argument:

... if $R(\text{R}_S) > \epsilon$, then $\text{R}_S$ must miss at least one of the regions $r_i$, $i \in [4]$.

i.e., $i = 1, 2, 3, 4$. Could someone please explain why this is the case?
The way I see it is this: given $\epsilon > 0$, if $R(\text{R}_S) > \epsilon$, then $\mathbb{P}_{x \sim D}(\text{R}\setminus \text{R}_S) > \epsilon$. We also know from this stage of the proof that $\mathbb{P}_{x \sim D}(\text{R}) > \epsilon$ as well. Beyond this, I'm not sure how the sentence above is reached.


texts: Logarithmic reduction from Clique to Half-Clique

texts:
so the question is in the title basically but I am now studying for a Complexity Theory Exam and encountered this problem in the exercises.
I understand how to make a poly-reduction but I am not able to wrap my head around how to do it in logarithmic space.

The question itself is as follows

Show that $Clique \leq_L Half-Clique.$
any help would be appreciated!

I am adding the definitions for comfort purposes:
$$ Clique = (G,k) : G \ is\ a\ graph\ that\ has\ a\ clique\ of\ size\ k$$
$$ Half-Clique = G : G \ is\ a\ graph\ that\ has\ a\ clique\ of\ size\ |V|/2$$


texts: Predicting the outcome of sporting events with multiplicative scoring

texts:
In the Olympic format for sport climbing, eight athletes compete in three rounds of climbing. Their final score is the multiplication of their rankings in each round. For example, an athlete who comes 1st in the first round, 5th in the second round, and 7th in the third will have a final score of $1\times5\times7=35$. The athletes  with the lowest final score wins.

Assuming that the competition is already partly underway (possibly even mid-round), is there a computer algorithm to quickly compute the probabilities $P_{ar}$ of each athlete $a$ achieving a final ranking $r$, assuming the performance of the athletes is entirely random from here on? Even with 8 athletes the brute force method seems too computationally intensive.

If this isn't computationally possible in a reasonable time, is there an algorithm to get "close enough" to those probabilities?


texts: First-time and second-time seen edges in DFS on undirected graphs

texts:
Assume an undirected graph and a DFS traversal on it. I am interested in the DFS tree which encodes the discoverer/discovered (parent/child) relationships of the traversal. Just to make sure we are on the same page, define a discovered vertex x as one that has been visited but descendants of it are still being processed, i.e., we have not yet returned back to x. Define, a processed vertex x as one that we have returned to after we have recursed into all of its descendants and we mark it as such upon return.
Let us define the following edge types on that tree

Tree edges: direct parent/child edges: the parent is the one to first discover the child.
Back edges: edge from a descendant to an ancestor at least 2 levels up on the tree: the descendant sees an already discovered vertex.

Those are the only two types of edges one can have on undirected graph DFS. Now, I have been reading The Algorithm Design Manual (page 173) which discusses the following:

Given an undirected graph DFS and an edge (x,y) as seen from x how can we tell whether we have seen this edge before from the side of y?

I can understand the cases when y is undiscovered or discovered but not yet processed.
However, the book says that if y is processed then we can say that it's the 2nd time (i.e., we have seen the edge (x,y) from y before); this is because we should have seen all edges coming out of y before marking it as processed. The part I don't understand is when such a case can occur. How can we see y again after we have marked it processed? Can you give me an example of such a graph?


texts: What case of the master theorem of this recurrence?

texts:
I have a question abou this recurrence:
$T(n) = 27T(n/3)+n³/ \log n$
By Master Theorem. will be: $T(n) = \theta(n^3)$ or $T(n) = \theta(n³ \log \log n)$ ?


texts: Can a classical supercomputer solve a large Max-Cut Problem?

texts:
The Fugaku is the most powerful computer. Its performance is 442,010 TFlop/s. That number does not mean much to a layman like me. I want to know how fast it can solve a hard problem. For example, can it solve the Max-Cut Problem of 1,000 vertices in minutes, hours,...,years?
By the way, what is the best record of solving the Max-Cut Problem by any classical computers?


texts: Is it possible to uniformly shuffle N items into a deque of size N where you can only modify the first or last elements?

texts:
I had a question about random shuffling. Given a sorted list, is it possible to design an algorithm to return a uniformly random arrangement of the items in a deque with the following operations:

read from list and add to front of deque
read from list and add to back of deque
remove from front of deque and add to back
remove from back of deque and add to front

I am trying to figure out an algorithm to do this without the aid of any other arrays or memory (i.e. outside of the original list of size N and the deque, there is no additional memory). After experimenting with it, I'm doubting it's possible to obtain a truly uniformly random arrangement of the items, but I'd love to be proven wrong. Any guidance would be appreciated.


texts: Inorder traversal of BST is always sorted.But can we say Binary tree is BST if and only if inorder is sorted?I mean if inorder is sorted,can we conclude it is always BST?


texts: When does Branch and Bound exactly stop giving solutions for the bin packing problem

texts:
I wrote a branch and bound algorithm for the bin packing problem and now I would like to know when exactly it stops giving solutions in a polynomial time.

I have N items (each item i has a volume Vi) and each bin has a volume V.

I tested the output of the algorithm and the execution time while varying the number of items N , the total volume of items Vtotal and the bin's volume V too.

What I noticed is that the termination criterion of the B&B algorithm does not depend only on N , it also depends on Vtotal and V .

For instance, if I have:

N = 18

Vtotal = 18

V = 8

The algorithm works fine and I get the output I want in a polynomial time (few milliseconds)

But , If I have :

N = 18

Vtotal = 18

V = 14

I don't get an output.

same for this test instance:

N = 18

Vtotal = 21

V = 14

(If Vtotal = 25 I get a solution in few milliseconds)

What I need to know is : Is there a way (for example, assemble the three parameters in one formula) to know when exactly I don't get a solution in a polynomial time?

Thank you


texts: How do you classify properties as Trivial and Non-trivial?

texts: I understand what Rice's theorem states and what Trivial and Non-trivial properties mean. However, when given some property, I am having a hard time seeing if it is Trivial or Non-trivial. Can someone help me understand this better, maybe with some good examples?


texts: Can differennt computation model lead to different complexity?

texts:
There are many examples where someone replaces a CPU with a GPU or an FPGA and get a performance boost of $\times 100$ or more, but is it possible for a change in the architecture of computational resource to reduce the least possible complexity of solving a problem, say, from $\Theta(n^2)$ to $\Theta(n)$?

Basically, I'm looking for an example like Bead sort.


texts: Minimum number that cannot be formed by any subset of an array

texts:
We have an array of Integers, $A[]$ and we have to find the minimum number that is not the sum of a subset of array using the elements from $L$ to $R$ indices. I was thinking of using coin change DP approach, and outputing the min number with value infinity. But the problem is that the sum of ranges can be as large as 109, and we have about 105 queries of the type $[L,R]$, so I was hoping there'd be a better approach. Can anyone point me in the right direction?

There are 105 elements in the array

Suppose the elements of the array are 1,1,2,7. Then for indices 1 and 4, the smallest number that cannot be formed as a sum is 5. since we can form all 1,2,3,4.


texts:
For range queries on a subarray [L,R] , I want to find all the indices of successive maximums from left to right within O(log(R-L+1)), excluding index "L". I know using segment trees I can find the single maximum in given time limit.
Example if [L,R] is 20 3 10 5 10 7 6 7 5 7 5
-> the bold ones are the answers
Note

that 20 is excluded but the first maximum i.e 10 has to be lesser
than 20
In case of multiple occurrences of a particular maximum, the rightmost index must be used

Also, there is a need for updation of array elements so an online query algorithm would be helpful!


texts: Why is two-phase commit better than naive master-slave replication?

texts:
In the context of a distributed database, I'm trying to understand why 2PC (as described in e.g. https://www.cs.princeton.edu/courses/archive/fall16/cos418/docs/L6-2pc.pdf) is better than the following hypothetical protocol between a client, master, and slave:

client tells master to commit
master commits it
master tells client the commit succeeded
master tells slave to replicate the commit. If the slave fails, master keeps on trying until it succeeds and gets the slave caught up on all edits.

This seems to me to satisfy the same properties as 2PC:

Safety: If the master commits, the slave will also eventually commit. If the slave commits, the master must have committed first. I suppose an advantage of 2PC is that if a participant fails before starting the commit, the transaction will be failed instead of only committing on the TC. However, in the proposed protocol, the commit on the master still eventually gets to the slave.
Liveness: This protocol does not hang.
Both rely on the master / TC durably recording the decision to commit. Both assume failed slaves / participants eventually wake up and catch up with the master / TC.
Both fail if the master / TC goes down.
In both protocols, it's possible to have temporary inconsistencies where the master / TC has finalized a decision, but the slaves / participants haven't yet committed.

It seems to me that the key theoretical difference in 2PC is that the participant (slave) can vote "no" to the commit, as opposed to merely temporarily failing. That would break the conclusion above where the slave eventually catches up. However, I don't see why the slave would need to vote "no" in the first place. Given the assumption that the slave / participant does not permanently fail, it seems it should either vote "yes" or fail to respond. (Unlike the bank account example, I expect the slave to blindly replicate the master.)

Distilling all this down, it seems to me that 2PC's assumption that participants don't permanently fail makes it unnecessary to give participants a chance to vote "no" in the "prepare" phase.

What am I missing here? Presumably there's some advantage to 2PC over the above that I'm not understanding, since 2PC is actually used to build distributed databases.

Am I incorrect in concluding that a slave shouldn't need to explicitly vote "no", as opposed to temporarily failing? (I'm only talking about the data replication use case, rather than the bank account example.)
Given the same assumptions as 2PC, and assuming slaves only say "success" or "try again", is there some guarantee 2PC offers that the naive replication above doesn't?

For the purpose of the question, I'd like to ignore practicalities, unless they're critical to the answer. In particular, I'd like to ignore things that could be interpreted as being disallowed by the no-permanent-failure assumption, such as  disk full, slave mis-configured, slave corrupt, operator error, buggy software, etc.


texts: Efficiently compute a complete set of representatives of cyclotomic cosets of $2$ modulo $2^n-1$

texts:
Let $n > 1$. For an integer $k$ with $0 \leq k \leq 2^n-2$ the cyclotomic class $C_k$ of $2$ modulo $2^n-1$ is the set given by
$$C_k = \{k, k\cdot 2, k \cdot 2^2 , \ldots, k\cdot 2^{n-1} \pmod {2^n-1}\},$$
where the entries are reduced modulo $2^n-1$. Note that either $C_k = C_i$ or their intersection is empty. A set $\{a_1, \ldots, a_m\}$ of integers in $[0, 2^n-1]$ is called a complete set of representatives of the classes if $C_{a_j} \neq C_{a_i}$ whenever $i \neq j$ and
$$
\bigcup_{i=1}^m C_{a_i} = \{0, 1, \ldots, 2^n-1\}.
$$

I am interested in, given $n$, efficiently computing the corresponding complete set of representatives of the cyclotomic classes. Any ideas? I'm hoping to be able to compute this for large enough $n$. Thanks!


texts: Proof of Space Hierarchy Theorem incompatible with Linear Speed Up Theorem for time

texts:
In this proof of the Space Hierarchy Theorem the following language is defined
$$
 L =  \{ (\langle M \rangle, 10^k) : M \mbox{ does not accept } (\langle M \rangle, 10^k) \mbox{ using space } \le f(|\langle M \rangle, 10^k|) \}.
$$
And then stated:

  Now, for any machine $M$ that decides a language in space $o(f(n))$, $L$ will differ in at least one spot from the language of $M$. Namely, for some large enough $k$, $M$ will use space $\le f(|\langle M \rangle|, 10^k|)$
  on $(\langle M \rangle, 10^k)$ and will therefore differ at its value.

I get the diagonalization argument, but what makes me wonder according to the linear speed up theorem for space we have [see for example Hopcroft/Ullman, 71]:

  If $L$ is accepted by an $S(n)$ space-bounded Turing machine with $k$ storage tapes, then for any $c > 0$, $L$ is accepted by a $cS(n)$ space-bounded Turing machine.

As shown in the linked wikipedia article $L$ is accepted by a Turing machine using $f(n)$-bounded space, then by linear speed up $L$ is also accepted by some machine $M'$ using at most $\frac{f(n)}{2}$ tape cells. But then we get a contradiction on the inputs $(\langle M' \rangle, 10^k)$, as $M'$ accepts $L$ if $(\langle M' \rangle, 10^k)$ is accepted, then $(\langle M' \rangle, 10^k) \notin L$, contradiction, and similar for the case if it is not accepted. If $(\langle M' \rangle, 10^k)$ is not accepted by $M'$ then $(\langle M' \rangle, 10^k) \in L$ by definition of $L$, but $(\langle M' \rangle, 10^k) \notin L(M') = L$, a contradiction.

My reasoning seems to be fine, but it should not be... what am I missing here? In my argument, the problem is with the speed up and essentially it derives that if speed up is possible, then we can separate $f$ and $cf$ for $0 < c < 1$, i.e., speed up is not possible. The only valid conclusion would be that linear speed up is not possible, but that is certainly not true...


texts: Algorithm to find best combination of datasources (Quality and price)

texts:
I have some sources of data, and each one of this sources have a cost per request. I know wich data attributes each one of these sources have, and what are the best sources for each attribute.

Given a list of attributes, I have to decide the best group of datasources to consume, thinking about Quality of the data first, and secondly about costs.

Its common to make requests to multiple datasources, getting just some attributes from each one, but i will give a simple example below:

Say I have something like this:

DATASOURCE A costs $0.50 returns NAME (good), BIRTHDAY (good), ADDRESS (good)

DATASOURCE B costs $1 and returns NAME (good), MONTHLY INCOME (good), ADDRESS (medium)

DATASOURCE C costs $0.70 returns MONTHLY INCOME (good), NAME (medium)

If i want NAME, it would be better to consume DATASOURCE A (quality and cost of NAME).

If i want MONTHLY INCOME, it would be better to consume DATASOURCE C. (quality and cost of MONTHLY INCOME)

If i want NAME and MONTHLY INCOME, now it would be better to consume DATASOURCE B (because NAME and MONTHLY INCOME are GOOD).

But if i want NAME, MONTHLY INCOME and ADDRESS, I need to consume DATASOURCE A (for NAME and ADDRESS) but will consume DATASOURCE B too for MONTHLY INCOME.

Im trying to make some algorithm that makes sense to do it, but its getting very messy hehe. I would love any help with the logic. Maybe in javascript, java, c# or anything else I could read and have good idea about the best way to solve this.

Any help will be apreciated.

edit

some things to note:

I will have only 3 types of Quality here, and always prefer the best quality, so If i know any datasource has quality GOOD for the attribute, i can filter all other datasources with quality lower than Good for this attribute.

I know that in my case, we will have something like 5 or 10 datasources at all, and only 2 or 3 will have the same attribute.


texts: Optimal prefix-free binary code with several codewords already assigned

texts: The classic Huffman algorithm, as Wikipedia states, finds an optimal prefix-free binary code with minimum expected codewords length, given a set of symbols and their weights. Now, suppose codewords for some (but not all) symbols are already assigned (maybe in a suboptimal way). How should we assign remaining codewords to the remaining symbols so as to minimize the minimum expected codewords length, assuming that there exists at least one binary sequence such that none existing codewords have it as their prefix, and neither of the existing codewords is its prefix?


texts: Are there well-specified formal languages that are not regular?

texts:
Given a finite alphabet, there are well-specified formal
  languages that can not be recognized by regular expressions, FSAs or regular
  grammars True/False

I am studying for my exam and I am unsure about this question. From my understanding, you generate formal languages from regex, FSA. For i.e. for a* our formal language will be

empty,a,aa,aaa etc.

So I can identify if a formal language can be described by a regex, but not sure if that is always the case. Could somebody please help me with this?


texts: I can't seem to convert a NFA to a regex. What am I doing wrong?

texts:
I have the following diagram :

I try to remove state 3:

Now I do this:

What do I do now to get my regular expression? I'm stuck.


texts: Identify common mathematical problem behind my task in scheduling area

texts:
Having single operator, which could do work and it's time of availability - for example from 8 am till 9 pm.  And operator have limited resource - let's call it energy (e), e <= E_MAX.

List of works that need to be done: [w1, w2, w3, ... ,wN], (operator could complete only subset of works, all incompleted works moving to next period)

Each work require:
    time - [t1, t2, t3, ..., tN] - t[I] - time required to complete w[I]
    energy - [e1, e2, e3, ..., eN] - e[I] - energy comsumed to complete w[I]

However some work have fixed schedule [wK1, ..., wKN], like w[k1] should be done from 3pm till 4pm. All other work could be completed in any other empty time slot.

And finaly each task have it's reward - [r1, r2, ..., rN], where r[i] - reword we get for w[i], but there is one more problem. Reward it's not a constant, it's some function from energy. so r1(e|t1) could be different from r1(e|t2), where e|t[i] - energy at moment i.

The problem is to build schedule which maximaze total reward for the period.

So this seems like optimization combinatorial problem and I'm trying to figure out - what is a common problem behind it. For the first look I thought about knapsack problem, but I think that fact of some work have fixed schedule make whole story pretty different.

I would appriciate for your ideas - what model it could be or maybe what changes I need to make to convert it to some existing problem.

UPD 1: Assuming there is no breaks in task. All unfinished/uncompleted task just moving to next period. So operator work only with subset of all works and could select any he like - the goal is just get max profit buy the end of the period.


texts: Find the maximizing row-column matches in a matrix

texts:
I have a set of R x C matrices similar to the following (can be much longer):

    C1      C2      C3      C4      C5      C6
R1  0.32    0.81    NA      NA      NA      NA
R2  0.90    -0.44   0.95    NA      NA      NA
R3  NA      0.93    0.86    0.24    NA      NA
R4  NA      NA      0.70    0.74    0.15    0.05
R5  NA      NA      NA      NA      NA      NA

I need to find the sequence of row-columns matchings that provides the overall maximum values (when summed). Each row can be associated to one and only one column, and "cross" matchings are not allowed, i.e. if R2 was matched with C4, a following row R>2 cannot be matched with a previous column C<4.

Given the limit on crossed matching, and as the number of rows and column can be unequal, obviously not all rows and/or columns will be matched

The solution in this example would be:

[R2:C1 = 0.90] + [R3:C2 = 0.93] + [R4:C4 = 0.74] = 2.57

which is higher than alternative solutions that may contain the highest values in the matrix, such as:

[R2:C2 = 0.81] + [R2:C3 = 0.95] + [R4:C4 = 0.74] = 2.50

The only solution I came up with is to create all possible RxC matrices populated by 1 and 0 where the marginal of each row and each column is not greater than 1, and where the no-crossing rule is respected.
Then by multiplying such matrices with the original ones, I obtain new matrices containing ONLY the values in the solution, which can be easily summed.

Example of the solution above:

    C1  C2  C3  C4  C5  C6  |   row
R1  0   0   0   0   0   0   |   0
R2  1   0   0   0   0   0   |   1
R3  0   1   0   0   0   0   |   1
R4  0   0   0   1   0   0   |   1
R5  0   0   0   0   0   0   |   0
_______________________________
col 1   1   0   1   0   0

This is a valid matrix as all the marginals are <= 1 and the positioning is ordered by column = 1,2,4 and by row = 2,3,4

The problem with this solution is that as R or C grows the number of possible permutations becomes extreme.

I need to implement a general and fast solution in a software, and I can't compute millions of table each time.

Any hint will be useful, thanks!!!!

EDIT: This is my implementation of D.W.'s answer in pseudo code

result = matrix(R, C, 0) //allocate response matrix RxC with all elements = 0
for (i from 1 to R){
  for (j from 1 to C){
    part1 = A[i-1,j]
    part2 = array[j] //allocates array of length j
    for(jPrime in 1:j){
      part2[jPrime] = M[i,jPrime] + A[i-1,jPrime-1]
    }
    A[i,j] = max(part1, max(part2))
 }
}

This returns the following A matrix:

     [,1] [,2] [,3] [,4] [,5] [,6]
[1,] 0.32 0.81 0.81 0.81 0.81 0.81
[2,] 0.90 0.90 1.76 1.76 1.76 1.76
[3,] 0.90 1.83 1.83 2.00 2.00 2.00
[4,] 0.90 1.83 2.53 2.57 2.57 2.57
[5,] 0.90 1.83 2.53 2.57 2.57 2.57


texts: Proving a language is not context-free using the pumping lemma

texts:
I had a question regarding the use of the pumping lemma for a particular language I came across. I feel like I have almost solved it, but have gotten stuck on the last steps and wanted some advice. Here's the language in question:
$$L = \{a^nb^jc^k:\ k = jn\}$$
$\space$
Choose $w = a^mb^mc^{m^2}$. For $w_0 = uv^ixy^iz$, we can come up with a total of five cases:

$vxy$ consists of all $a$'s.
Let's say $v = a^{k_1}$ and $y = a^{k_2}$. If we use $i = 0$, then
$$w_0 = a^{m-k_1-k_2}b^mc^{m^2}$$
Considering the original condition of the language of $k = jn$,
$$m^2 = m(m - k_1 - k_2) = m^2 - m(k_1 + k_2)$$
is satisfied only if $k_1 = k_2 = 0$, which gives us a contradiction because
that would mean $v$ and $y$ are empty and goes against the principle of the
pumping lemma which states that $|vy| \ge 1$.

$vxy$ consists of $a$'s and $b$'s.
Let's say $v = a^{k_1}$ and $y = b^{k_2}$. The same principle applies as case 1.

$vxy$ consists of all $b$'s. Same as previous cases.

$vxy$ consists of all $c$'s. Again, essentially the same principles may be used as previously.

The only case that I've been having trouble proving is the last one, where

$vxy$ consists of $b$'s and $c$'s.
Let's again say $v = b^{k_1}$ and $y = c^{k_2}$. For $i = 0$,
$$w_0 = a^mb^{m - k_1}c^{m^2 - k_2}$$
$$m^2 - k_2 = m(m - k_1) = m^2 - mk_1\ ?$$

I've been having trouble determining whether or not the last condition of $k_2 = mk_1$ holds or not. Could anybody give me some tips or advice?
Thank you.


texts: If you have a DFA M, how do you construct a new NFA that accepts L(M) and {e}?

texts:
Suppose you're given a DFA $M$ with a 5 tuple of $(Q, \Sigma, \delta, q_0, F)$.

How do you construct an NFA that accepts $L(M)$ and $\{\varepsilon\}$, the set containing the empty string? I know that a DFA is an NFA.

My thought is that you would simply add a new transition from the start state to the accepting state, which takes epsilon/the empty string.

For example (eps. is epsilon/empty string):

Since I've added an empty string transition, the machine is no longer a DFA, but it is an an NFA.


texts: Complexity of calculating a single model versus all models of a propositional formula with a SAT solver

texts:
I have little background with SAT sovers and theoretical computer science.

How can I describe the complexity of calculating all models of a propositional formula versus just the usual SAT problem of finding just one model?

I am writing a paper, in an area where finding a single of a model of a type of propositional formula is considered "easy", but for my reasearch I need to calculated all models. (I am using Picosat that can calculate all models of a logic formula.) Is there a way to describe how "hard" or "complex" finding all models is compared to finding a single model?


texts: How to prove that the composite strategy is prefix-closed and respects the alternation condition?

texts:
I'm doing some research on game semantics using these notes. Currently I'm trying to prove that the definition of composite-strategy is indeed a strategy.

I have already proved all the conditions of strategies except that it is prefix-closed(for even-length prefixes) and respects the alternation rule.

Can somebody give me a hint on approaching this two specific conditions? I have already tried many times but all my attempts led to unfinished proofs with a lot of cases (e.g. 10-12) and after proving most of those I couldn't finish the others, so I believe I'm approaching the problem from the wrong point of view.

For the definitions please refer to Chapter 3 of the notes linked above, not to the articles of, say, Abramsky and Hyland/Ong, since the definitions are slightly different(e.g strategies contains only even-length strings, while Hyland/Ong admit odd-length strings). If you refer to these you should also give some hint as to how to apply the techniques to the definitions in the notes.

Also note that the missing conditions that I'm trying to prove are all about proving that $u \upharpoonright A, C$ is a legal position for $A \multimap C$, which, in Ong's article, is something assumed in their definition of composite strategy.


texts: How to calculate the number of states in designing a Turing machine?

texts:
I would like to ask how to determine the number of states when designing a Turing machine from the description for a language? For example:

$\qquad \displaystyle L = \{wcw \mid w \in \{0,1\}^*\}.$

I mean how to know how many states are there in the set $Q$, with the information from the description of that language.


texts:
Given a 2d array of pixel values, is it possible to iterate over just the pixels in a circle in a way that is less costly than simply iterating over a square and checking if a value is within the circle?

I need to get the values of pixels within a circle given center coordinates and the radius. Ideally I would ONLY iterate over the pixels in the circle as the leave number of iterations possible is the least costly for time.

The only solution I have found so far is to iterate over a square(shown in green below) and for each pixel, check if its inside the circle using pythagoras before performing the logic I wish to do.

Is there a way to only iterate over the solid circle of pixels alone?

(Int the image below, the desired pixels are highlighted in RED and the containing square is in GREEN)

thank you in advance for any help and resources offered


texts: Does a polynomial solution to weakly-NP Complete problem mean P = NP?

texts: Suppose someone finds a polynomial solution to weakly-NP Complete problem does that mean P = NP.


texts: Prove by induction that a recurrence has solution $T(n)=\Theta(n^2 \log_{3}n)$

texts:
Prove by induction that $T(n)=\Theta(n^2 \log_{3}n)$ where
$$T(n)= \begin{cases} 1 & \mbox{if } n=1,\\ 9T(\lceil n/3 \rceil)+n^2 & \mbox{otherwise.} \end{cases}$$
The base case for $n=1$ seems to work, but I am unable to do the induction step.


texts: Prove that exists PARITYn fuction with size O(n^2)

texts:
Have to find Boolean circuit formula that solves PARITYn problem with complexity O(n^2)?

(Function PARITYn(x1, . . . , xn) is equal to 1 if and only if the number of variables x1, . . . , xn equal to 1 is odd.)


texts: Optimal substructure and dynamic programming for a variant of the rod cutting problem

texts:
The rod-cutting problem described in Section 15.1 of CLRS, 3rd edition is the following.

  Given a rod of length $n$ inches and a table of prices $p_i$ for $i = 1, 2, \ldots, n$, determine the maximum revenue $r_n$ obtainable by cutting up the rod and selling the pieces.

This can be solved by dynamic programming with the recursion (consider the leftmost piece of length $j$):
$$R(i) = \max_{1 \le j \le i} \Big(p_j + R(i-j)\Big),\; R(0) = 0,$$
where $R(i)$ denotes the maximum revenue obtainable by cutting up a rod of length $i$.

In exercise $15.3$-$5$, a variant is considered:

  we also have limit $l_i$ on the number of pieces of length $i$ that we are allowed to produce, for $i = 1, 2, \ldots, n$.

Problem: Is this variant of the rod cutting problem solvable using dynamic programming?


texts:
Let's say I have a long text of 1M words and I would like to create a table of all the words ordered by the number of occurrences in the text.

One approach would be populating a dynamic array with each word and linear search them to count the occurrences in $O(n^2)$ then sort the array by occurrences in $O(n \log n)$.

Another approach would be to use y priority queue and a trie. The insertion in the priority queue is $O(\log n)$ and the build of the trie is $O(n)$. But traversing the trie to build the priority queue is somehow difficult to evaluate.

Eventually using a hash map seems to be the best solution, but computing the hash could cost a little bit of time even though it is just a constant. In this you have $n$ insertion/lookup in $O(1)$ then a final sort of the hashmap by occurrences in $O(n \log n)$.

So it is clear that the former approach is the worse and the latter the best. But how can I evaluate the complexity of the second one?


texts: Is realization of unit disk graphs hard?

texts:
It is known that recognizing a unit disk graph is NP-hard [1].
However, the paper does not mention how hard the realization problem is.
I have looked up several references [2][3][4]. None of the papers answer whether the following problem is NP-hard:

Given a unit disk graph $G = (V,E)$, find a configuration of a set
$\mathcal{D}$ of disks, such that the intersection graph
$G(\mathcal{D})$ of $\mathcal{D}$ is isomorphic to $G$.

The difference between this problem and the recognition problem is that the input of this problem is guaranteed to be a unit disk.
Is there any study that shows the complexity of the above problem? I expect it to be NP-hard, but I am yet to find a full proof.


texts: I am trying to construct a DFA with this language L - all strings consisting of 0’s followed by a (possibly empty) string of 1’s followed by a (possibly empty) string of 0’s. I made the start state also an accepting state to accept the possible empty strings of 0's and 1's. Do I need to add more accepting states to represent the possible empty strings? How can I represent the possible empty string? I am not sure if I have built the DFA correctly. What is going to be the regex for this DFA?


texts: Are there P problems with no known polynomial-time algorithm?

texts:
As the title says, I'm just curious if there are any problems with polynomial-time algorithms, but where no polynomial-time algorithm for it is currently known? Of course, this question would be trivial if the only method of showing a problem is in class P is by providing an algorithm. However, there can also be non-constructive proofs, which is why I ask.
A quick Google search turned up nothing. Also, this is my first question on this site, so my apologies if I'm breaking any rules.


texts: Proving that for every computable function f: N → N, there exists a computable function g: N → N such that for every n we have f(n) ≤ g(n)

texts:
Prove that for every computable function $f \colon \mathbb N \to \mathbb N$, there exists a computable function $g \colon \mathbb N \to \mathbb N$ such that for every $n$ we have $f(n) ≤ g(n)$.

Can anyone please explain me, why my proof below is not correct?

  Lets assume, for the sake of arriving at a contradiction, that there exists a computable function $f$ such that for every computable function $g$, there
  exists an $n$ such that $f(n) > g(n)$.

  For each computable function $g$, let $n(g)$ be the smallest $n$ such that $f(n) > g(n)$. Let $n_0$ be the maximum of $n(g)$ over all computable
  functions $g$, and assume that this maximum is achieved for $g_0$, that is,
  $n(g_0) = n_0$.

  Define a function $g_1$ that is equal to $g_0$ for all values except for $n_0$, and for $n_0$ we have $g_1(n_0) = f(n_0)$. This function $g_1$ is computable because $g_0$ is computable and $g_1$ differs from $g_0$ in only one point. By definition, $n(g_1) ≥ n(g_0) + 1$, and this contradicts the fact that $n(g)$ was maximized at $g_0$.


texts: Can Tarjan's SCC algorithm find satisfying assignment to just 'any' digraph?

texts:
Is Tarjan's algorithm capable of finding satisfying assignment to any digraph consists of variables (vertices) and implications (edges)? I know that it solves implication graphs constructed by 2SAT clauses, but I wonder if the algorithm can handle the digraphs which cannot be expressed as 2SAT clauses. Let me clarify this by the following examples:

(a+b)(~b+c) translates to the following
(~a -> b),
(~b -> a),
(b -> c),
(~c -> ~b)
It is OK. But how about the following implications:
(a -> b),
(b -> ~c)
There is obviously no corresponding set of 2SAT instances. Does Tarjan's algorithm find a satisfying assignment to this?


texts: How to determine if prolog query will give an answer or not?

texts:
Explain what will happen if we try to evaluate the query “path(a,e).”. When the query was actually run, it kept looping.I used the following method. Is it correct?

When evaluating $path(Z,e)$, if $path(Z,e):-edge(Z,e)$ was chosen, it would have returned true since there is $edge(b,e)$. But why did the program choose the recursive rule? Or am I missing something here?

Another similar question was evaluated the same way,


texts: Is there a metric for the similarity of two image filters?

texts:
Definitions

An image filter is a matrix $m \in \mathbb{R}^{k_1 \times k_2 \times k_3}$ which gets applied to an image $I \in \mathbb{R}^{l_1 \times l_2 \times l_3}$ as a discrete convolution

$$I'(n_1, n_2, n_3) = \sum_{i=0}^{k_1} \sum_{j=0}^{k_2} \sum_{k=0}^{k_3} I[n_1-i - \lfloor \frac{k_1}{2} \rfloor, n_2 - j - \lfloor \frac{k_2}{2} \rfloor, n_3 - k - \lfloor \frac{k_3}{2} \rfloor] \cdot m[i, j, k]$$

There are some well-known filters like Laplace filters, Prewitt filters, ... (see my interactive example)

For example, for an RGB image $k_3 = 3$ and $k_1, k_2$ are width and height.

Question

Is there a metric to compare the similarity of image filters?

Context

Convolutional Neural Networks (CNNs) learn image filters. As they are randomly initialized, the filters they learn are different each time you train them. I am interested in quantifying those differences.

I could, of course, use any metric for elements of $\mathbb{R}^{k_1 \times k_2 \times k_3}$. However, consider the filters

$$
\begin{align}
m_1 &= \begin{pmatrix}-1&0&1\\-1&0&1\\-1&0&1\end{pmatrix}\\
m_2 &= \begin{pmatrix}1&0&-1\\1&0&-1\\1&0&-1\end{pmatrix}\\
m_3 &= \begin{pmatrix}-0.9&0.1&1\\-0.9&0.1&1\\-0.9&0.1&1\end{pmatrix}\\
\end{align}
$$

For the image

$m_1$ produces

and $m_2$ produces

You can see a difference, but much less than for the result of $m_3$:

This is probably not captured by most metrics. Another idea was to apply the metrics to the processed images on a given dataset, but this would make the results depend on the dataset and be computationally very intensive.

(In case you want to try image filters yourself with Python: https://gist.github.com/MartinThoma/f51a1044c4abc6c7b81915ef96b7cfbd)


texts: Analysis of a recursive algorithm, where running time strongly depends on input

texts:
I want to find the worst-case running time of an algorithm, which follows the following recurrence equation: The worst-case running time is $\Theta(n^2) + T(n, 2, n)$, where

$T(x, i, y) = \begin{cases}
1 & \textrm{if $(x=0)$ or $(y=0)$ or $(i > n)$} \\
    x+y+ T(x-a,\quad i+1, \qquad b)\\
    \ \qquad+ T(x-a,\quad i+1,\ y-b)\\
    \ \qquad+ T(\quad\ \ \ a,\quad i+1,\ y-b) & \textrm{otherwise}
\end{cases}$

where $a \in \{0, ..., x\}, b \in \{0, ..., y\}$, and $a,b$ can be different in each recursion step, dependent on the input.

(Note: $x$ and $y$ represent the sizes of two lists $|L_1|=x, |L_2|=y$, and in each recursion step, each list is split into two, i.e. into lists of size $a$ and $x-a$ (for $L_1$), and $b$ and $y-b$ respectively (for $L_2$).)

How can I analyze such a recurrence equation, i.e. determine $f$ s.t. $T(n, 2, n)\in O(f)$?
In particular, I do not know how to deal with $a, b$, especially since they are completely dependent on the input of the algorithm.

(I can solve the recurrence equation for special cases of $a,b$, e.g. $a=\frac{x}{2}, b=\frac{y}{2}$ for all recursion steps, or $a=x, b=0$ for all recursion steps etc., but not in general.)


texts: Finding partial traveling salesman path of specified length

texts:
For a given set of nodes, I can find optimal paths that visit all nodes using various traveling salesman algorithms. As a subset of this problem, I would like to be able to find shortest partial solutions as well. For example, if I simply don't have enough time to visit all n nodes, what's the shortest path that connects any n-1 nodes?

For example, in this image, the shortest path visiting 4 nodes is CBAD, 3 nodes would be CBA, and 2 nodes would be CB.

The n-1 case seems approachable at least, by solving TSP for each subset of nodes excluding 1 node and taking the shortest of these solutions, but the problem appears to become less elegant if you are attempting to to find the shortest path with a length of say n-5 or something.

I cannot simply truncate partial paths when solving using branch and bound, because my bound calculation still needs to know how to calculate a bound for shorter than total length path (though perhaps that is still the best solution).

Is there a name for this type of problem, and/or discussion of solution approaches?

Update:
I've been experimenting with ways to modify the bound calculation for this type of problem. One approach that seems to produce correct results, albeit at a steep performance cost, is to change the bounding function so that instead of summing all best paths out of each unvisited node, it only takes the k lowest paths out, where k=(partialPathLength - currentPathLength).

//bound = cost of current steps + minimum edge from each unvisited node
int getBoundForPath(final byte[] path){
        int bound = 0;
        //sum the cost of each step so far
        ...
        //if this is the complete path, we're done
        ...

        //then add the minimum distance out from each remaining nodes
        nBestPaths.clear();
        for(int i = 1; i <= numNodes ; i++){
            //if we've been to i, skip it
            ...

            int lowest = Integer.MAX_VALUE;
            for(int j = 1; j <= numNodes ; j++){
                //if you can't get from i to j, or we've been to j, skip it
                ...
                lowest = Math.min(shortestPaths.get(nodeList[j]).get(nodeList[i]), lowest);
            }
            nBestPaths.enqueue(lowest);
            //bound += lowest; //normal approach, sum all
        }
        //new approach: only sum the best k elements
        for(int i = 0; i < maxPathLength-second && i < nBestPaths.size(); i++){
            bound += nBestPaths.dequeueInt();
        }
        return bound;
    }

This is not really a viable strategy, however, as the performance cost of looping and dequeuing that many times every single time I check a bound totally trashes the performance of my implementation. I could clean up this code a little, but I'm not sure it's going the best direction.


texts:
Okay lets say i have two data structures . two phone data for example containing their Name and spec ( cpu , ram , display etc ) . I want to check if these two phones are the same or not . Their names can be different as their other features . For example we have a :

  Name : Galaxy s3,  CPU : Dual core , Display : 4 inches

and on the other hand i have :

  Name : galaxy SIII , CPU : dualcore 1.2 , Display : 4'

as a human can understand these two phones are the same . but how can a machine say this ? On top of my head i have a solution . I can set weight for each field and calculate the similarity between each two fields by simple text comparison and then multiple to its weight . define a threshold and thats it . BUT i want to know if there is any scientific field about this or not . Are there any deep learning solutions or anything else . Thanks


texts: Computationally and memory efficient algorithm for a relatively simple problem

texts:
Given a list of non-overlapping ranges and values, i.e. [(0, 5, 0.5), (10, 15, 1.1), ...], and a list of potentially overlapping ranges (bins), i.e. [(0, 10), (5, 15), (0, 5), ...], find the average, min, max, standard deviation of the bins.
For example, the answer for averages would be [0.25, 0.55, 0.5, ...]. Assume there is a implicit range (5, 10, 0) in the first list.
The max range is from 1 to 109. The number of bins ranges from 1 $\le$ n $\ge$ 1010.
What is a memory and computationally efficient way of solving this problem?
Edit: The first list of non-overlapping ranges would create a list: [0.5, 0.5, 0.5, 0.5, 0.5, 0, 0, 0, 0, 0, 1.1, 1.1, 1.1, 1.1, 1.1, ...]. A pair in the second list would specify the indices of the range to find a statistic. The average for the first pair, (0, 10), would be (0.5 * 5 + 0 * 5) / 10 = 0.25.
This is an actual problem in bioinformatics, and an algorithm already exists here, but I was wondering if there was a potentially better one.


texts: Optimize stacking time series by offsetting start times (feels like a backpack problem?)

texts:
Given a time-series of data collected from a single running process that takes 8 hours to complete:

Minute
GB of Disk Space Used

0
0

1
8

2
15

3
22

...Etc.  It is sampled every minute, for 8 hours.  The # of GB used jumps up and down a lot, and ends back at 0, like a big spiky mountain shape.  I'm making a (large) assumption that running multiple instances of this process in parallel takes up proportionally more space, but doesn't slow eachother down.

I've also got a hard upper bound that the summed area graph (the total of all space usage at any given minute) can't go above.

My personal upper-bound is 780GB (the amount of spare disk space), and if I ran 53 processes in parallel starting at the same time, they would all add up at minute 2 to (53 * 15) = 795 (which is > 780), the disk would run out of space, and everything would crash.  Or if I ran 35 in parallel, they would crash at minute 3.  No crashing allowed!

The goal is complete as many runs of the process as possible within the next 7 days, by "packing them in" and running them in some overlapping manner by deciding when each run of the process starts.

First Attempt: Greedy
At first I thought it was a simple greedy problem:
At every minute, ask "can you start a new process without the total of all running processes exceeding the limit in the future?"  If yes, great! start a new one.  If not, wait a minute and try again.  This leads to "start 3 processes immediately.  Wait until they all finish.  Then do it again for 7 days."
Second Attempt: recursive?
Done!  wait... that feels wrong, backpack-packing style.  What about "If you line up runs A and B just right, they make a valley you could fit C in to."
Which makes it feel like a recursive solve problem.  Is there an accepted way to optimize this sort of thing?
Third Attempt: Minimize the Maximum (like Tetris?)
My best guess at this point is a simple optimization strategy:

Define a time bound (7 days)
Place the next process start time at whatever is the minimizes the "max space used on the drive, over all time"
If there are ties, move the graph to the soonest start point.
Repeat #2 until nothing more fits.

This would work out to:

First process starts immediately.
Second process starts before the first one finishes: Whenever is in the downslope of the first one exceeds the upslope of the second one.
Keep adding process start times until there isn't a place to slot in one more.


texts: Which machine learning algorithm is appropriate for predicting a vector?

texts:
I have a very large set of animal migration data, consisting of many series of vectors - each series is basically a path of a single animal. The dataset I'm using consists of 244 of these series.

I want to train a predictive model so that when it is given a collection of these series and a map of environmental variables, such as a map of ocean surface temperature, it can output a new collection of these series.

My question is which machine learning algorithm would be optimal for this kind of prediction - I was looking into multinomial logistic regression, but that is for categorical data. I want the algorithm to develop a model that thinks at a point with an ocean surface temperature of 20˚C, an animal will travel along a vector with a magnitude of 35km and an angle of 34˚'.

I was also looking into using the random forest algorithm, but that seems to be more for classification than forecasting. Does the algorithm I'm thinking of exist? Thanks so much.

EDIT: My particular question is not how to fit this data with a particular ML method, but is there an ML algorithm that can predict a new vector (in polar form) given an old vector and an environmental variable at the tail of that vector.


texts:
How would you approach the knapsack problem in a dynamic programming situation if you now have to limit the number of item in the knapsack by a constant $p$ ? This is the same problem (max weight of $W$, every item have a value $v$ and weight $w$) but you can only add $p$ item(s) to the knapsack and obviously need to optimize the value of the knapsack.

Do we need a 3rd dimension or we could find an other approach without it. I tried to simply add the number of item in the knapsack in the cell and taking the max value at the end with the number of item <= $p$ but it is not the BEST solution.


texts: Kolmogorov Complexity proving there exists a constant for when if two strings are equal length

texts:
When talking about kolmogorov complexity, I understand that it describes true randomness of given (for now) a string $x$, if we can describe x in less than the $|x|$ then its complexity is said to be

$C(x) \leq |x| + c$

my question lies in finding that c for a given problem.
Given this problem

there is a constant $c$ $∈$ $\mathbb{N}$ such that, for $\forall$ x,y ∈ $\{0,1\}^+$ with $|x|=|y|$
$H(x,y)$ is the hamming distance between $x$ and $y$
$ C(y)$ ≤ $C(x)$ $+ 2·H(x,y)·$(1 + $ \lceil log|x|\rceil $)$ + c$

How would I go about mathematically proving there there is a constant $c$ $∈$ $\mathbb{N}$ what does finding a constant tell us

Constant is defined as follows
as in what does this given a TM M and universal TM $u$ s.t. there exists a constant $c_M$ s.t. $C_u(x) \leq C_M(x) + c_M$(From Solomonoff and turing's theorem)?


texts: Select a subset of the columns in $3\times n$ matrix, is it NP-hard?

texts:
I want to know if this problem is NP-hard?

The problem: Given a non-negative integer-valued matrix of size $3\times n$ of the form

$$
\begin{bmatrix}
a_1 & \ldots & a_n\\
b_1 & \ldots & b_n\\
a_1b_1 & \ldots & a_nb_n\\
\end{bmatrix},
$$

where $a_i,b_i$ are non-negative integers. Given four non-negative integer numbers $b<n$, $c_1$, $c_2$ and $c_3$.

The goal: Find a subset of the columns of cardinality at most $b$ such that (i) the sum of the first row over the subset of the columns is greater than $c_1$, (ii) the sum of the second row over the subset of the columns is greater than $c_2$ and (iii) the sum of the third row over the subset of the columns is less than $c_3$. Return no if no such subset exists. That is to say, is there exists a set $S$ of cardinality at most $b<n$ such that:

$$
\sum_{i\in S}a_i\geq c_1,\\
\sum_{i\in S}b_i\geq c_2,\\
\sum_{i\in S}a_ib_i\leq c_3,
$$

How to show that this problem is NP-hard?

Attempt:

Here is a "similar" NP-hard problem that I asked. This problem has as instance $(n,b,c,\mathbf{A})$ where $\mathbf{A}$ is given by
$$
\begin{bmatrix}
x_1 & \ldots & x_n\\
y_1 & \ldots & y_n\\
\end{bmatrix},
$$
I tried to reduce the previous problem to the new one as follows: choose $c_1=c_2=c$ and choose $c_3$ very big and create the matrix as follows:

$$
\begin{bmatrix}
x_1 & \ldots & x_n\\
y_1 & \ldots & y_n\\
x_1y_1 & \ldots & x_ny_n\\
\end{bmatrix},
$$


texts: Calculating diagonal of inverse of sparse band-like matrix

texts:
I'm trying find an optimization for an equation related to theorem 3.5.7 from "Finite Markov Chains" by Kemeny and Snell (1976). The theorem is:

$$H=(N-I)N_{dg}^{-1}$$

Where $N_{dg}$ is a diagonal matrix with all 0 except for the diagonal portion of N and

$$N=(I-Q)^{-1}$$

And $Q$ is a $n \times n$ square sparse pairwise transition matrix that looks like:

The matrix is symmetric structurally (shown by the colors), but not numerically. It is characterized by 3 tri-bands, with the distance between the bands related to $\sqrt{n}$. If there is a technical term for this matrix, I don't know what it is.

The modified version of the calculation I'm trying to solve simply involves pre-multiplying the theorem with a vector, like so:

$$v(N-I)N_{dg}^{-1}$$

I'm trying to apply this to extremely large matrices (n=1,000,000 is the low end of what we consider useful). I can solve the $v(N-I)$ part of the equation easily enough using the Ax=B approach. Inverting $N_{dg}$ is simple (simply invert the individual values, since the non-diagonal values are all 0). That only leaves finding $N_{dg}$ itself in a reasonably efficient manner (both in terms of time and memory requirements). I would also like to avoid estimation if possible.

Ideally, I wouldn't have to calculate $N$, which involves an inverse that results in a dense matrix, and instead solve the linear system. Unfortunately, the weird nature of $N_{dg}$ seems to preclude that option.

I can solve for individual rows and columns of $N$ by including a vector multiplication and solving the system. From this, I can extract individual elements of $N_{dg}$. However, to do so iteratively to calculate the entirety of $N_{dg}$ is impractically slow (months to years).

I did come across "The inverse of banded matrices" by Emrah Kılıç and Pantelimon Stanica (2013), and subsequently came across this Computer Science stackexchange post that also links to the same paper. Unfortunately, the answer provided assumes that the inverse will not be calculated directly, so my only option is to try and work through the paper myself. My hope is that because I don't need to calculate the entire inverse it will be practical. It looks promising, particularly the $i=j$ case in theorem 7, but it's also beyond my level of linear algebra, so it could take a while for me understand and just end up being a time-consuming dead-end.

Does anyone have any suggestions for a computationally reasonable approach for calculating $N_{dg}$? If the paper I found happens to be the best solution, just distilling it down would be helpful because I'm not a math major.


texts:
Computers and programming languages tend to be deterministic and predictable.  Yet progress bars seem the opposite, especially if the operation is complex.  Even for world class professional products, some progress bars do little to reflect the real progress of an operation.  I've seen them go from 10% to 90% in one leap after doing nothing for 4 hours.  I've even seen some take steps backwards, suggesting extra unexpected processing has been discovered.

Granted that there may be database operations, network processing and parallel operations but it seems that this could be quantified in some manner and a percentage estimated.  After all, there must be a finite amount of instructions executed to complete an operation.  Is this simply poor coding, or is there some fundamental reason representing progress is difficult?


texts: Why do neural networks seem to perform better with restrictions placed on their topology?

texts:
Fully connected (at least layer to layer with more than 2 hidden layers) backprop networks are universal learners. Unfortunately, they are often slow to learn and tend to over-fit or have awkward generalizations.

From fooling around with these networks, I have observed that pruning some of the edges (so that their weight is zero and impossible to change) tends to make the networks learn faster and generalize better. Is there a reason for this? Is it only because of a decrease in the dimensionality of the weights search space, or is there a more subtle reason?

Also, is the better generalization an artifact of the 'natural' problems I am looking at?


texts: Best combination of elements with defined constraints

texts:
My goal is to find the best combination, or good approximation, of weighted elements with different constraints / relations, for example:

B can only be there after A
B have to be there after A
B have a different weight if present after A
B have a different weight if present in the N next elements after A
B can only be there every N elements
B have a weight but does not cost an element
etc...

An elements can have more than one constraint at the same time.

The numbers of different elements available is 10-15, and the best combination should give a list of 60 elements, repeating this cycle of 60 elements should also follow the rules, like "A can only be done every N elements".

Following these rules, what would be the best way to find the best combination of elements?

I thought about Genetic algorithm, but during the crossover/mutation, we will have to verify if the rules are respected - 'ABAC' and 'ACAB' could be legal, but not necessarily the crossover 'ACAC'. Same for bruteforce, where going through 'AAAA', 'AAAB', etc will mostly give illegal combinations.

Maybe generating a graph out of it could help, but it seems to big and complicated to generate.


texts: Domain and range of recursive functions are recursively enumerable

texts:
I want to show the following two propositions:

The domain of a recursive function is recursively enumerable.
The range of a recursive function is recursively enumerable.

I have thought the following in order to prove the first proposition.

Suppose that we have a recursive function $f$. Then we know that there is an algorithm $A$ that computes $f$.
So if $m \in dom(f)$ then we know that the algorithm $A$ with input $m$ terminates, giving output "yes".
Since $m$ is arbitrary, we deduce that the domain of a recursive function is recursively enumerable.

Is my idea right? If so, can't we also deduce from that that the domain of a recursive function is recursive since the algorithm always terminates for the elements of the domain?

Can you give me a hint how we can show the second proposition?


texts: Survivors classes in the extremely unlikely scenario of P = PSPACE

texts:
If its proven today that $P=PSPACE$ the whole polynomial hierarchy collapses. Moreover since $BQP \subseteq PSPACE$, it will also result in $P=BQP$.

However unlikely the above scenario is, hypothetically if this were the case what are the complexity classes (the most important ones) that will survive this collapse into $P$. The classes we are talking about:

Should be above $P$ (thus $L, NC, NL$ etc. could be temporarily ignored)
Are interesting and open enough to be studied (thus $E, EE, ALL$ etc. can be ignored)

We are concerned about both the traditional as well as Quantum Complexity classes.


texts: What changes need to be made to a Turing machine to make them equivalent to a PDA, a DFA?

texts:
I believe in order to make a Turing machine have the same power as a DFA (by power I mean all languages which a DFA can decided so can the Turing machine) we just don't allow any use of backtracking or rewriting, that is you can only move right and read the string in the order it is presented.

To simulate a PDA however I am not sure what restrictions we could apply. I was thinking allowing backtracking but no rewriting on the tape may make a Turing machine with equivalent power to a PDA but I am not sure if that is a correct statement or how I would prove the equivalence of the two.


texts:
if i have an equation like
            $$f_n = x + y + z + a + b$$
and each variable has a discrete answer like $a = 0, 1 , 3$ . $b = 2 ,4,5$ etc.
i want to find the global optimum minimization point. I used Ant colony optimization (ACO) to solve the equation but i am stuck in the heuristic information and how to compute these parameters, as I saw in the traveling sale's man problem eta = one over distance between two cities. But here there is no relation between $x$ and $y$ .

Second i want to make sure that when computing $\delta_\tau$ pheromone updating trail , its equal to $$f_n(\text{best answer in iteration k})\over f_n(\text{worth answer in iteration k})$$ as i saw another equations in papers and got distracted.
I built a matlab model but it didn't give me the optimum point at each run time .
Thank you


texts:
I'm looking for a simple calculus that supports reasoning about reflection, namely, the introspection and manipulation of running programs.

  Is there an untyped $\lambda$-calculus extension that enables one to convert $\lambda$-terms into a form that can be syntactically manipulated and then subsequently evaluated?

I imagine that the calculus has two main additional terms:

$\mathtt{reflect}\ v$: takes $v$ and produces a representation of $v$ amendable to
syntactic manipulation.
$\mathtt{eval}\ v$: takes a syntactic representation of a term and evaluates it.

In order to support reflection, a syntactic representation of terms is required. It would look something like:

$\lambda x.e$ would be represented as a term $(\mathsf{LAM}\ R(e))$, where
$R(e)$ is the reflected version of $e$,
$e\ e'$ would be represented as term $(\mathsf{APP}\ R(e)\ R(e'))$, and
$x$ would be represented as $(\mathsf{VAR}\ x)$.

With this representation, pattern matching could be used to manipulate terms.

But we run into a problem. $\mathtt{reflect}$ and $\mathtt{eval}$ need to be encoded as terms, as does pattern matching. Dealing with this seems to be straightforward,
adding $\mathsf{REFLECT}$, $\mathsf{EVAL}$ and $\mathsf{MATCH}$, but will I need to add other terms to support the manipulation of these?

There are design choices that need to be made. What should the $R(-)$ function alluded to above do with
the body of $\mathtt{reflect}$ and $\mathtt{eval}$? Should $R(-)$ transform the body or
not?

As I am not so much interested in studying reflection itself -- the calculus would serve as a vehicle for other research -- I do not want to reinvent the wheel.

  Are there any existing calculi that match what I have just described?

As far as I can tell, calculi such as MetaML, suggested in a comment, go a long way, but they do not include the ability to pattern match and deconstruct code fragments that have already been built.

One thing I would like to be able to do is the following:

$\mathtt{let}\ x=\lambda y.y\ \mathtt{in}\ \mathtt{reflect}\ x
\to (\mathsf{LAM}\ (\mathsf{VAR}\ y)\ (\mathsf{VAR}\ y))$

And then perform pattern matching on the result to build a completely different
expression.

This is certainly not a conservative extension to the $\lambda$-calculus and the meta-theory is likely to be ugly, but this is kind of the point for my application. I want to break $\lambda$-abstractions apart.


texts: Minimum number of registers needed to compile code segment without spills?

texts:
For the following code segment,

c = a + b;
d = c * a;
e = c + a;
x = c * c;
if (x > a) {
    y = a * a;
} else {
    d = d * d;
    e = e * e;
}

All variables are assumed to be dead after this code segment. The only allowed compiler optimization is code motion, which moves statements from one place to another while preserving correctness, and each instruction can have at most two source operands and one destination operand.

The minimum number of spills to memory on a 2 register architecture for this code is 1, since c will have to be stored into memory, as it is not known if x > a or not. For this same code, with no other optimizations allowed besides register allocation, the minimum number of registers needed in the instruction set architecture to compile this code segment without any spills to memory during the compilation process is 4, but why is this?


texts: Expressing complexity class P using first-order logic with LFP

texts: Can anyone show how to express complexity class P using first-order logic with LFP? (descriptive complexity)


texts: Pushdown Automata - constructing a PDA to recognise a language with at least as many as as bs

texts:
I am trying to construct a 3-state PDA to recognise (I need to create a transition diagram for this question)

W = {w ∈ {a, b}^* | w contains at least as many as as bs}

My thought process so far has been this:

 1. Start off in q0 (q0 being an accept state)
 2. add a $ to the start of the stack (so you can see when the stack is empty), then transition to q1 (not an accept state).
 3. If you receive an a:
  - if there is an a at the top of the stack, push the a on.
  - if there is a b at the top of the stack, pop the b.
  - if there is nothing on the top of the stack, push the a on.
 4. If you receive a b:
  - if there is an a at the top of the stack, pop the a.
  - if there is a b at the top of the stack, push the b on.
  - if there is nothing on the top of the stack push the b on.
 5. Once there is no more input:
  - if there is a $ at the top of the stack, transition to q3 (q3 being an accept state) - this means there was an equal number of as and bs
  - if there is an a at the top of the stack, transition to q3 (q3 being an accept state) - this means there was more as than bs
  if there is a b at the top of the stack, it means there was more bs than as, and thus we stay in q2, which is not an accept state.

(Sorry if this is hard to understand, I am not sure how to link those transition diagrams of the PDA's I've seen in some posts, if someone can tell me how to create one and link it in the post, I can update the post to be more understandable if needed)

I have a few questions:

Is this approach correct?
Is the it correct to assume the machine is smart enough to know that if there isn't a b at the top of the stack, and I receive an a, it will push that a onto the stack (something like (q1, a, ε) -> (q1, a) to cover both cases where there is an a on the top of the stack and also the case where the stack has nothing in it))
Do I need to push a \$ at the start from q0 to q1 in the transition diagram (I've seen this to be the case for all PDAs on my lecture slide - which makes me think is it necessary to include if all machines need to do this - why is it not just implied?)
I am ok to have 2 different scenarios to go to q2 right? Or would I be better doing something in q1, where if I have reached the end of my input queue, keep popping off as on the top of the stack until I reach the \$, then transition to q2?

Sorry if anything is unclear - I am not super familiar with PDAs and the way to describe things - please let me know if I need to clarify anything.


texts: What are all local optima of the six-hump camel back function?

texts: This is a famous function to test optimization heuristics such as genetic algorithms and others. The 2 global optima are described clearly in many webpages, but surprisingly I'm unable to find any information about which input values correspond to the other 4 optima of the function and what these optima actually are. Does anyone know where I can find this information? Not really sure if this is the best place to ask this question also.


texts:
I studied LR(1) parsers and then LALR(1) and noticed that if we wanna construct LALR(1), We should FIRST construct the LR(1) parser and then by combining states we can go ahead for LALR(1) parser.

Now a question comes in my mind, Can we make LALR(1) parser DIRECTLY? Without using (Or constructing LR(1) parser) ? If Yes, How?

Thanks in advance!


texts: A technical clarification on subgraph isomorhism

texts:
Let $G$ be a graph on $|\mathcal{V}(G)|$ vertices. If $H$ is another graph that contains a clique of size $|\mathcal{V}(G)|$, then does it mean $G$ is subgraph isomorphic to $H$? Does this mean that all graphs with vertices less than $|\mathcal{V}(G)|$ are subgraph isomorphic to $H$?

If the above is not the case, is there another term for the exact presence of $G$ in $H$ as a structure preserved subgraph (when I say structure preserved, that means, edges are mapped to edges and non-edges are mapped to non-edges in the subgraph of $H$)?


texts: How do I develop a structured work method for theoretical computer science?

texts:
Please excuse the soft question and please dont close it prematurely as too broad.

When working on assignments that includes a wide range of topics from theoretical computer science (see tags), I often hit a wall  that I cant seem to get over.

When I see the solution it often involved some kind of 'trick' that you had to think of that I just didnt see. The solution to the original problem then makes sense to me.

My current problem solving strategy is to see if I know all the terms and definitions mentioned in the assignment. Then I look what needs to be shown or done to find a solution. Then I look at what I can play around with to get an overview of all the properties that I can use to get to the solution.
But my current problem is that I get stuck here. Sometimes hard.

How can I improve my problem solving skills ?


texts:
The language $A_{PTM}$ is defined as the acceptance problem on a Probabilistic Turing machine.

$A_{PTM}=$ { $<M, x> | M$ on input $x$ accepts with an error probability less than or equal to 1/3}

Basically, given a probabilistic Turing machine $P$ and string $x$, a decider $D$ simulates $P$ on $x$ and outputs accept if $P$ accepts on $x$, and rejects otherwise.

I claim $A_{PTM}$ is BPP-hard because BPP is the class of languages which are accepted a success probability of at least $2/3$. If the PTM for any BPP language is given as an argument to the decider $D$, then it will output accept if the PTM it was passed accepts, and reject otherwise. I know this is far from a formal proof, but I am just trying to understand the idea. Is this correct?


texts:
I've come across the CYK algorithm and was wondering, as it's quite old, if it is still relevant today.

Is it or an extension of it still being used in compilers (for example), or have other algorithms proven to be better?


texts:
Consider the algorithm LastMatch below, which returns the offset (shift) of the last
occurrence of the pattern P in text T, or -1 if P does not occur in T:

LastMatch(T,P)
 for(s = T.length - P.length downto 0)
   j = 1
   while(j =< P.length and P[j] == T[s + j])
     j++
   if(j == P.length + 1)
     return s
 return -1

I've been given a loop invariant for the while loop:

$\forall k(1 \leq k<j \rightarrow P[k] ==T[s+k])$

The initialisation of this invariant confuses me. Before we enter the while loop, $j=1$. So we're asking is there a $1\leq k<1$ such that $P[k] ==T[s+k]$?

I cannot find a $k$ which satisfies this inequality, so I do not understand what this is saying. So why is the invariant satisfied before we enter the loop? Is it because when I cannot find a $k$ it implies that $P[k]$ and $T[s+k]$ are both equal to the empty set?


texts:
In a 32-bit floating number with normalized mantissa and excess-64 exponent base 16, the number $16^{-65}$ denotes

Floating point overflow.
Negative floating point overflow.
All 0's in the exponent and mantissa fields.
The minimum representable positive number .

I think that minimum representable number should be $1 \times 16^{-63}$
because the minimum mantissa should be 1 and and the possible exponent range in bias form is from 1 to 127 (where 1 corresponds to most negative exponent i.e. -63, and 127 corresponds to most positive exponent i.e. 63)

So according to me, the answer is: A positive floating point underflow.
Please correct me if i am wrong. The IEEE-754 representation is confusing me.

Someone also told me something along the lines of " the mantissa part is always taken as 0.M if the base is something other than 2". However I don't have any reference for this statement.


texts: Label coloring to maximize number of "balanced" triangles (NP-hardness)

texts:
Define a triangle in undirected graph $G$ is balanced if the edge labels  in the triangle are $(+1, +1, +1)$, $(-1, -1, +1)$, $(+1, -1, -1)$ or $(-1, +1, -1)$ (social balance theory).

Problem definition:

Given undirected graph $G=(V, E)$, initial edge label function $f: E \rightarrow \{+1, 0, -1\}$ and $k \in \mathbb{Z}^{+}$, find another label coloring function $g: E \rightarrow \{+1, 0, -1\}$ that maximizes the number of "balanced triangles" in $G$

s.t.

$\forall e \in E \text{ such that } f(e) \neq 0, g(e)=f(e) \text{ holds}$ ($g$ conforms with $f$ for non-zero valued edges).
$|\{e \in E \mid g(e) \neq 0 \text{ and } g(e) \neq f(e)\}| \le k$ (up to $k$ unlabeled edges can be labeled.)

I am trying to prove the NP-hardness of this problem, failing to find an appropriate problem reduction.

Here is what I have thought:

First, the problem can be decomposed using recursion.

We consider assigning label to only one edge, then fix it and solve the sub-problem with updated $f$ and $k-1$ labelings.
However, this approach runs in exponential time.

Second, this problem can be seen from the "set cover" perspective.

We can consider each edge as a set containing a subset of all triangles (the universe), triangles can be classified into three types:

1st-order triangle which has only one unknown label edge ($f(e) = 0$)
2nd-order triangle which has two unknown label edges
3rd-oder triangle where all the labels in the triangle are unknown.

A triangle is considered covered if it's 1st-order and the labeled edge makes it balanced.

If we consider some greedy approach by labeling the best edge one by one, then whenever each edge is labeled, the triangle type information will change accordingly.

For example, some 1st-order triangles will no longer be 1st-order while some 2nd-order triangles will become 1st-order because of the newly-labeled edge.

The "chaining" effect actually couples edges together, which makes things more difficult.


texts: Cache memory temporal locality and spatial locality principles

texts: How does cache memory take advantage of both temporal locality and spatial locality principles?


texts: proving correctness of algorithm about graphs with DFS

texts:
I need to prove/disprove the correctness of the following algorithm:
Let G be a simple, undirected and connected graph. The task is to find if the graph contains an odd cycle. The algorithm goes that way. First, you run the DFS algorithm on the graph, since it is connected it will result in a single tree. The for each node $u$, you declare the field $L[u]$. $L[u]$=0 if $u$ is the root of the tree, otherwise $L[u]=L[\pi(u)] + 1$, when $\pi(u)$ is the parent of $u$ in the tree.

Finally the algorithm says that: if there exists and edge $e=${$u,v$} in the original graph $G$ so that $L[u] + L[v]$ is even than the graph contains and odd cycle. Otherwise (if such edge doesn't exist) the graph doesn't contain an odd cycle.

I am inclined to says that the algorithm is correct. I even have an idea of a proof that uses the idea that if such edge $e$ exists, then it must be a back edge in the DFS tree. That would mean there is a cycle and since $L[v] = L[u] + t$, where $t$ is the number of tree edges in the DFS tree between $u$ and $v$, I'll get $2L[u] + t = $ even number, which means that $t$ is even and then with the edge $e$ there is an odd cycle.

However, I want to make sure that I am not missing anything, So if some one approve my way or even give an example to disprove the algorithm I would be glad.


texts: What do CPUs do when a program aborts with an error?

texts: If a very severe interrupt occurs, say a divide by zero, this will quit the program. How is this done, is there a special instruction in the processor or is it a software routine? And after quitting the program, where will the CPU jump to?


texts:
Is a Turing Machine that is allowed to read and write symbols from an infinite alphabet more powerful than a regular TM (that is the only difference, the machine still has a finite number of states)?

Intuition tells me not, since you need an infinite number of states to differentiate each symbol. So I think some of the symbols or the transitions caused by the symbols (or some subsets of the transitions) have to be equivalent. So you can actually simulate such machine with a regular TM and a bounded subset of such symbols or transitions.

How could I approach a formal proof of this?


texts: How is the key in a private key encryption protocol exchanged?

texts:
Windows NT used a point-to-point protocol where a client can communicate "securely" with a server by using a stream cipher to encrypt an array of messages with some key $k$. The server also encrypts its response with the same key $k$. But how is it aware of this key?

More general: if Alice and Bob use some encryption/decryption algorithm that operates on the same private key $k$, what is a secure way of exchanging this key? (without using a different key ofcourse)

This is something that I've always asked myself whilest studying private key cryptography.


texts: How pictures and videos are usually loaded in Memory?

texts:
Lets assume I'm talking about Jpeg and Mp4 and a general video player(not sure if different ones load it differently, if they do please tell)

So do video players (process) usually load the entire Jpeg or Mp4 including metadata into its own memory space right? like lets say we have a 1920x1080  picture with 10 bytes of metadata, does the picture viewer's process loads this into its own heap or maybe stack?  and does it read it sequentially in order to display it?

I'm asking this because i want to know what stops criminals to for example inject some part of a video or picture with malware, lets say 10 malicious instructions are hidden in that file in a frame of a video or part of a picture, what stops the operating system with no good anti virus from executing these malicious instructions?


texts: Count Wildcard Parenthesizations of a String

texts:
Let $\Sigma = \{ (, ), ? \}$ be an alphabet. For a given string $s \in \Sigma^*$, we denote by $f(s)$ the number of ways to replace each symbol $?$ either with $($ or with $)$ such that $s$ is correctly parenthesized.

For example, for $s = ((????)))?$ the strings $((()(())))$ and $(()((())))$ are possible, so $f(s) \ge 2$.

GOAL. The task is to evaluate $f(s)$ efficiently, i.e. in subquadratic time in the length $n$ of $s$.

APPROACHES. I present my approaches as following. First, we can check in time $\mathcal{O}(n)$ if a string is correctly parenthesized and we always have $f(s) \le 2^n$. Thus, a $\mathcal{O}(n2^n)$ brute-force solution can be deduced. It's also quite an easy exercise to find one correct parenthesization of a string in time $\mathcal{O}(n)$, but that's not what I want. The goal is to count them.

Using dynamic programming the problem may be solved in time $\mathcal{O}(n^2)$. We define the potential $\varphi(s')$ of a string $s'$ as number of opening brackets "$($" minus number of closing brackets "$)$". For instance, we have $\varphi("((()()()") = 5 - 3 = 2$.

Denote by $dp(k, l)$ the number of ways to replace $?$ with $($ or $)$ in the substring $s_1s_2\dots s_k$ of $s = s_1s_2\dots s_n$ such that $\varphi(s') = l$ for the resulting string $s'$. We get the following reccurence:

$\displaystyle dp(k, l) = \begin{cases}
dp(k - 1, l - 1) & \text{ for } s_k =\text{ }(, \\
dp(k - 1, l + 1) & \text{ for } s_k =\text{ }), \\
dp(k - 1, l - 1) + dp(k - 1, l + 1) & \text{ for } s_k =\text{ }?.
\end{cases}$

The answer to original problem is $f(s) = dp(n, 0)$. Since there are $n \cdot \varphi_{max} \le n^2$ states (negative potentials are not allowed) and each state can be computed in time $\mathcal{O}(1)$, the total time complexity is $\mathcal{O}(n^2)$. Note that we assume addition to be a constant-time operation.

Are there any faster algorithms? Does this problem have a name and are there resources for further reading? I appreciate answers and thoughts to this problem.


texts: Partitioning a set based on binary predicate

texts:
Given a collection of objects $X = (x_0,x_1,...,x_{N-1})$ and a binary predicate $F$ which takes as parameters elements of the collection, find a better than $\mathcal{O}(N^2)$ algorithm which partitions the set as:

$X= \bigcup X_j$

such that for any $j$ it holds that $F(x_k,x_l) = 1$ if $x_k,x_l \in X_j$ and $F(x_k,x_s) = 0$ if $x_k \in X_j \land x_s \notin X_j$ (boolean values are being used at True/False).

My initial guess was to use a divide and conquer algorithm but was not able to find a merging algorithm which would make the divide-and-conquer strategy worth it in terms of complexity gain.  I imagine this is a standard problem but I am not sure where to look for a solution or if such a solution exists for an arbitrary binary predicate.


texts: Which Turing machine problems are Decidable?

texts:
Let $M_0$, $M_1$, $M_2$,..., be an effective enumeration of all Turing machines. Which of the following problems is (are) decidable ?

Given a natural number $N$, does $M_N$ starting with an empty tape halts in fewer than $N$ steps ?
Given a natural number $N$, does $M_N$ starting with an empty tape halts after at least $N$ steps?
Given a natural number $N$, does $M_N$ starting with an empty tape halts in exactly $N$ steps?

I've looked some of these similar problems like :-

Prove that this language is decidable or undecidable

Is the set of Turing machines which stop in at most 50 steps on all inputs, decideable?

I've got some idea that $TM$ problems related to $N$ steps, only the cells upto $N$ are significant.

Such problems are decidable, however long input we take.

Hence, I come to the conclusion that $1$st part of my problem will be decidable similar to the reasoning as given above.

Similarly, for $3$rd part, if we check $N$th cell we can say $Y/N$ hence Decidable.

But, I am stuck in $2$nd part.

(What I think is that upto $N$th cell we can check if it halted, making it semidecidable otherwise it will definitely halt after the $N$th cell. Hence, I think it is also Decidable).

Please let me know how much correct progress I made. I don't have solutions for these questions. Need some confirmation ?


texts:
Firstly, I'd like to apologize for any misused terms or ways I could have made the description much more succinct. It's been a while since I took machine learning during my bachelor's.

I have two disconnected, directed graphs that I am attempting to merge together. Each node in the graph represents a set of data. Each edge is a member of the data set that is used by the kernel.

For each node in DG1 I am comparing it to each node in DG2 into graph DG3. I compare the data sets of the node via a kernel and determine a similarity confidence. Beyond a given confidence I can merge the two nodes into DG3.

The issue that I'm having is, let's consider two sets of nodes in each of DG1 and DG2 such that:

DG1,N1 -> DG1,N2 (Node1 of Disconnected Graph 1 connects to Node2 of Disconnected Graph 1)

DG2,N1 -> DG2,N2

When trying to determine if DG1,N1 and DG2,N1 are similar, I need to take into account their connections. If DG1,N2 and DG2,N2 are to be merged (or similar enough), then that makes it more likely that DG1,N1 and DG2,N1 are similar. If DG1,N2 and DG2,N2 are not similar, then it makes it less likely that DG1,N1 and DG2,N1 are similar.

If this is the only connection it's relatively trivial. If the kernel is a function the ratio of the sum the similarities for each property in each node to the sum of all properties in both nodes, then I can just add the resulting value of kernel(<DG1,N2> ,<DG2,N2>) (where '1' would be the result if they are identical).

The problem that I have is (and I bet this is a common one), what to do with cycles? In this instance, where:

DG1,N2 -> DG1,N1

DG2,N2 -> DG2,N1

I've considered simply ignoring the edges (subtracting the value both from the sum of similarities and sum of every property), calculating a similarity, putting this value into the kernel and re-applying. This sounds to me like it could be represented as something similar to a Markov chain, in which I continually reapply this method to itself until it converges.

So I guess my question boils down to: Is there a way of determining a convergent probability that two nodes are similar? Is there a simple way this can be represented/calculated, possibly by something similar to a Markov chain?


texts: Lazy lists with call-by-value reduction strategy

texts:
I am currently writing lists with lazy semantics in the pure
lambda-calculus with call-by-value reduction strategy.

I tried to construct pleasant to use and relatively efficient "lazy" functions on lists. As in the Church encoding I identify list with its right fold function, but with some differences. Here is nil and cons:

nil       = \_ _ z. z
cons x xs = \_ f z. f (\_. x) (\f' _. force xs f' z)

This representation of cons gives a simple way to get the tail of a list, which is O(1):

tail xs = \_ f z. force xs (\_ r. force (r f)) z

You just discard the first argument of f in cons and force the second after applying it to function f, which the tail function receives. But it brings some problems with foldr. Consider

cons (s z) (cons (s (s z)) nil)

After call-by-value and full beta-reduction (it reduces a term to a readable form) it becomes

\_ f z. f (\_ s z. s z) (\f' _. f' (\_ s z. s (s z)) (\'f' _. z))

To fold this term with one function, e.g. plus, you need to wrap and replicate it a little:

(\x r. plus (force x) (force (r
(\x r. plus (force x) (force (r _))))))

'_' means "there is no difference, what term to choose". Then you add a default value z and after call-by-value and full beta-reduction the whole term

force (cons (s z) (cons (s (s z)) nil))
    (\x r. plus (force x) (force (r
    (\x r. plus (force x) (force (r _)))))) z

reduces to

\s z. s (s (s z))

foldr is the generalization of this idea and defined as

foldr f z xs = force xs (fix (\rec x r. f x (r rec))) z

For example

sum = foldr (\x r. plus (force x) (force r) z

"Wrapping and replicating" is defined by fix, which is Z-combinator:

fix f = (\x. f (\y. x x y)) (\x. f (\y. x x y))

Having the head and tail functions it's easy to define take:

take = fix (\take n xs. if (eq0 n) nil (ifNullNil xs
    (\xs. consC (\_. head xs) (take (pred n) (tail xs)))))

ifNullNil returns nil, if the null function (an emptiness test) returns true for its first argument, or applies the second to the first and wraps the result into the thunk otherwise:

ifNull    = \xs z f. if (null xs) z (\_. force (f xs))
ifNullNil = \xs. ifNull xs nil

consC receives a thunk instead of a value and defined as

consC = \x xs _ f z. f x (\f' _. force xs f' z);

Finally you can define infinite lists:

nats = fix (\rec n _. force (cons n (rec (s n)))) z

And compose them with usual functions on lists:

sum (take (s (s (s z))) (cons (s (s (s z))) nats))

It reduces to

\s z. s (s (s (s z)))

and equals to Haskell's

sum $ take 3 $ 3:[0..] -- 3 + 0 + 1 + 0 = 4

Edit2

You need an extra '_' in the arguments of cons because it allows you to compose ordinary functions with functions, that generate infinite lists. Consider

nats = fix (\rec n _. force (cons n (rec (s n)))) z

It reduces to

nats = \_. force (cons z (fix (\rec n _. force (cons n (rec (s n)))) (s z)))

So list, which cons receives, should be "forceable". So list, which cons produces, should be "forceable" too, because you want to compose conses.

So my question is: are there some sources, from where I can learn more about such a representation or a better representations, that allow you to write programms with lazy semantics in languages with eager evaluation, especially in the pure lambda-calculus?


texts:
The vertex of a binary tree is called an single child if it has a father's vertex but does not have a neighbor.
The root is not considered an single child.
let mark in  numOnly  a number of vertices in T that hold the attribute "single son ", and ‘with n we mark the total number of vertices in the T tree.
i need to prove that every non-empty AVL tree has inequality  $\frac{numOnly}{n}\leq \frac{1}{2}$


texts:
Is there any way to model the big M method for continuous variables?
Something similar to this but $B, C \in \mathbb{R}_{\geq 0}$ and $A\in\{0,1\}$.

Due to the precision problem, when the $B$ and $C$ are close I do not get the correct answer.

Let $p_{i,j} \in \mathbb{R}_{\geq 0}$, for $i=1,\dots, n, j=1, \dots, m$. As one of the constraints of my problem, I am looking for $h$ such that
$$
  g_i(h) := \sum_{j=1}^h p_{i,j} < 1.
$$
To find $h$, I defined  $a_{i,j} \in \{0,1\}$  such that
$$
a_{i,h} =
\begin{cases}
1 \qquad \text{if } g_i(h) < 1 \quad h=1, \dots, m, \\
0 \qquad \text{otherwise}.
\end{cases}
$$

To implement the if condition above, I used the big-M method, but the problem is that the big-M method works well for ILPs while the variable, here $p$, is non-integer.
When $g_i(h)$ is very close to 1 but not absolutely 1 due to the precision of the number, say $ g_i(h)=1-10^{-16}$, then $g_i(h)$ which actually is 1 will not be assumed as 1 by the program, and the program does not return the correct value for $h$.
I was wondering if there is a trick for this issue.


texts: Question about let syntax in type systems

texts:
I'm on the Wikipedia page for Hindley-Milner type systems, on the section about "let polymorphism": https://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_system#Let-polymorphism

I'm a bit confused on this sentence:

  Ideally, this would be allowed with any use of a bound variable

What does that mean exactly? I'm not following the syntax in this section.

Thanks!


texts: Showing that all vertex degrees in MSTs of Euclidian graphs are in O(1)

texts:
There is a finite set of points $S$ in the plane with $ |S| = n$. MST is the minimal spanning tree of S. "Minimal" here refers to the Euclidean distance between the points of $S$, so the MST is the minimum spanning tree with the lowest overall distance.

I want to prove that the degree of every node is in O(1).

I tried to use Euler's Theorem but unfortunately this did not lead to a solution. Any ideas?


texts: Checking acceptance of a word vs finding an accepted word

texts:
We know that checking whether some word w is accepted by a turing machine TM is undecidable. But what about the problem of finding one accepting word of a TM?

Are these two problems related in some way, i.e. undecidability of one implies the undecidability of other (in any structure, like FA, LBA, PDA etc)?

My hunch is that they are not related but I am not able to argue why?


texts: Is ambiguity in Programming Language always bad?

texts:
Suppose we have a token and our language allows the compiler to build two different derivation trees. However, it can happen that there exists two semantic ways to interpret our token. So ambiguity is not a problem in this case.
Am I correct?


texts: Is intersection used in regular expression?

texts: As union is part of regular expression in form of positive closure, similarly intersection is also a part of regular expression? in which form it can be used?


texts:
The natural grammar for dangling "else" is ambiguous.
But there exists an unambiguous version of the grammar that links the "else" to last uncompleted "if" statement.
Is this version also deterministic?
Is this language deterministic?

Natural grammar (ambiguous):
$$
S \rightarrow if~expr~S | if~expr~S~else~S | cmd
$$

Unambiguous grammar:
$$\begin{align*}
S &\rightarrow U~|~F\\
U &\rightarrow if~expr~S~|~if~expr~F~else~U\\
F &\rightarrow if~expr~F~else~F~|~cmd
\end{align*}$$


texts: Are there more languages than functions?

texts:
My gut says "no", but I don't know why.

For any function $f$ over strings on an alphabet, one can define a language in which every word is just the concatenation of a string $s$, a delimiter, and $f(s)$, or the empty string if $f(s)$ is undefined.  So there at least as many languages as functions.  How can we define a function for every language?  (Forgive my ignorance about languages, automata, etc.  I have not studied in that area.  Perhaps my question is poorly constrained.)


texts: Finding dimensions of a point cloud - floating point issues

texts:
I have $N$ data points of some dimension $D$.

I want to know the dimension of the shape that those data points represent - for instance they might be a 2 dimensional triangle, even though they are in 8 dimensional space.

A way of doing this mathematically is to pick one of the points and subtract it from all of the other points to get $N-1$ vectors.

If i make these vectors into a matrix, the rank of the matrix will tell me the dimension of the shape of the data points.

The problem though is that implementing this using floating point math, not all vectors will cancel out that should.

I was wondering, is there a better way to do this when using floating point math?  Or, is there a way to get a thickness in each dimension so that very thin dimensions can be ignored?


texts: The sorting problem for partially ordered sets

texts:
I have two questions about sorting for posets, one easy and one hard:

Easy: Suppose we have a set of objects and a partial order. Given any two objects such that $a \leq b$, we want to delete $b$ from the set. Is there a sub-quadratic time algorithm that can accomplish this, perhaps for some suitable data structure?

Hard: suppose we actually want to sort the list by putting it into some suitable data structure (such as a directed graph). Does there exist a nice data structure leading to a sub-quadratic time sorting?

The second is the natural generalization of the sorting problem to posets. The first is an easier variant that will suffice for this application.


texts: what is the defintion and aim of "inductive bias"?

texts:
I am newbie in Machine learning.
As we know, in machine learning the aim of an algorithm is to find out (approximate) the output from some examples as training example. these training examples help the algorithm to predict the output of other examples which have not occurred yet. According to Wikipedia, we need "inductive bias" by which we can be assured the algorithm can approximate the output correctly. But the thing is I am not sure that I catch the concept. does "inductive bias" mean we add another examples to our training set or we delimit the training examples? any precise explanation is appreciated.


texts:
There is a problem I don't know the answer too.
The 3 approximation for the bottleneck TSP that involves first getting the MST.
I have not been able to come up with the right "shortcut" method so far.

To be more specific.

The problem comes from Cormen's Introduction to Algorithms 3rd edition . The problem is

  In the bottleneck traveling-salesman problem, we wish to find the hamiltonian cycle that minimizes the cost of the most costly edge in the cycle. Assuming that the cost function satisfies the triangle inequality, show that there exists a polynomial time approximation algorithm with approximation ratio 3 for this problem. (Hint:Show recursively that we can visit all the nodes in a bottleneck spanning tree, as discussed in Problem 23-3, exactly once by taking a full walk of the tree and skipping nodes, but without skipping more than two consecutive intermediate nodes. Show that the costliest edge in a bottleneck spanning tree has a cost that is at most the cost of the costliest edge in a bottleneck hamiltonian cycle.)

I can prove that the MST is also a bottleneck spanning tree, however when I search online and Google scholar for the step where we walk on the bottleneck spanning tree, all of the articles are on much better approximations, and I can't seem to find any reference to this type of argument online.


texts:
In the book Reinforcement Learning An Introduction，Chapter 8.5，there is an example that compares the efficiency of expected and sample updates:

According to the author, "In this case, sample updates reduce the error
according to $\sqrt{\frac{b-1}{bt}}$ where $t$ is the number of sample updates that have been performed (assuming sample averages, i.e., $\alpha = \frac{1}{t}$."
I just wonder how to  compute the sample-update error(i.e.,How to get the formula $\sqrt{\frac{b-1}{bt}}$?


texts: Fenwick Tree Traversal using Binary value of Index

texts:
Can someone explain me how do I execute sum query from Index 0 to Index I given the binary value of that Index I. There are some trivial question that I want to know :

Do we have to remove last set bit and all the bits following it.
How many times do I have to access the temporary array made for the data structure i.e Fenwicktree[ ] array.
I have been trying to think about these from the binary index of the Index I.

For eg I have the binary

  001100100100100011

I removed the last set bit. I took 0 as left and 1 as right and traverse it . Whenever I take a right , I access the tree elements and accessing the array finally when I reach the node.So the count comes around  around 6 times.
But when I did the same with

  1000110111011101100

The answer comes out to be 10 but the the number of times I access the array is 12. How do I get to this ? What am I missing out ? Is there a general way to calculate the number of times just looking at the binary value of Index ? Please help me out.


texts: How is the following ML Curry expression evaluated

texts:
This question is not homework but it's related to material in a general course I take about programming languages, so I don't know whats the site policy about this

In ML the following expression:

fun f x y z = x (y , z) = x (z, y) ;

Evaluates to this:

val ('a, ''b) f = fn : ('a * 'a -> ''b) -> 'a -> 'a -> bool

I understand the type inference done here, but not the structure of the expression returned.

Can someone explain how this works ?

Thanks


texts: Which of these two functions has a higher order of growth/complexity?

texts:
Consider the following functions:
$$f(n)=2^{\log^*n} \text{ and } g(n)=\sqrt{2}^{\log{n}}$$
Using $\log{}$ properties I think that $g(n) < f(n)$, since:

$f(n)\sim n$,
$g(n)\sim n^{\frac{1}{2}}$, and
$n^{\frac{1}{2}}<n$.

However the book that I'm reading says otherwise.
What have I gotten wrong?


texts:
I know that if a language class is closed under operation X then the problem  is decidable.

for eg: "Intersection of two CSL is CSL"? this problem is decidable because it is already proved that CSL follow intersection closure property.

But what if language is not closed under the operation.
for eg: problem: Is intersection of two CFL is CFL or not?

as CFL/DCFL is not closed under intersection. then is this true saying that not following closure opertion implies Undecidable problem?

My approach:This problem is same as saying that "A given CSL is CFL or not?" because intersection of two CFL's is CSL for sure. as every CSL is RE then can we also say this problem as "A RE is CFL or not"? if my last statement is true then by using rice theorem this problem must be undecidable and even not RE.

how to approach these type of question when a language is not closed under the given operation?