texts: Proof that complement of HAMPATH is not in NP

texts:
The Sipser book says, Complement of HAMPATH is not in NP.

I tried to find the solution for this, actually, a rigid proof like HAMPATH, which can state Complement of HAMPATH is in/not in NP, but I could not come up with any.

This is what I think, We are given a path from s to t(which can be a certificate for the problem, or not?), and check if it is not a HAMPATH. But this is easy, we can check this in P time right--Just list down the path, see that if any vertex is repeating in it, or if it is missing any vertex of the graph.

How come we are saying this problem is not in NP

I am very new to P and NP, Please correct my mistakes, and apologies if my question sounds like a silly one.


texts:
Assume my language is
$$
L= ww^{r}\
$$

Now when we use NPDA for this,we will guess middle every time. It may be actual middle or it may not, so a new branch is created every time as I have a choice here. Now each branch will get the current stack contents and start its operation.

So my question is, do these branches operate in parallel or one after another? We have only one stack and each branch will do push/pop according to its requirement and changes the stack. Even if a branch results in dead end, we need to proceed further. How is a single stack able to manage this scenario, as stack contents are changed by each branch?


texts: Is it decidable whether one language is polytime reducible to another?

texts:
Let $L_1$ and $L_2$ be two decision problems.

Is there an algorithm deciding whether $L_1 \leq_P L_2$, that is, whether $L_1$ is reducible to $L_2$ in polynomial time?


texts:
There is a grammar that describes the walks of a turtle around Manhattan, such that the turtle
always returns home. It is described in the book "Parsing Techniques" by Dick Grune and Ceriel
J.H. Jacobs, page 18. Unfortunately, I could not find a source online, but the rules are
rather simple:

$$ G = \left\langle \{0\}, \Sigma = \{N, S, E, W\}, R, 0 \right\rangle \\[2ex]
R = \left\{ \begin{align}
& 0 \to N 0 S    \\
& 0 \to E 0 W    \\
& 0 \to \epsilon \\[2ex]
& N S \to S N \\
& \dots \quad \scriptsize{(\text{11 other pairs of distinct } \sigma, \tau \in \Sigma)}
\end{align} \right.$$

I actually went ahead and generated some sentences of this grammar. Example:

$$ NENNEENSWWSWSS $$

(Sentence № 10617)

A sentence such as this one corresponds to a graph, like the following:

+-----------------+
|                 |
|                 |
|              *  |
|              ⭣  |
|      * ⭠ * ⭠ *  |
|      ⭣          |
|  * ⭠ *          |
|  ⭣   ⭡          |
|  * ⭢ *          |
|  ⭣              |
|  +              |
|                 |
|                 |
+-----------------+

(Or, rather, to a path on the square lattice of Manhattan, but a path defines a subgraph.)

As this example shows, the walk of our turtle will sometimes have loops.

How hard would it be to compose a grammar that generates exactly the acyclic walks?

P.S. As pointed out in comments, there will always be at least one cycle. Let us call that cycle "trivial" and say "a grammar that generates exactly the walks with only the trivial cycle" instead.


texts:
If 'S is a set complement of S, then a set complement of a superset of S' is a subset of S.

Just want to verify that above is true just based on the definition of set complement and superset.


texts: Time complexity of finding a fixed-size matching in a hypergraph

texts: Define a size $k$ matching in a hypergraph $H = (V,E)$ to be a collection of $k$ pairwise disjoint edges in $E$. Is anyone aware of the (best-known) time complexity of finding, for fixed $k$, a size $k$ matching in an arbitrary hypergraph? I can find plenty of references for the problem with respect to graphs, but not hypergraphs.


texts: What are some of the most important results from "Implicit computational complexity" theory?

texts:
I just found out about implicit computational complexity theory. It seems very interesting. I would like to know more about it.

For me to get an overview of the results of the field, what are roughly the most important results? Or what are the most important papers I should look at to get a good sense of the most important contributions?


texts: Perform an operation on an array in O(n)

texts:
I'm required to perform the following operation on an array in O(n): P[1..n] is an array of positive integers. For each index 'i' in the array, I must find how many "cells" I can advance toward the beginning of the array until I reach an element whose value is greater than P[i], or reach the beginning of the array. The output of the function should be an array S[1..n] that contains these values.

For example, if:

 P = [ 4, 3, 6, 1, 2, 7, 9 ]

Then I must create this array:

 S = [ 1, 1, 3, 1, 2, 6, 7 ]

If I start at P[3] (=6), I can advance 3 cells until the beginning of the array, and therefore S[3] = 3; but if I start at P[5] (=2) I will advance only 2 cells and reach P[3] (=6 > 2), so S[5] = 2.

Implementing such algorithm in O(n^2) is trivial, but I'm required to do so in O(n). I was hinted to use a stack.


texts: Relations among different boolean approximations

texts:
Essentially similar question to here Different boolean degrees polynomially related? (change being error condition $\epsilon\in(0,1)$).

Let $p$ be the minimum degree (of degree $d_f$) real polynomial that represents boolean function $f$ such that $f(x)=p(x)$.

Let $p_{0,\epsilon}$ be the minimum degree (of degree $d_{0,f,\epsilon}$) real polynomial  that represents boolean function $f$ such that $$f(x)=0\implies p_{0,\epsilon}(x)=0$$$$f(x)=1\implies|p_{0,\epsilon}(x)-f(x)|\leq\epsilon.$$

Let $p_{1,\epsilon}$ be the minimum degree (of degree $d_{1,f,\epsilon}$) real polynomial  that represents boolean function $f$ such that $$f(x)=1\implies p_{1,\epsilon}(x)=1$$$$f(x)=0\implies|p_{1,\epsilon}(x)-f(x)|\leq\epsilon.$$

Is $d_{f}\leq d_{0,f,\epsilon}^{c_0}$ and $d_{f}\leq d_{1,f,\epsilon}^{c_1}$ for some  $c_0$ and $c_1$?

Above holds if $\epsilon\in(0,\frac{1}{2})$ as mentioned here in link Different boolean degrees polynomially related?.

However what happens if $\epsilon\in(0,1)$ instead of $(0,\frac{1}{2})$ (does polynomial relation still hold)?

That is we consider $0<\epsilon<\frac{1}{2}\leq\delta<1$.

Note that defining $p_\delta$ makes little sense if $\delta\in[\frac{1}{2},1)$.

I am most interested in $\delta=1-\frac{1}{h(n)}$ with some function of $n$ (logarithmic/polynomial/exponential).


texts: How to extent primitive recursion from natural numbers to finite strings?

texts:
Primitive recursion seems to be related to bounded quantification. It is easier to make sense of bounded quantification with respect to natural numbers than to make sense of bounded quantification with respect to finite strings.

A relatively clean way out of this dilemma could be a two sorted language with both natural numbers and finite strings, and some basic functions between the two sorts, like the lengths of a string, or the string where one symbol is repeated n times.
A nicer solution could be to avoid the need for natural numbers, and work with some more native finite string related concepts, like head/tail, substring, ... instead.

I wonder whether there exist a robust computational model (on finite strings) corresponding to primitive recursion, just like Turing machines represents a robust computational model (on finite strings) corresponding to general ($\mu$-) recursion.


texts: Grammar for a language: odd length, middle character not repeated

texts:
Consider the following language over the alphabet $\mathcal{A} = \{a,b,c\}$:
$$L = \left\{w \in \mathcal{A}^* \mid \text{\(|w|\) is odd and the middle character in \(w\) occurs nowhere else in \(w\)} \right\}$$

I am trying to come up with a grammar for $L$, but I'm getting nowhere. I came up with some sample strings from the language which would be accepted: b, abcab, accbcaa
I understand the length of the string has to be odd, and the middle character cannot be repeated anywhere in the string.

Therefore, the above three strings are accepted. However, something like aabbb will not accepted, because even though the length is odd, the middle character is repeated.

Can someone help with a grammar for $L$?


texts: Pedagogic reference on cut generating functions

texts:
Can you recommend an introduction to the topic of cut generating functions?  I am looking for introductory or review-like material.

I did find the following survey paper, but it seems to be addressed to experts, so not what I'm looking for:

A geometric approach to cut-generating functions.  Amitabh Basu, Michele Conforti, Marco Di Summa.

I have talked to a few researchers in the topic and haven't been able to find anything good.  I do not have access to libraries at this point and can't access books, so I would prefer freely available online resources.


texts: Nim Games: Is it possible to reduce following using Grundy Number?

texts:
Following is the problem from a finished programming contest.

  Two players try to create a number, DesiredTotal, by adding numbers
  from 1 to N. The first to cross the number is the winner. The number to be
  added cannot be repeated. For example, if one player used 4 to increase the sum from
  20 to 24, the neither player can use 4 again in the game.

Now I understand how the above problem could be solved using dynamic programming by exploring all the possible paths and memoizing the solution, but the game being impartial still qualifies to be a Nim game.

Am I correct that, it is a Nim game? If yes, could somebody help me to reduce into a Nim game?

Below is the source but it requires signing in.

Theory: https://www.topcoder.com/community/data-science/data-science-tutorials/algorithm-games/

Source: https://leetcode.com/contest/leetcode-weekly-contest-10/problems/can-i-win/


texts: Algorithm to generate combinations of n elements from n sets of m elements

texts:
Suppose I have 3 sets of 2 elements: [A, B], [C, D], [E, F], and I wanted to generate all possible combinations of 1 element from each set, such that the result of the algorithm would be:

[A, C, E], [A, C, F], [A, D, E], [A, D, F], [B, C, E], [B, C, F], [B, D, E], [B, D, F]

What algorithm can I use to generate all combinations. Keep in mind that I'm looking for an algorithm that will work on any number of sets that have any number of elements, the above is just an example. Also, remember that I'm looking for an algorithm to actually generate the combinations, not just count them.


texts: Different types of interpolation used in computer vision

texts:
Known codition:

four pixels shown in the image $(i,j),(i+1,j),(i,j+1)$ and $(i+1,j+1)$
$a=0.9$ and $b=0.4$

I was able to calculate the bilinear interpolation using the algorithm provided by https://en.wikipedia.org/wiki/Bilinear_interpolation.
But how should we calculate the Average Interpolation and Nearest Neighbor Interpolation?


texts: Random algorithm with biggest sequence that never repeats

texts: I am going to attempt to write a random number generator using exisiting randomize algorithms. Can you suggest which algorithm has the biggest sequence that never repeats? I don't care if they are fast or slow.


texts:
I am a programmer by hobby. I stumbled upon lambda calculus from Kevlin Henney's talk lambdas to the slaughter and I was sold! It was an interesting new way of thinking that's entirely different than the way most of us program. But if I want to push someone to learn lambda calculus, what concrete benefits can I state.
I tried for long but the only one I could come up with is that its fun to play around. And it acts as the base of functional programming.
P.S. when I first heard about Lisp I couldn't understand why so many C brackets. After spending some time with lambda calculus, now I know ;P


texts: Big number of false positives in binary classification

texts: I am fine-tuning the inception-v3 network(pretrained on ILSVRC) of tensorflow in a binary classification problem. I want to recognize if an image contains food or not. My dataset is imbalanced, the non-food class contains 5 times more images than the food class. I read that in an imbalanced dataset, I should train the network with balanced batches to get right results. So I split the dominant class in 5 splits and when I have to train the network for 50000 iterations I am changing the split every 10000 iterations, so that the batches that are passed to the training are balanced with food and non-food. I am testing the network in a balanced test-set. From the first 5000 iterations I am getting high accuracy in the food images, but the non-food class gives me imbalanced accuracy. I can receive high accuracy in the beginning and then it will be low. By accuracy I mean (number of rightly predicted food) / (number of food) for the food class and respectively for the non-food. Generally the network learns the food characteristics because the softmax can output non-food for a food image, but the localization of food would be right using the weights of food (I made test). To sum up, the network is probably overfitted but I don't know yet. Any ideas of what might be happening?


texts: Efficient rasterisation of vector image with polygons

texts:
Imagine I have a 2D area where I have many simple polygons ("simple" meaning not self-intersecting, they are not necessarily concave). A polygon is given to me as a series of points. I have between 25 and 150 polygons in my area. I also have several thousand points that I need to figure out if they are inside any of the polygons or not. I need to do this about every second, with a new set of points. The set of polygons stays the same.
I know there are point-inside-polygon algorithms but they seem to be too computationally demanding for the numbers I have, particularly executing on a mobile phone in real time. So an alternative I am thinking is to pre-compute a black and white bitmap of the area (with white areas outside polygons and black inside). One pixel can simply be a single bit. Or you can see the whole thing as a 1D array of true and false values that the whole 2D area maps unto. So using area coordinates x,y  we can access an element in that array and get an answer true/false. This will be considerably faster. The problem then becomes constructing this bitmap. Ideally I want this construction to happen at the phone if it's not too costly. As an alternative the phone can download this bitmap.
So how do I efficiently create this bitmap? I can run the point-in-polygon algorithm for successive "pixels" with the resolution I want, but this seems inefficient for 100K-200K "pixels", and probably rules out the phone processing option. I suspect there are more efficient algorithms than that.  How do the programs convert SVG images to bitmap for example? I googled a bit, but what I get is the much more difficult problem of bmp->svg, also called vectorisation.
Update
Inspired by the D.W. suggestion I expanded it to an answer. I have not implemented it to tell you what kind of savings I might get but it seems a bit expensive. Happy to receive completely different approaches.
Practically what I am currently doing is rasterising an svg file using public tools/libraries. I am doing this outside the mobile phone, and transfer the image to the phone.


texts: Decide whether a DFA accepts the empty language

texts:
Let $X = \{\langle M \rangle\ |\ M\text{ is a finite state machine and }L(M) = \emptyset\}$ where $\langle M \rangle$ is an encoding of the
machine $M$.  Is $X$ Turing decidable?  Why or why not?


texts:
I am stuck on that question, it's about Voronoi diagrams

  Show that for some set of $n$ points, there can be $\Omega(n^2)$ intersections
  between the edges of the Voronoi diagram and the edges of the farthest site Voronoi diagram.

In this question, I think the intersections is the vertexes of the farthest site. Am I correct?
And I need to prove there is at least $\Omega(n^2)$ intersections like that?

Could you please give me some hint about it?


texts: What is the differences and similarities between refinement type and liquid types?

texts: Looking at the examples here and here both refinement type and liquid types look very similar. What are the differences and similarities?


texts: Selecting connected subgraph that exceeds value c, with least possible weight

texts:
Given a graph $G$ where each node has a value $c$ and weight $w$, I want to select a connected subgraph $V^*$, such that,

Sum of all values in  $V^*$ crosses threshold $t$.
Sum of all weights(say $w^*$) in $V^*$ is as low as possible.

A practical example is finding smallest continuous area of a country that hosts at least $x\%$ of the population. In this case, value would be population, and weight would be area.
I found a related question, but it only asks about the complexity, not the algorithm.
I thought of 0 - 1 knapsack, such that values and weights swap role. So,

Size of knapsack is $t$, however we are allowed to cross it once.
minimize $w^*$.

However, I think this won't work, mainly because we can't order the nodes by $value/weights$, and secondly because of ability to exceed knapsack size.


texts:
Sometimes I read about the term userland and sometimes userspace.

From Wikipedia, it is said that userland is referring userspace:
https://en.wikipedia.org/wiki/Userland

Is there any difference between the terms userland and userspace?


texts:
Consider decision problems stated in some “reasonable” formal language. Let's say formulae in higher-order Peano arithmetic with one free variable as a frame of reference, but I'm equally interested in other models of computation: Diophantine equations, word problems from rewriting rules using Turing machines, etc. An answer expressed in any classical formalization would be fine, though if you know how much the choice of formalization influences the answer, that would also be interesting.

Given the length $N$ of the statement of a decision problem, we can define the number $D(N)$ of decidable statements of length $N$ and the number $U(N)$ of undecidable statements of length $N$.

What is known about the relative growth of $U(N)$ and $D(N)$? In other words, if I take a well-formed decision problem at random, what is the probability of its being decidable for a given statement length?

 Inspired by this question which asks whether “most problems and algorithms [are] decidable”. Well, if you don't filter by interest, are they?


texts:
In the reference below, a 1-sparse recovery algorithm over a vector $a \in R^n$ is defined as follows. My question is why do we need the modulus (i.e. $x \mod p$)?
Algorithm:

Keep track of
$$
   \begin{split}
   w_1 &= \sum a_i \\
   w_2 &= \sum i a_i \\
   w_3 &= \sum a_i z^i \mod p
   \end{split}
   $$
Test if
$$
   \begin{split}
   w_3 \equiv w_1 \cdot z^{w_2 / w_1} \mod p
   \end{split}
   $$
For some large prime $p$.

Reference: Section 3.2, "1-sparse recovery: second attempt", https://web.stanford.edu/class/cs369g/files/lectures/lec11.pdf


texts: Is there a name for this type of Turing machine?

texts: I'm considering turing machines with tape alphabet equal to $\{0,1\}$ and the blank symbol equal to $0$. Is there a name for this type of Turing machines? Isn't this type the one computers are based on?


texts: On the analysis of Christofides's algorithm

texts:
Suppose you have even number of vertices, they form as a complete graph denote the graph by $G$. Now, suppose we compute the minimum weight perfect matching denoted by $P$ (so $P$ has alternating edges, i.e. one is a perfect matching and one is not along all the path $P$ through all vertices of $G$). Now, suppose $T^*$ is TSP tour of $G$.

Show that the inequality is true:
$$ \operatorname{cost}(P) \le \min \{ \operatorname{cost}(N_1), \operatorname{cost}(N_2) \},$$
where $N_1$ and $N_2$ are any two perfect matchings on $T^*$.

Note that this inequality from the analysis of Christofides's algorithm, see this nice paper.


texts: Recognizing a language given an automaton

texts:
I'm trying to figure out which language can be recognized in this automaton

Automata http://cdn.imghack.se/images/64b81d259a1d403b810dd9744dc222f7.jpg

According to Wikipedia here "The language L ⊆ Σ* recognized by an automaton is the set of all the words that are accepted by the automaton."

So using what Wikipedia states and knowing that this automaton is a finite state automaton, I would dare to say that this automaton accepts regular languages.

If I would use M to define this automaton then I could say:

The language recognized by M is the regular language given by a certain regular expression.

But I'm having a a hard time figuring out the regular expression.

I'm not sure of about this but here is what I think the regular expression looks like

$$
L = (a|b)(a|b)^*a^*
$$

I would appreciate any help in this matter


texts:
$L_4 = \{ w | w \text{ does not contain symbol a immediately followed by symbol b} \} $

where: $ \Sigma = \{ a, b, c \} $

So far I believe I have a defined regular grammar for this language, however I am having trouble coming up with an equivalent regular expression.

$<Language\_4> ::= a <AOrC> $

$<Language\_4> ::= b <Language\_4> $

$<Language\_4> ::= c <Language\_4> $

$<Language\_4> ::= \epsilon $

$<AOrC> ::= a <Language\_4> $

$<AOrC> ::= c <Language\_4> $

$<AOrC> ::= \epsilon $

Via a standard regex grammar this could be done via a lookahead, however I don't believe that the lookahead operation is a valid regular language operation.  I'm having trouble proving that if it is true though.

This is for a homework assignment, so I'm not expecting a full answer just some pointers in the right direction.

Edit

I went through this set of answers:
How to convert finite automata to regular expressions?

I then used Arden's Lemma as it seemed the most straight-forward.

First I defined:

$Q_0 = aQ_1 \cup bQ_0 \cup cQ_0 \cup \epsilon $

$Q_1 = cQ_0 \cup aQ_1 \cup \epsilon $

$ Q_1 = cQ_0 \cup aQ_1 \cup \epsilon $

Apply Arden's Lemma:

$ U = a $,
$ L = Q_1 $,
$ V = cQ_0 $

Then I get:

$Q_1 = a * c Q_0 \cup \epsilon $

By then substituting $Q_1$ into $Q_0$ I get:

$Q_0 = a[a*cQ_0 \cup \epsilon] \cup bQ_0 \cup cQ_0 \cup \epsilon $

$Q_0 = \underbrace{(aa * ac \cup b \cup c)}_U \underbrace{Q_0}_L \cup \underbrace{a \cup \epsilon }_V $

$Q_0 = (aa * ac \cup b \cup c)* a$

Is this a correct application of the lemma?

EDIT 2

I've tested the regex more and it doesn't match the desired language.  I think there may be an error in my application of the lemma. I'm going to try the application again in case I missed something.


texts: 1230C | Codeforces | Find count of numbers that divide all numbers in an array

texts:
Here is the question: Link. In a gist, we need to count the total count of numbers that would divide every number in an array.

The approach that I took was that any number that has to divide all the numbers must be less than or equal to the smallest number in the array. For e.g., if the array is [6 90 12 18 30 18] - any divisor cannot be greater than 6, because that would not divide 6.

Based on above logic, here's the code that I wrote:

#include <bits/stdc++.h>

using namespace std;

//output
#define output(x) cout << x << endl
#define ll long long

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;

    vector<ll> v(n);

    ll smallest = LONG_MAX;
    for (auto &it: v) {
        cin >> it;

        if (it < smallest) {
            smallest = it;
        }
    }

    set<ll> divisors;

    for (ll i = 1; i*i <= smallest; i++) {
        if (smallest%i == 0) {
            ll q = smallest/i;
            divisors.insert(i);
            divisors.insert(q);
        }
    }

    for (auto &it: v) {
        vector<ll> removeEl;

        for (auto &div: divisors) {
            if (it%div != 0) {
                removeEl.push_back(div);
            }
        }

        for (auto &rem: removeEl) {
            divisors.erase(rem);
        }
    }

    output(divisors.size());

    return 0;
}

This fails [wrong answer] on some test case - is there something incorrect in my implementation or my approach to the question?


texts: Need help understanding how to find big theta of a snippet of code

texts:
Say I have a snippet of code:

k = 5
i, j = 0

for i -> n
    if i == k
        for j -> k
            /* do something */
        end for
    k = k * 4/3
    end if
    /* do something */
end for

I can tell that the algorithm is worse than n but can't be worse than n^2. In fact it seems like it would be less than n log (n). Though I admit these are just guesses I'm making. Is there any methodology to figuring out what the big theta is for such algorithms?


texts:
I'm kinda confused by Asymptotics, the exercises in the book I'm reading say to prove for example $f(n) = \Omega(g(n))$, and there is something I don't understand about these kind of proofs.
Do I have to prove them algebraically or is it possible to find some constant ($c$) such that this statement holds?
For example would it be correct to write $(n + a)^b = \Omega(n^b)$ since $ (n + a)^b \gg 1 \cdot n^b$?
Any help would be much appreciated.


texts:
I need help with my CS homework, and I don't quite know what to do..

The problem is to define a function and return a string as shown as:

1111
    2222
        3333

I wrote my function as:

def steps():
    for i in range (1,4):
        string = str(i) * 4
        print(string)

How do I put in the little spacings? I know  I have to use the '\t', but I do not know where to put it in the function...


texts:
Can someone explain in plain English what "two's complement integer" means? I read this:

  in Java long is a 64-bit signed two's complement integer


texts:
I want a hueristic algorithm for the following problem. Here, $V(G)$, $E(G)$ respectively refer to the vertex set and edge set of a graph $G$.

Input: two planar bipartite graphs, $G,H$ and a map $\phi: A\to V(H)$, where $A$ is a subset of $V(G)$.

Task: determine if there is a (bijective) map $\phi': V(G) \to V(H)$, such that $(\phi(x),\phi(y)) \in E(H) \iff (x,y) \in E(G)$, and the restriction $\phi'\mid_A$ is $\phi$. (i.e.  $\phi'(a) = \phi(a)$ for all $a \in A$)

Does there exist a practical fast running algorithm for determining if such a $\phi'$ exists? If not, does there exist a simple heuristic algorithm which has a "decent chance" of answering in the affirmative.

I'm looking for an algorithm I can actually understand and code myself, rather than use a large complicated system like nauty.


texts: Vector clocks: Why is it necessary to increment my clock on receiving a message?

texts:
Assume I have a distributed system of entities, each with a replica of the same data object that can be modified by broadcasting the changes and I'm using vector clocks to know how to order changes.

In this scenario, Why would I need to increment my own clock if I receive an update? (I noticed in the original paper on vector clocks, they didn't mention this rule, yet followed it in the examples...) Would it be sufficient if I only incremented my clock when I change the data object?


texts: Compute relational composition in $O(|E||V|)$

texts:
Definitions: Let $G=(V,E)$ be a DAG without self-loops, and $X \subseteq G$ and $Y \subseteq G$ be graphs.

Input: $X,Y$. Output: The relational composition relational composition $X \circ Y$ in $\mathcal{O}(|E||V|)$.

Case 1: $|E| \le |V|$. Two for loops over $E(X)$ and $E(Y)$: Runtime $ \le \mathcal{O}(|E|^2) \le \mathcal{O}(|E||V|)$.
Case 2: $|V| \le |E|$

Draw the graph $(V(G),E(X) \cup E(Y))$: $(O(|V|)+\mathcal{O}(|2E|)))$. We call edges from $E(X)$ black and from $E(Y)$ red.
Topologically sort it (Kahn: $\mathcal{O}(|V|) + \mathcal{O}(|E|)$). Let the first level be $0$, and edges go from a level to a higher level.
Draw this graph twice.
In the first copy, remove every red edge beginning at even level, and every black edge beginning at odd level: $\mathcal{O}(E)$.
In the second copy, remove every "black even" and "red odd": $\mathcal{O}(E)$.
For the first copy:

for all nodes $u$ on level $2i$
for all nodes $v$ on level $2i+1$
report edge $(u,v)$ (Runtime $\mathcal{O}(V^2) \le \mathcal{O}(EV)$).

For the second copy: The same for "$2i+1$".
Union the reported nodes, throw out duplicates  $\mathcal{O}(V^2) <= \mathcal{O}(EV)$ (I hope the graph representation allows this).

Could some of you please look over my algorithm and check whether

it is correct
it is in $\mathcal{O}(|E||V|)$

If it's correct, does my algorithm already "exist"? If not, could you provide an alternative? I'll accept the first answer, but upvote if some more people are so kind to check.

EDIT: Step 6 Seems to be in $O(E^2)$ sometimes. I wish this would not be true. Has anyone a working algorithm?


texts: Graph where only two vertices have the same degree

texts:
Let's say that $N$ is the number of vertices. We want to create a graph where only two vertices have the same degree. For what kind of $N$ is this possible?

I tried it and I've been able only to come up with such where $N$ is $3$ and $4$.


texts: Can't understand why the DP Subset Sum algorithm is not polynomial

texts:
I can not understand why the dynamic programming algorithm for the Subset Sum, is not polynomial.

Even though the sum to find 'T' is greater than the total sum of the 'n' elements of the set , the number of iterations is always (T * n) and not exponential  I'm not understanding it.

The algorithm always do 'n*T' comparisons, and writes in the matrix only 'n*T' times...I'm missing something and I don't know what it is.


texts: How can primitive recursion in two variables be made to be of only one variable?

texts:
Problem 7.16 in The Nature of Computation reads as follows:

  [...] show that when defining primitive recursive functions, we really only need to think about functions of a single variable. In particular, show that a function $f(x)$ is primitive recursive if and only if it can be generated from $0$, $S$, $pair$, $left$, and $right$, using composition and iteration, where iteration is defined as follows: if $f(x)$ and $g(x)$ are already defined, we can define a new function $h(y)=g^y(f(0))$. In fact, we can simplify this further and just take $h(y)=g^y(0)$.

($S$ is the successor function. $pair$, $left$, and $right$ create a tuple and take it apart again.)

It's easy to see that one can use $pair$, $left$, and $right$ to put multiple arguments into a tuple, pass that to a function and have that function extract the arguments back out. Similarly a recursive function of the form $f(x) = g(x,f(x-1))$ can be replaced by $f(x) = h^x(0)$. ($h$ will have to return a tuple $(x, f(x-1))$).
However I'm unable to deal with the case where multiple parameters and recursion occur simultaneously, i.e. $f(x,y)=g(x,f(x,y-1))$. The trouble occurs before trying to replace the recursion by iteration, at the stage where multiple arguments have to be combined. The problem is that, the way I see it, primitive recursion is only allowed to call the immediately next smaller case. For instance, $f(64)$ can call $f(63)$, but not $f(32)$. But $pair(x,y-1)\neq pair(x,y)-1$. So when calling a recursive function with a tuple, it can't access the corresponding smaller case that it would've had access to in the multi-parameter setting.

For reference: $pair$ is defined similar to how the rationals are put in a one-to-one correspondence to the natural numbers by Cantor's argument. Though instead of snaking back and forth along the diagonals, it always moves along a diagonal in the same direction, starting over when reaching the end of one.


texts: How we can prove that if $O(f(x))=O(g(x))$ then $Θ(f(x))=Θ(g(x))$?


texts: What are examples of $\mathsf{NL}$-complete problems?

texts:
Wikipedia lists exactly two problems as $\mathsf{NL}$-complete - 2-satisfiability and St-connectivity (although stating that there are "several"):

https://en.wikipedia.org/wiki/Category:NL-complete_problems

My old literature on complexity (from study) also has no additional examples. And the complexity zoo also lists the graph reachability problem as sole example:

https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N

So, are there any other problems known to be $\mathsf{NL}$-complete?


texts: Help with understanding Hopcroft's algorithm

texts:
So I wrote an implementation of Hopcroft's algorithm. While testing, I discovered that it would sometimes produce an automaton that wasn't equivalent to the original. At first, I figured it must be a bug in my code, but after going over the algorithm by hand with a small example, it seems to be a bug in my understanding of the algorithm. Can someone help me correct my understanding?

Here is the algorithm, copied from the paper "Re-describing and algorithm by Hopcroft" by Knuutila. (This version differs a little from the one on Wikipedia, but I have essentially the same problem with that one too.)

let P = {F, F^c}, where F is the set of accepting states
let W = {(F, x) for every x in the alphabet}
while W is non-empty:
    remove an arbitrary element (A, x) from W
    let X be the set of states that move into A on input x
    for every Y in P that intersects non-trivially with X:
        replace Y in P by (Y intersect X) and Y \ X
        for every symbol x:
            if (Y, x) in W:
                replace (Y, x) in W by (Y intersect X, x) and (Y \ X, x)
            else
                add either (Y intersect X, x) or (Y \ X, x) to W
return P

Note that there are two sources of non-determinism in this algorithm: we can remove an arbitrary element from W, and if (Y, x) is not in W then we have a choice as to whether to add (Y intersect X, x) or (Y \ X, x). Unless I have misunderstood something, the algorithm is supposed to be correct no matter what choices we make.

Now, here is my example:

The alphabet is {a, b, c} and the only accepting state is 4, so we start the algorithm with P = 0123|4 and W = {(4, a), (4, b), (4, c)}.

In the first round, suppose we choose (4, b) as our arbitrary element of W. Nothing moves to 4 on input b, so the inner loop is empty. We get back to the outer loop with P=0123|4 and W = {(4, a), (4, c)}.

Next, suppose we choose (4, c). Then X = 12, which intersects non-trivially with 0123, splitting it into 03|12. Since no (0123, x) belongs to W, the "if" condition always fails. Suppose that we add (12, a), (12, b) and (12, c) into W. We get back to the outer loop with P=03|12|4 and W = {(4, a), (12, a), (12, b), (12, c)}.

Next, suppose we choose (4, a). Then X = 3, which intersects non-trivially with 03, splitting it into 0|3. Since so (03, x) belongs to W, the "if" condition always fails. Suppose that we add (0, a), (0, b) and (0, c) into W. We get back to the outer loop with P=0|12|3|4 and W = {(12, a), (12, b), (12, c), (0, a), (0, b), (0, c)}.

All of the rest of the main loop iterations leave P alone, since 0 is the only state that leads into any of 0, 1, or 2. So we end up returning 0|12|3|4. This is clearly wrong, though, because the string "aa" is an accepting input for state 1 but not state 2, so states 1 and 2 are not equivalent.


texts: Does an Expression in RPN Give us a Linear Way of Writing What Happens in a Circuit?

texts:
I mean, say we want to show how we can implement an OR gate in terms of a NAND gate. If we write in Polish notation, then we've suggested that the circuit takes the gates before the inputs. If we write it in infix notation, we've suggested a mix. But if we write ppDqqDD, then we've suggested that we have the input 'p', then 'p' again, then those pass through NAND in the circuit, 'q', then 'q' input again, then they pass through NAND, and finally the result of what the previous NANDs found passes through the final NAND.

So doesn't an expression in Reverse Polish Notation tell us exactly how a circuit behaves?  Or does it only describe the behavior of some circuits?  Which types of circuits, if any, does RPN describe in this way?


texts: What complexity class does is this set of grammars? NL-complete?

texts:
The unrestricted grammars characterize the recursively enumerable languages. This is the same as saying that for every unrestricted grammar G there exists some Turing machine capable of recognizing L(G) and vice versa.

Context: Grammars are Turing-complete. Therefore complexity classes like NL have equivalences in grammars.

  One important NL-complete problem is ST-connectivity (or "Reachability") (Papadimitriou 1994 Thrm. 16.2), the problem of determining whether, given a directed graph G and two nodes s and t on that graph, there is a path from s to t. ST-connectivity can be seen to be in NL, because we start at the node s and nondeterministically walk to every other reachable node. ST-connectivity can be seen to be NL-hard by considering the computation state graph of any other NL algorithm, and considering that the other algorithm will accept if and only if there is a (nondetermistic) path from the starting state to an accepting state.

Given a directed graph, deciding if a->b is a directed path is NL-complete.

We will reduce the directed graph to a grammar rules with one symbol on each side:

For each directed edge in the graph, add a grammar rule. The directed edge a->b becomes the grammar rule a|b.

The NL-complete query becomes, "If I set a to the start symbol, can I derive symbol b using the grammar rules?"

Each grammar rule has one symbol on each side (i.e. a|b).

Therefore grammar rules with one symbol on each side is NL-complete.

Are grammars consisting only of rules with one symbol on each side NL-complete?

Related questions:

What complexity class does is this set of grammars? L-complete?

What complexity class does is this set of grammars? P-hard?

What complexity class does this correspond to?


texts: If $L$ is CFL and $\overline{L}$ is CFL, then is L regular?

texts:
I've seen in previous exams that professors marked the theory as correct:

  If $L$ is CFL and $\overline{L}$ is CFL, then L is regular.

I just don't see how this would work. How would we prove such a thing? I also can't come up with contradicting languages.


texts: Regular language not accepted by DFA having at most three states

texts:
Describe a regular language that cannot be accepted by any DFA that has only three states.

I'm not really sure where to start on this and was wondering if someone could give me some tips or advice. I understand that the pumping lemma can be used to prove a language is not regular, but in this case, it should be a regular language. If anyone has any thoughts it would be appreciated.


texts: Is a subtree of a minimum spanning tree a minimum spanning tree of the subgraph spanned by the subtree?

texts:
Let $G$ be a connected weighted undirected graph. Let $T$ be a minimum spanning tree (MST) of $G$. Consider removing an edge $e=(a,b)$ from $T$, which will give two subtrees $T_a$ and $T_b$, where $Ta$ contains the vertex $a$ and $T_b$ contains the vertex $b$. Now consider the subgraph of $G$, $G_a$, which contains the vertices of $G$ that are in $T_a$, and the edges of $G$ that have both endpoints in $T_a$.
Is $T_a$ an MST for the subgraph $G_a$?
Intuitively, I believe $T_a$ is an MST for the subgraph $G_a$, but I'm having a lot of difficulty proving the result.


texts: What is the Big Theta of $(\log n)^2-9\log n+7$?

texts:
How can I find the Big Theta of $(\log n)^2-9\log n+7$?

I thought of $(\log n)^2-9\log(n)+7 < c_1(\log n)^2 +7$ or something like this and can't find the right way.


texts: Can we push and pop both at a single transition in a PDA?

texts:
Let say I have a pda :

δ(q1,a,Z)=(q2,aZ)

δ(q2,a,aZ)=(q2,bZ)

Is this allowed....

you can see that in δ(q2,a,aZ)=(q2,bZ), we are basically popping 'a' and pushing 'b' for a single transition...

Is this allowed for PDA ??


texts: "Equivalent device" for testing for NP and coNP?

texts:
I'm trying to understand some aspects of the $P=^?NP$ and $NP=^?coNP$ problems.

I am engineer and not mathematician nor computer scientist so I do not completely understand what a turing machine is.

I'm currently thinking about a variant of the "subset sum problem" known to be in $NP$ and suspected to be not in $coNP$. However I'm thinking of a modified variant of the problem.

It is easy to prove that a computer based on a "real" CPU can prove the answer "yes, a subset exists" (when the subset is known) in less than $(n+a)^2$ operations (while $a$ depends on the type of CPU used) when the original set contains $n$ elements.

From my understanding of $NP$ this implies that the problem belongs to $NP$. My first question is if this understanding is correct.

(I write "belongs to $NP$" and not "$\in NP$" because I know I mix up terms like "problem", "formal language", ...)

I suspect the minimum number of operations (on the real CPU) to prove the answer "no, no matching subset exists" to be more than $\frac{2^n}b$ (while $b$ depends on the type of CPU used).

So my second question is if this would mean that the problem does not belong to $coNP$.

As far as I know that there are differences between Turing Machines and CPU-based computers:

A Turing Machine has unlimited memory while a computer has limited memory
A Turing Machine can't generate true (undeterministic) random numbers while on a computer you may use the noise of the microphone input...
...

So I'm not sure if "cannot be calculated by a computer in polynomal time" implies "cannot be calculated by a Turing Machine in polynomal time".

-- Edit --

Having read the answers I think I have to say something about the background of the question:

I think I had already understood what P, NP or coNP is before asking the question but I was not 100% sure because I was not sure about the differences between a Turing Machine and a computer.

I have an idea how it could be possible to prove the impossibility to build a digital computer that can solve a certain problem in less than $a^nb$ steps while $n$ is the number of inputs and $a$ and $b$ depends on the computer and the problem.

I was just wondering if such a proof was sufficient to prove $P \neq NP$ if it could be done for a problem that is known to be in NP.

Having read your answers I think that such a proof would be sufficient. Thanks.

(Needless to say that I am not able to carry the proof I'm thinking of for any problem.)


texts: Does solving subproblems in logspace in different models implies solving original problem in logspace?

texts:
Let's consider the following situation:

We have a problem $\mathsf{L\text{}}$ . We would like to solve it in $LOGSPACE$. Let assume that our problem $\mathsf{L\text{}}$  can be divided to two parts: $A$ and $B$.

We can solve $A$ using computatation model $M_1$ in $LOGSPACE$.

We can solve $B$ using computation model $M_2$ in $LOGSPACE$, $M_1 \neq M_2$

Does it mean that we  can solve $P$ in $LOGSPACE$ ? Why?


texts: Pattern classification: what goes into the sample?

texts:
I am trying to compare the performance of a classification result with Bayes classifier, K-NN, Piece wise component analysis (PCA). I have doubts regarding the following (please excuse my lack of programming skills since I am a biologist and not a programmer thus finding the Matlab documentation hard to follow).

In the Matlab code

    Class = knnclassify(Sample, Training, Group, k)
    Group =  [1;2;3]   //where 1,2,3 represents Class A,B,C respectively.

What goes in the sample because my data is a 100 row 1 column for each of the classes? So Group 1 contains data like $[0.9;0.1;......n]$ where $n=100$. Would the sample be a vector containing random mixtures of the data points from the three classes? Same question for the Training matrix.


texts: How does one generate a list of size N of all possibilities using a dictionary of size D?

texts:
Say that we have a list of size $N$ to fill with elements of a dictionary of size $D$. So we would have in total $D^N$ elements/possibilities.

It makes sense to me how to write an algorithm for this when the number of possible slots to fill $N$ is fixed. For example if $N = 2$:

A %array of size (D x D x D) = D^3
for i1=1:3
    for i2=1:3
        for i3=1:3
            A[i1,i2,i3] = (i1,i2,i3)

however, I was having some issue generalize such algorithm because it wasn't clear to me how to extend this chain of for loops for general N. Someone have an idea how to do this?

I think the recursive solution is:

V %dictionary of size D
N %number of slots
def combos(n)
    if n==1:
        return V
    answers = []
    for combo in combos(n-1):
        for word in V:
                answers.append(combo+word)
    return answers


texts: Distribution of cycles length in a graph

texts:
Given a random directed Graph G:

$$
 G=(V,E) \\
 \lvert V \rvert = n , \lvert E \rvert = k
$$

where for each vertex, either:
$$
  d_{incoming}(v) = 1 , d_{outgoing}(v) = 1
$$
meaning - for each incoming (outgoing) edge to vertex v, there is also an outgoing (incoming) edge from vertex v.

Or:
$$
d(v) = 0
$$

What is the distribution of lengths of the longest cycles for this set of random graphs?

This question relates to the riddle presented in the last minute-physics video. (for the general case)


texts: Dynamically Learning Haar Cascade (in OpenCV)

texts:
I am new to computer vision so please excuse me if this question is very simple.

I am trying to learn how to use the Haar Cascade creation tool provided with OpenCV to train a cascade classifier. It seems relatively easy, with the tools provided, but I was wondering if there was a way to improve the network after the initial training. I plan to gather an initial set of positive images and train the cascade on those, but afterwards, continue collection and feed new positive images into the cascade to improve detection rates, reduce false positives and allow for better results in more difficult scenarios. Instead of retraining the cascade every time a new batch of positive images is produced, it would be extremely helpful if the cascade could prune itself and improve predictions based on the new images. I was wondering if this is possible, and how one would go about implementing it.

(Note: In this tutorial, the author discusses the use of more than one training epochs in a Deep Belief Network to improve detection rates by strengthening connections that result don't. I'm not sure how this works, but I would assume that if new images are added in each epoch, they could be incorporated without a full retraining, just a pruning. I would like to apply a similar approach to the cascade classifier.)

(Note on Note: The reason that I am using a cascade classifier and not a DBN is because I don't want to be restricted to defining a set number of output neurons. There may any number of detectable objects in the image, in addition to the fact that some results may be a plain boolean value. It doesn't seem that a DBN will work well. However, I have relatively little knowledge of the subjects and any suggestions on what approach to take to achieve the above implementation would be helpful.)

Thank you.


texts: Are there (highly) restricted process calculi? Perhaps similar to formal grammar?

texts:
I've started to read about process calculi (such as CSP and π-calculus). It seems to me that they are extremely general and can represent pretty much any concurrent system, many of which will be unable to "make progress".

I wondered if there were much more restrictive formalisms for describing concurrent processes? Perhaps something close to formal languages augmented with a parallel composition (a kind of tensor product of the joined languages) might work quite well? Maybe, in particular a Parsing expression grammar.

Process calculi seem to generally have a concept of channels on which synchronous messages are exchanged. The set of allowable messages are known as the alphabet of a process, and it seems analogous to the symbol set of a formal language (you'd need to augment the symbols with a send and a receive label).

The possible traces of a process calculus would be analogous to the possible strings of a language.

So, the actual questions: is there something like this in the research literature? Thanks!


texts:
I'm reading a recent paper "Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem" by Gregory Valiant on finding approximate closest pairs in $R^d$. Valiant says the current upper bound for this problem is $O(n^2)$.

On Wikipedia however it is said that the 2d divide-and-conquer algorithm can be generalized to solving the problem in $O(n\text{log}n)$ for any number of dimensions. There are no direct sources to this, but in the talk page, a few papers are referenced.

Reading those papers, they all seem to refer to Jon Louis Bentley's thesis from 1980 "Multidimensional Divide-and-Conquer". However as far as I can understand, the closest pair problem is hear described as solved in $O(n\text{log}^dn)$ time.

Hence, I feel like I must have absolutely confused myself on the definitions. Can anyone help me figure out what the correct upper bound for this problem really is?

Update: I should of course define the problem properly: Given a set $S$ of $n$ points from $R^d$, find two points $p, q\in S$, $p\neq q$ which minimise $d(p, q)$, where $d$ is euclidean distance. The model is RAM or similar.


texts: I am looking for an algorithm that can find the best possible combination of inputs, in order to determine the optimum output

texts:
So as the title poorly implies, I'm looking for an algorithm that can accomplish the following task (as an example):
Given the inputs A(1:100), B(1:100), C(1:100), that can take on any value between 1 to 100.
Given the outputs X, Y, Z, which are determined by a combination of the inputs eg:

A=2, B=3,C=4, returns X=76, Y=87, Z=34
A=5,B=1,C=100 returns X=52, Y=45, Z=24 etc.

The problem is, I have no clue how the inputs affect the outputs and so id like to find an algorithm of some sort that can try out various combinations of inputs in a logical manner (not randomly) to find the optimal output or get as close as possible to said optimum output, which in my case is finding the highest possible valued combination of X,Y,Z so best case scenario is finding a set of inputs that return 100, 100, 100 as the XYZ values.
If anyone has any idea how I could approach this or if a question like this has already been answered, I appreciate any and all help.
Thank you!


texts: A function computable using a circuit of size $10s$ but not of size $s$

texts:
I'm studying Computational Complexity and I have stumbled upon the following question which I have no idea how to even start proving. I would appreciate any help.

  Prove that for every function $s(n)$ such that $n \le s(n) \le \frac{2^n}{100n}$ there exists a Boolean function $f\colon \{0,1\}^n \to \{0,1\}$
  such that $f$ doesn't have a Boolean circuit of size $s(n)$ that computes it but has a Boolean circuit of size $10s(n)$.


texts: Improve worst case time of depth first search on Euler graphs

texts:
How to improve the worst case scenario for a depth first search on an Euler graph, starting at some point and ending at that same point?

I need to do the whole search but it is not fast enough for large amounts of data. I have tried bidirectional search but I can not keep the result numerically ordered. Therefore I wonder if there is any other good method to smooth the worst case scenario for the depth first search.


texts:
Summary:

I am struggling with the Pseudo code for an that algorithm assigns "least filled slot first" to a tasks on multi-core chip.

Detail

So far I have written following:

What I do not like here is:

In while loop I am removing one by one elements of $R$ (which is a row vector with $m$ elements). This means the complexity of $m^2$, however I could have sorted $R$ outside the loop and then just removed the head every time that would reduce the complexity to $m\log m + m$ for this part. But in that case the index $j$ will get jumbled up and not usable in the rest of the part. Is there an elegant Pseudo-code way of saying "store the indices before sorting for later use"?
Any other stylistic suggestions that make it easier to read while still reducing the "implementation complexity" ?

In general, I know its a trade-off between readability vs complexity. Generally, the main purpose of presenting an algorithm is to make it readable and leave the implementation details to the implementer. But just to be pedantic ..

Thanks.


texts: Finding row wise sum of transpose of hv-convex binary matrix

texts:
I'm stuck on a problem involving the Gale-Ryser Theorem. The problem's input gives me the row-wise sum of an hv-convex binary matrix(n*m).

e.g. I get {4,3,2,2,1} in the input. It's the row wise sum of the following matrix:

    1 1 1 1
    1 1 1 0
    1 1 0 0
    1 1 0 0
    1 0 0 0

To solve the problem, I have to find the row-wise sum of it's transpose.

i.e. I need to calculate {5,4,2,1}

1 1 1 1 1
1 1 1 1 0
1 1 0 0 0
1 0 0 0 0

Can it be achieved in less than O(n*m)?


texts: How does a language abstract away from underlying byte machines?

texts:
So as the title suggests,

  How does a programing language, such as Java or C, abstract itself away
  from underlying byte machines?

Im curious, because I know that static/dynamic typing, data abstraction and control abstraction play a role. But I don't understand it so I was wondering if anyone could shed a nice explanation on this question!

Thanks a lot in advance!

EDIT: I currently have this as an explanation so far..

  Programming languages tend to abstract away from the underlying byte
  machines to provide a high-level view for the programmer. This can be
  for multiple reasons ranging from making code easier to write and
  debug, to solving platform issues.

  One way languages abstract themselves away is through typing. Using
  java as an example, it uses predefined base types of a certain size,
  including but not limited to: int, float and char. It also uses
  object/structured types which have a dynamic size such as Object and
  String. Like some others, it provides a garbage-collection and automatic memory management utility. This makes it abstract even
  further away as you can worry less about allocating memory space to
  data types, compared to a language like C.


texts: How broad is the meaning of "algorithm"?

texts:
This is a purely terminological question.

The word algorithm, as I have learnt it refers to something like an "effective method, a sequence of steps, for doing something". There are alternative statements giving roughly the same idea.

But for some computer systems, such as neural networks, it is somewhat stretching it (for me) to say that they are "algorithms".  e.g. neural networks are very "approximate" compared to traditional software algorithms.

Would people in general say that a particular neural network with a particular parameterization (i.e. not the learning algorithm, but the resulting neural net itself) is an "algorithm")?
If not, what other word is there to refer to the more general class that contains such networks as well?


texts: Traverse tree collecting nodes combinations

texts:
Summary: I have a tree, containing car parts, from which I need to build all valid combinations of these parts.

Parts can be required - every build must contain them.

Parts can be optional.

Parts can conflict with other parts.

Parts can have optional parts inside them.

Example tree:

Car
| - Motor (required)
| - - V8
| - - V12
| - - - Colour (optional)
| - - - - Black
| - - - - Chrome
| - Transmission (required)
| - - Mechanical
| - - Automatic
| - Wheels (optional)
| - - Basic
| - - Fancy
| - - - Colour (optional)
| - - - - Red
| - - - - Blue
| - BodyStyle (optional)
| - - Hatchback (conflicts with Motor.V12)
| - - Buggy (conflicts with Motor.V8)

Valid builds for this tree:

Car | Motor.V8 | Transmission.Automatic
Car | Motor.V8 | Transmission.Automatic | Wheels.Basic
Car | Motor.V12.Colour.Black | Transmission.Automatic | Wheels.Basic
Car | Motor.V8 | Transmission.Automatic | BodyStyle.Hatchback
Car | Motor.V12 | Transmission.Mechanical | Wheels.Fancy | BodyStyle.Buggy
Car | Motor.V12 | Transmission.Mechanical | Wheels.Fancy.Colour.Red | BodyStyle.Buggy

What algorithm should I look for, that can solve this task


texts: No number is equal to Zero, is this statement true or false?

texts:
While reading an article on logic, there is a sentence "No number is equal to zero" and we have to assign truth values to this sentence. I hope this is true and the article says it as false.

Can someone explain me why it is false? Or the author of the article is wrong?


texts: How to linearly combine loss functions to preserve optimal substructure property?

texts:
I've been working on a binary tree optimization problem with two choices of loss function (let's call them A and B). I'm fairly certain that the problem of minimizing either A or B individually has the optimal substructure property. That is, if I have a set U and I construct the A-minimizing tree T out of all the elements in U, each subtree of T must be the A-minimizing tree for the subset of U it corresponds to (same logic goes for the B-minimizing tree).
However, I would like to also construct trees that minimize some positive linear combination of A and B -- let's call this C, such that C = kA + B for a specific k > 0. Does the problem of minimizing C also have optimal substructure? What kind of additional constraints on A, B, and C would I need to impose in order to achieve this?


texts: is there an example of an algorithm that has O(1/n)?

texts:
Possible Duplicate:
  Complexity inversely propotional to $n$

I'm curious if anyone's come up with a problem or method as n => infinity t => 0. Are there any sort of cases found in quantum computing?


texts: Interval tree: find all intervals containing a given interval

texts:
Given an interval tree $T$ and an interval $I$, I need to find an algorithm that returns all intervals in $T$ that contain $I$. The asymptotic running time should be $O(min(n,(k + 1) log n))$ where $k$ is the number of intervals returned. The only solution I can think of is bruteforcing in $O(n)$ time, but that's clearly too simple.
While looking for an answer I came across stabbing queries and the problem seemed very similar to this one. Is this something I could base my algorithm on or am I on the wrong track?

Edit: I might have an idea, but I'm still missing something.
Let $I=[I_s,I_e]$ and $x$ a node. If $x.s \leq I.s$ then there is an interval that contains $I$ in the left subtree of $x$ if and only if $left[x].max\geq I.e$. Suppose you had a similar statement for the right subtree of $x$, then you could do the following:
If the condition for the left or/and subtree is satisfied, recurse on those trees. Since there must be an interval covering $I$ in these subtrees this will result in $k$ paths with a maximum length of $logn$.
If $x.s > I.s$ there can't be an interval in the right subtree that covers $I$, but there might be one in the left, so recurse on left. If this happens repeatedly until you find a leaf, you get a path of length $logn$ without finding anything.

My question is: given $x.s \leq I.s$, how can I know for sure whether the right subtree of $x$ contains an interval covering $I$?


texts: Choosing potential function in amortized analysis

texts:
How should I think to choose the potential function in the amortized analysis?
More specifically are there techniques or tips for choosing optimal or good potential functions?


texts: Name of a sequence that is unknown to stop on a given input

texts:
Several years ago I was self learning lisp by a book which I do not remember. As an example there was a recursively defined sequence which was said to be unknown to be finite or not for every input --- to generate a sequence you were required to provide two(?) initial values. At least that is how I remember.

There was a Wikipedia article on it but I can't find it either. Does anyone know what I'm talking about?


texts: Understanding Cache Mapping and Access (Computer Architecture)

texts:
Consider a 512-KByte cache with 64-word cachelines (a cacheline is also known as a cache block, each word is 4-Bytes). This cache uses write-back scheme, and the address is 32 bits wide.

Answer the next questions for Direct Mapped cache, Fully Associative and Way Set Associative

What is the size in bits of the cacheline offset, cachline index and tag?

What I know:

Direct mapped caching allows any given main memory block to be mapped into exactly one unique cache location.

Set-associative mapped cache allows any given main memory block to be mapped into two or more cache locations.

Fully-associative mapped caching allows any given main memory block to be mapped into any cache location.

I don't know how that would make a difference in computing byte offset, index and cache

$Byte offset=log_2(\text{bytes in one cache block})$
$Index=log_2(\text{Number of cache blocks in the cache})$
tag: The rest of bits in the address

Attempt at a solution

I would do the mapped cache part by using the previous expressions. I don't want the answer, but I would like orientation.

Thanks!!


texts: What to call a script that runs other scripts?

texts: I have a number of small scripts that are being called, in order, by one larger script. So I can run them all with just one command. I was wondering if there was a technical name for this main program (that runs the smaller ones). Currently I am calling it the 'master', but am not sure if that is correct.


texts: How do you read the regular expression (0^∗10^+)^+?

texts:
Give an example of a string in the language of $(0^*10^+)^+$.

I've been asked to give an example of a string in this language but I'm confused on how to read this notation. I'm guessing the acceptable strings are supposed to start with 0, but that's about all I can infer.


texts: In what sense the computer program (Turing machine) can be considered as the complex system and its IIT Phi can be measured and improved?

texts:
I am reading https://global.oup.com/academic/product/a-world-beyond-physics-9780190871338?cc=us&lang=en& about one approach of complex systems' theory for the emergence of the life. It is about the autocatalytic soup of molecules from which the life can emerge. Of course, one is thinking further - every computer program, every Turing machine is more ore less autocatalytic soup of interacting software components from which the consciousness, mind and Artificial General Intelligence (https://content.sciendo.com/view/journals/jagi/jagi-overview.xml) can emerge.

Of course - ther program (Turing machine) should be of sufficient complexity for such consciousness to emerge - and such complexity/level of consciousness can be measured by Phi measure of https://en.wikipedia.org/wiki/Integrated_information_theory .

My question is - how the theory of complex systems is applied to the software programs (including logic programs, sets of first order formulas, knowledge bases, functional programs, lambda terms), e.g. to derive the directions (modular organization, wealth of functionality, et.c) for evolving the programs into the programs with higher level of Phi, whith higer level of autonomy and consciousness? I presume, that consciousness is the driving force for the program to exhibit commonsense knowledge, for the capability to make generalizations and transfer skills among tasks (all those are very hot topics and deep learning community without almost any theory behind them). All these issues are the grails of current computer science and that is why my question is very applied in nature.

Currently computer programs and algorithms are developed in trial-and-error process. The development of software systems that are called cognitive architectures (http://bicasociety.org/cogarch/architectures.php) or that are called cognitive systems (http://www.cogsys.org/journal) is prominent features of such efforts. But maybe the theory of complex systems can be applied to such programs to determine why such programs exhibit or do not exhibit the capabilities of consciousness (as determined by IIT or any other computational theory of consciousness or mind - there are some others, academically sound) and what can be do on such programs to evolve them into capable systems with higher Phi. We have tried to design and program features but no cognitive architecture has achieved sufficient level of AGI. We can try still more harder. But maybe the theory of complex systems can provide some guidance to estimate the weak points and to provide some direction?

Just some reference for applying the theory of complex systems to the programs in the widest sense?

I tried Google queries like software as complex system, computer program as complex system, Turing machine as complex system but with no results, there is almost no any article relevant to such queries. There is stack-physics question https://physics.stackexchange.com/questions/284456/are-ordinary-desktop-computers-complex-systems that was not received well.

Complex systems exhibit such feature as emergence and programmers are very well aware of the emergence of bugs from their software. That is why they intentionally try to reduce the complexity of the software and improve the predictability (use of formal methods helps). But - is it open question - can we ever achieve artificial general intelligence (are any useful application of AI) by writing simple and predictable software? Maybe software should be a complex system at the end?


texts:
A book I am reading demonstrates how $5n^3 + 2n^2 + 22n + 6 = O(n^3)$, which I believe is true. After all, there exists a value $c$ for which $cn^3$ is always greater than $5n^3 + 2n^2 + 22n + 6$ for all $n$ greater than or equal to some value $n_0$.

However, the book then casually notes that $c = 5$ and $n_0 = 10$. Where did these values come from? What algebraic calculations were done (if any) to derive the $c$ and $n_0$ values?


texts: Proving infinity of CFL with pumping lemma

texts:
Given a CFG G in Chomsky Normal Form with n variables. Prove that
  $|L(G)| = \infty \iff \exists w \in L(G)$ such that $2^n<|w|\le2^{n+1}$

Now, proving left to right I've encountered a problem.
I am trying to prove it by taking a word above the pumping length, and "pumping down" till I get a word of length in the correct interval.
From the pumping lemma for CFL, the substrings we "pump", for example $v,y$  $|vy| \le l=2^n+1$ where $l$ is the pumping length

So when we "pump down" to reach a word within the interval, suppose we reached a word of length $2^{n+1}+1$, and the only appropriate $v,y$ are such that $|vy|=2^n+1$ , we get $2^{n+1}+1 - (2^n+1) = 2^n$ and we "miss" the interval. How is this correct then?


texts: How can you use HMMs and ANNs for on-line handwriting recognition?

texts:
On-line handwriting recognition is the task of converting a series of $(x(t),y(t))$ coordinates to symbols and words. In contrast to off-line handwriting recognition, where you only have a bitmap of the written symbols, you have the way it was written in on-line recognition.

The paper Npen++: An On-Line Handwriting Recognition System describes a system that makes use of Hidden Markov Models (HMMs) and Artificial Neural Networks (ANNs) to recognize symbols.

  [...] each character is modelled with three states representing the first, middle and last part of the character. Hence, the MS-TDNN can be regarded as a hybrid recognizer that combines features of neural networks and hidden Markov models (HMMs).

Source: Npen++: An On-Line Handwriting Recognition System, page 6.

One of my problems is that I don't know what a TDNN (Time delay neural network) is. At the moment, I think I've understood what feed-forward neural networks are and I know that they are trained with backpropagation. But all examples I have seen so far have a fixed input vector (e.g. colors of a fixed-size image; positions on a fixed-size board).

How exactly are the lists of coordinates mapped to the input neurons?

Is the following "mind model" I have of those HMMs correct?

When I understand it correct, then you have one HMM for each symbol.
How do you get the probabilities $p_1, p_2, p_3, p_{1,2}, p_{2,3}$?
How do you get the probability which character to recognize given the trained HMMs and a list of coordinates? When you can get a probability for every symbol with HMMs only, how does the ANN help?


texts: Solving recursion $T(n)=2T(n/2) +2/\log(n)$

texts:
everybody, I'm trying a whole day to compute this recursion. I will be
grateful if someone can try and solve it

$$T(n)=2*T(n/2)+2/\log(n),$$

where $\log n$ is the logarithm to the base 2 - of course! thanks!


texts: Matrix chain multiplication and exponentiation

texts:
If I have two matrices $A$ and $B$, of dimensions $1000\times2$ and $2\times1000$, respectively, and want to compute $(AB)^{5000}$, it's more efficient to first rewrite the expression as $A(BA)^{4999}B$ and only then evaluate numerically, because $AB$ is of dimension $1000\times1000$ but $BA$ is of dimension $2\times2$.

I want to solve a generalized version of this problem. Is there a reasonably efficient algorithm (not brute force) to optimize an expression containing:

Free matrix variables of known dimensions
Products of arbitrary subexpressions
Arbitrary subexpressions raised to natural power

... so that it takes the least amount of work to evaluate numerically, after substituting the free matrix variables with concrete matrix values?

The matrix chain multiplication problem is a special case of my problem.

Edit:

This is a tentative answer. It seems intuitively right to me, but I have no proof that it's correct. If it turns out to be correct, I'm still interested in the proof. (If it's not correct, of course, please do correct me.)

For every product raised to a power, say, $(A_1 A_2 \ldots A_k)^n$, consider every cyclic permutation of the factors:

$(A_1 A_2 \ldots A_k)^n$
$A_1 (A_2 \ldots A_k A_1)^{n-1} A_2 \ldots A_k$
$A_1 A_2 (A_3 \ldots A_k A_1 A_2)^{n-1} A_3 \ldots A_k$
...
$A_1 A_2 \ldots A_{k-1} (A_k A_1 A_2 \ldots A_{k-1})^{n-1} A_k$

... recursively. Each power is to be calculated using exponentiation by squaring (obviously), and all other products are to be calculated using the optimal order returned by the matrix chain multiplication algorithm.

Edit:

The idea outlined in my previous edit is still somewhat nonoptimal. The exponentiation by squaring algorithm actually evaluates expressions of the form $K A^n$ or $A^n K$, where $K$ isn't necessarily the identity matrix. But my algorithm doesn't consider the possibility of using the exponentiation by squaring algorithm with $K$ not equal to the identity matrix.


texts: How to sum vectors to maximize magnitude?

texts:
There are $n$ vectors, represented as $(d_x, d_y)$ pairs. Someone stands at point $(0, 0)$ of infinite euclidean grid. For every vector he can either move by $d_x$ in $x$ axis and $d_y$ in $y$ axis or ignore the vector and don't move at all. Each vector can be used at most once.  He wants to get as far away from $(0, 0)$ as possible. What is the maximum distance from $(0, 0)$ which he can achieve?

For example:

$n = 5$, vectors: $\lbrace (2, -2), (-2, -2), (0, 2), (3, 1), (-3, 1)\rbrace$.

Result: $\sqrt{26} \approx 5.099$ (when $(0, 2), (3, 1)$ and $(2, -2)$ are used, as shown in the picture. Another equally good solution uses $(0, 2), (−3, 1)$ and $(−2, −2)$).

How can this problem be solved in $O(n \log n)$ time?


texts: Traveling Salesman Problem with Neural Network

texts: I was curious if there were any new developments in solving the traveling salesman problem using something like a Hopfield recurrent neural network.  I feel like I saw something about recent research getting a breakthrough in this, but I can't find the academic papers anywhere.  Is anyone aware of any new, novel developments in this area?


texts: Doing matrix multiplication with $\lceil n^3 / \log n \rceil$ processors in $2\log n$ steps by Brent's principle

texts:
On a parallel machine with $n$ processors we can compute the sum (or product, or the result of any associative operation) on $n$ numbers in $\log n$ steps. In the first step combine neighbors to get $n/2$ numbers left, then combine them so that $n/4$ numbers are left and so on until a single number, the result, is left which happens after $\lceil \log n \rceil$ steps.  With this is it obvious that we can compute the matrix product of two $n \times n$ matrices $A = (A_{ij}), B = (B_{ij})$ with $n^3$ processors in $\log n + 1$ steps, in a first step compute all the $n^3$ products of the entries $A_{ik} \cdot B_{kj}$ for $i,j,k \in \{1,\ldots, n\}$. Then with $n^2$ processors compute the $n^2$ sums of the $n$ numbers $A_{i1}\cdot B_{1j} + \ldots + A_{ik}\cdot B_{kj}$. Hence we get by with $1 + \log n$ parallel steps.

Now the following argument is from C. Papadimitriou, Computational Complexity, page 361, to show that we get time $2\log n$ using just $n^2 / \log n$ processors (the argument used is called Brent's principle according to the book).

  We compute the $n^3$ products not in a single step as before, but rather in $\log n$ ''shifts'' using $\lceil n^3 / \log \rceil$ processors at each shift. We use shifts of the same $\lceil n^3 / \log n \rceil$ processors to compute the first $\log \log n$ parallel addition steps, where more than $\frac{n^3}{\log n}$ processors would be ordinary needed. The total number of parallel steps is now no more than $2\log n$, with $\frac{n^3}{\log n}$ processors [...].

(those arguments could also be found on these slides).

But I get more parallel steps as $2\log n$.

1) First we compute the $n^3$ products $A_{ik}\cdot B_{kj}$ with $\log n$ shifts, hence we need $\log n$ parallel steps for this.

2) If we combine the results as written in the introduction, then in the $k$-th step we have $n/2^k$ numbers to combine. Hence if $2^k < \log n$ we do not have enough processors to do this in a single step, hence we have to ''shift'' again, this time $\lceil \log n / 2^k \rceil$ times. If $2^k \ge \log n$ we can use a single parallel step as we have enough processors at hand.

Combining the above reasoning we get the following equation (I omit the rounding)
for the number of parallel steps:
$$
 \log n + \sum_{k=1}^{\log \log n} \frac{\log n}{2^k} + \log n - \log \log n.
$$
The first summand commes from the shift over the $n^3$ numbers, the second summand for the shifts needed if in the combination/summation of the product we still have to many numbers for our processors, and the last for the number of steps if we do have enough processors.
This equals
\begin{align*}
 & \log n + \log n \left( 1 - \frac{1}{2^{\log \log n}} \right) + \log n - \log \log n \\
 & = \log n + \log n - 1 + \log n - \log \log n \\
 & = 3 \log n - \log \log n - 1
\end{align*}
The last is in general more than $2\log n$, so what am I missing. Why does they argue they get by with $2\log n$ steps. Do I miss anything here?


texts: How to represent OOP concepts in algorithms in a standard way?

texts:
I have usually been using the Cormen algorithm format to teach some introductory courses in Programming. I mean something like this:

TreeSearch(k,n)
1. if x==NIL or k==x.key
2.     return x
3. if k<x.key
4.     return TreeSearch(k.left,n)
5. else return TreeSearch(k.right,n)

Actually I have not agree with a couple of lecturers in my institution that they insist to put the type of the variable that they are using in the algorithm. I mean, to do that, will it not be to make a bias toward the programming language and not to focus on the algorithm? For example what would happen if the student grab other programming language, like R or Python, that really do not care about the type of variable.

The other issue that I have is how to represent OOP algorithms in a nice algorithmic way. For example when I make a constructor should I put something like:

Class: car
Attributes: wheels
Constructor car()

or something like

Class: car
Function car()

also when I come to the part of inheritance, one of my colleages put the word super() to define inheritance in an algorithmic way, but again I think that is too Java-way to do this part. Usually they teach in that way because the practical part is made in Java, but again I think that the algorithm should be more freely, directly towards the logic, and not to an specific programming language.

Does anybody knows some standard to represent algorithms for OOP?


texts: How to simulate a parallel computer (with certain number of processors) on a serial computer

texts: I am a novice to parallel computing. I would like to solve the traveling salesman problem (TSP) using a parallel genetic algorithm (GA). I need to write a simulator of a parallel computer (for example, a multicore workstation) that will implement the parallel version of the GA. But the simulator should run on a serial processor. I know the basics of GAs and I know how to design a GA algorithm to solve the TSP. I thought that this could be an example of an "embarassingly parallel" problem in the sense that I could assign each processor a fixed number of chromosomes (i. e, potential solutions, with solution meaning a given sequence of cities to be visited as specified by the chromosome) with the task of calculating the objective function for each of the assigned chromosomes. In this case, the objective function for a given chromosome is the inverse of the total distance described by that chromosome. The task of performing crossover and mutation would be carried out by a master processor. If this is a valid or reasonable way of parallelizing the problem, then there's no need for inter-processor communication during the objective function evaluation step and I can hardly see this as a truly parallel problem. Since minimum communication is needed, wouldn't the speed scale with the number of processors? What would we learn from such a simulation that we don't already know? I'll be grateful for any thoughtful answers.


texts: If we had some $K_n$ subgraph where $K_n \subseteq G$, must the complete subgraph $K_n$ be an induced subgraph from $G$? In other words, can we create a situation where we remove vertices from a simple graph $G$ to obtain some complete subgraph where the subgraph was not complete when it was a part of $G$?


texts: Why is Pigeonhole sort not ideal for key count smaller than element count?

texts:
Wikipedia has this about Pigeonhole sort:

  Pigeonhole sorting is a sorting algorithm that is suitable for sorting lists of elements where the number of elements (n) and the length of the range of possible key values (N) are approximately the same.

I can see how it would be counterproductive to have more key values than elements, since we must iterate through all key values at the end of the algorithm.  But I don't get why it would be a problem to have far fewer keys than elements.

I'd appreciate help understanding this.


texts: Space complexity and recurrence equation of a recursive method

texts:
I recently had to do the assignment to determine the space complexity of methods similar to the following. I need to state the recurrence equation (line by line), derive the closed form and use that to determine the Big Oh of the space complexity. I have already handed it in, but I still have trouble understanding how to properly approach it.

public int call(int[] arr) {
    return calculate(arr, 0, arr.length - 1);
}

private int calculate(int[] arr, int a, int b){
    if(a > b) {
        return 0;
    }
    System.out.println("a = " + a + "\t b = " + b);
    return calculate(arr, a + 1, b)
            + calculate(arr, a, b - 1)
            + arr[a] + arr[b];
}

My line of thinking was the following:

If a > b then it needs a space to store the return value of 0, so the first block has a space complexity of 1. The second block also needs to store only one integer for the return value. However, it also calls upon itself twice. I reasoned that as the calls are consecutive, it can reuse the same space, so only needs the space of one.

This means that the recurrence equation is the following:
\begin{align*}
S(0)&=1\\
S(n)&=S(n-1) + 1
\end{align*}

The total number of simultaneous calls is most times it starts a new call without returning a value, which is at most $n$. Therefore the closed form equation is:
\begin{align*}
S(n)&=S(n-1) + 1\\
&=\big(S(n-2) + 1\big) + 1\\
&=S(0)+n\cdot 1\\
&=n+1
\end{align*}
And therefore $S(n)=O(n)$.

Still, intuitively I feel that I'm doing something wrong. Can you please check if this is correct, or if not, tell me how to do it right?


texts: Tools for practicing problem solving and expression of algorithms

texts:
I'm involved in a university course which is a crash course in the basics of problem solving and common concepts in computer science. The course contains a number of practical assignments and ends with a group project (~30 hours) in which at least two students solve a problem given to them. Lately we have focused on assigning problems to be solved by use of some computer program and/or device. Examples include visualizing algorithms in a virtual world by use of Alice and Scratch, as well as programming pre constructed Lego Mindstorms robots to perform specific tasks. We think those kinds of environments are suitable because of the low pre-requisites needed and because of the quick feedback that the students are given. As a bonus, the presentations tend to not be boring.

We are currently searching for additional tools to use in the course, which is why I ask you users of Stack Exchange Computer Science this:

What kinds of tools have you come across that could be used to practice problem solving and expression of algorithms? Feedback does not have to be visual -- we are investigating sound/song generation as a possible assignment. What is important is that basically any pair of students should be able to solve our assignments (with guidance if needed) in ~30 hours. That is, the students should not need any pre existing knowledge other than possibly basic mathematics. Whatever tool is required must be available for free.


texts:
Is there an efficient algorithm to visit/enumerate all unique connected subgraphs of a labelled graph?

E.g., when the graph is a path, $v_1v_2\dots v_N$, there are $N(N-1)$ unique connected graphs: for any $1\leq i<j\leq N$, the subgraph $v_i\dots v_j$. For graphs with denser edge structure, the number of unique connected subgraphs can be as high as $2^{|V|}$ (for cliques).

Fortunately, graphs I'm interested in have a lot of articulation points, so the total number of unique connected subsets should be polynomial in the size of the input.

For those who are interested, I'm modeling a problem in protein mass-spectrometry. Starting from a protein (chain of amino acids, with occasional long-distance bonds due to disulphide bonds), I'd like to generate a database of all possible sub-species that may result from breaks in peptide and/or disulphide bonds.


texts: Is there any connection between imperative programming and the Von Neumann architecture?

texts:
I have ran into a wall with this question in the exercise my teacher gave me, is there any actual connetion between the Von Neumann architecture and imperative programming ?

I have tried googling and finding questions similar to this, but I couldn't find anything, and the one question that I have found actually said that there shouldn't be any connection between the Von Neumann architecture and programming paradigms.

Any help would be appreciated, I'm new to StackExchange, so if I'm breaking any rules please do tell me :)


texts:
For double hashing, we have some constraints on $h'(k)$

(1) It should never evaluate to 0

(2) It should be relatively prime to m

How to show that all slots in an open addressing table will be included in a probe sequence.


texts: A question about postfix/RPN came up in my class due to the current ACSL competition. Is it a rule or convention that 4 + (5 * 6) in infix is written 4 5 6 * + in postfix, as opposed to 5 6 * 4 + in postfix? When the second postfix example is translated into infix, the order of the arguments is switched, but should that matter for operators with the commutative property?


texts: NFA on 3 states with equivalent DFA on at least 8 states

texts:
For all NFA $A = (Q, \Sigma, Q_0, \Delta, F)$ such that:

$\Sigma = \{0,1\}$
$|Q| = 4$

There exists a complete DFA $A' = (Q', \Sigma, q_0, \delta, F')$ such that:

$L(A) = L(A')$
$|Q'| \leq 15$

How does one go about the proof of such a thing? I think it should be true that if $|Q| = 3$, then $|Q'| \leq 7$, however I am not able to formulate a strong claim. Any help in this matter would yield great fruit.


texts: Is there k-approximation algorithm for MIS in general graph reduced from dual of k-uniform hypergraph?

texts:
I have been thinking about this problem for a long time. If anyone can help me out here, I'd really appreciate it.

A hypergraph $H = (V,E)$ consists of a set $V = \{v_1, v_2, \cdots, v_n\}$ of vertices and a set $E = \{e_1, e_2, \cdots , e_m\}$ of edges, each being a subset of $V$.

A subset $M \subseteq E(H)$ is a matching if every pair of edges from $M$ has an empty intersection.

The dual $H^*$ of $H$ is a hypergraph whose vertices and edges are interchanged, so that the vertices are given by $\{e_1, e_2, \cdots , e_m\}$ and whose edges are given by $X = \{X_1, X_2, \cdots, X_n\}$ where $X_j = \{e_i | v_j \in e_i \}$, that is $X_j$ is the collection of all edges containing $v_j$.

The degree $d(v)$ of a vertex v is the number of edges that contain it. H is k-regular if every vertex has degree k.

The dual of a uniform hypergraph is regular and vice versa.

My question: maximum matching problem is equivalent to maximum independent set problem in its dual graph, right? We know that k-uniform maximum matching has k-approximation algorithm, then maximum independent set in its dual hypergraph also has k-approximation ?

If we reduce the dual hypergraph to general graph (k = 2) by replacing each edge with a clique (convert 1-vertex edge into 1 vertex), does this make the maximum independent vertex set in the resulted general graph k-approximation??

I have been thinking about this for a long time, but not sure about it. If you have any thought please help!


texts: How to transform an Abstract Syntax Tree (AST) to an Abstract Binding Tree (ABT)? (for machine learning fo theorem proving)

texts:
I was reading the HOList paper that applies Graph Neural Networks (GNNs) to the HOL Light (HOList) data set and benchmark for ML for theorem proving. They describe their results etc but there is no code I can find or even pseudocde (algorithmic description) of how to transform an AST -> ABT. How does one do this?
This seemed like a solved problem obviously so I wanted to avoid re-inventing the wheel - especially if something already existed that is probably optimized or takes care of nuanced of the process.

References:

paper https://arxiv.org/abs/1905.10006
zulip chat about it: https://leanprover.zulipchat.com/#narrow/stream/219941-Machine-Learning.20for.20Theorem.20Proving/topic/HOList
cross post on quora: https://qr.ae/pGroph
reddit DL: https://www.reddit.com/r/deeplearning/comments/nfdkbg/how_to_transform_an_abstract_syntax_tree_ast_to/
reddit FM: https://www.reddit.com/r/formalmethods/comments/nfdqwl/how_to_transform_an_abstract_syntax_tree_ast_to/


texts: Locality Sensitive Hashing on binary / categorical data

texts: I'm wondering if it already exist LSH or an alternative to apply a fast segmentation of binary/categorical data and how to implement it.


texts: Name for almost random memory distribution on the heap

texts:
If I had a heap like the following: with blue blocks being occupied memory and white blocks being free memory

What is the general name given to the situation illustrated, where the free and occupied cells become distributed almost 'randomly'?

This is an exam question, I've tried searching online and through the provided slides but to no avail.


texts: How to apply ant colony optimization to the TSP but repeating nodes and edges

texts:
I'm learning the Ant Colony Optimization Algorithm and I would like to apply it to a variation of the TSP problem (find the path that start from a node, crosses all nodes and finish in the initial node) where you can cross a node or edge more than once. Actually, my problem wouldn't have solution for the TSP because some nodes only have one edge.

Basically, I see two problems:

In most of examples I've seen, nodes are represented by (X,Y) positions and they suppose that is a complete graph, so from every node you can go to every node, which involves that an ant will always have a edge to go to a node that hasn't been visited yet. But in this problem, it may happen that an ant arrives to a node where al the adjacents nodes have already been visited, so, how would it decide the way to go? The worst case would be that there is only one node left to visit and it is the one farthest from the current node.
What repeating edges involves to pheromones. If and edge is crossed several times in the tour, it could or could not have much more pheromones, depending on the implementation, and I'm not sure if it could have a negative impact.

This is a very simple example, where red edges mean that the cost is 1 and blue that is very big, for example 20. As you can see for the best path you need to repeat edges.

Regards.

EDIT2:

I want to add that my particular problem has around 1000 nodes and 2000 edges.

I have some new ideas. First of all it looks like I must have a way to find the distance and the path between cities, so that each ant can decide which is the next city to go. The main option is the Johnson's Algorithm which offers good performance for this sparse graph.

To store all the possible paths I could use a triangular matrix where each element is a vector of nodes. If we suppose that the mean of the paths is 50 nodes (represented with 2 bytes integers) the memory needed would be around (N: nº nodes) N*N/2*50*2 bytes so more or less 50Mb.

The other option is to have the same structure but in each element of the matrix I would have only one node, and to find the path I would have to access the position of that node and so on until I find the one I'm looking for. Because if the shortest path from node A to node C crosses B, the path is the shortest path from A to B joined with the one from B to C. This option need N*N/2*2 bytes more or less 1Mb. But it will probably have worse performance because it needs much more access to memory and I doesn't take advantage of space locality so it will have many cache misses.

About ACO, maybe I can use an algorithm like Minimun Spanning Tree or something like that to put some extra initial pheromones, but I'm not sure if that will be positive.


texts: Testing whether the language of one automaton is a subset of another

texts:
Is there an algorithm to solve following problem?

Given two finite automata $A$ and $B$. Determine whether the language recognized by automaton $A$ is a subset of language recognized by automaton $B$ or otherwise.


texts: To detect isomorphic graphs Is it enough to check if they have the same number of same degree vertices?

texts:
Given two lists of non directional graph edges e.g.
 [(1,3),(3,5),(5,1),(5,7)] [(4,5),(2,3),(3,4),(4,2)]
In order to check if the two graphs are isomorphic is it enough to count the vertices with the same degree between them?

e.g. Vertice   1: 2    1: 0
               2: 0    2: 2
               3: 2    3: 2
             4,6: 0    4: 3
               5: 3    5: 1
               7: 1    6,7: 0

So in our example: both graphs have 2 vertices with 2 edges 1 with 3, one with one and 3 with 0


texts: Splitting the array in the median-of-median solution for $k$th smallest element problem

texts: Regarding the median of medians solution to the $k$th smallest element in an array, why does the algorithm split the array into subarrays of length $n/5$, where $n$ is the length of the initial array? Why not $n/7$ or $n/3$? Why 5??


texts: Reduction to complement of Accept Problem

texts:
I am reducing a given Turing Machine to the complement of the known undecidable problem,
$$ Complement(A_{TM}) = \{ \langle M,w \rangle \mid M  \text{ is TM}, w \not\in L(M) \}$$

To this Turing Machine, known as SPARSE TM:
$$
SPARSE_{TM} = \{ \langle M \rangle \mid M \text{ is 1-tape TM}, |L(M)| \leq 1000\}
$$

Here is what I have so far, but I think I need help because one of the statements I make seems fishy.

Assume there is a TM S that decides the complement of the accept TM and a TM R that decides SPARSE. Then S looks like:

S = "On input `<M,w>`:
    Construct M':
        M' = "On input x:
            if x in L(M):  #Fishy statement
                accept
            else: reject
     Run R on <M'>
     if R accepts: accept; if R rejects: reject

This (if right) would then reduce the SPARSE TM and prove that it is undeciable, right? Any help would be appreciated.


texts: Proof that quicksort's running time is ∼1.39 n log n

texts:
In the fourth edition of Sedgewick's Algorithms, it's claimed that the running time of QuickSort is $\sim 1.39n\log_2 n$. I'm trying to find a "simple" proof and explanation of this.

All I know is that the total running time obeys $$C_n = C_{\mathrm{partitioning}} + C_{\mathrm{leftArray}} + C_{\mathrm{rightarray}}$$

and that quicksort's average case is about $2n\log_\mathrm{e}n$.


texts: How do I use induction to show that the language of a grammar is contained in a given set?

texts:
Given that I have the grammar

$\qquad\displaystyle G_1 = (\{a, b, c, d\}, \{S, X, Y \}, S, \{S → XY, X → aXb, X → ab, Y → cYd, Y → cd\})$,

how am I supposed to prove that

$\qquad\displaystyle S(G1) ⊆ \{a^{n+1} b^{n+1} c^{m+1} d^{m+1} \mid n, m ≥ 0\}$

by using Induction?


texts: N numbers, N/2 pairs. Minimizing the maximum sum of a pairing. Proving greedy algorithm

texts:
So say I have n numbers, where n is even. I want to pair the numbers such that the maximum sum of the pairs is minimized. For example -2, 3, 4, 5. The ideal pairing is (-2, 5), (3, 4), since its maximum sum is 3 + 4 = 7, and that is the minimal sum possible for a max sum in any pairing. The key to the algorithm is to sort the values from least to greatest. Then pair the least with the greatest, and so on, until you reach the center of the ordering.

Example: 3, -2, 4, 5

Algorithm sorts the values: -2 , 3, 4, 5

Then pairs first with last: (-2, 5)

Then pairs the next available first and last: (3, 4)

Terminates since no pairs left.

This is a greedy algorithm and I am trying to prove that it is always correct using a "greedy stays ahead" approach. My issue is that I am struggling to show that the algorithm's maximum sum is always $\leq$ optimal maximum sum. My intention was to suppose for contradiction that the optimal maximum sum is $<$ the algorithm's maximum sum. But I'm not sure how to find a contradiction. How would this proof go?


texts: Constructing a directed graph for O(1) queries

texts:
This question appeared in an undergrad data structures final. The details are sound.

I need help to design a data structure for a directed graph with the following properties:

Initialization should be done in O(1) time.
AddVertex(id1,id2,...idK) - Add a new vertex to the graph. The new vertex is added with id=N+1 where N is the number of existing vertices.
id1...idK are the neighbors of the new vertex, such that there is an outgoing edge from the new added vertex to each of the vertices id1 .. idK.
This should be done in O(K) time.
GetNumberOfNeighbors(id) - Return the number of outgoing edges for a vertex with a given id (id is in 1..N). This should be done in O(1) time.

All O(1) times are for worse case.

I know that the idea is to allocate a new array of K*constant length during the AddVertex method, and to copy K vertices to it in O(K) total, but I don't know how to do this exactly.

Thanks a lot


texts: Is it decidable whether a TM accepts more than one word?

texts:
Is the following language:
$\qquad\displaystyle L= \{\langle M\rangle \mid M \text{ is a TM }, |L(M)|>1\}$
Turing-decidable?

I think it isn't, because if a Turing machine T can decide L, then T can say if M stops or not (impossible this is the halting problem). So T accepts when M stops and accepts the string (with a length > 1) and refuses otherwise.
I want build a Turing machine S, based on T, that decide if M with an input w stops or not, but how I can build it?
If T exists then also S exists, so the halting problem would be Turing-decidable (impossible).
I think L is only Turing-recognizable. Is my reasoning right?


texts: Complete finite automaton to never fail a match but either match original or up until the orginal

texts:
Suppose I have a finite automaton to match a simple string "abc" and I built some software around it to not only match the start of a string or a full incoming string, but rather to search through a string and find the first match. As an example consider the string to be "12abcxxx".

The naive approach is to start with reading the '1' and trying a transition in the automaton. It fails. So we advance the input and try again, with `2'. Fail again. Now read 'a', 'b', 'c' nicely transition though the automaton, reach the stop state, store it, read 'x', fail and declare a match for the latest stop state we ran through.

If we assume that every 'fail' in this algorithm is inefficient, while transitions through the automaton are fast, an improvement would be to extend the automaton such that it matches either 'abc' or '[^a]+' and mark the different stop states as 'found abc' and 'not found abc'. Then '123' would be a match, supposedly much faster then three fails to skip over.

But adding '[^a]+' is not the only optimization. We could even add something like '([^a]|a[^b]|ab[^c])+' (which is not completely correct) to the automaton to skip over the non-matching sequences quickly.

Question: Working with a finite automaton that allows to mark stop states with different markers, and given an automaton for a regular expression re, is it possible to "complete" the automaton such that it implements the quick skip over non-matching substrings as described informally above.

If it is possible, what would be the operation to perform either on the regular expression or an NFA or DFA representation? I would expect the result to talk about something like the complement set of the prefix set recognized by the original automaton.

Question rephrased: Reading the first answer I realized that the question is equivalent to the following: Given a regular language $L$, is there a regular language $L_p$ that satisfies the following: For all strings $s\in\Sigma^*$, $L_p$ shall contain the prefix of $s$ that ends just before an $s_x\in L$ or the complete $s$ if no such substring exists.


texts: All strings that contain no run of a's of length greater than two for $\Sigma = \{a,b,c\}$

texts:
The solution to this problem is $$(b + c)^*+(b + c)^*((a + aa)(b + c)^+)^*(a + aa)(b + c)^*.
$$
Isn't the $+$ sign a union between sets?, I am asking because I am viewing the line $(b + c)^*+(b + c)^*$
as $A\cup A$ which is $A$ so I do not see a reason to repeat the same set.