texts:
I'm trying to understand the NFA and $\epsilon$ moves logic.
Let's say there is an NFA $A$ with $\epsilon$ moves,
if $\epsilon ∈ L(A)$ then $q_0 \in F$? and vice versa? If $\epsilon \in L(A)$ then $q_0 \in F$?
How can I prove it?


texts: $(\log n)^{\log n}$ lower-bound and upper-bound

texts: we know that $n \geq \log{n}$ however I understand that $(\log n)^{\log n}$ grows faster than $n$. I have been trying to prove this however I can't seem to figure it out.


texts: Problem with understanding Multi-party security circuit for secure stable matching

texts:
I am reading the following paper:
MPCircuits: Optimized Circuit Generation for Secure Multi-Party Computation

Paper Link

I have following question:

We have two groups shown in the circuit. Why we call it a multi-party circuit?

Paper provides a comparison of its multi-part technique with the old 2 part based technique:

  In secure stable matching, the match list is computed while keeping
  the  preference lists private to their respective owners. This problem
  has  been studied in the recent literature [21], [22] where the secure
  stable matching problem is reduced to a two-party secure computation
  scenario. Each individual XOR shares her preference list and sends it
  to two non-colluding servers who perform the secure computation.
  However, stable matching is inherently a multi-party problem and the
  assumption of two non-colluding servers may not be feasible in
  practice. To the best of our knowledge, we provide the first solution
  for multi-party secure stable matching.

The attached figure shows only how to input the preference list of group#1 and group#2. How can we perform n*n computation using the figure?
 Somebody please guide me. Zulfi.


texts: Algorithm to find a all valid matrix permutations

texts:
I have an array of $N^2$ numbers like $ a = \{ a_1,a_2, ..., a_{N^2} \}$ where all $a_i < F$ where $F$ is a fixed number.

I am looking for all permutations where if I put values in $A$ in order (i.e. fill the matrix row by row) in a $N \times N$ matrix $A_{N \times N}$ where sum of all columns and all rows are equal to $F$.

$$
A = \begin{pmatrix}
a_1 & a_2 & ... & a_N\\
a_{N+1} & a_{N+2} & ...  & a_{2N}\\
... & ... & ... & ...\\
a_{N^2-N+1} & a_{N^2-N+2} & ...  & a_{N^2}
\end{pmatrix}
$$

There is a straight forward algorithm to find all permutations of $a$ in $O(N^2!)$ and check if sum of all rows and columns are equal to $F$.


texts: Why doesn't everyone use distributed operating systems?

texts:
As requested by a moderator, this question as been separated from my question about microkernel-based operating systems.

In the 1980's, the team that developed C and Unix developed a distributed operating system Plan 9 from Bell Labs. Its descendant Inferno is still with us. Given its impeccable pedigree, the fact that Unix's own creators agree it is better, and the fact that the are accustomed to ideas such as that of a virtual machine today, one would have expected such operating systems to have replaced Linux, Windows, and so on. But this hasn't happened.

Wikipedia cites several opinions as to the probably reasons for the failure of Plan 9, including Eric Raymond's:

  It looks like Plan 9 failed simply because it fell short of being a compelling enough improvement on Unix to displace its ancestor. Compared to Plan 9, Unix creaks and clanks and has obvious rust spots, but it gets the job done well enough to hold its position. There is a lesson here for ambitious system architects: the most dangerous enemy of a better solution is an existing codebase that is just good enough.

However, to choose one pet example, in another domain, platforms such as lichess prove that a new upstart platform (in lichess's case a chess platform) can displace established platforms if it offers a compelling enough advantage in terms of a user-friendly experience.

So I would like to ask, why has the world not switched over to Inferno? What, in fact, prevents the world from migrating to distributed OS's, particularly given that virtual machines, multiple CPUs, etc. are commonplace? Is there a "hard barrier" that Inferno has not crossed in terms of its capabilities?


texts: What does it mean when saying "we want $\Lambda$ to be $\tilde{O}(1)$ as a function of $M$"? (it appears on the top of page 12 of this paper)


texts: Is the language of Turing Machines that halt on every input recognizable?

texts:
I  am trying to reduce the complement of the HALTING problem (WLOG, the complement of the HALTING problem is the language of TMs that loop on some string w)to this language in order to show that it is not recognizable. Does anyone know how to do this reduction, what I come up with is:

Using python-like syntax:

def R(<M>,w):
    def F(x):
        if M(w)loops: //Run M on w
            return True on every x
        else
            loop on every x
return F

Of course the problem here is that we can't really know when M loops on w

Does anyone know how to do this reduction, or if it is possible to prove that the language of TMs that accept every input string is unrecognizable using a reduction from a different unrecognizable language?


texts: Collisions of prefixes of MD5 hashes in some fixed interval

texts:
I was wondering, if there is an MD5 hash collision in the UNSIGNED MEDIUMINT Range (0 - 16777215). Sadly, I'm unable to run a script to check this myself, due to Memory (RAM) limitations. The answer is probably no; the next step would be - how many characters are even needed, until the first collision is found?

An MD5 hash has 32 Characters. If you only would use, lets say, the first nine characters from all MD5 hashes in the MEDIUMINT range, would they still all be unique?

The reason behind this: I'm trying to find a simple way to basically use an MD5 hash for every number in the MEDIUMINT range, to create a short, unique string, preferably not longer than 9 letters -- as abstraction to the actual number (so instead of an 1, you get something like c4ca4238a)

Are the first nine characters of all MD5 hashes in the UNSIGNED MEDIUMINT (whitout 0) range unique?


texts: How to find the maximum size of a B+ tree?

texts:
I came across this paper (page 16) which explains how to calculate the size of B+ trees.

According to it the maximum number of nodes at level $i$ is $2(n/2)^{i-1}$ for a B+ tree of order $n$. Thus a B+ tree of $l$ levels will contain at most $\sum_{i=0}^{l} 2(n/2)^{i-1}$ nodes (*).

But we also know that for example for a B+ tree which stores $N$ records there're at most $\frac{N}{\lceil n/2 \rceil-1}$ leaves (**).

The height of a B+ tree can be calculated by this formula: $\lceil \log_{\lceil n/2 \rceil}N \rceil$.

But then the formulas * and ** contradict each other. For example a B+ tree has $1024$ records and is of order $16$. The depth of the tree will be $4$.

According to ** there're at most $146$ leaves in the tree.

But according to * there're at most $2\cdot 8^3=1024$ nodes at level $4$ which is where the leaves are.

Please help me understand where this contradiction is coming from and what is the correct way to calculate the max size of B+ tree.


texts:
Consider this implementation of the Bakery Lock:

integer array[0..n-1] label = [0,...,0]
boolean array[0..n-1] flag = [false, ..., false]

lock(me):
  flag[me] = true;
  label[me] = max(label[0], ... , label[n-1]) + 1;
  while (∃k ≠ me: flag[k] && (k,label[k]) <l (me, label[me])) {};

unlock(me):
  flag[me] = false;

If we suppose that every thread calculated a unique label, we can say that the lock is fair: the first threads to enter get a lower label. That means that these threads get prioritised when trying to acquiring the lock.

But what if we have a large n and 10000 threads calculating their label? It is certain that some threads will end up with the same label. In that case we order the processes with their hash or id, which does not prioritise the processes which entered the lock  first.

Is the Bakery Lock still considered fair?


texts:
I am trying to write a program to recognize if a given lambda calculus expression is primitive recursive. I believe that a general algorithm to do this does not exist, but I am interested in the most general algorithm. This is a subset of the primitive recursive functions in the LC.

Primitive recursion is built up from the following rules: "http://safalra.com/lambda-calculus/partial-recursive-functions"

To outline some of these rules

(λfx. x) is zero
(λnfx. f (n f x)) is successor
etc...

Now in my program I can just recognize these axioms directly. My confusion is what happens when I get to things derived from them. Take the number 5 for example encoded as (λs.(λz.(s (s (s (s (s z))))))). This is the result of applying the the successor function to zero 5 times. But the above expression is not one of the axioms. I believe that the rule set says that the result of primitive recursive functions are also primitive recursive, but I do not see how given one of these results the result can be shown primitive recursive.

What I mean is that given just the encoding of the number 5 how can I show that it is primitive recursive? That is without brute force search building up from the axioms. Also is my method of representing the primitive recursion axioms correct (for suc and zero) or are the axioms not that literal? Thanks!


texts: How to convert recursive language grammar tree into automaton for optimal parsing?

texts:
So I have a definition of a sort of grammar for a programming language. Some aspects are recursive (like nesting function definitions), other parts of it are just simple non-recursive trees.
Originally I just treat this sort of like a Parsing Expression Grammar (PEG), and parse it using recursive descent. But this is kind of inefficient, as it sometimes has to build up objects as it's parsing, only to find 10 calls down the road that it isn't a good match. So then it backs up and has to try the next pattern.
I'm wondering what the general solution to this is. What can be done to create the most optimal algorithm starting from nothing but a tree-like data structure encoding the grammar?
Can you process the tree-like, recursive-ish BNF PEG data structure in a while loop, rather than using recursive descent? Better still, can you convert the data structure into a sort of automaton which you can (in some simple way) transition through, to parse the string without having to go down a bunch of wrong paths and generate stuff you only have to soon throw away if you find it's a mismatch? Or if not, is there anything that can be done here with automata?
Sorry for my terminology (BNF vs. PEG), I am not using it exactly. I just mean I have a grammar, which is context-sensitive which falls outside the scope of either of these. So I am picking one or the other to simplify this question for the purpose of this site, even though I'm not 100% sure what the difference between BNF and PEG are at this point.


texts: $L = \{a^{n^3} | \ge 0\}$ Use the Pumping Lemma to show that L is not regular

texts:
Use the Pumping Lemma to show that $L$ is not regular:
$$ L = \{{a^{n^3} | \ge 0}\}$$

I feel like I have a good intuition of what the Pumping Lemma states; strings that belong to a regular language have a part or parts that repeat over and over again.

Example strings:
$a^{0^3} = a^0 = $ "" ($\epsilon$)
$a^{1^3} = a^1 = $ "a"
$a^{2^3} = a^8 = $ "aaaaaaaa"
$a^{3^3} = a^{27} = $ "aaaaaaaaaaaaaaaaaaaaaaaaaaa"

I understand that this proof is done via contradiction, and looking at the examples it becomes obvious that constructing a DFA is difficult. But how do I prove that's impossible?!


texts: Is there any practical application for arrays that contain themselves?

texts:
I'm reading the introduction to Godel, Escher, Bach and and there's heavy discussion of mathematical sets which contain themselves. Being a far better programmer than mathematician, I put it into terms I'm more comfortable with and started to think about arrays which contain/reference themselves.

I know that recursion is a very powerful concept in CS but that it's typically manifested through functions which call themselves. I see recursive functions in algorithms all the time, but I've never before run across an array that has itself as an element. I was just wondering if there's any particular "usefulness" or practical application for arrays which contain themselves (as there is for functions which call themselves).


texts:
Problem statement
Let $K$ be a set of keys with $|K| = n$ and define the index set $I = \{0, \ldots, m-1\}$. Now let $H = \{h \mid h : K \to I\}$, i.e. $H$ contains all hash functions which map the keys from $K$ to the set $\{0, \ldots, m-1\}$.
Prove or disprove that $H$ is universal.
Attempt
Reiterating the definition

A family of hash functions $H$ is universal if and only if for $\forall x, y \in K, (x \neq y)$ we have
$\left|\{h \in H : h(x) = h(y)\}\right| = \frac{|H|}{m}$

I know you can construct specific families of universal hash functions and there are families which aren't universal. But if you consider all of them how would you know which part would outweigh which to decide if this statement still holds?
I'm probably going the wrong way so I would appreciate any help or hints!


texts: Given price and number of pages of each book, What is the maximum number of pages you can buy?

texts:
You are in a book shop which sells n different books. You know the price and number of pages of each book.

You have decided that the total price of your purchases will be at most x. What is the maximum number of pages you can buy? You can buy each book at most once.

Example:

In:
4 10
4 8 5 3  //price
5 12 8 1 //pages
Out:
13
Explaination: You can buy books 1 and 3. Their price is 4+5=9 and the number of pages is 5+8=13

This is my recursive approach :

f(i,j) is max pages, when you can afford i units of money and j is the index in vector uptill the jth book. ie 0 to jth books are considered.

f(x, 0)=max( f(x-price[indx], indx+1) + pages[indx], f(x,indx+1) );

I am having difficulty making the base case, what should be the base case?

Thank you.


texts:
I am interested in procedures for fair division of land (i.e. envy-free division, or at least proportional division).

In contrast to the well-studied cake-division problem, land-division is two-dimensional, i.e., the preferences of the users may vary both horizontally and vertically. Therefore, it is not practical to limit the algorithm to parallel cuts.

The only reference I found so far is Karthik Iyer and Michael Huhns, 2007. They say that "We have not come across any constructive (algorithmic) solutions so far to the generic land division problem. All the papers have
offered existential solutions to qualified versions of the problem."

They themselves prove an O(n^2) algorithm for proportional land division, with certain limitations (e.g. each of the n agents must mark n rectangular regions with utility 1/n, and if the rectangles don't overlap too much, the algorithm guarantees that each agent gets one of its rectangles).

Do you know of any newer references on this problem? I am interested specifically in practical algorithms, and they may be approximate.


texts: Why MIT lecture breadth-first search algorithm is so complicated?

texts:
I watched a video for BFS from MIT and the algorithm the lecturer presented was really complicated compared to what I came up. My solution seems to work fine and walk through the vertices in the correct order. Am I missing something?

public static void BFS(GraphNode currentNode, GraphNode searchedNode) {
    if (currentNode.index == searchedNode.index) {
        System.out.println("Found!");
        return;
    }

    if (visited[currentNode.index]) {
        return;
    }

    visited[currentNode.index] = true;

    for (GraphNode child : currentNode.children) {
        if (!visited[child.index]) {
            nodeQueue.add(child);
        }
    }

    if (!nodeQueue.isEmpty()) {
        BFS(nodeQueue.poll(), searchedNode);
    }
}

One drawback is that it keeps running after finding a node, but that could be fixed easily by clearing the queue when element is found.


texts:
We know that if $B$ is in $P$ and if $A \leq_p B$ then $A$ is in $P$ too.

If $B$ is in $SPACE(n^2)$ and $A \leq_p  B$ then so $A$ will be in $SPACE(n^2)$?

I think that the answer to this question is true, because if $A\in P$ then $A \in PSPACE$, and then $A$ could be in $SPACE(n^2)$. I doubt my answer because of that $(n^2)$.


texts: What does it mean "given a NFA and its accepted language L build the DFA that accepts L*"?

texts: Supposing we have either a NFA or a DFA with accepted language $L$, what is $L^*$? And how can I build an automaton that accepts it?


texts: Shifting deletion algorithm for linear-probing hash table

texts:
I'm looking for the algorithm for deleting an element from a linear-probing hash table that does a delete-and-shift instead of just using tombstone elements.

The basic idea is quite simple - but I keep getting caught up in corner cases (notably, w.r.t. "wraparound", where an element hashes to a high slot but all the end slots are full so the index it is actually inserted at is low.)

Basic idea:

When you delete an element, keep track of the slot and start scanning forwards. If you hit an element that's null (read: not present), you're done. Otherwise, if you hit an element that hashes to a slot <= the slot kept track of, move that element to the kept-track-of slot, and keep track of the current slot instead.

Or in pseudocode:

func del(item i):
    slot s = get_slot_of(i)
    table[s] = null
    fixup(s)
func fixup(slot s):
    assert table[s] == null
    slot t = s
    while table[++t] != null:
        if get_slot_of(table[t]) <= s:
            table[s] = table[t]
            table[t] = null
            s = t

In simple cases, this works. But as soon as you include the modulo behavior, it falls flat on its face.

So how would I go about fixing this up such that it doesn't fall flat on its face in such cases? I looked around, but couldn't find this algorithm implemented anywhere - it seems like most places that use linear probing just use tombstone elements instead.


texts: How to write negation of an 'AND' statement in logic

texts:
Suppose the given proposition is:
"Zach blocks emails and texts from Jennifer"

Where,
P implies "Zach blocks emails from Jennifer".
Q implies "Zach blocks texts from Jennifer".

So it's P AND Q in logic.

Now we want to find its negation. So what I found as it's negation is:
"Zach does not block emails from Jennifer, or Zach does not block texts from Jennifer "

Now it is !P OR !Q which I can understand to be true since !(P AND Q) is equivalent to !P OR !Q.

But what if I write it as:
1. "Zach does not block emails and texts from Jennifer".
2. "It is not the case that Zach blocks the emails and texts from Jennifer".

What really confuses me is the statement 1 and 2  seems more like !P AND Q.

But then what I think !P AND Q can be more accurately written as:
3. "Zach does not block emails from Jennifer, and Zach block texts from Jennifer."
4. "It's not the case that Zach blocks the  emails from Jennifer, and Zach blocks the  texts from Jennifer."

Now my question are:
A. What is more accurate way to write !(P AND Q)?
B. Can it be written as statement 1 and 2?


texts: How to produce a context free grammar for this language?

texts:
I've already attempted it but I am finding it difficult to understand if this is correct.

give a context free grammar for the following:

$$ \{p^{3m+n}q^nr^2p^m\mid m,n\ge 0 \}$$

The answer i've attempted is:
$S \to XY$
$X \to pppXp \mid \ q$
$Y \to qYr \mid \epsilon$

I've been trying to understand if i need to break down:
$$ \{p^{3+m+n} \}$$ in to

$$ \{p^{3}p^m p^n \}$$

to give me: pppXp

then q and r would value to

qYr | $\epsilon$


texts: Proof that "local" minimum spanning tree is "global" minimum spanning tree

texts:
I'm trying to understand a proof from the book "Graph Theory with Application to Engineering & Computer Science" by Narsingh Deo.
The chapter is about trees in non oriented graphs.
A bit of terminology so that you can understand the theorem and the beginning of the proof from the book:
The author calls minimum spanning trees, shortest spanning trees.
The author calls a branch of a spanning tree any edge of the tree.
A chord of a spanning tree is any edge of the underlying graph that is not in the tree.
A fundamental circuit associated to a spanning tree is a circuit formed by adding one of its chords to a spanning tree (for the author a "circuit" is a closed path, there is no repetition of vertices, it's what most other sources I've read call a cycle). So, a fundamental circuit associated to a spanning tree is a actually a cycle formed by adding one of its chords to a spanning tree.
The distance between two spanning trees $S$ and $T$ of the same graph is (regarding $S$ and $T$ as sets of edges), is $|S\setminus T|$ (which happens to be equal to $|T\setminus S|$).
There's a step in the proof of Theorem 3-16 that I don't understand.
Theorem 3-16:
A spanning tree T (of a given weighted connected Graph G) is a shortest spanning tree (of G) if and only if there exists no other spanning tree (of G) at a distance of one from T whose weight  is smaller than that of T
Proof:
Let $T_1$ be a spanning tree in G satisfying the hypothesis of the theorem (i.e. there is no spanning tree at a distance of one from $T_1$ which is shorter than $T_1$). The proof will be completed by showing that if $T_2$ is a shortest spanning tree (different from $T_1$) in G, the weight of $T_1$ will also be equal to that of $T_2$. Let $T_2$ be a shortest spanning tree in G. Clearly, $T_2$ must also satisfy the hypothesis of the theorem (otherwise there will be a spanning tree shorter than $T_2$ at a distance of one from $T_2$, violating the assumption that $T_2$ is shortest).
Consider an edge $e$ in $T_2$ which is not in $T_1$. Adding $e$ to $T_1$ forms a fundamental circuit with branches in $T_1$. Some, but not all, of the branches in $T_1$ that form the fundamental circuit with $e$ may also be in $T_2$; each of these branches in $T_1$ has a weight smaller than or equal to that of $e$, because of the assumption on $T_1$. Amongst all those edges in this circuit which are not in $T_2$ at least one, say $b_j$, must form some fundamental circuit (with respect to $T_2$) containing $e$.
I'm stuck at the last sentence I just quoted:
"Amongst all those edges in this circuit which are not in $T_2$ at least one, say $b_j$, must form some fundamental circuit (with respect to $T_2$) containing $e$."
I don't see why among those cycles, there should necessarily be one that contains $e$. Why is that?


texts: Finding A String Using A Suffix Array/Table

texts: Is it possible to find out a string only having its corresponding suffix array/table and knowing that the string contains only, for instance, letters "f", "g", "r"? If so, how is that possible?


texts: I read about post-selection and didn't understand the meaning behind this thing. I didn't understand the Wikipedia article well, so what is a simple but understandable explanation of post-selection and how to use it in complexity?


texts: How do you prove these string/number radix encoding/decoding algorithms work?

texts:
A while back I learned of these great algorithms:
function parseInt(value, code) {
  let x = 0
  let i = 0
  while (i < value.length) {
    const a = value[i]
    x = x * code.length + code.indexOf(a)
    i++
  }
  return x
}

function toString(value, code) {
  const radix = code.length
  let result = ''

  do {
    const digit = value % radix
    result = code[digit] + result
    value = Math.floor(value / radix)
  } while (value)

  return result
}

which allow you to convert toString any (albeit 32-bit) number to a string using a custom "alphabet" or "code", and do the reverse and parse a corresponding string to int.
console.log(parseInt('dj', 'abcdefghijklmnopqrstuvwxyz0123456789+-'));
// 123
console.log(toString(123, 'abcdefghijklmnopqrstuvwxyz0123456789+-'));
// dj
console.log(parseInt('a', 'abcdefghijklmnopqrstuvwxyz0123456789+-'));
// 0
console.log(toString(0, 'abcdefghijklmnopqrstuvwxyz0123456789+-'));
// a

How do you prove that these algorithms actually do the trick? What does the proof look like from base principles? Tangent/bonus: How would you ever go about figuring this out from scratch? To me this is pure magic and I would never have been able to figure this out "from scratch". I would like to know what I could've done to figure this out using mathematical techniques/principles.


texts:
This is a pretty naive question, but I would like to better understand the basics of information storage on a computer.  I am not concerned with the detail of how any one operating system achieves this.

I know there are different ways to identify which bits in memory make up a given file (on a given machine at a given time) as revealed in the difference between "Size" and "Size on disk" in the properties of a file.  Windows File Explorer currently says one of my files has Size 14.0 KB (14,415 bytes) and Size on disk 16.0 KB (16,384 bytes)  Each is correct but they measure somewhat different things.

Here are my two core questions:  Is it fair to say that a 14,415 byte file can be interpreted as a binary number with roughly  115,320 binary digits (8 times 14,415)?  And is it likely that the same file transferred to another machine would be placed in storage a little differently so that it would be a different binary number? Or is that just way off track?

I will not ask more now since comments may help me to clarify the question in ways I would not think of myself.


texts: How to determine if this problem is decidable?

texts:
I am currently stuck on the following problem:

Given a WHILE-program P and the knowledge that all input variales are set to 0, is it decidable if a specific instruction is reached 1000 times?

My intuition is that it is not decidable. Rice's theorem says that a non-trivial property of a program is always undicidable. But I am not sure if "a specific instruction is reached x times" even qualifies as a "property of a program".

I am stuck on this for a while now, so I hope someone can give a hint where to look to find an answer to this problem. Thank you so much! All help is greatly apprechiated.


texts: How does this last step in Shor's algorithm work?

texts:
Page 854 of The Nature of Computation states the following (This discussion has made the simplifying assumption that $M/r$ is an integer):

  If each of the observations gives us a random harmonic, how long does it take to learn the fundamental frequency? Suppose we observe the frequencies $k_1 = b_1 M/r$, $k_2 = b_2 M/r$, and so on. As soon as the $b_i$ are relatively prime, i.e., $\gcd(b_1, b_2,...) = 1$, then $\gcd(k_1, k_2,...) = M/r$. With constant probability even the first two observations suffice, since as Problem 10.26 shows, $b_1$ and $b_2$ are mutually prime with probability $6/\pi^2$ when $r$ is large. Thus we can determine $M/r$ from a constant number of observations on average, and we simply divide $M$ by $M/r$ to obtain $r$.

But how can we figure out that we've reached the point that the $b_i$ are mutually prime? This procedure reads to me as if there was a deterministic way of detecting that and it was only the number of necessary observations that was random.


texts:
1D Pink noise, is easy enough to generate. See https://www.dsprelated.com/showarticle/908.php for example.

What about higher-dimensional pink noise, such as 2D or 3D pink noise? Is there an algorithm to generate that?

EDIT: One approach might be to simulate a natural process, since pink noise often arises in nature.


texts:
What is the power of a Turing-machine that cannot write?

So it can still read and go back and forth on the tape, but it cannot write.

I am wondering what this would be equivalent to in the computational hierarchy.

I suppose this would be a finite-state automaton, but it can go left and right along the input: does that increase its powers?


texts:
It is common to define $P$-completeness with respect to logspace many-one reductions. I am looking for a complexity class $C$ such that if $C=P$ then all problems in $P$ are $P$-complete under many-one $C$-reductions.

  What is the weakest many-one reduction (computable in class $C$) for which the class of P-complete problems remains unchanged?

Note that $C$ is contained in $P$.


texts: Number of possible programs in a language

texts: Is the number of possible programs usually finite or infinite? I'm playing with the idea of generating all possible programs for a language - is that even a finite number or must we be more specific, finite RAM etc?


texts: The complexity of $A^{k \cdot log_{x} (n)}$ is exponential?

texts:
The complexity of $A^{k \cdot log_{x}(n)}$ is exponential? ($k$ and $x$ is constants, $A$ is defined constant base, $n$ is the size of the task).

It is in a class of polynomial complexity?


texts: Length of mid part of the string in Pumping Lemma

texts:
This statement of the pumping lemma from Wikipedia.

  Let $L$ be a regular language. Then there exists an integer $p \ge  1$ (depending only on $L$) such that every string $w$ in $L$ of length at least $p$ ($p$ is called the "pumping length") can be written as $w = x y z$ (i.e., $w$ can be divided into three substrings), satisfying the following conditions:

  $\lvert y \rvert \ge 1$
  $\lvert x y \rvert \le p$ and
  for all $i \ge 0$, $x y^i z \in L$.
  $y$ is the substring that can be pumped (removed or repeated any number of times, and the resulting string is always in $L$).

What confuses me about the definition of pumping lemma are two requirements: $\lvert y \rvert \ge 1$  and $i \ge 0$, $x y^i z$. The way I read it, that we are required to have $y$ length be equal to one or greater, and at the same time, we can completely skip it, since $i \ge 0$, i.e. effectively  $\lvert y \rvert = 0 $.
Intuitively, it makes sense that we should be able to skip $y$ and still have string be in $L$.


texts: Multidimensional 0-1 knapsack as the solution to 0-1 goal programming problem

texts:
I am trying to find the algorithm for the 0-1 goal programming problem. Actually I don't have any recent references for explicit algorithms, all the recent articles are about the modelling and not about the solution and algorithms (the solution is found using the commercial software like LINGO or CPLEX).

Now I am thinking that linear goal programme can be reduced to the multidimensional 0-1 knapsack problem where the the simple linear combination of goal program auxiliary variables n1(+)+n2(+)+... can be considered as the objective function the initial goal expressions can be considered as the constraints of the multidimensional knapsack problem together with the remaining constraints of the goal program.

Am I right? To which classical integer (0-1) programming problems the 0-1 goal programm can be reduced?

There is simple procedure how to convert nonpreemptive simple integer goal program to linear program and that procedure is described in article "Linear Goal Programming and Its Solution Procedures" (can be Googled). The problem in my case is that my initial variables xi are 0-1 variables but auxiliary variables y(+)j, y(-)j can take any value and so the resulting problem is general mixed-integer problem or at least general integer problem. Is this the best possible conversion in this case? It could be better to stay end with 0-1 problem and use all the efficiency of the solution of such problems.


texts: How is the Liquid State Machine's readout function trained?

texts:
I’m trying to make a Liquid State Machine in python and I already read many articles about it, but still there are many points I don’t understand.

The readout function is a Feed-forward Neural Network, but how is it taught to read out the states? In the echo state network I had a train period when I feed a train signal through backward weights and by saving each step’s state, the output weights were calculated.

Is it the same way in the Liquid State Machine, or is its “inner weight matrix” trained instead (the connections between the inner nodes / neurons)? Or does it have an entirely different method?


texts: Are their problems that we can not even approximate efficiently?

texts: Most hard problems can either be solved efficiently in average time, or an approximation can be efficiently found. Are there any natural problems for which this is not the case? In particular, is there a natural problem that can not be solved in polynomial time in the average case, even if we only demand an approximation?


texts: Decidability of language that contains all TM encodings that accept at least one word

texts:
I have a language that contains all encodings of the Turing machines that accept at least one word.

Is this language recursive, recursively enumerable, or neither?


texts: I want  to prove that $$A \leq_p {\overline{A}} \Leftrightarrow {\overline{A}} \leq_p A$$. Does anyone have a Idea how to solve this ?


texts: Generating Combinations from a set of pairs without repetition of elements

texts:
I have a set of pairs. Each pair is of the form (x,y) such that x,y belong to integers from the range [0,n).

So, if the n is 4, then I have the following pairs:

(0,1) (0,2) (0,3)
(1,2) (1,3)
(2,3)

I already have the pairs. Now, I have to build a combination using n/2 pairs such that none of the integers are repeated (in other words, each integer appears at least once in the final combination). Following are the examples of a correct and an incorrect combination for better understanding

 1. (0,1)(1,2) [Invalid as 3 does not occur anywhere]
 2. (0,2)(1,3) [Correct]
 3. (1,3)(0,2) [Same as 2]

Can someone suggest me a way to generate all possible combinations, once I have the pairs.


texts: Equivalence classes of regular languages

texts:
One used equivalence relation in regular languages is that for a language $L$ over alphabet $\Sigma$, $(x\sim^Ly)\Leftrightarrow (\forall w\in \Sigma^* xw\in L \Leftrightarrow yw\in L)$.

That means, if two words $x,y$ are not in the same class, there exists $w\in \Sigma^*$ such that $xw\in L$ but $yw \notin L$.

It is implied by Myhill–Nerode theorem, that if we have infinitely many equivalence classes for a language $L$, that $L$ is not a regular language.

My question is this:
Is it correct to say that if we have an infinite amount of equivalence classes then there are infinitely many different $w\in \Sigma^*$ that "breaks" such equivalence relation between those classes? If so, how do we prove it? If not, is there a counter-example?


texts: Product of all nodes except for one in Binary Tree

texts:
Assume we are given a binary tree with an integer sitting at each node. I am looking for an efficient way to find for every path from the root to a leaf every possible product with exactly one node omitted. I am looking for a solution without divisions (i.e. integers can be zero).

One way to go about this I thought of is
I can compute all possible partial products starting at the root. That is each node stores the product of the unique path from the root up this node ( but except the integer stored at that particular value ). Then for each leaf node I can walk up the path to the root node multiplying the integers on the way. At a given node before accumulating the node into the product I can multiply the product with the prefix product stored in the node.

It feels like I am doing a lot of redundant multiplications when visiting each path from a leaf to the root, since these paths potentially share a lot of nodes. Is there a way faster way to do this?


texts: What machine learning algorithm to use and how to implement it?

texts:
I have a virtual world with a grid filled with squares (x by y). There are entities that can do:
1. move 1 step in the four cardinal directions
2. eat food
3. fight another entity of a different type
4. mate with the same type of entity to reproduce (create one more of that type of entity)

The objective is to obtain the highest score possible.
The score is calculated by:
+1 per food eaten
+1 per enemy killed
+1 per entity of that type

The inputs (neurons) are as follows:
1. position (x, y) on board
2. board size
3. types of entities in adjacent squares (including food, and null if empty)

I would like to create a program that will create hidden neurons that give rise to a sophisticated moving and attacking pattern that will allow it to obtain the highest score.

Which algorithm should I use?


texts: Understanding algorithm for maximum sum of non-consecutive elements

texts:
There is a well-known problem in CS of finding the maximum sum of non-consecutive integers in a list. There is even an SO post about how to solve it:

https://stackoverflow.com/questions/4487438/maximum-sum-of-non-consecutive-elements

That said, I have read this post many times, and many other posts online about how to solve this problem, and I still do not understand why the solution is correct.

Following another post about the problem (that shows the solution, but again lacks in an explanation as to why the solution is correct), I created the following snippit to run in JShell:

class MaxSubset {
    public static Integer maxSum(final List<Integer> ints) {
        final class MaxSubsetR {
            private Integer maxSumR(final List<Integer> ints, final Integer i, final String str) {
                if(i == 0) {
                    System.out.println("in i == 0: " + str);
                    System.out.println("in i == 0: get i " + ints.get(i) + " " + str);
                    System.out.println("in i == 0: get 0 " + ints.get(0) + " " + str);
                    System.out.println("returning: " + ints.get(0));
                    return ints.get(0);
                }

                if(i == 1) {
                    System.out.println("in i == 1: " + str);
                    System.out.println("in i == 1: get i " + ints.get(i) + " " + str);
                    System.out.println("in i == 1: get 0 " + ints.get(0) + " " + str);
                    System.out.println("in i == 1: get 1 " + ints.get(1) + " " + str);
                    System.out.println("returning: " + Math.max(ints.get(0), ints.get(1)));
                    return Math.max(ints.get(0), ints.get(1));
                }
                System.out.println("no match " + i + " " + str);
                return Math.max(maxSumR(ints, (i - 1), "left"), ints.get(i) + maxSumR(ints, (i - 2), "right"));
            }
        }
        return new MaxSubsetR().maxSumR(ints, ints.size() - 1, "init");
    }
}

but after running the algorithm and watching the output, I'm still just as confused as I was when I began.

Can someone explain this algorithm to me? In particular:

1) How is the alternation of choosing (i - 1) or (i - 2) is even determined in the recursion in the first place?

2) How does simply subtracting 1 or 2 from the size of the array create the effect of selecting the optimal subset of non-adjacent items?

3) And just generally, how is it going about picking the right items from the list to achieve the stated goal?

New Question

4) We note that the List<Integer> never mutates during the recursion, so for the two if statements, i == 0 will always return the first item in the list, regardless of list size, and the i == 1 case will always return the greater of the first or second item in the list, regardless of list size. So, how is it that every item in the list is even being considered, if the return statements literally only care about arr[0] and arr[1]?

EDIT NOTES

I have re-written my second question to, hopefully, make it more clear what I mean.

For ease of reading, here is the algorithm in pseudo-code, without print statements:

func maxSum(Int[] arr, Int i)
  if(i == 0) return arr[0]
  if(i == 1) return Math.max(arr[0], arr[1])
  return Math.max(maxSum(arr, (i - 1)), maxSum(arr, (i - 2)) + arr[i])

and it would be called with

maxSum(arr, arr.size - 1)


texts: Smoothed analysis of the Partition problem

texts:
I am studying smoothed analysis and trying to apply it to the Partition decision problem: given $n$ real numbers with a sum of $2 S$, decide whether there exists a subset with a sum of exactly $S$.

The common definition of the smoothed runtime complexity of an algorithm is:
given $n$ and $\sigma$, the smoothed runtime of an algorithm is the maximum, over all inputs of size $n$, of the runtime on the input when it is perturbed by a perturbation of size $\sigma$, e.g. by adding to each input a number selected randomly from a normal distribution with standard deviation  $\sigma$, or from any distribution with support $[0,\sigma]$.

If I apply this definition to the Partition problem, it seems that for any $\sigma > 0$, the runtime complexity is $O(1)$, since for any random noise that is added to the original numbers - no matter how small - the answer is "no" with probability 1.

This is strange, since in the more common examples of smoothed analysis, the runtime complexity depends on $\sigma$, and here it does not.

Is there something I misunderstood? What is the smoothed runtime complexity of Partition?


texts: Dijkstra's algorithm for edge weights in range 0, ..., W

texts:
Suppose I want to run Dijkstra's algorithm on a graph whose edge weights are integers in the
range 0, ..., W, where W is a relatively small number.
How can I modify that algorithm so that it takes time just O((|V| + |E|) logW) and relatively easy implement that in C/C++?


texts: What's the regex corresponding to this DFA?

texts:
Here is a DFA from a research project. We created the DFA manually.
We are interested in which regex is this DFA corresponding to.
Certainly, there could be multiple regex corresponding to it; we prefer a simpler one.

Inspired by the first answer from Karolis Juodelė, one correct Answer should be:

(00*10*1|1(0*|(10)*)*110*1)*1(0*|(10)*)*110*


texts: Big O notation for finding duplicates in a list using binary search

texts:
I've written an algorithm to find duplicate integers in a sequential list of integers, but I'm running into issues when trying to calculate it's worst case complexity.

Given a sequential list of integers the algorithm is as follows:

1. get the length of the list of integers, assign to list_length - O(1)
2. while list_length is greater than 0: O(n)
  1. remove the item at index 0 from the list and assign to checking - O(1)
  2. set list_length to the current length of the list
  3. perform a binary search of the remaining list for the value assigned to checking - O(log n) where n is the current length of the list
  4. if the item is in the list return True
3. if none of the binary searches found a match return False

My understanding is that the complexity of a binary search is $O(\log n)$ and if I were not to remove an item from the list on each iteration, the complexity of my algorithm would be $O(n \log n)$ (as I am running an $O(\log n)$ algorithm $n$ times).

What I am not sure of is how the shortening of $n$ will affect the binary search, as on each iteration the complexity of the binary search will change: $O(\log (n - 1))$ on the first iteration, then $O(\log (n - 2))$ on the second.

How do I represent the diminishing size of $n$?


texts: How is deciding a problem not equivalent to finding a valid certificate for verification?

texts:
Take a decision problem $Q$, which maps encoded instances of a problem, i.e., $\lbrace 0, 1 \rbrace \ast$ to the solution set $\lbrace 0, 1 \rbrace$.
Since $Q$ is in $NP$, there exists a verification algorithm $A$, which takes an input and a certificate, in that order, as arguments and maps those to $\lbrace 0, 1 \rbrace$, depending on whether there exists a certificate proving that the solution to the input is $1$.

If this presentation of what a verification algorithm does is correct, then it is unclear to me if, for a binary-encoded problem instance $x$,

$$Q(x) = 1 \iff \exists y (A(x, y) = 1).$$

It seems to me that if there is a certificate, this means that the decision for that input is affirmative, so that in theory, you could attach sufficient information to a certificate such that it characterizes a solution to the decision problem, iterate through the entire set of certificates and, once you have found one that satisfies $A(x, y) = 1$, you have also found a solution to the problem for the respective input.

Maybe someone could explain to me if that equivalency above is wrong and if so, why. I know the difference between a problem and the verification part, but then again, on some level I do not.Neither am I sure about anything else, so feel free to point out mistakes.


texts: Optimized algorithm to compare templates of two websites

texts:
My task is to compare templates of two websites. I am ready with my algorithm. But it takes too much time to give a final answer.
Here, "template" means the way any page presents its contents.

Example:

Any shopping website have page of any Shoes, that contains,

Images in the left.
Price and Size in the right.
Reviews in the bottom.

If two websites are of any specific product, then it returns "Both are from same templates". Example, this link and this link have the same template.

If one website shows any product and another website shows any category, then it shows "No match".
Example, this link and this link are from different template.

I think that this algorithm requires some optimization, that's why I am posting this question in this forum.

My algorithm

Fetch, parse two input URLS and make their DOM trees.
Then if any page contains , UL and TABLE , then remove that tag. I done this because, may be two pages contains different number of items.
Then, I count number of tags in both URLS. say, initial_tag1, initial_tag2.
Then, I start removing tags that have same position on corresponding pages and same Id and their below subtree, if that tree has number of nodes less than 10.
Then, I start removing tags that have same position on coresponding pages and same Class name and their below subtree, if that tree has number of nodes less than 10..
Then, I start removing tags that have no Id ,and No Class name and their below subtree, if that tree has number of nodes less than 10.
Steps 4, 5, 6 have (N*N) complexity. Here, N, is number of tags. [In this way, in every step DOM tree going to shrink]
When it comes out from this recursion, then I check final_tag1 and final_tag2.
If final_tag1 and final_tag2 is less than initial_tag1*(0.2) and initial_tag2*(0.2) then I can say that Two URL matched, otherwise not.

I wrote my code in Java using Jsoup and Selenium. I asked before on Stack Overflow, but the answers did not help me.

I think a lot about this algorithm, and I found that removing node from DOM tree is pretty slow process. This may be the culprit for slowing this algorithm.

I discussed with some geeks, and

  they said that use a score for every tag instead of removing them, and add them , and
  at the end return (score I Got)/(accumulatedPoints) or something similar, and on the
  basis of that you decide two websites are either similar or not.

But I didn't understand this. So can you explain this statement, or can you give any other algorithm that solves this problem efficiently?


texts: Use of graph grammars/rewriting systems in compilers?

texts:
A(n imperative) program - in a higher-level language and more importantly in assembly language or  intermediate representations like LLVM - can be formalized as a directed "port graph", in which vertices are instructions and ports correspond to input/output operands/arguments. An optimization applied of a program's code therefore corresponds to a rewrite applied to its port digraph.
Now, graph rewriting is a small but somewhat-active area, in itself. What I'm wondering if these kinds of systems have been actually put to explicit use in the context of a compiler. That is, representing the optimization phase as a rewriting process, or a derivation using a port-graph grammar.
I'm not much of a "compilers guy" - I took a basic course on them in my undergraduate degree, and I know about LLVM and its IR - but it seems to me that graph rewriting systems is the "obvious" formalism to use; and at the same time - I don't see almost any FOSS projects involving such systems, nor do the papers about them discuss their use in compilers.
Note: I'm more interested in practical-use, popular-language compilers more than academia-only systems, but I'll take what I can get.


texts: Analyzing time complexity of solution in tutorial

texts:
Could someone explain time complexity of solution of in this tutorial?

I'm having hard time figuring out, how asymptotic bounds for first solution is $O(3^k k)$.

What I figured so far is, for computing $f(Y)$, we would require $O(\lvert Y\rvert)$ steps and for fixed set $X$ (such that $\lvert X\rvert=k$), we would have $2^{n-k}$ number of $Y$ sets that would contain set $X$. And there would be ${n \choose k}$ such $X$ sets.

So total steps should be $${n \choose k } {\sum_{r=0}^{n-k} {n-k \choose r} ({k+r})} \leq {n \choose k} n  2^{n-k}$$

But is this value tightly bounded by $3^k k$?


texts: Given a set of intervals on the real line, find a minimum set of points that "cover" all the intervals

texts:
I've been trying to find an efficient way to solve the problem of finding a minimum (not minimal) set of time points that cover a given family of intervals on the real line, that is, for each interval $I$ there should be some time point $t$ from the chosen set such that $t \in I$. However, I am not sure if it's that straightforward. I tried modeling it as a minimum edge cover problem ("P" polynomial time complexity: intervals are vertices and intersection between intervals is an edge), but that doesn't work because for 1 time point in optimum solution there can be multiple edges.

I developed a greedy solution: have intervals sorted in increasing order of their end times. Then iterate over the intervals in the order. If a time point hasn't been inserted into the solution that covers the current interval, then insert it and remove all intervals that are covered by it from consideration. Continue till no intervals remaining.
Example:
(0, 10), (3, 12), (11, 15)

Add time 10 to the solution.
Remove (0, 10) and (3, 12) from consideration.
Add time 15 to solution.
Remove (11, 15) from consideration.
Final solution is of size 2. (time 10 and 15).

I can't prove it's optimum because it's not modeled as edge cover or vertex cover or known graph problem. I tried modeling it as "minimum clique cover problem" but not sure if it works.

How to model it properly to understand its complexity (P vs NP complexity)?
How to know if the above solution is optimum?


texts: Differences between programming model and programming paradigm?

texts:
What is the relation and difference between a programming model and
a programming paradigm? (especially when talking about the
programming model and the programming paradigm for a programming
language.)
Wikipedia
tries to answer my question in 1:

  Programming paradigms can also be compared with programming models that are abstractions of computer systems. For example, the
  "von Neumann model" is a programming model used in traditional
  sequential computers. For parallel computing, there are many
  possible models typically reflecting different ways processors can
  be interconnected. The most common are based on shared memory,
  distributed memory with message passing, or a hybrid of the two.

But I don't understand it:

Is it incorrect that the quote in Wikipedia says "the 'von Neumann model' is a programming model", because I understand
that the Von Neumann model is an architectural model from
https://en.wikipedia.org/wiki/Von_Neumann_architecture?
Are the parallel programming models "typically reflecting different ways processors can be interconnected"? Or are parallel
architectural models "reflecting different ways processors can be
interconnected" instead?

In order to answer the question in 1, could you clarify  what a programming model is?

Is it correct that a programming model provided/implemented by a
programming language or API library, and such implementation isn't
unique?

From Rauber's Parallel Programming book, "programming model" is
an abstraction above "model of computation (i.e. computational
model)" which is in turn above "architectural model". I guess that a
programming model isn't just used in parallel computing, but for a
programming language, or API library.


texts: Graphs invariant to permutations of vertices

texts: I am reading a paper on Semi Supervised Learning and I am confused about a term. The paper talks about graphs that are invariant to permutations of the vertices. Can somebody explain or perhaps give an example? Is it same a regular graphs?


texts:
I don't have a CS degree but I have recently taken up studying algorithms very seriously.
I have been studying greedy and dynamic programming for days and I come across the below definition a lot, seems they all come from the same source, but I do not understand what it means, it is one of the vaguest definitions I have ever come across. I wonder if someone can please help me explain this.
e.g. I don't understand what they mean by optimal solution, what constitutes an optimal solution, how can I define it?

In computer science, a problem is said to have optimal substructure if
an optimal solution can be constructed from optimal solutions of its
subproblems. This property is used to determine the usefulness of
dynamic programming and greedy algorithms for a problem


texts:
This variant is almost similar to the normal nim game which states -

  Two players take turns to remove one or more items from a single, non-empty pile. The player who removes the last item from the last non-empty pile is declared as a winner.

The twist is an inclusion of a "pass" move for each non-empty pile. To make myself clear, a player can choose to pass his move on any non-empty pile on which there was no "pass" move made.

I looked up grundy numbers to solve this problem, but I do not how to add the rule of pass move.

For ex:

$G(0) = mex(empty-set) = 0$

$G(1) = mex(G(1),0) = ?$

Heremex(g) is a function which takes a set of non-negative integers and outputs smallest non-negative integer that is not present in the list.

For ex : mex(0,1,2) = 3 and mex(0,2,3) = 1

I just don't know how to proceed. I'd appreciate some help. Also, I'd like to add that the number of piles is small say 10-15 but the number contained in each pile is quite huge. Hence those recursive backtracking type of solutions won't work.

Update : The pass move is not mandatory.


texts:
Consider the most naïve backtracking for CNF-SAT. It only checks if an assignment satisfies the input formula $\phi$ when all the $n$ variables have values assigned. Let $m$ be the size of $\phi$. Then the time complexity for this backtracking is $O(m 2^n)$.

Now, consider DPLL. This algorithm is just a simple backtracking with some pruning strategy. Besides, DPLL simplifies $\phi$ along the backtracking, instead of doing it only at once, so the $O(m)$ cost is amortized. Hence, its running time should also be $O(m 2^n)$. Still, some places state that $O(2^n)$ is also an upper bound for DPLL (Wikipedia, for example). Does anybody knows the analysis to find this upper bound?


texts:
We can invert the Burrows-Wheeler with this method:

  The inverse can be understood this way. Take the final table in the
  BWT algorithm, and erase all but the last column. Given only this
  information, you can easily reconstruct the first column. The last
  column tells you all the characters in the text, so just sort these
  characters alphabetically to get the first column. Then, the first and
  last columns (of each row) together give you all pairs of successive
  characters in the document, where pairs are taken cyclically so that
  the last and first character form a pair. Sorting the list of pairs
  gives the first and second columns. Continuing in this manner, you can
  reconstruct the entire list. Then, the row with the "end of file"
  character at the end is the original text.

From: https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform

I don't understand why this method works.


texts:
So my problem is as follows: I get responses (such as "yeah whatever", "yes do it", "no don't do it", "nah", "yeah do it" etc.) and I need to classify them into either "yes" or "no" i.e. a binary classification. What algorithm and features should I use for this?

My thoughts yet: Use an averaged perceptron or logistic regression or boosted trees. As for features, I was considering using the tf-idf score and sentiment analysis but I can't think of much else.


texts: Is decidability closed under the mapping f where f(a)=f(b)=0 and f(c)=1?

texts:
Consider the function $f$ that maps strings over $\{a, b, c\}$ to strings over $\{0, 1\}$ by replacing each $a$ by 0, each $b$ by 0, and each $c$ by 1. For example $f(cabbc) = 10001$. The function $f$ extends naturally to languages: if $L$ is a language over $\{a, b, c\}$, then $f(L)$ is the language over $\{0, 1\}$ defined as $\{f(w) \mid w\text{ is in }L\}$.

Prove that if a language $L$ is decidable, then so is $f(L)$.

I am thinking that since $L$ is decidable it must be regular so there exists a DFA for $L$. $f(L)$ is closed -- dk how to prove though. Then $f(L)$ is also regular. Therefore is also decidable.


texts: How is expected value in entropy derived?

texts:
I was self learning about entropy and came across this equation.
$$
H = - \sum p(x) \log p(x)
$$
The equation for entropy in expected value,
$$
H(x) = \operatorname*{\mathbb{E}}_{X \sim P}[I(x)] = -\operatorname*{\mathbb{E}}_{X \sim P}[\log P(x)].
$$
But the expected value is written as
$$
\mathbb{E}[X] = \sum_{i=1}^k x_i p_i = x_1p_1 + x_2p_2 + \cdots + x_k p_k
$$
Using the above expected value formula, I expected the entropy equation looks something like this
$$H(x)= -\operatorname*{\mathbb{E}}_{x \sim P(x)}[\log P(x)]= - \sum xP(x)\log P(x) $$
where is the $x$ gone in the real entropy formula in summation notation?


texts: Is how much memory a program needs computable?

texts:
We know that how much time a program needs is not computable.

Do we know how much memory a program needs is decidable?


texts: Is this NP-hard: min-weight n-clique in a complete n-partite graph

texts:
I have a complete $n$-partite graph, where each partite set has $n$ vertices (yes it's also $n$), so the graph has $n^2$ vertices in total.  My problem is to find a minimum weight $n$-clique in the graph.  I would like to know whether the problem can be solved in polynomial time.

More details of the terms:

Complete $n$-partite graph: a graph in which vertices are adjacent if and only if they belong to different partitions (wikipedia).  There are $n$ partitions in the graph.  (In my case, each partition contains exactly $n$ vertices.)

Minimum weight clique:  Every edge in the graph has a weight.  The weight of a clique is the sum of the weights of all edges in the clique.  The goal is to find a clique with the minimum weight.

Note that the size of the required clique is $n$, which is the largest clique size in a complete $n$-partite graph, and it is always attainable.

I have searched for hours and there seems no research tackling the exact problem.  Any suggestions?


texts: In what sense a type of parser is less power than the other?

texts:
I am learning LR(0), SLR(1), CLR(1) and LALR(1) parsers.
I know how parsing tables of each of them is formed. If x < y means parser x is less "powerful" that parser y, then, I read, the relationship between these parsers can be shown as:

  LR(0) < SLR(1) < CLR(1) < LALR(1)

However, I am not very clear about exactly what being "powerful" means. I can guess following possibilities for being less powerful:

a. Cannot accept valid string
b. Accept valid string very late
c. Cannot reject invalid string
d. Reject invalid string very late
f. Involves SR, RR conflict for some grammars

Doubts

I know point 5 holds for sure. However what exact effect a conflict have on parsing? Do we say that parser is non deterministic and/or requires backtracking to steps involving conflict or we simply say parser of certain type cannot be simply prepared for given grammar?
Which of first four (a,b,c,d) holds? I tried solving one example, for which I prepared both SLR(1) and CLR(1) parsing table. I SLR(1) parsing table had reduce move for state 2 and terminal ), whereas CLR(1) did not. I took an invalid string for which SLR(1) was able to incorrectly reduce when stack top was state 2 and next input symbol was ). But eventually it failed to shift ). So, in the end rejecting the string. However, CLR(1) rejected the string right away without incorrectly reducing. Is this what all can happen? Or there can be an invalid string which SLR(1) may incorrectly accept (point c)? Or points (a) and (b) do also hold?
I feel only point (d) holds. Also SLR(1) and CLR(1) can accept valid string in same number of steps (that is, point b does not hold). Am I right with what I feel?

 Edit

I concluded following for above points (a) through (d). Need someone to confirm:

(a) SLR(1) always accept valid strings as it will be able to correctly do shift reduce moves for such strings. So, point (a) is incorrect.

(b) Accepting valid strings late can only happen when valid string causes traversing through incorrect reduce moves of SLR(1) parsing table. However, this never happens. Valid strings can never be accepted by going through incorrect reduce move cells of parsing table. Those are only hit by invalid strings. Hence, point (b) is also wrong.

(c) SLR(1) can never fail to reject invalid string as it will always fail to shift some terminal in such string. So, point c is also not correct.

(d) SLR may reject some invalid strings late since it may do incorrectly do some reductions. So only point d is correct.

Another (possibly last) doubt

Though in (c) above, I said SLR(1) can never fail to reject invalid string, I doubt its correctness. If a parser accepts invalid string, we simply say that the parser does not implement that grammar, right? But my doubt is whether such parser always involve SR / RR and such "conflict is the only reason to fail to reject invalid string"? We know that SLR can do some incorrect reductions. So, "can't such incorrect reduction be reason for acceptance of invalid string"? Or in other words, for some invalid string, can't SLR shift all of it (so that no terminal will remain un-shifted in the end), and finally do incorrect reduction of whole invalid input string to starting symbol S, thus accepting invalid string? After all we know SLR parser may do some incorrect reductions. Then, why it cant do incorrect reduction of whole invalid input string to the start symbol?


texts: Finding triples that satisfy given constraints in $O (n \log n) $ time

texts:
Given a string comprised solely of the characters $\text{a, b, c}$ we want to know the number of different $(i, j, k)$ triples such that $0 \leq i,j, k < n \text{ (here n denotes the length of the string)}$ satisfying the following two conditios :

  $\bullet \text{ }s[i] = "a", s[j] ="b" \text{ and } s[k] = "c"$

  $\bullet \text{ } (j + 1)^2 = (i+1)(k + 1) $

  We consider such two tuples, $(i, j, k)$ and $(x, y, z)$ to be different only of $i \neq x$ or $j \neq y$ or $k \neq z$.

  Example case and solution :
  The string $"ccaccbbbaccccca"$ with $n = 15$.
  There are two triplets that satisfy the given constraints, namely $(2, 5, 11)$ and $(8, 5, 3)$.

  The second solution shows that $i$ is not necessarily less than $k$.

I know this is a programming question, but I'm more inclined to look for a mathematical approach that I currently seem to be missing. Since $n$ could be as large as $5 \cdot 10^5$ brute force is not feasible.

I've attempted coming by the solution by noticing that in order for $\sqrt{(i + 1)(k + 1) } = (j +1 ) \in \mathbb{N}$, $k +1$ should be of the form $(i + 1) \cdot \alpha^2$ or of the form $\frac{\alpha^2}{i + 1}$.

Hence, we would have to iterate and test in order to find the $
\alpha$ values that would satisfy our conditions. Later on, I found out by inspecting the process that the latter form covers all the solutions, multiple times, so I would only need to look for answers by using the second form.

This still led to a temporal complexity of $O(\sqrt{n} \cdot \sum_{k=1}^{n}\sqrt{k})$.

I've been at this for too many hours and I have no idea how to proceed. How would you solve this?
I'm guessing $O(n)$ isn't possible but $O(n \log n)$ should probably do the trick.


texts: Is the halting problem specific to Turing machines?

texts:
The proofs that the halting problem is undecidable seem to make very few assumptions about the kind of program/machine under consideration: just that the programs take one input and either loop or produce an output. Not just Turing machines have these characteristics: for example, a linear-bounded automaton can also loop.

So, as well as a proof that you can't use a Turing machine to decide whether a Turing machine will halt, is it not also a proof that you can't use a pushdown automaton to decide whether a pushdown automaton will halt, and so on, for any automaton/language that has the ability to loop?


texts: Is it possible to build any regular expression in a computer language with just 3 basic operators?

texts: Many computer languages have complex regular expressions tools. For example, in Javascript you have global flags, escape characters, whitespace character, assertions, character classes, groups and ranges etc. I'm wondering if using just the 3 basic regular expressions operators as defined in formal languages, that is concatenation, alternation and Kleene star can achieve the same result as any pattern described with more tools as for example in Javascript. Is there a theorem about this?


texts: Can anyone explain why this is an inadmissible recurrence case that cannot be solved by the master theorem?

texts:
Wikipedia says that the following recurrence is inadmissible since there is a non-polynomial difference between $f(n) = \frac{n}{\log n}$ and $n^{\log_b a}$:

$$ T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log n} $$

In human language, what does non-polynomial difference mean? Why was $n/\log n$ compared to $n^{\log_ba}$ in the first place?

In addition, what happens if I replaced $n/\log n$ with $n/\log^*n$, where $\log^*n$ is the log-star function. Would a similar type of analysis take place?


texts: log(n) complexity. Difficulty understanding example

texts:
So, I am revisiting complexity analysis.

Here's the example: the instructor reduced an algorithm to:

n*(1 + 1/2 + 1/3 + ... + 1/n), and I can't seem to grasp why the part in parentheses is log(n).


texts: If two languages together cover all words and one is regular, is the other one as well?

texts:
If $L_1$$\subseteq$ $\Sigma^*$, $L_2$$\subseteq$ $\Sigma^*$ , $L_1$ is regular and $L_1$$\cup$ $L_2$ = $\Sigma^*$ then is $L_2$ necessarily regular?

I think that the answer is yes, but I'm not sure on my proof.

The reason that I think that $L_2$ is regular is because surely $L_2$ just accepts all the words in the language that $L_1$ doesn't? So, to me, that suggests that $L_2$ must be regular as well, I just don't know where to begin on a formal proof.

Any guidance would be appreciated.


texts: Is the empty string and some words of even length are elements of this set?

texts:
$L = \{w \in \{a,b\}^*| \text{the first, the middle, and the last characters of $w$ are identical}\}$.

I have my answers, but I need confirmation:

Is the empty string $\epsilon \in L$? Yes. Reason: there is no first, middle, or last character to break the rule.

Words of even length, assuming the first and last characters of them are identical, again, must be in $L$, as there is no middle character to break the rule in such words.

This is in the context of theory of computation by the way.


texts:
I am studying over my notes, and there is something I don't understand about $e_m$. We represent the floating point numbers as  $1.d_1d_2...d_t \times \beta^e$. Now, my professor defines $\epsilon_m$ as the smallest $x$ such that $fl(1+x) > 1$. But then she writes

$$\epsilon_m = \beta^{1-t} \hspace{1cm} \text{    (for "chopping")}$$ and

$$e_m = \dfrac 12 \beta^{1-t} \hspace{1cm} \text{ (for rounding)}$$
However, I think these should be $\beta^{-t}$ and $\dfrac 12 \beta^{-t}$, respectively.

The number $1$, and the next number right after, are

$$1.00 \cdots 00 \times \beta^0$$
and
$$1.00 \cdots 01 \times \beta^0$$
where the $1$ is in the $t^{th}$ decimal place. Therefore their difference is $\beta^{-t}$ so if $x = \beta^{-t}$, then $1+x$ is itself a floating point number, so $fl(1+x) = 1+x>1$.

Am I wrong, or are the notes wrong?

Thank you very much.


texts: Given N positive integers are they the integers 1-N : What is the relationship between this problem and NP?

texts:
Here’s the decision problem:
Suppose I have N positive integers encoded in base-2 (as oppose to unary)
Are these integers precisely the integers 1-N in some order?
This is related to the Hamiltonian path problem which is NP-complete
Given a graph with N vertices you can nondeterministically walk a path of length N
If you could decide whether or not the sequence is precisely the integers 1-N in some order then you could decide whether or not the path is Hamiltonian
Hence the decision problem is related to the Hamiltonian path problem
What then is the relationship to NP?
Is it NP hard?
Is it NP complete?


texts: How different is the working of SNN (Spiking Neural Network) as compared to a real Neuron System in biological systems?

texts: Assuming its one step closer to realism as compared to ANN, DNNs and other Neural Network models, what are the primary differences between a real neuron system and SNN?


texts: How does SpaCy make its dependency tree?

texts:
I discovered that SpaCy had the ability to make dependency trees. For instance given a question “To whom did the Virgin Mary allegedly appear in 1858 in Lourdes France?”

We can create its dependency tree with the following code :

I know that it is a set of edges $E$ which represents the relations of labeled dependencies of the particular analysis of $G$. More precisely, an edges $w_i, r, w_j \in E$ represents a relationship of dependence of head $w_i$ towards $w_j$ labeled with the type of relationship. A dependency graph $G$ is therefore a set of dependency relations between tokens in $S$.

For instance we present the dependency graph that follows
 by the following graph:

$G = (V, E)$
$V = \{\mbox{It, is, a, replica, of, the, grotto, at, Lourdes, France, where, the, Virgin, Mary}\\ \mbox{reputedly, appeared, to, Saint, Bernadette ...}\}$
$E=\{\mbox{(is, NSUBJ, It), (is, ATTR, a replica), (a replica, PREP, of),...}\}$

But I was wondering how does $E$ was made with Spacy? How does the dependency tree method chose which node is the root and which aren't?

I have heard from this French paper that, on the one hand that $E \subseteq V \times R \times V$ where $R = {r_1, ..., r_m}$ is a finite set of dependency possible names that we call dependency relationship. They can link two tokens in a sentence. A dependency name $r \in R$ is also called a labeled edge. For example, a relationship between a head verb and its subject can be noted with $r = SBJ$.

On the other hand it was an analysis problem of finding the dependency graph that has the highest score for an input sentence.

Yet I haven't seen where there is a child-children ordering creation.

The context is that I am using SpaCy dependency trees to get the root of sentences of a paragraph and match it with the root of a question.

For the question given above we have to find the answer in the following paragraph :

  Context — “Architecturally, the school has a Catholic character. Atop
  the Main Building\’s gold dome is a golden statue of the Virgin Mary.
  Immediately in front of the Main Building and facing it, is a copper
  statue of Christ with arms upraised with the legend “Venite Ad Me
  Omnes”. Next to the Main Building is the Basilica of the Sacred Heart.
  Immediately behind the basilica is the Grotto, a Marian place of
  prayer and reflection. It is a replica of the grotto at Lourdes,
  France where the Virgin Mary reputedly appeared to Saint Bernadette
  Soubirous in 1858. At the end of the main drive (and in a direct line
  that connects through 3 statues and the Gold Dome), is a simple,
  modern stone statue of Mary.”

The expected answer is  “Saint Bernadette Soubirous”.
The sentence having the answer — is “It is a replica of the grotto at Lourdes, France where the Virgin Mary reputedly appeared to Saint Bernadette Soubirous in 1858”. Its dependency tree of the sentence containing the answer is :


texts: Need to remove indirect left recursion from CFG

texts:
I need to remove indirect left recursion from the following CFG:
remove indirect left recursion from the following CFG.
$$A → Ba| b$$
$$B → Cd | e$$
$$C → Df | g$$
$$D → Df | Aa | Cg$$

In the following solution, I have expanded all the non-terminals to get them converted to direct recursion, instead of indirect recursion (if applicable), so that I may apply Rule for removal of direct left recursion:

$$A → Ba → Cda → Dfda → Aafda$$
$$C → Df → Cgf$$
$$D → Df$$
$$D → Cg → Dfg$$
$$D → Aa → Dfdaa$$
So, it becomes:
$$A → Aafda| b$$
$$B → Cd | e$$
$$C → Cgf | g$$
$$D → Df | Dfg | Dfdaa | ba | gg$$
So, it becomes (after removal of direct left recursions):
$$A → bA'$$
$$A' → afdaA'| eps$$
$$B → Cd | e$$
$$C → gC'$$
$$C' → gfC' | eps$$
$$D → baD' | gg D'$$
$$D'→ fD' | fgD' | fdaaD' | eps$$

My specific Question is: Do I have to follow this way (convert all production rules emanating from all non-terminals or should I do that for only one, e.g. D?


texts: Hardness of a constrained quadratic maximization

texts:
Consider the following quadratic maximization:
\begin{align}
\max_{\mathbf{x} \in \mathcal{X}} &\quad\mathbf{x}^{T}\mathbf{A}\mathbf{x}
\end{align}
with
\begin{align}
\mathcal{X} = \lbrace
\mathbf{x} \in \mathbb{R}^{n} :~ \|\mathbf{x}\|_{2}=1, \|\mathbf{x}\|_{0}\le k
\rbrace,
\end{align}
where $\mathbf{A}$ is a positive semidefinite matrix and $k \le n$ is a sparsity parameter.
This problem is NP-hard, by a reduction from the max-clique problem.

I am interested in a similar problem obtained by imposing additional structure on $\mathcal{X}$.
In particular, assume that the $n$ variables in $\mathbf{x}$ are partitioned into $k$ disjoint groups.
We restrict the feasible set to unit-length vectors $\mathbf{x}$ with one active variable per group.
That is, $\mathcal{X}$ contains again $k$-sparse vectors, but the support cannot be arbitrary; it contains (at most) one nonzero entry for each of the $k$ groups.

Note that the feasible set in the modified problem is a subset of the previous maximization, but the number of feasible supports can still be exponential in the number of variables $n$ (for appropriately chosen $k$).

I suspect that the modified problem is also NP-hard. Any ideas on how to show that (or disprove)? Feel free to share your intuition.


texts: I would like to learn Lambda calculus (informally). What are the pre requisites for studying lambda calculus ? Can someone recommend an interesting textbook that introduces subject historically with motivation for the concepts and is easy enough to read?


texts: The time complexity of the Wikipedia version of Pollards $(p-1)$ algorithm

texts:
I am trying to understand the runtime of Pollard's $(p-1)$-algorithm as presented on Wikipedia. There the author writes that it takes $\mathcal{O}(B\log B\log^2n)$ time, but I do not see why.

Here the Wikipedia version:

Inputs: $n$: a composite number

Output: a nontrivial factor of $n$ or failure

select a smoothness bound $B$
define ${\displaystyle M=\prod _{{\text{primes}}~q\leq B}q^{\lfloor \log _{q}{B}\rfloor }} $ (note: explicitly evaluating $M$ may not be necessary)
randomly pick $a$ coprime to $n$ (note: we can actually fix $a$, e.g. if $n$ is odd, then we can always select $a = 2$, random selection here is not imperative)
compute $g = \operatorname{gcd}(a^M − 1, n)$ (note: exponentiation can be done modulo n)
if $1 < g < n$ then return $g$
if $g = 1$ then select a larger $B$ and go to step 2 or return failure
if $g = n$ then select a smaller $B$ and go to step 2 or return failure

I would say that:

The first step takes constant time (clear).

The second step takes $\mathcal{O}(B \log B)$ time due to the
distribution of prime numbers.

The third step takes constant time.

Concerning the 4th step: Fast-Exponentiation takes (in the version that I
know) $\mathcal{O}(\log M)$ time.   The gcd takes $\mathcal{O}(\log n)$ time. (I supposed that $ n < a^M-1$, but I am not sure if this is safe to assume.)

The remaining steps take constant time.

So because of step 2 and 4 I would say that the algorithm takes $\mathcal{O}(B \log B) + \mathcal{O}(\log n) + \mathcal{O}(\log M)$ time. What am I doing wrong?


texts: Checking whether an integer is a square or higher power

texts:
Is there an algorithm to check whether an integer $n$ is a square?  What about higher powers, e.g., testing whether $n$ is a $k$th power?

I understand that the Jacobi symbol $\left(\frac{b}{n}\right)$ can be computed in $O(\log n)$ without needing to know the prime factorization of $n$ but then this seems to be useful only for squares (not higher powers), and even then, it can still be inconclusive.

Maybe there is some way of refining the use of the Jacobi symbol for my question?


texts:
I have only intro CS under my belt, so I'm looking for some fast advice. I want to write a scheduling algorithm for the following scenario.

I have customers who have selected how many hours they want and what times they are available (choosing in 4 hour increments). I have 1 service person I then need to schedule to maximize the number of hours scheduled (so only 1 service person at a time). There is no ranking of preferences by customers, just a binary availability for each time slot and a number of hours. My thought was to start with the biggest job, schedule that, and then work downwards greedy-style. I also thought this must be a well-known problem. Can someone tell me the name of this 'problem' or what else I should be looking at? I can also restructure the inputs if that would help finesse this into an optimized algorithm that exists out there.


texts:
How can one prove that every nontrivial property of pairs of
semi-decidable sets is undecidable? (This is an extension of Rice's theorem that "Every nontrivial property of the r.e. sets is undecidable")


texts: Does having a similar constraint while reducing a problem to similar problem to prove np hard means they are same?

texts:
I have been trying to find the computational complexity of my optimization problem and found that it is Np-Hard. To prove it to Np-Hard, I try reducing it Nurse Scheduling Problem. I am quite confused with the idea during the reduction. Does having a similar constraint in my problem and NSP means that both problems are the same and have a solution already?
My problem:
We have a set of classes, and each class has a set of timing associated with a penalty. We have hard and soft constraints where every soft constraint violation. We have to schedule classes to timing such that the sum of all penalties is reduced.
We just have a hard constraint stating: Two classes cannot be scheduled at the same time of day and week (overlap constraints).
Here is the link to the nurse scheduling problem: Nurse Scheduling problem and they have a constraint stating: Two nurses dislike each other and thus cannot work on the same shift because of that.
I have to question:
Does this make my problem the same as the NSP problem?
Does my approach of reduction to NP-HARD is wrong? If yes, where did I go wrong? Is there any similar problem that I can use for reduction?
Can someone please help me with this?


texts: Given a list of vertices in a binary tree output minimal sublist with the same lowest common ancestor

texts:
The input: a binary tree and a list $L$ of vertices in that tree.
The output: a sublist of $L$ of minimal length that has the same lowest common ancestor as $L$. If there is several sublists of minimal length it is OK to output any one of them.
We could just check all the possible sublists of $L$ but that seems inefficient.
Is there an algorithm for this problem whose running time grows polynomially with respect to the length of $L$?
One idea that doesn't work is checking for each vertex in $L$ whether removing it changes the lowest common ancestor and then simply removing the "useless" vertices. If it worked the running time would be linear.
Another idea that might work but I haven't verified in detail is to pick one vertex removing which doesn't change the lowest common ancestor, then remove it and again pick one vertex etc. This has a quadratic time.


texts: How to correctly define the ratio of an approximation algorithm?

texts:
For a maximization problem $P$, I know that an $\gamma$-approximation algorithm for $P$ produces a solution $S$ that is $|OPT|\ge |S| \ge \gamma\cdot|OPT|$ for $\gamma <1$ and $OPT$ the optimal solution for $P$.

Is there an alternative definition?

For example, can we say that an $\gamma$-approximation algorithm for $P$ produces a solution $S$ that is $|S| \le \gamma\cdot|OPT|\le |OPT|$ for $\gamma<1$.


texts:
I have a table like below. Each row has store id, discount % for one of their coupons. Each store could have multiple coupons but (store+discount %) is a primary key. I would like to find out top 10 coupons (by decreasing order of discount %) but would like to get only 2 coupon from the same store. What is the most efficient way to do this? My logic involves sorting data multiple times. Is there a better and more efficient way?

Sample data in R:

df <- data.frame(Store=c("Lowes","Lowes","Lowes","Lowes","HD","HD","HD","ACE",
                         "ACE","Misc","Misc","Other","Other","Last","Last","Last"),
                 `discount_%`=c("60%","50%","40%","30%","60%","50%","40%","30%",
                                "20%","50%","30%","20%","10%","10%","5%","3%"),
                 check.names = FALSE)

my solution is ignore the store and sort the table by discount then
create a ID. ID would represent coupons in descending order
Then by Store and discount create ID2 which would have rankings of
coupons by store.
then filter all rows where ID2>2
then sort table by ID
take top 10 rows

The question that was posed to me was if this table has billions of rows then what is the most efficient (less computing power and time) way of getting our answer?


texts: How to prove a recursive's function Big-Theta without using repeated substitution, master theorem, or having the closed form?

texts:
I have a function defined: $V(j, k)$ where $j, k \in \mathbb{N}$ and $t > 0 \in \mathbb{N}$ and $1 \leq q \leq j - 1$. Note $\mathbb{N}$ includes $0$.

$V(j, k) = \begin{cases} tj & k \leq 2 \\ tk & j \leq 2 \\ tjk + V(q, k/2) + V(j - q, k/2) & j, k > 2\end{cases}$

I am not allowed to use repeated substitution and supposed to prove it by induction. I can't seem to use the master theorem because the recursive part is not in that form. Any ideas on how I can solve it with the given restrictions?

If I start with induction: I fix $j, q$ and induct on $k$. Then the base case is $k = 0$. Then $V(j, 0) = tj$. The question hinted that the function can be $\Theta(jk)$ or maybe $\Theta(j^2k^2)$ (but it doesn't necessarily have to be one of the two).

I choose $\Theta(j, k)$. In the base case, this would mean I would have to prove that $tj = \Theta(j, k)$ when $j = 0$. However, when I start with the Big-Oh, I would have to show that $km \leq mn = m\cdot0 = 0$ which right now I see not to be possible.

I am not sure if I did the base case wrong or if there is another approach to this.


texts: What are degenerate polygons? How does one check whether a given pair of polygons is degenerate or not?


texts: About the properties of the coresets in k-median clustering

texts:
I have seen two observations from the paper by Har-Peled but I do not know how to prove them
(i) If $C1$ and $C2$ are the $(k, ε)$-coresets for disjoint sets P1 and P2 respectively, then $C1 ∪ C2$ is a $(k, ε)$-coreset for $P1 ∪ P2$.
(ii) If $C1$ is $(k, ε)$-coreset for $C2$, and $C2$ is a$(k, δ)$-coreset for $C3$, then $C1$ is a $(k, ε+δ)$- coreset for $C3$
Can anyone please figure it out?


texts:
i have a context free grammar

i  want to create a tokens from the language

is there any techniques to do that ?

for example , this CFG from Prof.Alex Aiken notes :

 D -> D ; P | D

 D -> def id(ARGS) = E ;
 ARGS -> id, ARGS | id
 E -> int | id | if E1 = E2 then E3 else E4 | E1 + E2 | E1 - E2 | id(E1,...,En)

how can i crate the tokens ?

the professor explain how i do that in some inputs

for example , if i have the input :

x = 10

then i have

<id.,x> < opp., = > ......

but how i can do that from the CFG

thank you All


texts:
You are given a Graph G and an integer k.

The question is: Does G contain a vertex set X of size at most k such that deleting X results in a graph of degree at most 1?

Design an FPT (or a kernelization) algorithm for this problem and argue why it is correct.

Hint: Observe that vertices of higher degree must be "dealt with" somehow.

I do not exactly know where to start. I suppose that some reduction rules can be applied first, but not so sure what those can be (probably something that "deals with" vertices of higher degree.

Any ideas?


texts: Cannibals missionaries problem - solving usings graphs

texts:
I am trying to solve the cannibals - missionaries problem; we have the number of cannibals, the number of missionaries and the position of the boat. We are trying to transfer all of them to the other side, however there can't be more cannibals than missionaries on either side. The capacity of the boat is limited by 2.

There are multiple ways to solve this problem, I'm trying to do it using graphs. My questions is, how to I transform these "states" (M,K,B) into vertices in a graph? Each state represent the number of missionaries, the number of cannibals and the position of the boat.

I'm having troubles with visualization of these practical problems into graphs. Could you give me any help on how to add those vertices to the graph? Once I have the graph completed, it should be easy to solve using BFS.


texts: How can I prove the following problem is NP complete?

texts:
The problem:
I have a list $\displaystyle S=\{s_{1} ,s_{2} ,\dotsc ,s_{n}\}$ places. Each unordered pair of places has cost and gain: $\displaystyle c\{s_{i} ,s_{j}\} \in \mathbb{N}$, $\displaystyle g\{s_{i} ,s_{j}\} \in \mathbb{N}$. Also the pairs are only for $\displaystyle i\neq j$.
I have two numbers: $ $$\displaystyle b\in \mathbb{N}$, $\displaystyle p\in \mathbb{N}$.
The problem is to check wether it exist a combination of pairs such that:
$\displaystyle c_{1} +c_{2} +\dotsc +c_{m} \leqslant b$ and $\displaystyle g_{1} +g_{2} +\dotsc +g_{m} \geqslant p$. Where of course $\displaystyle c_{i} ,g_{i}$ are cost and gain of a used pair $s_i$.
To show it is NP-complete I have to show a Karp reduction.

There are some problems we've studies and so that I can use:
Clique, Composite, SAT - Satisfiability problem, 3SAT, CSAT, IS - Independent Set, VC - Vertex, Cover, DHC - Directed Hamilton Cycle, HC - Hamilton Cycle, DS - Dominating Set, SSS - Subset, Set, 3COL, Partition, Bin-Packing.
Since it's talking about a sum I thought of using Subset-sum. If I set $\displaystyle p=b=k$, and I set $\displaystyle c_{i} =g_{i}$ for each $\displaystyle i$, then it really is just a sum question, to find a combination of elements of sum $\displaystyle k$.
But what it's complicating it for me is that if I have $\displaystyle n$ elements, I will have $\displaystyle \frac{n^{2} -n}{2}$ pairs, and so these many different costs. How can I rewrite the $\displaystyle n$ elements of partition, into some $\displaystyle k$ elements here such that there are $\displaystyle \frac{k^{2} -k}{2} =n$ pairs?
I've thought maybe I can only assign the cost to the first $\displaystyle n$ elements, and then all the rest to $\displaystyle 0$, but then cost and gain must be natural numbers.
Any advice?


texts: Determining a value in an algorithm on its first run

texts:
I was given the following algorithm as a solution to one of my problems.
However, I am baffled at understanding how c' is ever initialized. The first if statement can never be reached, as c' is never set the first time. Can someone explain this to me? Am I just missing where c' gets set?

This is for Kleinberg and Tardos, Chapter 11, Question 12.


texts: Implementing a job-scheduling problem with multiple dependencies and variable tasks (time frames) using dynamic programming

texts:
I'm writing a "Chores Scheduler" in Python. It has to be implemented using dynamic programming and has to take in two types of chores, as below:

Regular chores with a start time and end time (a real-life example of this may be taking classes at the same time from Monday to Friday). I need 5 of these in my implementation with dependencies (see under inputs).
A list of jobs that may be executed at variable times (for example, I may go on a spontaneous dinner within a given timeframe OR I need to go to the post office a given day, which is only open between 9AM and 3PM). I need 3 of these, with dependencies (see under inputs).

Inputs: A list of all chores and constraints on each chore.

To remember: Some chores are regular, others are variable (see above). Additionally:
Chores have a weight (profit) which has to be optimized for. For example, going to lectures has a high importance/profit, while watching YoutTube videos may have a low profit/importance, even if I do both every day.
Chores also have dependencies, i.e. one task depends on the completion of another. Real life example: To finish a paper, I must have done research prior (these being two separate jobs).

Output: Optimal schedule to follow in order. The output has to be "Optimal weight/profit is: x by doing these following jobs 'Job2', 'Job5', 'Job3'.

My question is: I've looked up a myriad of possible solutions, from Open Shop to Job Shop to Regular Weighted Job Scheduling (link to GeeksforGeeks). None of the problem classifications match what I need or how I might implement this. Is there some kind of a classification of these problems? Any similar problems? I'm having a difficult time structuring the problem and how it can potentially be solved (other than through dynamic programming, which is mandatory for this task).


texts: Redundancy elimination in the superposition calculus

texts:
When proving theorems with the superposition calculus, we deal with three kinds of rules:

Generating rules: from pair of clauses A and B, generate new clause C while keeping the original pair, e.g. superposition in the general case.
Rewriting rules: from clause A generate new clause B, e.g. equality reflexivity, equality factoring; superposition with a unit equation can also be regarded as a rewriting rule.
Eliminating rules: delete a clause, e.g. subsumption, tautology elimination.

The question is, regarding the second category, can we perform a strict rewrite, replacing the original clause with the new one, or do we have to keep the original as well as the new one? In the case of equality reflexivity it looks like we can do the former, but for equality factoring and superposition with a unit equation it's not immediately clear whether this would preserve completeness.

Is there a general way of knowing which is the case? Or a list of which needs to be done in each case?


texts: Is there a basic proof that there exists some edit distance between two strings?

texts:
Title says it all pretty much. I do realize that often edit distance is defined as the minimum number of operations needed to transform one string to another, but I want something to point to that's even more general than that.

I recently saw a brain teaser that claimed that some string was connected in a network to another as "friends" given an edit distance of one. It then went on to claim that friends of friends, friends of friends of friends, etc. (with no given upper bound on the degree of separation), were also in the network of that original string. I can't see how this definition of network doesn't include every possible string, and so I think the brain teaser is ill-formed. Given sufficient edits, a string can transform to any other string, right? -- but is there a name for that observation? I think this is so fundamental as to be near-impossible to Google, but there is always the distinct possibility of me being an idiot.


texts:
I'm trying to figure out what this NP-hard problem is most similar to and therefore which solutions are available to me.

There are a fixed number k of bins, each with the same initial capacity c1. There are a number of items of different sizes packed into each of the bins, such that the sum of the sizes of the items in each bin is less than c1. In other words, we are given a viable solution to the bin packing problem.

If we now change the capacity of each of the bins to c2 < c1, can we redistribute the items so that the sum of the sizes of the items in each bin is now less than c2, in such a way that minimises the total amount of size moved. There is no limit on the number of items in each bin, just the sum of their sizes.

Illustrated as an example:

c1 = 20

|     |    |     |    |     |    |  4  |
|  3  |    |  2  |    |  1  |    |  2  |
|  1  |    |  1  |    |  7  |    |  3  |
|  4  |    |  7  |    |  4  |    |  4  |
|__3__|    |__4__|    |__4__|    |__5__|

First bin total = 11 < 20
Second bin total = 14 < 20
Third bin total = 16 < 20
Fourth bin total = 18 < 20

By changing c2 to 16, a (potentially sub-obtimal) solution is:

|  4  |    |  1  |    |     |    |     |
|  3  |    |  2  |    |     |    |  2  |
|  1  |    |  1  |    |  7  |    |  3  |
|  4  |    |  7  |    |  4  |    |  4  |
|__3__|    |__4__|    |__4__|    |__5__|

First bin total = 15 < 16
Second bin total = 15 < 16
Third bin total = 15 < 16
Fourth bin total = 14 < 16

We moved a 4 from the fourth bin to the first, and a 1 from the third bin to the second - giving a total movement of 5.

There are some similarities with a view problems I'm aware of, but nothing which quite is the same.

Formally, as a decision problem:

Given a capacity $C$, and a set of $B$ bins $\{b_1, b_2, ..., b_B\}$ each containing a number of items with varying sizes. Can we redistribute the items such that $\sum$ (contents of bin) $< C$ for each bin $\in \{b_1, b_2, ..., b_B\}$ where the total size moved is at most $M$.


texts: CLRS 4.4-3 Height of recursion tree for T(N) = 4T(n/2 +2) + n

texts:
I'm having a hard time with the following question:

Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n) = 4T(n/2 + 2) + n$. Use the substitution method to verify your answer.

This is not homework, I'm just practicing myself for an upcoming exam.

The thing I'm having a hard time with is the $n/2 + 2$, what will the height be of this recursion tree?

I came up with the following formula to calculate the cost of each level after a lot of labor:
$2^i n + 2^{i+2}(2^i -1)$ not 100% sure this is correct either.

Any help appreciated, really looking forward to the answer :D
I often make stupid mistakes and I just started doing algo's for my first time.


texts: Finding all feasible solutions to a multiple-knapsack program

texts:
How can I find all feasible solutions to a 0-1 integer program that I have based on a knapsack-style problem?

I have $n$ items and $m$ knapsacks. Each knapsack has a space limitation and each item occupies some space. I need to find all feasible combinations of items which can fit in the knapsacks.

The brute force approach is to find all possible combinations of items up to length $n$ and then evaluate each combination for feasibility.

My current approach is to formulate the problem as an IP where each item is a binary decision variable. I maximize the sum of decision variables provided the $m$ space constraints for each knapsack. This gives me the maximum number of items $r$ which can fit in the knapsacks. Then I use the following algorithm to find the set of feasible solutions:

Initialize two sets ---feasible and infeasible as empty.
Add all combinations of items with length $> r$ to infeasible set.
Formulate all combinations of length $r$. For each of these combinations which are not present in the feasible set, check feasibility. If feasible add this combination and all  sub combinations of length $< r$ to the feasible set. If infeasible, add this combination to the infeasible set.
Set $r := r-1$.
Repeat step 2 until $r = 1$.

Is there any other method which is more efficient than this approach?


texts: Turing machine and coming up with an idea

texts: I read many things about the Turing machine and understand how it works but what I can't get the grasp of (and what none of the books seem to try to teach) is how should I approach a problem I am given to solve? I mean: checking if a word is a palindrome, for example, consists of 11 states in the book I'm learning from. For my current state of knowledge, just sitting over an empty sheet of paper and coming up with all these states seems next to impossible, to say the least. When I try to do something like this, I get stuck immediately since I don't know what should I do to make these states work somehow "together". I don't have such problems when programming in some prog languages but here, I just can't figure out how I should approach something consisting of some n-teen states. Could you please point me some direction to learn about it?


texts: Prove the recursive enumerability of the class of NP-hard context-free languages

texts:
I was asked to prove that the next language is recursive enumerable :

$$L= \{ \langle G \rangle \mid SAT<L(G) \} $$

where $G$ is a context free grammar and there is a polynomial reduction from the SAT problem to the language that's accepted by $G$.

I can't seem to understand why this problem is in RE. Isn't determining whether a word is accepted by a certain CFG done in a polynomial time? What am I missing here?