texts: Grouping/Clustering results based on shared values

texts:
I have a data set that is similar to this:

10,000 jobs with 200,000 applicants which are linked to a job.

I'm looking to cluster the shared jobs based on applicants that they share, am I reinventing the wheel looking to build this or is there a common solution?

Most of the example I found all require a "distance" but I can't see how I could compute one in this case?

Edit: To add, the clustering criteria would be fairly straightforward more than X applicants (say 5) in common, with only a single cluster per job.


texts: Most efficient way to check if key exist on a table

texts:
Imagine a person called Albert. Albert lives in Europe and would love to move to America. One day he got his wish come true. A person called Margareta gave him a key. The value of the key is the same as the address for a house in USA. Albert doesn't have that much money to travel to America to confirm whether the key is a hoax or not, by going to the address of the key. He certainly doesn't have the money for a house in America. If the key turns out to be a hoax, Albert would have a very hard time to make a living in America. It would cost him dearly. One day, a postman who knew all the addresses in America visited Europe. He happened to meet Albert.

Can the postman carry a certain information that is less than the information of all addresses in America to confirm whether Albert's key is valid or not? Then what is the information and what kind of operations is made to make the confirmation?

Assume all information is numeric here.

Background:
I was looking at implementing a hash table for already known keys and I was wondering whether there exists efficient lookups where I don't have to visit a bucket in a hash table(America) to confirm whether a key exist or not.


texts: What is the abstract idea of a semaphore and how can we use it to implement mutual exclusion?

texts:
So I've got this so far to try and wrap my head around the abstract idea of a semaphore:

  A semaphore is a variable or abstract datatype (commonly an integer),
  used to control access to a common resource by multiple processes in a
  concurrent system.

I'm not sure that this definition fully encompasses the full idea of semaphores.

As well as this, I'm not sure how we could use them to implement mutual exclusion.

Any notes to help me understand this concept is appreciated!


texts: If the language of a TM is TMs which cannot self recognize, can the original TM?

texts:
I've been thinking about this one for a while:

  Consider the language of TMs which do not recognize themselves: $L_{s}=\{ \langle M\rangle ~|~ M \text{ does not accept } \langle M\rangle \}$. If $N$ is a TM where $L(N) \subseteq L_s$, then is $\langle N\rangle \in L_s$?

Intuitively, I'm pretty sure it is true. I pictured $N$ as a compiler, and imagined some machine $P$ that $N$ compiled. It seemed that if $P$ was not able to bootstrap, then $N$ wouldn't be able to either. But I'm having trouble thinking about this problem more formally.

Am I on the right track? A hint would be really helpful.


texts: Both $\overline{A_{TM}}$ and $\Sigma^*\backslash A_{TM}$ are not turing-recognizable?

texts:
if we define $A_{TM}$ and $\overline{ A_{TM}}$ as follows:
$$
\begin{align}
A_{TM}&= \{ \langle M,w \rangle |M \text{ is a turing machine and $M$ accepts $w$} \}\\
\overline {A_{TM}}&= \{ \langle M,w \rangle |M \text{ is a turing machine and $M$ do not accepts $w$} \}\end{align}
$$
$\overline{A_{TM}}$ and $\Sigma^*\backslash A_{TM}$ both are not turing-recognizeable. right?(a bit confused by the way $\overline{ A_{TM}}$ is defined. noramly $\overline A = \Sigma^*\backslash A$).
My reasons :
1.$\overline{A_{TM}}$ is not reconizable because: if it was then we could run two recognizer for $\overline{A_{TM}}$  and $A_{TM}$ in parallel and decides $A_{TM}$.
2. $\Sigma^*\backslash A_{TM}$ is not recongnizeable by fallowing lemma :
lemma:  $L$ and $\overline L$ recognizeable iff $L$ is decideable.
in fact both reasones are quite the same but in second one we are considring inputs ($\langle M,w \rangle$) which are not properly formated.


texts: Algorithm to assign producers to consumers with respect to connections

texts:
I am trying to analyze supply chains in a game and have come across this problem:

First, an informal description: I have producers and consumers. Each producer produces a certain amount of goods, each consumer requieres a certain amount of goods. Each producer is connected to some consumers (these connections have infinite capacity).

Is there a way to transport goods from producers to consumers so that each consumer has sufficiently many goods? Each producer can provide goods to multiple consumers and each consumer can accept goods from multiple producers. A producer also doesn't have to deliver the entire production, as the rest  can be discarted.

The connections form a bipartite graph with producers $p \in P$ and consumers $c \in C$ as vertices (so $V = P \mathbin{\unicode{x228D}} C$) and edges $E \subseteq (P \times C)$. Each producer has a positive production rate and each consumer a positive consumption rate.

We model how much is transported over each connection with a weight function $w: E -> \mathbb{R}$. For each producer $p$ , we get the required production by summing up the weights of all edges incident to $p$. This must not be higher than the production of $p$.

Similarly, for each consumer $c$, we get the total delivery by summing up the weights of all edges incident to $c$. This must not be lower than the consumption of $c$.

Does such a $w$ exist for a given graph, production rate and consumption rate?

The left example has such a function, the right one does not:

I am pretty sure that if we allow negative $w(e)$, the problem is very easy (for connected graphs, just compare total production to total consumption). Therefore, it probably makes sense to restrict $w(e) \geq 0$.

I have tried to find similar problems, but most flow problems have limited flow rates and sources with infinite capacity (whereas here, it's exactly the other way around). I also know about the Assignment problem, but I don't think it applies here.

Perhaps there is a way to slowly remove consumers and producers. In the first example, we know that the top producer can only supply the top consumer, so we could just remove the producer and reduce the consumption rate on the right. It might also be possible to merge multiple producers and consumers if they all supply each other. However, I don't think that these operations alone suffice to solve the problem in all instances.

Perhaps there is no efficient algorithm, so I've also tried proving that the problem is NP-complete, but my attempt to reduce SAT to this problem wasn't successful.

This probably isn't the most enjoyable way to play Anno, but at this point, it don't want to give up...


texts: Array contains elements that differ by K correctness proof

texts:
I have been puzzling over an algorithm that decides whether a sorted array of numbers contains two numbers that differ by k. I do not intuitively understand why this algorithm works, or what thought process might have led me to think of this algorithm on my own, although I believe that I can prove it's correctness.

CONTAINS_DIFFK(arr, k)
    n = size(arr)
    if n == 1 return false
    i = 1
    j = 2
    while i <= n and j <= n
        if i != j and arr[j] - arr[i] == k
            return true
        if arr[j] - arr[i] < k
            j++
        else
            i++
    return false

My questions are:

Is the following proof sound
Is there a more concise way to prove correctness?
What thought process might have lead me to derive this algorithm on my own? (I had to look up the solution)

Proof by Induction

Let arr be an arbitrary sorted array of integers of length n. Assume for the sake of induction that CONTAINS_DIFFK return true if arr contains two numbers which differ by k and false otherwise. Let arr' be an arbitrary sorted array formed by adding a single arbitrary integer to the end of arr. We prove that CONTAINS_DIFFK return true if arr' contains two numbers which differ by k and false otherwise.

Assume that it is the case that arr contains two elements that differ by k. By our inductive assumption, CONTAINS_DIFFK will return true for arr. Because CONTAINS_DIFFK immediately returns after finding two elements that differ by k without considering further elements, and the first n elements of arr and arr' are identical, the n+1'th element of arr' will not be considered and will not affect the output of the algorithm. Thus CONTAINS_DIFFK returns true for input arr'.

Therefore we need only consider the case, which is now assumed, in which arr did not already contain two elements which differ by k. We must consider the cases in which the n+1'th element of arr' does not differ from any of the first n elements by k and the case in which it does.

First, consider the case in which the n+1'th element of arr' does not differ from any of the first n elements of arr'. We show that the algorithm returns false. Let i' be the value of i when j is incremented to be equal to n+1. Note that i' <= n. Now simply note that the last element of arr' will be compared to some subset of the elements after and including the i'th element. Since we assumed that the last element of arr' does not differ from any element by k, the condition for returning true will never be met and false will be returned.

Finally, we consider the case in which there exists some element e in arr which differs by k from the n+1'th element of arr', and show that the algorithm returns true. Again, let i' be the value of i when j is incremented to n+1 while processing arr. Now, critically, note that j was incremented to n+1 because arr[n] - arr[i'] < k. If we note also that arr'[n+1] >= arr'[n] (because it is sorted) and arr'[n+1] - e = k, then we  may derive e > arr[i']. Thus, we note that i will be increased from i' up to the index of e at which point CONTAINS_DIFFK will return true as desired.

Base case

Let arr be an arbitrary sorted array of two integers. We may trace through the execution of this algorithm and note that if arr[2] - arr[1] then it will return true and it will return false otherwise. Thus, the induction is complete.


texts: I want to learn more about computer science. Where should I start?

texts:
Hello computer scientists,
I am a mathematician. I have taken some undergraduate courses in C++, Python, assembly language, boolean algebra, logic, graph theory, etc.  I would like to learn more about computer science because I think it's cool. Could you give me some advice as to where to start? Thanks!


texts:
Also,

is n O(n lg n)?

I'm trying to understand this notation to better understand Big O. (Apparently they ask you questions about Big O in interviews, so I wanted to learn). I found a few formulas that I didn't understand.


texts: What makes it so difficult to prove P =/≠ NP? — The subset sum issue

texts:
I can't understand or imagine some fact about NP-hard problems. If I understand it correctly there is only one polynomial-time algorithm needed – for whichever NP-complete problem – to prove that P = NP.

Let's take the subset sum problem, which is NP-complete. It says that given a set such as $\{-7, -3, -2, 5, 8\}$, we're able to find out if there exists a subset of this set summing to zero, within exponential time (and obviously check a solution, for instance $\{-3, -2, 5\}$ within polynomial time).

So if someone finds an polynomial-time algorithm for this task, he'll show that P = NP, right?

EDIT: I removed:

  Assuming, that opinions whether P = NP or P ≠ NP amongst computer scientists are about 1:1 (this site claims that they're ~ 52% and ~44% respectively)...

As the guys noticed in comments, it's wrong. I should say the proven cases are like 1:1.

Okay, so it gets more intuitive now. I mean, P ≠ NP actually seems to be 'more likely now':

However, assuming that there are still, say, 5-10% of formally educated people who believes that P = NP and the cited problem is not, say, the most complex one, how is that even possible that no one  of them had found a polynomial-time algorithm yet OR (maybe more likely?) no one of their opponents proved that there's no such an algorithm? Or, does it also mean that (in terms of those people's opinions, again) the 'chances' of there being  such an algorithm are like 1:1, too?

From my (maybe naive) point of view, the subset sum problem seems so simple to crack – at least for advanced computer scientists.

As you're probably aware of, searching in the Net would not help me much as I just can't deeper into this problem. I've got no such mathematical knowledge to even comprehend it more.


texts: Algorithm to determine a minimal cost graph

texts:
I'm trying to solve this problem:

  Given a collection of cities and the number of commuters between cities, design a network of roads for minimal cost where cost includes the cost of building the roads, and traveling of commuters. (So if more commuters use one edge, that edge will have a modified cost since the commuters want to get to their destination quickly)

I've been treating the cities as nodes in a graph and the roads as edges. I want the weight of the edges to be dependent on the length of the edge (longer edges cost more) and somehow dependent on how many commuters are using that edge.

My thought was to try doing something like a Minimum Steiner Tree, which if cost didn't depend on the commuters would minimize the cost of building the roads, but I'm not convinced that the solution to this should be a tree. And if I try to find a Minimal Spanning Tree or Minimum Steiner Tree I'm not sure how to deal with the fact that I don't know the edge cost until I know the full tree/graph. That is if people want to travel from A to B and we remove the edge from A to B, those people will now have to travel from A to C then from C to B which will modify the edge cost between A and C and C and B.

Does anyone have any ideas on how to deal with the changing edge costs or know of a better way to solve this problem?

edit: You can make any sort of network you want, the roads can go straight from one city to another, or to any intermediate node(s) which can be placed anywhere in the plane. I'm planning on making the cost of building a road just a constant times the length of the road. For the cost of commuters I think another fractional constant times the distance they have to travel along the roads times the number of commuters traveling along that section of road.


texts: $ACC^{0}$ vs Poly-size circuits of bounded degree

texts: We know that NEXP $\not\subset ACC^0$ (Ryan Williams'10 Result). Also, We know that even $\Sigma_{2}^{P}$ cannot have polynomial circuits of bounded degree i.e. $SIZE(n^k)$ for some $k \in N$ (Kannan's Result). Does this give a hint towards $ACC^0$ is far more powerful than polynomial circuits of bounded degree? Are they even comparable?


texts: First Order interpretation of arbitrary structures as a graph

texts:
I am currently trying to get some intuition on the concept of First Order reductions, and have come across this exercise question by Immerman, dubbed "Everything is a Graph".

Given some arbitrary relational structure $S$ of some vocabulary $\sigma$, show that there are first-order queries $I$ and $I^{-1}$, such that $G:=I(S)$ is a directed graph, and $I^{-1}(G)$ is isomorphic to $S$.

I would be grateful for some hints and proof ideas, as I struggle a bit with seeing how the encoding would work.


texts: Which Machine Learning algorithm should I use to detect abnormal behaviour in a home-automation environment

texts:
I want a system to learn what is "normal" in a home-automation(KNX) environment.

I have data like, address/group address, timestamp,... is there a matching machine learning algorithm I could use in that situation?

I started to read a book abt Machine learning, but I'm not quite sure which kind of algorithm I need

If machine learning is the right thing for me here to use, which language should I use? I have most experience in Java, but also little in R and Python(but nothing machine learning related yet)


texts: What is the reason behind a specific ordering of the rows in the generator matrix for Hamming codes?

texts:
What order the rows are in a Hamming generator matrix are irrelevant for the Hamming coding to work, given the check matrix is built accoridngly.

In order to limit cognitive overload, it could have been decided that the "official" way of doing it should be either all data rows first then all parity rows after, all in ascending order, or just all rows in ascending order. In that case, in the description of a communications protocol it would be enough to specify the number of bits without providing the generator matrix, and everyone would know how to implement it. Very simple software libraries could be written which implement it.

However, after looking at some implementations, this is not the case. People seem to use arbitrary matrices, such as

$$\begin{pmatrix}
1 & 1 & 0 & 1  \\
1 & 0 & 1 & 1  \\
1 & 0 & 0 & 0  \\
0 & 1 & 1 & 1  \\
0 & 1 & 0 & 0  \\
0 & 0 & 1 & 0  \\
0 & 0 & 0 & 1
\end{pmatrix}$$

Is there a reason why one such ordering would be superior to other orderings?


texts:
$ALL_{REGEX}$ is the computational problem of determining for regular expression x if $L(x) = \Sigma^*$.  In a proof for $ALL_{REGEX} \in PSPACE$, the following non-deterministic turing machine $M(R)$ on regular expression $R$ is given

Convert R to an NFA $N = (Q,\Sigma,\delta,S,F)$;   $K = S$;

While $K \cap F \neq \emptyset$

Non-deterministically guess a character $a \in \Sigma$
S' = Compute the new set of states from character $a$ and states $K$
K = S'

The proof states that iff $M$ does not halt, then $L(R) = \Sigma^*$.  Suppose we have $\Sigma = \{a,b\}$ and R = a*. Why doesn't this machine halt?  Won't there be a single path of guesses (namely, a*) that goes on forever, implying the whole machine does as well?

The algorithm goes prove that after $2^{|Q|}$ steps, we know the language must be $\Sigma^*$, so we accept instead of looping.  I understand the intuition of the algorithm and how it would be implemented deterministically  , but I'm confused as to how the algorithm above works when the NTM formalism accepts if any path accepts and it is making me question my understanding of NTMs.


texts: Finding longest subset arithmetic progression with given difference

texts:
Given a list of distinct positive integers, I am trying to find the largest subset that forms an arithmetic sequence with a given difference D.

For example, given D = 5, with the set of numbers 1, 5, 10, 6, 7, 8, 15, 11 the longest sequence would be 5, 10, 15

I have tried using sets to solve this but I can't find a solution faster than $O(n^2)$. For example, I have tried adding all items in the array to a TreeSet. This automatically orders the elements, after which I brute force check all the possible sequences. Am I on the right lines or is there a better approach?


texts: Start learning about Theory of Distributed Systems?

texts: What's the best way that anyone can do to have a good introduction to the theory of distributed system, any books or references, and topics should be covered first and requirements to start learning in this topic.


texts: Approximate max weight path in directed graph

texts:
Context
This question is related to the fact one can't use Bellman-Ford to find max weight paths in directed graphs with cycles. The reason is that giving a new graph $\tilde{G}$ with negative weights (e.g. $\tilde{w}_{ij} = - w_{ij}$) will result in cycles with negative sum, thus no minimum cost walk exists in $\tilde{G}$.
General question
How well can we approximate the maximum weight path between $i$ and $j$ in $G$, using the shortest path algorithm on a graph $\tilde{G}$ with transformed weights $\tilde{w}_{ij}$ ?
In my case, one has $w_{ij}\in\mathbb{N}\setminus\{0\}$. The transformed weights $\tilde{w}_{ij}$ can be obtained using any function, but I assume a decreasing function $f$ is well adapted so that $w < w' \iff f(w) > f(w')$.
My approach
I am currently trying to use $f(w) = \dfrac{1}{w}$, in this context we have two important paths given a fixed path length $L$.
Denote a path $p = (i_0i_1, i_1i_2, i_2i_3, \dots i_{L-1}i_L$) with weights $W = (w^{(1)}, w^{(2)}, w^{(3)}, \dots, w^{(L)})$,
denote the maximum weight path of length $L$ by $p^*$ with weights $W^*$ achieving
$$ W^* = \arg\max_W\{\mathtt{Cost}(W)\} = \arg\max_W \sum_{k=1}^L w^{(k)}$$
and the path $p_*$ achieving minimum transformed cost with weights $W_*$
$$ W_* = \arg\min_W \sum_{k=1}^L \tilde{w}^{(k)} = \arg\min_W \sum_{k=1}^L f(w^{(k)}) = \arg\min_W \sum_{k=1}^L \dfrac{1}{w^{(k)}}$$
Specific question
In this specific context, do we have the approximation $\mathtt{Cost}(W^*) \approx \mathtt{Cost}(W_*)$ ?
Or is it "very wrong" to replace $W^*$ by $W_*$ ? What would be the distribution of the relative error defined as
$$E_r = \dfrac{\lvert\mathtt{Cost}(W^*) - \mathtt{Cost}(W_*)\rvert}{\mathtt{Cost}(W^*)}$$
Statistical analysis
I have tried a quick statistical analysis as follows:

Letting $L\in\{3,4,5,6,7,8\}$
sampling $w \sim \mathrm{Uniform}(1,w_{\max})$
The value for $w_{\max}$ was also picked from the set $\{50, 100, 150, 200, 500\}$
for each combination of $L,w_{\max}$ I computed $10^5$ values of $W^*, W_*$ using $10^3$ candidate weights $W_i$

The results:

In $80.8\%$ of cases we have $\mathtt{Cost}(W^*) = \mathtt{Cost}(W_*)$ and even better $W^*=W_*$
When computing the relative error $E_r$ one finds that $82.6\%$ of error values are less than $0.001$, $89.7\%$ less than $0.01$ and $99.9\%$ less than $0.1$

The histogram for $E_r > 0$ is as follows


texts: What is the advantage of Greibach Normal Form over Chomsky Normal Form?

texts: I wanted to know the pros and cons of Chomsky normal form and Greibach normal form.


texts: Hardness of an instance of a problem independent of algorithms?

texts: The paper “Where the really hard problems are” (https://www.ijcai.org/Proceedings/91-1/Papers/052.pdf) and others that cite it provide evidence that lots of algorithms for many NP complete problems (when suitably parametrised) perform poorly on the problems that lie on the phase transition from under constrained to over constrained which occurs as the parameter is increased. Is there a way to assign hardness to an instance of say 3SAT, without invoking or involving a specific algorithm that may perform poorly on that instance? Or is this line of thinking necessarily restricted to specific algorithms?


texts: Why do they say `A, B, C, ... implies M` instead of `A∧B∧ C∧ ... implies M`?

texts: The conclusion follows from all the premises. It seems to me that this means that conclusion from the conjuntion of the premises. Right? Why does logic uses comma instead?


texts: What is a good reference for NP hardness in the machine learning/optimization/operations research context?

texts:
I am reading some papers in machine learning and at the very beginning (introduction) you will see statements of theorems that says, for example:

Theorem 1.1. For any constant ϵ > 0, it is NP-hard to find a
halfspace that correctly labels (1/2 + ϵ)-fraction of given examples
over {0, 1} n even when there exists a monomial that agrees with a (1
− ϵ)-fraction of the examples.
https://people.eecs.berkeley.edu/~prasad/Files/mono.pdf

At this point, the definition of NP-hard is not even defined. I have seen many examples like this, which makes me wonder
"Do all these  thousands of authors have the same definition of NP-hard/complexity notions"?
"These contexts seem so different from the usual contexts where NP-hardness come up such as graph coloring or traveling salesman problem, how can I be sure that these notions of complexity/NP hardness are equivalent?"
Can someone point out a good reference for studying complexity theory in a machine learning/operation research/optimization context? Many thanks!


texts:
Problem: Suppose $V$ is an AVL tree (a self-balancing binary search tree) of $n$
  elements. After the insertion of $n^2$ elements, what would be its
  height?

My idea: the height of an AVL tree is originally $O(\log(n))$ where $n$ is the number of elements. After insertion of $n^2$ elements, its height will be:$$O(\log(n+n^2))=O(\log(n^2))=O(2\log(n))=O(\log(n))$$

My answer would be $O(\log(n))$ but I'm having doubts.

Why is the asymptotic complexity of the result the same despite the fact that there are more elements?


texts: Which "entity" is working at more deeper level than Characters of a program?

texts:
It is commonly told that, while we write a program, we input with our language (A, B, C, D etc), whom computer translates into machine language into machine language made up of Zero (0) or switch off and One (1) or switch on, a.k.a. ASCII code.

Letter  ... ASCII Code  .... Binary

A ...........   065 ............  01000001

B ...........   066 ............  01000010

But I don't think it is that simple.

When I type A on the keyboard, the programming prompt (say C-programing) screen shows me a letter A or a (depending upon caps lock or not) that have a definite geometric shape and orientation. There are other factors, like which part on screen the letter will be shown.

Even if A=01000001 I don't think just turning off 6 pixels (Six ZEROS) and turning on 2 pixels (two ONES) it is possible to render  triangular capital-letter A.

Now my question is; What is the "Entity" (maybe a software) which is rendering a small 0-1 code into a geometric figure (glyph)? Such as 01000001 into a triangular shape (A) or rendering 01000010 into a vertical line with two bulge at right hand side (B) etc.


texts: Does polynomial time reduction from CNFFAL to CNFSAT is also polynomial time reduction from CNFSAT to CNFFAL?

texts:
CNFSAT is the language of all strings that are encoding of satisfiable boolean formula in conjunctive normal form while CNFFAL is the language of all strings that are encoding of falsifiable boolean formula in conjunctive normal form.

Any boolean formula is satisfiable if and only if exists an truth assignment of True and False to the boolean variables so that the boolean formula evaluates to true.

Any boolean formula is falsifiable if and only if exists an truth assignment of True and False to the boolean variables so that the boolean formula evaluates to false.

CNFFAL is in $\Bbb{P}$, because the deterministic Turing machine that decides CNFFAL in polynomial time only needs to find falsifiable clause and deciding whether or not disjunction of literals is falsifiable is as hard as deciding 1SAT that is deciding the satisfiability of conjunction of unit clauses, where each unit clause is single literal, and it is also in $\Bbb{P}$.

Because of the fact that $\Bbb{P\subseteq NP}$ CNFFAL is also in $\Bbb{NP}$ and also non deterministic Turing machine to decide CNFFAL is to guess and choose an truth assignment non deterministically and accept if the input boolean formula evaluates to false, reject otherwise.

According to the fact that $CNFFAL\in\Bbb{NP}$ and to the paper of Cook, Levin and Karp that was submitted in 1971, it is also true that $CNFFAL\le_PCNFSAT$.

I want to know if $CNFFAL\le_PCNFSAT\implies CNFSAT\le_PCNFFAL$.

In other words I want to know if it is also true that $CNFSAT\le_PCNFFAL$, because I read the 1971 paper of Cook, Levin and Karp and as I understood, the deterministic polynomial time reduction from an arbitrary NP language to satisfiability problem is done by first describing the non deterministic Turing machine that decides the arbitrary NP language in polynomial time and then there is polynomial time deterministic algorithm to generate the boolean formula that is true on every accept path/route of the non deterministic Turing machine for the input string and it is false on every reject path/route of the non deterministic Turing machine for the input string.

Therefore the string is in the arbitrary NP language if and only if the non deterministic Turing machine that decides the arbitrary NP language in polynomial time accepts the string and the non deterministic Turing machine accepts the string if and only if there exists an accept path/route, i.e. the non deterministic Turing machine has an accept path/route for the input string and there exists an accept path/route or the non deterministic Turing machine has an accept path/route for the input string if and only if the boolean formula is satisfiable.

Let $NTM_{CNFFAL}$ be the non deterministic Turing machine that decides CNFFAL in polynomial time as described above.

Therefore if the input boolean formula $\alpha$ is falsifiable then there exists an accept path/route, i.e. $NTM_{CNFFAL}$ for $\alpha$ as input has accept path/route, but if $\alpha$ is also satisfiable then there also exists reject path/route, i.e. $NTM_{CNFFAL}$ also has reject path/route for $\alpha$, but if $\alpha$ is unsatisfiable then all paths/routes of $NTM_{CNFFAL}$ are accept and therefore the boolean formula $\beta$ generated from $NTM_{CNFFAL}$ is tautology and not falsifiable.

Therefore $\alpha$ is unsatisfiable if and only if $\beta$ is tautology.

Therefore $\alpha$ is satisfiable if and only if $\beta$ is falsifiable.

So my question is does $CNFSAT\equiv_PCNFFAL$?


texts: Constructing a Context Free Grammar for checking non-equality of strings

texts:
I have been studying the book Introduction to Computation by Michael Sipser on my own, and I'm stuck on this exercise from the chapter on Pushdown Automato and Context-Free Languages. The exercise is to show that  $$A=\{x\#y\,|\, x \neq y\}$$ is a context-free language.

I'm having a hard time proving this because of the second string not reversed. I've tried both making a context-free grammar and a pushdown automata, but in both cases I can't figure out how to make/check that the initial characters of both $x$ and $y$ are the same.

I would appreciate any hints that could help me get to the answer.


texts: How does Hoare's quicksort work, even if the final position of the pivot after partition() is not what its position is in the sorted array?

texts:
All variable names are from Quicksort's wikipedia page's Lomuto's and Hoare's quick sorts pseudocode.

If p is what is returned by the partition function, Hoare divides his array from lo to p and from p+1 to hi, while Lomuto divides his array from lo to p-1 and from p+1 to hi.

I may be wrong about this, but Quicksort's philosophy is...

Take an element in the subarray (pivot).
Rearrange the subarray in such a way that all elements left of the pivot are smaller than the pivot, and all the elements right of the pivot are greater than the pivot.
Divide the array about the pivot. Repeat the process for the two smaller sub-subarrays. Keep doing this until you encounter an array with only one or less elements, because that is already sorted.

I find Hoare's partition to be more simpler to understand, than Lomuto's. Hoare's partition simply instructs us to start from the left end and the right end and to keep moving towards each other. If left marker encounters an element greater than the pivot, then the left marker pauses, and waits for the right marker to find an element smaller than the pivot. Then they exchange the elements, so that the left marker has the smaller element, and the right marker has the greater element. They keep doing this until they meet. Very straightforward.

Lomuto's partition, can be considered as a snake, of sorts, made of two parts, a head and a tail. The pivot is fixed (I usually take the last element as the pivot for Lomuto). The snake starts from the left-hand side, and stops just before the last element. When the snakes encounters an element smaller than the pivot, that element goes to the tail and the length of the tail increases. When an element greater than the pivot is discovered, that element goes to the head of the snake. Finally, the pivot is placed between the tail and the head. It's pretty clear but not as intuitive or efficient (in some cases) as Hoare's partition.

What confuses me is that Hoare's partition doesn't ensure that the position of the pivot after the partition has run its course, will be it's position in the final, sorted array. The only pattern that I could recognise in Hoare's partition was that i is at the final position of the pivot and that j is either i or i-1, j and i being the right and left markers.

Lomuto's partition, however, guarantees it. So, when I step back and look at the bigger picture, it makes sense for Lomuto to divide the array from lo to p-1 and from p+1 to hi. But, I can't understand how Hoare can divide his array from lo to p and from p+1 to hi, make up for his partition not putting its pivot in its rightful place.


texts:
This may be a naive question but I am a bit clueless. I was under the opinion that given two NP complete problems, $P1$ and $P2$, if $P2 \in APX$ and $P1 \notin APX$, then we cannot have a direct reduction $P2\leq P1$ but we can have a reduction $P1\leq P2$.

In this paper on page 165 http://www.lancaster.ac.uk/staff/letchfoa/articles/cut-projection.pdf, there is a reduction $MAXCUT \leq STABLESET$. That is, given an instance of STABLESET, I can find an instance of MAXCUT. Why cant I use the approximate solution for MAXCUT to find an approximate solution to STABLESET?


texts: When is an ATM network connection superior to an IP connection?

texts: Currently learning about Networks in Computer Science, and I don't understand why you would ever use an ATM (asynchronous transfer mode)  network instead of IP, as IP doesn't have to be as reliable and can be set up much more quickly, and is what the entire Internet basically uses.


texts: Ambiguous grammar? Could the grammar be parsed by SLR parser?

texts:
I got one grammar:

re2: re1 $

re1: expr == expr | expr != expr | expr < expr | expr <= expr | expr >= expr | expr > expr | expr

expr: expr + term | expr - term | term

term: term * factor | term / factor | factor

factor: (expr) | num | id

num: (0|1|2|3|4|5|6|7|8|9)num | ε

id: (a|b|....|z|A|B|....|Z|)id | ε

Here are the FOLLOW sets:

FOLLOW(r2) = {}
FOLLOW(r1) = {$}
FOLLOW(expr) = {=,!,<,>,+,-,)}
FOLLOW(term) = FOLLOW(factor) = FOLLOW (id) = FOLLOW (num) = {=,!,<,>,+,-,),*,/}

Now this grammar clearly got reduce-reduce conflict from
num: ε and id: ε because FOLLOW(num) ∩ FOLLOW(id) != empty set

Now let's say I fix the grammar by  doing the following (I assume it is mistake in the grammar because (ε == ε) makes no sense):

num: (0|1|2|3|4|5|6|7|8|9)num | (0|1|2|3|4|5|6|7|8|9)
id: (a|b|....|z|A|B|....|Z|)id | (a|b|....|z|A|B|....|Z|)

Now my question is, is this grammar SLR i.e can it be parsed by SLR parser? I know by building the parser I can find out but on exam I can not make the whole parser and then determine (I would lose lot of time).


texts: Proving sets of regular expressions and context free grammars are decidable

texts:
Consider below languages:

$L_1=\{<M>|M$ is a regular expression which generates at least one string containing an odd number of 1's$\}$
$L_2=\{<G>|G$ is context free grammar which generates at least one string of all  1's$\}$

Its given that both above languages are decidable, but no proof is given. I tried guessing. $L_1$ is decidable, its a set of regular expressions containing

odd number of $1$'s, or
even number of $1$'s and $1^+$ or
$1^*$

So we just have to parse regular expression for these characteristics. Is this right way to prove $L_1$ is decidable?

However, can we have some algorithm to check whether given input CFG accepts at least one string of all 1's? I am not able to come up with and hence not able prove how $L_2$ is decidable.


texts:
I have a problem (A) on undirected graphs that I wish to show is NP-Hard. I can show that there is a reduction from a well known NP-Hard problem (B) to A by constructing an instance of A with a complete graph that solves B.

Since undirected graphs generalize complete graphs, am I safe in saying that A is NP-Hard for undirected graphs? Something about that doesn't seem right to me, since problem A on complete graphs is essentially the "non-graphical" version of the problem. Am I missing something?

Disclaimer: I am new to proving hardness results.


texts:
I'm working through an example that looks like a fairly simple Karnaugh map and simplification, but I feel stupid that I can't seem to understand the correct answer.

This is the map:

My groupings:

This is the equation:

But I don't know how it simplifies to the correct answer here:

I understand why the NOT A goes outside of the bracket, but I don't see how the C OR NOT C just becomes a C inside the bracket?


texts: Why the language of unary primes isn't regular

texts: I have some difficulties proving that the language of unary primes ($L=\{1^p\mid p\text{ is prime}\}$) is not regular using the pumping lemma. Any suggestions?


texts:
I'm a newbie and a paper I'm reading specifies the following grammar:
ChangeDomain  ≔    Domain ∣ Domain [{Changeable}] ({NewDomain})

Changeable  ≔  ChangeDomain ∣ CP∣ Domain∣ Domain ⊳ NewDomain

Domain; NewDomain; Need    ≔                              Name

I'm new to grammars and wondered whether an experienced reader could immediately identify it as Backus-Naur Form, or might more information be required to ensure that it is not some other grammar?
Also in this vein, could someone please recommend introductory resources for learning more about grammars?
Many thanks
Max


texts: If there are two longest paths in a connected graph with path lengths of 79 (going through 80 vertices each). How can I prove that they share more than 1 vertex.


texts: Make maze connected removing minimal number of obstacles

texts:
Input consists of two numbers $n$ (number of rows) and $m$ (number of columns) with the maze consisting of $2\cdot n + 1$ rows, where each row consists of $2\cdot m + 1$ symbols: '+', '-', '|', '.'

First and last rows stand for horizontal borders of maze.

First and last columns stand for vertical borders of maze.

Cells with even coordinates are '.' symbol

Cells with odd coordinate are '+' symbol

Other cells can be '.'   , '|' or '-'

We should change minimal number of '|' or '-' in order to have connected inner space of maze (connected means that every '.' is connected to others).

Consider input n = 2, m = 3 with maze
\begin{matrix}
 +&  -&  +&  -&  +&  -& +\\
 |&  .&  |&  .&  .&  .& |\\
 +&  -&  +&  -&  +&  -& +\\
 |&  .&  |&  .&  .&  .& |\\
 +&  -&  +&  -&  +&  -& +
\end{matrix}

The answer is one of the possible solutions, for example
\begin{matrix}
 +&  -&  +&  -&  +&  -& +\\
 |&  .&  .&  .&  .&  .& |\\
 +&  .&  +&  -&  +&  -& +\\
 |&  .&  .&  .&  .&  .& |\\
 +&  -&  +&  -&  +&  -& +
\end{matrix}

My idea is to make groups of connected inner spaces (in this picture we will have 4 groups with two groups consisting of 1 dot and two others consisting of 3 dots) and then to reduce amount of them while it remains only one.

Will this work or maybe there is a better solution to this problem?


texts:
Unicode has an abundance of open circles, diamonds and boxes. Using these, we can typeset linear-time temporal logic formulas such as

$$
(\mathop{⬦}ψ)\ \,\land\ \,\mathop{⬦}(θ\ \mathsf{U}\ \mathop{◻}\mathop{○}φ)\ \ .
$$

However, in my browser, the sizes of the symbols vary too much; the heights don't match, and the result looks ugly. The same happens in LaTeX (though, you could fiddle with sizes there manually in some circumstances, but it's a mess). Are there any "proper" Unicode codepoints made specifically for typesetting LTL formulas? I failed to find any, but, maybe, I have not looked everywhere. As the pre-Unicode LTL standard take a look into the papers and books by Manna/Pnueli, e.g., http://theory.stanford.edu/~zm/tvors3.html .

Crosspost: http://latex.org/forum/viewtopic.php?f=46&t=32886


texts: Efficient approximation for find all the nodes and edges which match with some sub-tree in a graph

texts:
Let's suppose that I have a big digraph D and a small tree T (small w.r.t D), both directed, D can be connected or not, but T is connected.

Here an example:
Let's say that D is as follow:

And T is the following tree:

So I would like to identify the nodes and edges in D that can potentially match with T. In other words, I would like to color in red the set of nodes and edges that participate in any isomorphism from T to D. Something like this:

What efficient algorithm can I use? I was reading about sub-graph isomorphism, but in my case, I don't have necessarily the label of edges, and I'm worried about the complexity. Are there other approaches?

About the output of the algorithm, the node P, for example, is red because don't exist any way that P with a combination of all their neighbor's nodes match with T due to his pattern which needs 4 consecutive nodes with edges pointing to the same direction, like a chain.


texts: How does modulus affect the regularity of language?

texts:
the question is as follows, further the notation used are standard as used in theory of computation
$$L = \big\{ w : w \in \{a,b\}^*,\ |n(a) - n(b)| = 2k\}\,.$$

Beware 'K' is not a fixed integer its a set of natural number , so 2k means all natural nunbers divisible by 2 and so on for 3k , 4k... .I think the above language is irregular or its finite automata can't be formed. Firstly the above question in basic language can be thought of as modulus of difference of number of $a$ and number of $b$ is divisible by $2$ or is even , similar to this reasoning we can extend this to more general like $3k$, $4k$, $5k$,... and so on. Secondly we know that any condition which have comprise the difference between the symbols would have infinite possible comparison between symbols, like an equation of
 $n(a) - n(b) =0/1/2/3...$ needs infinite states of finite automata which makes them irregular.

But here with the use of modulus it seems no different as here also we will need many comparison between symbols.

Thirdly its more of a general question like when define regularity of language $L$ over condition like,  $n(a) - n(b)\bmod 3 =0$, we say the all strings can be classified as having either remainder $0$,$1$,$2$ which by using Myhill-Nerode theorem proves the language regular. But why cant we use the same analogy over the relation like $n(a) -n(b)=2$ saying the all the strings would either have a difference $2$ or not. Further if you could answer the regularity of $n(a)- n(b) = 2k$, also how does taking modulus effect its regularity and how does it makes the states of finite automata finite which before applying modulus were infinite if you could a graphical representation would be appreciated.


texts:
An algorithm is a finite sequence of operations on an abstract machine. (Correct me, if I am not correct).

If two algorithms can take the same set of inputs, and for each input, they generates the same sequence of intermediate and final results/output, are they the same algorithm?

What I am thinking is if an algorithm can be thought of just as a mapping from the set of inputs to the set of sequences of intermediate and final results/output.

Thanks.


texts: Where can I find practice for given atom instructions, implement ME

texts:
I'm trying to practice for my upcoming distributed systems test.  My teacher said that their will be a problem where he'll give us atomic instructions and we're going to have to implement Mutual Exclusion (ME) using those instructions.

Where can I find practice problems/solutions for these types of problems?  I can't seem to find them anywhere.


texts: Proof of a greedy algorithm concerning “Buy and Resell Problem”

texts:
"Buy and Resell Problem" can be described in the following way:

There are $n$ cities. For each city, the price of products in this city is given (a positive number). Now a person will travel from city 1 to city $n$, one by one. When reaching a city, he can buy exactly one product with the price in this city, or sell exactly one product if he currectly has at least one product. He can also do nothing and then go on to the next city. The problem is how to plan a strategy so that he can earn maximal money. He has unlimited money initially.

For example, if $n=5$ and the prices are 3,2,5,1,4, then the maximal profit he can earn is $5-2+4-1=6$.

There is a correct greedy algorithm to this problem. When reaching city $i$, consider all $j$ in $1 ... i-1$, and find a $j$ with lowest price such that he doesn't buy a product in city $j$ (he could have sold a product in city $j$). If such $j$ does not exists or the price of city $j$ is higher than city $i$, he simply does nothing in city $i$. Otherwise he buys a product in city $j$ and sells it in city $i$. If he has sold a product in city $j$, it means he does nothing in city $j$ after finishing the $i$th city. The algorithm runs all $i$ in increasing order, and finally gives the best strategy.

The pseudo-code can be written as:

maintain a set s which is empty initially
maintain a boolean array named sell whose items are false initially
profit = 0
for i in 1 to n
  if s is not empty
    select an item j in s with the loweset price
    if price_j is lower than price_i
      profit += price_i - price_j
      if sell_j == true
        sell_j = false
      else
        erase item j from set s
      endif
      sell_i = true
    endif
  endif
  insert i to set s
endfor
output profit

The solution is quite simple and can be easily implemented using a priority_queue, which takes $\Theta(n \log n)$ time in total, but how to prove its correctness?


texts:
Say I have 3 compartments in my backpack: red, green, blue and 3 sets of items: red items, green items and blue items which all have a weight and benefit. I also have a requirement around the total number of total items that MUST be placed in each compartment of the backpack. Red Compartment MUST have 2 red items, Green Compartment MUST have 3 green items and the blue compartment MUST have 3 blue items. My backpack can hold some kind of max weight. I need to optimize for the max value given some weight.

To solve this problem I attempted to use the branch and bound technique used for solving the 0/1 backback. This technique computes quickly but picks items that leave too much left over space and doesn't return the optimal items.

What techniques can be used to solve this problem? I am unfamiliar with dynamic programming but is this something better suited to that or is there a different technique I can use?


texts:
I am working on an algorithm that ranks a set of nodes in a graph with respect to how relative this node is to other predefined nodes (I call them query nodes). The way how the algorithm works is similar to recommendation algorithms. For instance, if i want to buy an item from an online store, the algorithm will look at my preferences (and/or history of purchased items) and recommend new items for me. Applying this to graph theory, the set of nodes are items and my preferred items are the query nodes. The problem am facing right now is how to benchmark my results (i.e. I want to run recall and precision on my results) but I don't have a ground truth data. My question is: does anyone know a benchmark for this problem, if not, how do you think I can evaluate my results.

Note: My algorithm has nothing to do with recommendation algorithms (i.e. the application is different), but I gave this to deliver the general idea of the RELATIVE IMPORTANCE algorithms. I am looking for any dataset with benchmark that may help me in this context.

Edit: Based on some requests, I will explain my algorithm with more details. The algorithm takes as input: graph (can be directed or undirected, weighted or unweighted), and a set of query nodes (included in the graph). The algorithm will try to rank the nodes in the graph according to their importance with respect to the query nodes. The importance of a node increases as the relationship between it and the query nodes increases. Depending on the application, this relationship is quantified by a value (the weight of an edge) that reflects the level of association between two nodes. For instance, in the DBLP co-authership dataset, the relation between two nodes is the number of common papers between the two nodes (authors). Therefore, in this case, the algorithm will rank the authors in the DBLP graph according to how close they are to all query nodes (the predefined authors).
I hope that this is clear.

Thank you


texts: Thirty-one game. Prediction of the winner

texts:
I have a problem with creating an algorithm to predict a winner of thirty-one game.

Players from a deck of cards, take the Ace, 2, 3, 4, 5, and 6 of each suit. These 24 cards are laid out face up on a table. The players alternate turning over cards and the sum of the turned over cards is computed as play progresses. Each Ace counts as one.
The only limit is the sum value of stacked cards: it cannot exceed 31. The player who cannot make a move loses.

My task is to determine the winner in the game based on stack of cards put aside. We assume that both players play perfectly.

For example:

356656 means gameplay: player A puts down 3, player B puts down 5, player A puts down 6, player B puts down 6, player A puts down 5, finally player B puts down 6 and wins because player A cannot make any move.

356656 -> winner B
35665 -> winner B
3566 -> winner A
111126666 -> winner A
552525 -> winner A
2 -> winner A


texts: What do we mean by polynomially upper bounded and lower bounded

texts:
I just came across this asymptotic bound :

$(\log n)!= \Theta \left(n^{\log \log n}\right)$

Which had the following remark:

    Hence, polynomially lower bounded but not upper bounded.

I found this here:

https://gateoverflow.in/12928/%24-log-and-log-log-are-polynomially-bounded-anybody-can-prove

I am confused on how can we conclude whether it's polynomial lower bounded and not upper bounded.

Could someone please help me on understanding this.


texts: Minimum number of rounds to notify a hierarchy of people with DP

texts:
I'm trying to figure out a problem reported in Kleinberg (ch 6 no.16). I know that there are solutions based on ordering, anyway i'd like to understand if another way exists.

Basically, we have a hierarchy of people represented by a tree. The root person has to postpone a picnic due to rain: in a first moment he calls by phone his direct subordinates, one at a time. As soon as each subordinate gets the phone call, he must notify each of his direct subordinates, one at a time. This continues until everyone has been notified. Any person at a node can notify only his own children in the tree (e.g. no grandchildren).

You can view this process as being devided in rounds: in one round, every person who has been notified can call one of his subordinates (thus in parallel).

It's important to note that the number of rounds required to notify everyone depends on the sequence in which each person calls their direct subordinates. E.g. with the following tree we have 2 rounds if A notifies B first, or 3 rounds if A decides to start from D:

The problem requires an efficient algorithm that determines the minimun number of rounds. My approach is the following: like in largest independent set i obtain first a post order transversal $v_1, v_2, \ldots, v_n$ of the whole tree. Then i define the following recurrence relation:

$$
OPT(v_i)=
\begin{cases}
0 \qquad \qquad \qquad \qquad \qquad \qquad \quad \hbox{if leaf} \\
\displaystyle\max_{v_j\ \text{child of}\ v_i}\left\{k(v_i), 1 + OPT(v_j)\right\}  \ \hbox{otherwise}
\end{cases}
$$

Where $k(v_i)$ is the children count of the node $v_i$, and $OPT(v_i)$ is the minimum number of rounds required to notify the people contained in the subtree with $v_i$ as root.

Let's consider a more complex tree:

Due to the recurrence we have $OPT(v_i)_{v_i \in \left\{C, E, F, G, H, I, L \right\}} = 0$, $OPT(B)=4$, $OPT(D)=2$ and finally $OPT(A)=5$ that, as you can see, is exactly the minimum number of rounds to reach every node in the tree.

Please, if my approach is wrong can you give me some hint or counter example showing that ordering is required?


texts: Do subqueries add expressive power to SQL queries?

texts:
Does SQL  need subqueries?

Imagine a sufficiently generalized implementation of the structured query language for relation databases. Since the structure of the canonical SQL SELECT statement is actually pretty important for this to make sense, I don't appeal directly to relational algebra, but you could frame this in those terms by making appropriate restrictions on the form of expressions.

An SQL SELECT query generally consists of a projection (the SELECT part) some number of JOIN operations (the JOIN part), some number of SELECTION  operations (in SQL, the WHERE clauses), and then set-wise operations (UNION, EXCEPT, INTERSECT, etc.), followed by another SQL SELECT query.

Tables being joined can be the computed results of expressions; in other words, we can have a statement such as:

SELECT t1.name, t2.address
  FROM table1 AS t1
  JOIN (SELECT id, address
          FROM table2 AS t3
         WHERE t3.id = t1.id) AS t2
 WHERE t1.salary > 50,000;

We will refer to the use of a computed table as part of an SQL query as a subquery. In the example above, the second (indented) SELECT is a subquery.

Can all SQL queries be written in such a way as to not use subqueries? The example above can:

SELECT t1.name, t2.address
  FROM table1 AS t1
  JOIN table2 AS t2
    ON t1.id = t2.id
 WHERE t1.salary > 50,000;

This example is somewhat spurious, or trivial, but one can imagine instances where considerably more effort might be required to recover an equivalent expression. In other words, is it the case that for every SQL query $q$ with subqueries, there exists a query $q'$ without subqueries such that $q$ and $q'$ are guaranteed to produce the same results for the same underlying tables? Let us limit SQL queries to the following form:

SELECT <attribute>,
      ...,
      <attribute>
 FROM <a table, not a subquery>
 JOIN <a table, not a subquery>
  ...
 JOIN <a table, not a subquery>
WHERE <condition>
  AND <condition>
  ...
  AND <condition>

UNION
 -or-
EXCEPT
 -or-
<similar>

SELECT ...

And so on. I think left and right outer joins don't add much, but if I am mistaken, please feel free to point that out... in any event, they are fair game as well. As far as set operations go, I guess any of them are fine... union, difference, symmetric difference, intersection, etc... anything that is helpful. Are there any known forms to which all SQL queries can be reduced? Do any of these eliminate subqueries? Or are there some instances where no equivalent, subquery-free query exists? References are appreciated... or a demonstration (by proof) that they are or aren't required would be fantastic. Thanks, and sorry if this is a celebrated (or trivial) result of which I am painfully ignorant.


texts: Bellman Ford for directed graph G finds shortest paths within one iteration

texts:
Given directed graph G, vertex s, and all v∈V(G) are 1 edge distant from vertex s.

Is it possible to find a specific edges order (from E(G)) such that a single iteration of Bellman Ford pass over these edges in this order finds all the shortest paths (in weight) from vertex s to all vertices?

I couldn't find a counterexample for that, and it seems correct. But I have no idea how to prove it - would appreciate any hint and direction....


texts: Basic Determine exact amount of iterations

texts:
How exactly do you track the exact amount of iterations? I know its probably basic but can't figure out how so was hoping someone could explain to a complete beginner how you arrive at an answer.

def f(n):

i = 4

 while i < n:

 print(i)

 i = i + 1

( The answer should be max(n−4,0)  )


texts: How to prove NP-completeness of this variant of the set cover problem?

texts:
The problem exactly:

Suppose you're helping to organize a summer sports camp, and the following problem comes up. For each of the n sports offered at this camp, the camp is supposed to have at least two counselors who are skilled at this sport. They have received job applications from m potential counselors. For each of the n sports, there is some subset of m applicants qualified in that sport. The question is: For a given k < m, is it possible to hire at most k of the counselors and have have at least two qualified in each of the n sports?

So, you are given a set U of elements, a collection of S1, S2...SM subsets of U, and an integer k. The original vertex-cover problem asks if there exists a collection of <= k of these sets whose union is equal to U. This question seems to ask how would we prove this is NP-Complete if we instead had to find a collection of <=k of these sets whose union covered the elements in U at least twice.

My first thought was to try to reduce the set cover problem. I was going to try to extend it to make it have to cover the union twice, but have no idea how to do that.

My next thought was to use 3-SAT since everything comes from that it seems, but I will die of old age before I figure that out.

My question is, what problem should I try to reduce from? Any could I get a hint for a first step to take? I've never proved one of these before so I'm really lost. I've been staring at this problem for 3 hours now.


texts: Thoughts on definition for disadvantage of concurrent processing?

texts:
I'm a Computer Science student currently learning about concurrent processing. I found the benefits and disadvantages in my book vague, did some online research and put together a more detailed way of defining the disadvantage of concurrent processing; thoughts and corrections are appreciated.

Book version: "The drawback is that if a large number of users are all trying to run programs, and some of these involve a lot of computation, these programs will take longer to complete."

My version:
Using concurrent processing on multiple users running the same program, means no one can finish until everyone has nearly finished. This is inefficient compared to consecutive processing where the last user would finish at the same time as the last user in concurrent processing, but some users would finish significantly earlier. However the scaling of this inefficiency is limited by the amount of threads, because concurrent processing only switches between the first process of each thread queue. The process at the beginning of each thread can change with the use of interrupts though.

Do you think I elaborated on the book properly, or misunderstood it?


texts: Variable Length Encoding of Integers Using a Modulus Algorithm

texts:
Continuing on the theme from my last question Variable Length Encoding of Integers, I have come up with a simple encoding scheme, but for which an efficient algorithm eludes me.

The constraints are simple enough: no (binary representation) number is allowed where it is divisible by 3, or a subset (prefix) of that representation is divisible by 3.

To terminate the number two bits are added so that the number is divisible by 3.

For example 1101 is allowed since neither 1101, 101, 01 nor 1 are divisible by 3.

However, 1011 is not allowed since 11 is divisible by 3.

The representation 1101 would then have 10 prepended to make it divisible by 3 (101101).

All this allows a stream of bits to be read, at each point testing to see if the number is divisible by three. If not, keep reading the next bit, until it is divisble by three. Hence allowing for a (unique) variable length encoding.

My question is about the mapping of integers on to this encoding scheme. However hard I try I can't seem to create a straightforward algorithm to do the mapping. Is there one?

Clarification

The examples above are to be read in the order right to left. So any prefix is on the right. So the stream of bits will be read right to left.


texts:
I'm going through Adam Chlipala's "Certified Programming with Dependent Types" (available here for convenience), and I'm a bit stuck at internalizing the introduction of co-induction principle for the stream_eq predicate in Chapter 5.

Firstly, I'm used to induction schemes defined for data structures (stream in this case, if it were data and not codata). Yet, the co-induction principle being introduced seems to be defined for the predicate we're trying to prove itself, and how does it connect with the following (cursive ours)?

  Dually, a co-induction principle ought to be parameterized over a predicate characterizing what we mean to prove, as a function of the arguments to the co-inductive predicate that we are trying to prove.

Or should I parse this as implying parametrization over the predicate R : stream A -> stream A -> Prop, which, to me, seems like a reformulation of stream_eq, taking the following hypothesis into account?

Hypothesis Cons_case_hd : forall s1 s2, R s1 s2 -> hd s1 = hd s2.
Hypothesis Cons_case_tl : forall s1 s2, R s1 s2 -> R (tl s1) (tl s2).

Secondly, considering the quoted text again, we're trying to prove stream_eq. What would be the arguments to that predicate here? Looks like it should be the streams, but the hypothesis seem to be much more complex than that.

Lastly, all of this stream_eq_coind looks to me a like a somewhat generic way to do the match acrobatics on the streams to allow the simplifier to proceed (as Chlipala does in the version of the proof preceding this part). Is this correct or am I missing some deeper sense?

Oh, and what would be some good sources for me to read on co-induction? A few papers or tutorials I've found refer to some algebra or logic (i.e. Kripke models) quite beyond my current knowledge.


texts:
I'm a bit confused on how Variational Autoencoders are trained. In particular I'm confused on how the latent variable is generated for each input.

My questions are as follows:

When running stochastic gradient descent does the sampled latent variable stick with the data point during the entire run or does a new latent variable get sampled each time descent is run?
If running batch or full gradient descent, each data point gets its own set of sampled latent variables right?
How do you check for convergence? Assuming the latent variable is sampled at each iteration, it's not clear to me how you can evaluate if you have converged or not given the stochastic nature of the performance function.


texts: MAP estimation (for stationary iid gaussian environment)

texts:
This is my first post, and have been self studying Haykin's Neural Networks and Learning Machines book.  I'm not sure if this is a typo or if I'm doing something wrong, but I've been stuck on a statement on page 75.

The context was the process of finding a Maximum likelihood estimate for a parameter vector assuming a stationary, iid, and Gaussian environment.

Given:
d is a scalar, i indexes time from 1 to N, and $\mathbf{w},\mathbf{x}_i $ are  m-dimensional vectors.

$\hat{w}_{MAP} = max_{\mathbf{w}}[-\frac{1}{2}\Sigma_{i=1}^{N}(d_i - \mathbf{w}^T\mathbf{x}_i)^2 - \frac{\lambda}{2}||\mathbf{w}||^2]$

we should get the same result if instead we find the minimum of the quadratic function

$E(\mathbf{x}) = \frac{1}{2}\Sigma_{i=1}^{N}(d_i - \mathbf{w}^T\mathbf{x}_i)^2 + \frac{\lambda}{2}||\mathbf{w}||^2$

Haykin says you should arrive at the result (by differentiation wrt $\mathbf{w}$ and setting the result to 0)

$\hat{w}_{MAP} = (R_{xx} + \lambda I)^{-1} r_{dx}$

where $R_{xx} = -\Sigma_{i=1}^N \Sigma_{j=1}^N \mathbf{x}_i \mathbf{x}_j^T $ is the M*M correlation matrix of x and $r_{dx} = -\Sigma_{j=1}^N \mathbf{x}_i d_i$

My question is why isn't $R_{xx} = -\Sigma_{i=1}^N \mathbf{x}_i \mathbf{x}_i^T?$
Haykin goes through about a paragraph saying how the correlation matrix is time averaged and I think this is an important point.
Thanks for any help!


texts: What would you do if the author of a published CS article does not respond to code requests?

texts:
Since reproducibility is a major principle or basic norm of scientific experiments, simulations, and computations, what would you do or what to do if the author of a published CS article does not respond to code requests?
Thanks a lot!


texts:
An undirected graph on $n$ vertices and $n-1$ edges $G = (V,E)$ is partitioned between two players $A$ and $B$ such that $A$ knows $(V,E_A)$, $B$ knows $(V,E_B)$ and $E_A \dot\cup E_B = E$.
Initially, $B$ receives an advice $m_1$ that depends on $G$ and the given partition. After that, $B$ receives a randomized message $m_2$ from $A$, and has to decide whether $G$ is connected or not. If $G$ is connected, then there should be an advice $m_1$ such $B$ will accept with probability at least $2/3$. If it does not, then for any given advice $m_1$, $B$ will accept with probability at most $1/3$.
Is it possible to achieve such a protocol with $m_1 = o(n)$ and $m_2 = o(n)$?


texts: Impact on the order of elements on the cost of searching in a linked list

texts:
I have the following homework question that I am struggling with. I have read the corresponding chapter from the book, but no guidance there.

Consider a linked list $X: X_1 \to X_2 \to X_3 \ldots$.
Assume that the cost of examining a particular element $X_i$ is $C_i$. Note that to examine $X_i$,
one needs to scan through all elements in front of $X_i$. Let $P_i$ be the probability of
searching for element $X_i$, so the total cost for all searches is
$$
\sum_{j=1}^{n} \left( P_j \cdot \sum_{i=1}^{j} C_i \right)
$$

Show that storing elements in non-increasing order of $P_i/C_i$ does not necessarily minimize the total cost.
Show that storing elements in non-decreasing order of $P_i$ does not necessarily minimize the total cost.

Any help and direction how to approach the problem will be highly appreciated.


texts:
I need to prove that this language is in co-NPC:
$\{ \langle M,x,1^n \rangle \mid M $ is a TM and for all $c \in \Sigma^*$ , $M$ accepts in $ $$n$ steps when given $(x,c)$ as input $\}$.

I tried to do so by showing that the complement is in NPC, that is $\{ \langle M,x,1^n \rangle \mid M $ is a TM and there exists  $c \in \Sigma^*$ , s.t $M$ doesn't accepts in $n$ steps when given $(x,c)$ as input $\}$.

I can prove that it's in NP by giving a polynomial non-deterministic algorithm, but I get stuck in the reduction part and don't know from which language in NPC to do a polynomial reduction and how. Does anybody know how do deal with such reduction?


texts: Why is O(n log n) the best runtime there is?

texts:
I am taking a course on Coursera about algorithm design. The course said that a time of $O(n \log n)$ is considered to be good.

However, there are faster runtimes such as (from now on just assume it is in big o notataion), such as $1$, $n$, and $\log n$. I understand that it is almost impossible to have a algorithm in $O(1)$ as that is for trivial tasks such as adding or multiplication.

However, why is there no algorithm in $O(\log n)$ time? Mergesort is considered to be a great algorithm and in its best and worst case scenario it is $O(n \log n)$ (I could be wrong). Why is merge sort considered to be a great algorithm when $O(n \log n)$ is only faster than $n^2$, $n!$, and $2^n$?

Also, why is there no sort with a time of $\log n$? This is not a homework question by the way, I am just purely curious as to why no sorting algorithm is in $\log n$ time.


texts: What is the relation between syntax and type theory?

texts:
Type theory and syntax are similar, in that they are inductive rules that determine whether a  particular string of symbols is "correctly specified" in some sense.

There is a difference between syntax and type theory. Syntax in programming languages for example, concerns things that do not concern type theory, such as the fact that the statement if import microsoft.(false ==== 5) then import is "syntactically nonsense". This is not a type error, but a syntax error.

But I'm unsure what the relation is.

I normally think of syntax and type systems as follows: Let $L$ be the set of possible strings of some symbol set $S$. A particular syntax inductively specifies a subset $T\subseteq L$ of "terms" in $L$. e.g. a program is not well-specified if it is not in $T$. A particular type system then makes an additional restriction, by inductively specifying a subset $W\subseteq T$ of "well-typed terms".

But given such a syntax and type system, we can always consider a new syntax which is simply the old syntax plus also has the inductive rules of the type system as an additional restriction.

Therefore it is not clear to me why there is a fundamental difference between a syntax and a type system.

Is my intuition correct? Can we see type checking a particular form of syntax checking?


texts: Is there a difference between perfect, full and complete tree? Or are these the same words to describe the same situation?


texts: Expected runtime for hashing with a binary search tree as collision handling

texts:
I thought about implementing a data structure with expected runtime of O(1) for insertion, deletion and look-up and a worst case runtime for these operations of O(log(n)). This is under the assumption of uniformly distributed data.
What I thought of was a simple hash table using BST for the collisions. Does that make sense or is there a simpler solution to this problem?


texts: Forward must problem explanation in compiler design

texts:
While studying, I came across the following statements:

A join point is a program point where two branches meet.

Available expressions is a forward, must problem.

Forward = Data Flow from in to out.

Must = At joint point, property must hold on all paths that are joined.

I get what joint point, available expression and forward is. But I am getting what exactly is meant by MUST.

Someone please explain what MUST is with example.

Edit: Could you please relate your statement with the following example.


texts: () = ( − 2) + 4, giving asymptotic bounds

texts:
How do I go about solving this? When I try to google examples I only see problems with "+1" or "+n" constants and never anything above that.

If possible could anyone also describe the suggest method to solve these as well?

() = 3( − 1) + 3

() = 2 (/8) + 4^2

Update: I couldn't find any examples or helpful resources for solving recurrences with "weird" constants so I figured it would be unique enough to ask here.


texts:
I have been trying to learn more about amortized analysis. Recently I came across the Disjoint Sets or Union-Find structures. I am using union by rank and path comparison. The potential of such data structures is  sum of $\phi(x)$ for all nodes  where

$$\phi(x) = \begin{cases}
0,  & \text{if }\mathrm{rank}(x)=0 \\
\alpha(n)*\mathrm{rank}(x), & \text{if $x$ is the root} \\
(\alpha(n) - \mathrm{level}(x))\mathrm{rank}(x) - \mathrm{index}(x), & \text{otherwise.}
\end{cases} $$

I could somehow successfully analyze the above potential function (trust me, it was really really hard for a beginner like me, but I somehow managed to do it). But I am getting stuck in the middle of my analysis when I change the definition of $\phi(x) $ to a simple $\mathrm{height}(x)$. It would be great if someone could help me learn more about this potential function and guide me how I could analyze the data structure when I change my potential function..

P.S : I tried reading documents online about the union-find(disjoint-sets) data structure. But as i read more about the data structure, my analysis is becoming more and more confusing. So if you could point me in the right direction, it would be great. Also, this is my first post here, so if I am in the wrong group and I need to ask the question else where, please let me know the right group where I can post this question.


texts: Euler circuit for undirected graph versus directed graph

texts:
I'm working on finding an Euler circuit for an indoor geographical 2D grid. when abstracting the grid as a an undirected graph, all nodes in the graph are connected (i.e, there is a path between every node in the graph). The graph could be huge (more than 100,000) nodes. The requirements are simple :

1- The generated path has to pass by every edge in the graph in both directions.

2- I need to minimize the number of times any edge appears in the generated path, such that the Optimal solution is a path that would include each edge ONLY once for each direction.

First Approach

I abstracted the problem as an undirected graph, for which I have to find an Euler circuit in one direction. I did so for simplicity. If I was able to produce a path that would include every edge in one direction, I could simply reverse that path and hence meet the requirement of generating a path that covers the edges of the graph in both directions. Since I was looking for an optimal solution (minimizing the number of edges after including them at-least once), I planned the following steps:

1- 10 percent of the nodes had an odd degree (about 10,000 nodes!), therefore, I had to employ a matching algorithm to find the shortest mutually disjoint paths between pairs of odd nodes such that the sum of the distance between pairs is minimized. In other words, using a variation of blossom algorithm http://web.eecs.umich.edu/~pettie/matching/Edmonds-Johnson-chinese-postman.pdf

2- After adding the artificial edges between odd pairs, the nodes of the graph are all of even degree. Find the Euler circuit for the graph.

3- Include a reverse version of the generated path to the final solution.

Issues with first approach

Understanding and Implementing J.Edmond's algorithm (blossom algorithm) is a tedious task. More importantly, the solution is still not optimal (several edges are covered more than once due to pairing of odd nodes).

Second Approach

1- Abstracting the grid as a directed graph, simply by doubling the edges of each node of the graph (i.e, one edge from node A->B and the other B->A). Hence, guaranteeing that all nodes are of even degree, such that the number of incoming edges of every node is equal to the number of outgoing edges.

2- Finding an Euler Circuit for the directed graph. The optimal solution (which is an Euler circuit that exists) is in this case double the summation of all edges.

My question is simple. Before I get too excited, are there any shortcomings to the second approach ?. Does the second approach (directed graph) meet the requirements of an Euler circuit ?


texts:
I am trying to understand the Bellman-Ford algorithm from Jon Kleinberg, Éva Tardos: *[Algorithm Design].
Page no: 296 The recursive equation that is written:
$$M[v]= \min(M[v], \min_{w\in V}
(c_{vw} + M[w]).$$
I am not getting how this equation is correct?
Because in the book it is written that $M[v]$ is the shortest path from $v-t$,
but shouldn't $M[v]$ be the shortest path from $s-v$ using at most $i-1$ edges?


texts: How to find the Big-O for finding combinations of balanced parentheses?

texts:
Given n pairs of parentheses, a function which returns the total number of all combinations well-formed parentheses could be:

def count_parenthesis(n, opened, closed):
  if closed == n:
    return 1

  num_pairs = 0

  if opened < n:
    num_pairs += _count_parenthesis(n, opened + 1, closed)

  if opened > closed:
    num_pairs += _count_parenthesis(n, opened, closed + 1)

  return num_pairs

Calling count_parentheses(3, 0, 0) results in the following call tree:

count_parenthesis(2, 0, 0)
  count_parenthesis(2, 1, 0)
    count_parenthesis(2, 1, 1)
      count_parenthesis(2, 2, 1)
        count_parenthesis(2, 2, 2)
  count_parenthesis(2, 2, 0)
    count_parenthesis(2, 2, 1)
      count_parenthesis(2, 2, 2)

How can the time and space complexity of this algorithm be determined?

There are a few areas which I'm unsure how to handle:

The variable that moves towards the base case (closed == n) does not get incremented every time.

Calls where a brace is opened (opened + 1) do not directly move towards the base case.

There isn't an obvious relationship (IMO) between n and the number of well-formed combinations:

n = 3, f(n) = 5
n = 4, f(n) = 14
n = 5, f(n) = 42
n = 6, f(n) = 132
n = 7, f(n) = 429
n = 8, f(n) = 1430

I'm unsure how a recurrence relation can be defined when the base-case is not 1 or 0, but n?
Should I approximate based on well-known runtime complexities? I.e. this looks like either exponential or factorial.

Note: I'm not looking for just an answer. I'd like to understand  the process finding the time/space complexity for this type of recursive algorithm.


texts: Where does the lg(lg(N)) factor come from in Schönhage–Strassen's run time?

texts:
According to page 53 of Modern Computer Arithmetic (pdf), all of the steps in the Schönhage–Strassen Algorithm cost $O(N \cdot \lg(N))$ except for the recursion step which ends up costing $O(N\cdot \lg(N) \cdot \lg(\lg(N)))$.

I don't understand why the same inductive argument used to show the cost of the recursive step doesn't work for $O(N\cdot \lg(N))$.

Assume that, for all $X < N$, the time $F(X)$ is less than $c \cdot X \cdot \lg(X)$ for some $c$.
So the recursive step costs $d \cdot \sqrt{N} F(\sqrt{N})$, and we know this is less than $d \cdot \sqrt{N} c \cdot \sqrt{N} \lg(\sqrt{N}) = \frac{c \cdot d}{2} \cdot N \cdot \lg(N)$ by the inductive hypothesis.
If we can show that $d < 2$, then we're done because we've satisfied the inductive step.
I'm pretty sure recursion overhead is negligible, so $d \approx 1$ and we have $\frac{c}{2} N \cdot \lg(N)$ left to do the rest. Easy: everything else is $O(N \cdot \lg(N))$ so we can pick a $c$ big enough for it to fit in our remaining time.

Basically, without digging into the details that will contradict this somehow, it looks like things would work out if we assumed the algorithm costs $O(N \cdot \log(N))$. The same thing seems to happen if I expand the recursive invocations then sum it all up... so where is the penalty coming from?

My best guess is that it has to do with the $\lg(\lg(N))$ levels of recursion, since that's how many times you must apply a square root to get to a constant size. But how do we know each recursive pass is not getting cheaper, like in quickselect?

For example, if we group our $N$ initial items into words of size $O(\lg(N))$, meaning we have $O(N/\lg(N))$ items of size $O(\lg(N))$ to multiply when recursing, shouldn't that only take $O(N/\lg(N) \cdot \lg(N) \cdot \lg(\lg(N)) \cdot \lg(\lg(\lg(N)))) = O(N \cdot \lg(\lg(N)) \cdot \lg(\lg(\lg(N))))$ time to do. Not only is that well within the $N \cdot \lg(N)$ limit, it worked even though I used the larger $N\cdot \lg(N)\cdot \lg(\lg(N))$ cost for the recursive steps (for "I probably made a mistake" values of "worked").

My second guess is that there's some blowup at each level that I'm not accounting for. There are constraints on the sizes of things that might work together to slow down how quickly things get smaller, or to multiply how many multiplications have to be done.

Here's the recursive expansion.

Assume we get $N$ bits and split them into $\sqrt{N}$ groups of size $\sqrt{N}$. Everything except the recursion costs $O(N \lg N)$. The recursive multiplications can be done with $3 \cdot \sqrt{N}$ bits. So we get the relationship:

$M(N) = N \cdot \lg(N) + \sqrt{N} \cdot M(3 \cdot \sqrt{N})$

Expanding once:

$M(N) = N \cdot \lg(N) + \sqrt{N} \cdot (3 \cdot \sqrt{N} \cdot lg(3 \cdot \sqrt{N}) + \sqrt{3 \cdot \sqrt{N}} \cdot M(3 \cdot \sqrt{3 \cdot \sqrt{N}})$

Simplifying:

$M(N) = N \cdot \lg(N) + 3 \cdot N \cdot lg(3 \cdot \sqrt{N}) + \cdot \sqrt{3} \cdot N^{2-\frac{1}{2}} \cdot M(3^{2-\frac{1}{2}} \cdot \sqrt{\sqrt{N}})$

See the pattern? Each term will end up in the form $3^{2-2^{-i}} \cdot N \cdot lg(N^{2^{-i}} 3^{2-2^{-i}})$. So the overall sum is:

$\sum_{i=0}^{\lg(\lg(N))} 3^{2-2^{-i}} \cdot N \cdot \lg(N^{2^{-i}} 3^{2-2^{-i}})$

We can upper bound this by increasing the powers of 3 to just 3^2, since that can only increase the value in both cases:

$\sum_{i=0}^{\lg(\lg(N))} 9 \cdot N \cdot \lg(N^{2^{-i}} 9)$

Which is asymptotically the same as:

$\sum_{i=0}^{\lg(\lg(N))} N \cdot \lg(N^{2^{-i}})$

Moving the power out of the logarithm:

$\sum_{i=0}^{\lg(\lg(N))} N \cdot \lg(N) \cdot 2^{-i}$

Moving variables not dependent on $i$ out:

$N \cdot \lg(N) \sum_{i=0}^{\lg(\lg(N))} 2^{-i}$

The series is upper bounded by 2, so we're upper bounded by:

$N \cdot \lg(N)$

Not sure where the $\lg(\lg(N))$ went. All the twiddly factors and offsets (because many recurrence relations "solutions" are broken by those) I throw in seem to get killed off by the $\lg$ creating that exponentially decreasing term, or they end up not multiplied by $N$ and are asymptotically insignificant.


texts: Choosing the optimal radix/number-of-buckets when sorting n-bit integers using radix sort

texts:
This is a popular question:

  What is the most efficient (in time complexity) way to sort 1 million 32-bit integers?

Most answers seem to agree that one of the best ways would be to use radix sort since the number of bits in those numbers is assumed to be constant. This is also a very common thought exercise when CS students are first learning non-comparison based sorts. However, what I haven't seen described in detail (or at least clearly) is how to optimally choose the radix (or number of buckets) for the algorithm.

In this observed answer, the selection of the radix/number of buckets was done empirically and it turned out to be $2^8$ for 1 million 32-bit integers. I'm wondering if there is a better way to choose that number? In "Introduction to Algorithms" (p.198-199) it explains Radix's run-time should be $\Theta(d(n+k))$ (d=digits/passes, n=number of items, k=possible values). It then goes further and says that given n b-bit numbers, and any positive integer $r \leq b$, radix-sort sorts the number in $\Theta((b/r)(n+2^r))$ time. It then says:

  If $b \geq \lfloor \lg(n) \rfloor$, choosing $r = \lfloor \lg(n) \rfloor$ gives the best time to within a constant factor.

But, if we choose $r = \lg(10^6) =20$, which is not $8$ as the observed answer suggests.

This tells me that I'm very likely misinterpreting the "choosing of $r$" approach the book is suggesting and missing something (very likely) or the observed answer didn't choose the optimal value.

Could anyone clear this up for me?


texts:
One of the definitions of NL is the set of all languages that can be decided by a logarithmic space verifier with a 'read-once' witness tape, i.e. the witness tape head can only move right.

I want to prove that if we allow the verifier to read the witness tape twice, i.e.  when the witness tape head reaches the end of the tape, it goes back to the beginning and we can read it once more, the set of languages that can be decided by such verifier is still NL.

I thought of proving it by saying that, given a 'read-twice' verifier, $V$, which expects a witness $w$, we can build a 'read-once' verifier, $V'$, which works the same as $V$, but expects a witness of the form $ww$, i.e the originial witness concatenated to itself. Is that correct? If not- why not?

Thanks!


texts:
Given a sequence $(a)$ of lenght $n$, such $a_1 = a_n = 1$ and $a_i \in \left \{ -1, 1 \right\}$.

We want to find a subsequence $(b) \subset (a)$ which statisfies the following conditions:

The length of $(b)$, (let's call it $k$) is the largest possible
$b_k = b_1 = 1$
Each prefix sum $b_1$, $b_1+b_2$,  $b_1+b_2 + b_3,\ \ldots\ , b_1 + b_2 + \ldots + b_k$ is $\geq 0$.
Each suffix sum $b_k$, $b_{k} + b_{k-1}, b_{k} + b_{k-1} + b_{k-2}, \ \ldots\ , b_k + b_{k-1} + \ldots + b_1$ is $\geq 0$.
Sum of $(b)$ is the biggest possible.

Is it possible to construct linear algorithm to solve it?


texts: If both the concatenation of two languages and the second "half" are regular, is the first too?

texts:
Given that $L_2$ is regular and infinite and $L_1 \cdot L_2$ is regular, then $L_1$ is also regular.

I need some help on getting started on proving this is the case.

My intuition is that if $L_1 \cdot L_2$ is regular there exists a DFA for it, in which case you can just remove the states that correspond to the $L_2$ part of the DFA and you are left with a DFA that recognizes $L_1$.


texts:
Wikipedia says:

fun factorial n =
    if n = 0 then 1 else n * factorial (n-1)

  A Standard ML compiler is required to infer the static type int -> int of this function
  without user-supplied type annotations. I.e., it has to deduce that n
  is only used with integer expressions, and must therefore itself be an
  integer, and that all value-producing expressions within the function
  return integers.

I don't understand how a compiler could infer this. It sounds like SML is essentially solving the halting problem for the factorial function, and showing that it only halts on positive integer inputs.

Am I missing something?


texts: Dynamic programming algorithms with log in the run-time

texts: Most of the classic examples of dynamic programming algorithms have run-times such as $n$ or $n^2$. Are there any natural examples with a $O(n \log n)$ run-time?


texts:
I'm looking for a list of informed search algorithms, also known as heuristic search algorithms.

I'm aware of:

best-first search

Greedy best-first search
A* search

Are there more best-first algorithm or other informed searches that are not best-first?


texts: Blocking because of concurrency correctness condition

texts:
I am confused about a statement in The Art of Multiprocessor Programming:

Theorem 3.6.2: Let inv(m) be an invocation of a total method. If <x inv P> is a pending invocation in a linearizable history H, then there exists a response <x res P> such that H · <x res P> is linearizable.
...
This theorem implies that linearizability by itself never forces a thread with a pending invocation of a total method to block.

(The Art of Multiprocessor Programming, Herlihy & Shavit, 2008 Edition, page 58)
I understand that partial methods might need to block for correctness reasons. For example, it is reasonable to block a dequeue operation until there are elements to remove.
However, I don't see why any correctness condition (e.g. linearizability or quiescent consistency) would force an invocation of a total method to block. Is there such a case, or am I misreading the implication of the theorem?
Additionally, what does blocking mean in the context of a history? Does blocking remove an item from the history?


texts:
I have network flow $G=(V,E,s,t)$ where every edge capacity is $\sqrt{2}$ except one edge, which capacity is $2$. I need to describe efficient algorithm to find max flow.
If all capacities where exactly the same, I could use dinic on the same network with capacities of 1 and at the end multiply the max flow in $\sqrt{2}$, but how can I deal with the problematic edge of capacity $2$?
thanks!


texts:
It might be a silly question, I do take a carefully read about approximation algorithm through coursenotes, but when I saw the words "approximation algorithm with polynomial complexity", I can't understand what it means, I searched a lot and here is my assumption.

First, for some NPc or NP hard problem, we can try to solve them approximately, because there is no optimization algorithm right now. So compared with some opotimal solution theoretically, some optimazation problem can use approximation algorithm to get an approximation solution, such like vertex covering problem.

Then it is the term polynomial complexity, an algorithm is polynomial if for some k>0, its running time on inputs of size n is O(n^k).

So is "approximation algorithm with polynomial complexity" means an approximation algorithm that whose complexity is in polynomial time? So is it means there are approximation algorithm that has other complexity such as exponential complexity.

By the way, through the approximation algorithm for vertex covering problem, I know what the algorithm is (briefly it is takes an arbitrary edge from subset E' of all possible set of edges, add two vertax at set S and remove all edge who has the same vertex with that arbitrary edge and continue until E' is empty). But how to observe it is polynomial complexity or what?

I really apprexiate if someone can solve my confusion.


texts: optimizing the calculation of $\sum^n_{k=2} p(\Omega(k))\Omega(k)$

texts:
I want to optimize an algoritm for calculating $g(n)=\sum^n_{k=2} p(\Omega(k))\Omega(k)$
where $$  p(n) =
\begin{cases}
1  &\text{if $n$ is odd} \\
-1 &\text{if $n$ is even}
\end{cases}$$
and $\Omega(n)$ is the prime factor counting function or more exactly, I want to optimize calculating all it's values up to $n$
my current best try is
def Omega(k):
    Factor = 0
    b=1
    while(k>1):
        b +=1
        if (k % b == 0):
            while k % b == 0:
                k /= b
                Factor += 1
    return Factor
sum = 0
for i in range(n)
   w = Omega(i)
   sum += ((w%2)*2-1)*w
   #using it

First, I am trying to calculate the current algorithm's computational complexity.
we calculate $\Omega(k) ~~n$ times, I haven't managed to calculate $\Omega(k)$'s computational complexity but it seems to be $O(\sqrt k \log k)$ thus, I think the entire program is $O(n^{1.5} \log n)$.
Am I correct?
Can any of you help optimize my algoritm?
Note: Is this the correct exchange for this question?
Ideas:
1.Calculating $\Omega$ less,$\Omega$ is an Completely Additive function, i.e. for any $a,b$, $\Omega(ab)=\Omega(a)+\Omega(b)$, I've tried to use this to optimize the calculation, but have not managed to.
2.Optimizing the prime factorizing algoritm, I'm unsure about this.
The reason I'm interested in this is to graph the function, My current code is the first thing that went into my head, i.e, very nonoptimal.
This function is related to Liouville function.


texts: What is the current state of research on the representation of boolean functions using wavelets

texts:
The harmonic representation of boolean functions such as XOR or AND has been studied in different course note lectures that can be found on Google.

http://cs.mcgill.ca/~hatami/comp760-2011/

http://www.cs.cmu.edu/~odonnell/papers/analysis-survey.pdf

What is the state of research on the representation of boolean functions using wavelets?


texts: Finding a median in logn from a list of distinct integers

texts: I got an interview question asking for data structure and algorithm. The question is: Given we have unlimited space, We need to insert a key in $O(logn)$ and find a median in $O(logn)$. Min heap/ Max heap are good candidates to insert a key in $O(logn)$ but sorting requires $O(nlogn)$. How can we design a data structure so that it can find a median in $O(logn)$? The hint given by the interviewer is confused to me, the interviewer said we need two heaps. How can two heaps work?


texts: Algorithm to convert a fixed-length string to the smallest possible collision-free representation?

texts:
I have a US-based telephone number (in the format 000-000-0000) and need to convert it to a "shorter" representation. Using base32/64 produces too long of a string. I've discovered CRC-16, which produces a string of length 4, however, I'm not sure it's a suitable tool for the job (I want to prevent collisions).

Basically, if the input is 000-000-0000 (without the dashes), I want the output to be something like 4xg4. In this use case, the advantage is that I have 10 digits, thus I could "convert" them to something smaller that uses letters as well.

Are you aware of any algorithm implementation for this?


texts: How to count the biggest size of the problem during some time period?

texts:
We assume that time of solving the problem $=f(n)$$\mu$s.
Now we have to calculate how big problem we can calculate for each time periods.

So there are:
$\lg n,
\sqrt{n},
n,
n\lg n,
n^2,
n^3,
2^n,
n!$,

How to calculate size of the biggest problem during those times periods?:
1s,
1min,
1h,
1 day,
1 month ,
1 year,
100 years

I completely don't know how to start.


texts: Can a Multi-Tape Turing Machine have an infinite number of tapes?

texts:
So if k is the number of tapes, is a multi-tape Turing machine allowed to have k = ∞ tapes.

I'd assume not since this would give an infinite transition function?


texts: Find Optimal Permutation/Positioning to Minimize the Total Distance for a Given Path

texts:
Summary:
A task for picking certain objects is given in the form of an ordered sequence (eg. to pick apple, banana, apple, apple, orange, order matters). The objects have to be preassigned to certain physical locations with all the pairwise distance being known and fixed. The question is how to efficiently find the best location assignment so that the total traveling distance is minimized.
What I Have Tried:
I cannot map this problem to any other algos that I know. For example, Dijkstra is to find the path given the graph, Knapsack is to find the right combination which the order doesn't matter.

I posted this question on Stackoverflow
I wrote an article on my blog to describe the problem in more detail for your reference
I wrote a script to demonstrate how to find the optimal position assignment in a brute force way for a small number of objects.

Right now, this is at a complexity I believe of O(n!) and will totally explode as we increase the number of different objects.
# task is a sequence of order picking
task = '1212103' # means first pick up obj1, then obj2, then obj1, ..etc.

result = []
for c in permutations(range(4), 4):
    # c contains the positions for all objects
    # (1, 0, 2, 3) means obj0 stored at pos1, obj1 stored at pos0, etc.
    res = 0

    for f,t in zip(task, task[1:]):
        pos_f = c[int(f)]
        pos_t = c[int(t)]
        # abs(...) is one oversimplief way to calculating distance between two positions
        # in a 1d space for demonstration purpose
        res += abs(pos_f - pos_t)
    result.append((c, res))

And the outputs are all the permutations and the total distance:
[((1, 2, 3, 0), 6),   # optimal position assignment #1 the yields the shortest distance
((2, 1, 0, 3), 6),    # optimal position assignment #2 the yields the shortest distance
((0, 2, 3, 1), 7),
((1, 3, 2, 0), 7),
((2, 0, 1, 3), 7),
((3, 1, 0, 2), 7),
((0, 1, 2, 3), 8),
((0, 3, 2, 1), 8),
((3, 0, 1, 2), 8),
((3, 2, 1, 0), 8),
((0, 2, 1, 3), 9),
((3, 1, 2, 0), 9),
((0, 1, 3, 2), 11),
((1, 0, 2, 3), 11),
((1, 2, 0, 3), 11),
((2, 1, 3, 0), 11),
((2, 3, 1, 0), 11),
((3, 2, 0, 1), 11),
((0, 3, 1, 2), 13),
((3, 0, 2, 1), 13),
((1, 0, 3, 2), 14),
((2, 3, 0, 1), 14),
((1, 3, 0, 2), 15),
((2, 0, 3, 1), 15)]


texts: why are WAW and WAR hazards not possible in mips architecture

texts:
i have read about data hazards and then came across that mips architecture doesn't allow WAR AND WAW hazards can someone please help me understand it? the reason is not given in the book the MIPS pipeline is divided into :

1.IF(instruction fetch) 2.ID(decode the instruction) 3.EX(execute instruction) 4.MEM(write or read from the memory) 5.WB(write back to the register file)
for eg in case of  WAW hazards :

I1:  LOAD R1,0(R2)

I2:  ADD R1, R2, R3

I1:  |IF|ID|EX|MEM|WB |
I2      |IF|ID|EX |MEM|WB|

The above is expected way in which the instructions execute without data hazards
but here the second instruction has to wait till the WB phase of the instruction I1  for getting the value of R1  hence it will stall till the value of R1 is available in register file i.e till WB phase of the I1. here what my doubt is in case I2 Takes less number of clock cycles than I1 for completion then can I2 access the register file going to WB phase directly in case it has nothing to do in the phase of MEM  will this give rise to a hazard?


texts: Using Genetic Algorithms for volatile problems

texts:
Suppose I am looking at an optimization problem with a large number of interconnected constraints, but the solution is - in some regions - extremely volatile (With volatile I mean: small mutations might drastically change the evaluation of the proposed solution. Also note that not all changes are volatile in this way, changing other parts of the solution might result in much smaller changes in the value of the solution).

In this case, is it still practical to try and find an optimal solution by using a genetic algorithm? I am worried that the potential volatility would more or less change the problem into almost a brute-force search, or are there ways around this?


texts: ignoring overflow in two's complement addition of numbers with different signs[specific case]

texts:
I understand the rule says that overflow cannot happen for two's complement addition of numbers with different signs, but do not understand why this specific case does not cause overflow:

 1001010
+0010101
--------
 1011111

Am I simply misunderstanding the actual rule or missing a step somewhere?
Thanks in advance!

EDIT: removed an extra 1 in the result


texts: Periods of an LFSR with characteristic polynomial that is a product of primitive polynomials

texts:
I want to find the minimal period of any state of an LFSR (except the initial state of all zeroes) whose characteristic polynomial is the product of two primitive polynomials.

In particular, $f(x),g(x) \in GF(2)[x]$ are primitive polynomials of order $n$, and the characteristic polynomial of the LFSR is given by:
$$c(x)=f(x)g(x).$$
What is the minimal period of any state of this LFSR, other than the all-zeros state?

I've tried to say that if $c(x)$ is a product of two primitives then it has a period of
$$\pi=2^{2n}-1 $$
but my math gets me to
$$\pi =2^{n+1}-2$$
What did I do wrong?


texts: kd-tree stores points in inner nodes? If yes, how to search for NN?

texts:
The link in wikipedia about kd-trees store points in the inner nodes. I have to perform NN queries and I think (newbie here), I am understanding the concept.

However, I was said to study Kd-trees from Computational Geometry Algorithms and Applications (De Berg, Cheong, Van Kreveld and Overmars), section 5.2, page 99. The main difference I can see is that Overmars places the splitting data in the inner nodes and the actual points of the dataset in the leaves. For example, in 2D, an inner node will hold the splitting line.

Wikipedia on the other hand, seems to store points in inner nodes and leaves (while Overmars only on leaves).

In this case, how do we perform nearest neighbour search? Moreover, why there is this difference?