texts: So if a problem is more difficult the language it represents is smaller?

texts:
I'm reading the definition of polynomial time reducible:

  Let $L_1, L_2$ be two language. If $L_1$ is polynomial time reducible to $L_2$ then exists $f:\{0,1\}^*$ s.t. $\forall x\in\{0,1\}^*$ $$x\in L_1\iff f(x)\in L_2$$

For me this means the $L_1$ may be bigger (in cardinality) than $L_2$, but $L_2$ is more difficult since $L_1$ can be solved after reduced to $L_2$?


texts: Relationship between dependent sum type and dependent product type?

texts: Since dependent sum type ($\sum_{n\in \mathbb{N}} P(n)  $) is interpreted as ($\exists n\in \mathbb{N}:P(n) $) and dependent product type ($\prod_{n\in \mathbb{N}} P(n)$) is interpreted as ($\forall n\in \mathbb{N}:P(n)$), is it correct to say that an element of dependent product type represents a set(in a vague way) of elements of corresponding dependent sum type for every n?


texts: Using singly linked list instead of a doubly linked list?

texts: Are there advantages of implementing a singly instead of a doubly linked list other than space?


texts:
I have this function

int fct (int Y){
        int y = 0 ;
        for ( int i =0; i<Y;++ i ){
            for ( int j=i ; j >=0;--j ){
                y++;
                }
            }
            return y ;
    }

I want to know the order of this function, I know that the first for loop its O(n), but I confused to the second for lood, I'm not sure if is O(n).

I think the order of function its O(n^2)

Any help?


texts:
According to this German Wikipedia article, the time required to merge relations $R$ and $S$ is $\in \mathcal{O}(|R| + |S|)$ if both relations are already sorted.
[Note: You don't really need to read the text and the link jumps right to where the time complexity is stated. But I added a translation of that section to this question for some clarity.]

Assume $R = S$ with $R$ having 2 columns. One is a random number and one is always 5 for every line. Join $R$ and $S$ on the column which is 5 for every line. The resulting output's space complexity is $\in \Theta(|R| \cdot |S|)$. Time complexity is always $\in \Omega(\text{spaceComplexity})$.

How can the time complexity stated by the Wikipedia article be true?

Here is the "Sort-Merge Join" section translated to English. Sorry, no markdown quote, just everything from here on is the quote. It's translated poorly (not how you would write it in English if you know what you're writing) in some parts to preserve the meaning as well as possible. I marked my own inline comments with ///.

Quote of https://de.wikipedia.org/wiki/Joinalgorithmen#Sort-Merge_Join

Sort-Merge Join

Both relations get sorted by their join attributes. The result can be determined via a single scan through both sorted relations.

The algorithm is only suited for natural join and equi-join.

Pseudocode

Implementation of $R\bowtie_{R.a=S.a} S$ in pseudocode:

p_r := first tuple in R
p_s := first tuple in S
while(p_r != endof_r && p_s != endof_s)
    // Collect all tuples in S with the same join attributes.
    M_s := set with contents p_s /// Yes, it says "with", not "of".

    foreach(t_s in S > p_s)
        if(t_s.a = p_s.a)
            M_s += set with contents t_s
        elseif // I think they mean "else".
            p_s := t_s
            break foreach
        endif
    endforeach

    // Seach suitable start tuple in R. /// "passend" can also be translated "fitting" or "matching", not just "suitable".
    foreach(t_r in R > p_r)
        p_r = t_r
        if(t_r.a >= t_s.a)
            break foreach
        endif
    endforeach

    // Output tuples.
    foreach(t_r in R > p_r)
        if(t_r.a > t_s.a)
            break foreach
        endif

        foreach(t_s in M_s)
            Write output: (t_r, t_s)
        endforeach
        p_r = t_r
    endforeach
endwhile

Evaluation

Sorting can be done with effort $\mathcal{O}(|R|\log|R|+|S|\log|S|)$. The number of block accesses to sort $S$ is $b_s\left(2\log\frac{b_s}{b_{free}}\right)+b_s$ in the worst case, analogous for $R$.

A merge of both relations after sorting them costs $\mathcal{O}(|R|+|S|)$. In the best case – i.e. the relations are already sorted –, the costs of merging are the only ones.

In the normal case, the total costs are $\mathcal{O}(n\log n)$.

Variants

[Not translated because it doesn't seem to be important for the question.]


texts: How to encode date as input in neural network?

texts:
I am using neural networks to predict a time series.
The question I'm facing now is how do I encode date/time/serial no. of each input set as an input to the neural network?

Should I use 1 of C encoding (used for encoding categories) as described here?

Or Should I just feed it the time (in milliseconds since 1-1-1970)?

Or is feeding it the time unnecessary as long as I feed it the rest of the data chronologically?


texts: Contrast Enhancement For An Image Using A Gaussian Function

texts:
I am working on a program that involves detecting faces in photos, i am reading a paper that someone has wrote and they said that they had more success detecting faces once he they applied some enhancements to the image, one of these being a contrast enhancement. The exact words are...

  Contrast enhancement improves the overall quality of the image. Gaussian convolution using
  the Gaussian function G(x, y) is first applied with the input value channel image in the HSV
  space. The convolution process can be expressed as follows

They then give you Equation 3: $V_{con} = V_1(x,y) \oplus G(x,y)$ NOTE: $V_1$ is the original value

  $V_{CON}$ in Eq. 3 denotes the convolution result, which contains the luminance information from
  the surrounding pixels. The center pixel value is now compared with the Gaussian convolution
  result in order to find the amount of contrast enhancement of that center pixel. This process is
  described by the following equation

Equation 4: $V_{ce}(x,y) = 255V_{le}(x,y)^{E(x,y)}$ NOTE: $V_{le}$ is the result of another enhancement done previously.

  where $V_{CE}(x, y)$ is the result of contrast enhancement and $E(x, y)$ is given by the following relation

$E(x,y) = (V_{con}(x,y)/V_1(x,y))^g$

  Here g is the image dependent parameter determined by using the standard deviation of the
  input value channel image. If the center pixel is brighter then the surrounding pixels, the contrast
  of the pixel is pulled up. On the other hand, if the center pixel is darker then the neighboring
  pixel then the contrast of the pixel is lowered.

The problem is that with my understanding of maths (NCEA Level 3, Last year at collage) i don't understand how to do the first part, any help would be much appreciated

The full paper is here: http://jips-k.org/dlibrary/JIPS_v09_no1_paper9.pdf


texts:
In FKS hashing, I wonder if the size of the table $G[1..n]$ (used to record the functions $g_i$ which is chosen randomly; one entry per bucket) is really strictly $O(n)$. Given that the probability of a hash function $g_i$ is higher than 0.5, I can see that it will mostly hold small values (assuming we start with $g_0$, and if that doesn't work, try $g_1$ and so on). But I think for $n$ to $\infty$ there will be larger values as well, so that the number of bits for each entry is $log^*(n)$ and not fixed. Right?

The reason I ask is that many minimal perfect hash functions, such as the CHD algorithm, rely on a similar mechanism, and those algorithms claim to be strict $O(n)$ space.


texts: Trying to understand CLRS bucket sort analysis

texts:
I'm trying to understand the analysis of bucket sort in CLRS. Specifically, equation 8.2 that states:

$$ E[{n_i^2}] = 2 - \frac{1}{n} $$

To prove, CLRS:

Random variable denoting number of elements that fall into bucket i:

$$ {n_i} $$

An indicator random variable that a given element in the input falls into a particular bucket.

$$ X{_i}{_j} $$

so

$$ {n_i} = \sum_{j=1}^{n}X{_i}{_j} $$

Now, CLRS says to expand the square and regroup the terms:

$$ E[{n_i^2}] = E\left[\left(\sum_{j=1}^{n}X{_i}{_j}\right)^2\right] $$

I can see how the above goes to the next step:

$$ = E\left[\sum_{j=1}^{n}\sum_{k=1}^{n}X_{ij}X_{ik}\right]$$

I'm confused as to how the above turns into:

$$ = E\left[\sum_{j=1}^{n}X_{ij}^2 + \sum_{1 <= j <= n}\sum_{1 <= k <= n, k != j}X_{ij}X_{ik}\right] $$

For what it's worth, the Algorithms in a Nutshell books has a section on bucket sort that also analyzes why it's 2 - 1/n, and it helps me see things a bit more clearly, but still am unclear about the above. From the AiaN book:

$$ E[n_i^2] = Var[{n_i}]+ E^2[n_i]$$

where

$$ Var[{n_i}] = n * p * (1-p) = n * \frac{1}{n} * \left(1 - \frac{1}{n}\right) = 1 - \frac{1}{n} $$

and

$$ E[{n_i}] = n * p = n * \frac{1}{n} = 1$$

which equals 2 - 1/n


texts:
I understand how I would do this if the problem were as such

$8n + 5$ is $O(n)$

$c>0$ and an integer constant $n(not 0) \geq 1$ such that $8n + 5 \leq cn$ for every integer $n \geq n(not 0)$

we could let $c= 13$ and $n(not 0) = 1$

or we could let $c = 9$ and $n( not 0) = 5$.

I'm just not sure how to go about $6n^2 +12n$


texts: Graph Coloring Problem : How to Think About Algorithms Exer 1.6.2

texts:
The problem says:

Given an undirected simple graph G such that each node has at most d + 1 neighbors, color each node with one of d + 1 colors so that for each edge the two nodes have different colors.

Hint : don't think too hard. just color the nodes. what loop invariant do you need?

I was trying to solve this.. but quickly realized a complete graph of 4 vertices, whose vertices have at most 3 neighbors, cannot be colored with one of 3 colors so that each node has different color nodes.

I did some research and it seems like the book had a typo and it should have been "... each node has at most d neighbors, color each node with one of d + 1 colors... "

It is possible to find a graph with maximum degree of d + 1 that can be colored with d + 1 colors but this cannot be true for any graph with max degree of d + 1, right?

Am I correct in assuming that the typo should be corrected like how I did so AND about the last remark?


texts: n'th cheapest MST in a graph, with multiple edges that can have the same weight

texts:
I'm trying to think about an algorithm for this problem.
I know there is an algorithm for the second cheapest MST in a graph, but
if I understood it correctly it only solves cases in which every weight is singular. My question is how do I get the n'th (say 3rd) MST where duplicate weights count as same tree.

I thought about first applying prim's algorithm to get the MST, then given that such edge exists take the smallest out of the edges in G that are not in MST1,
and then, because we create a circle, remove the maximum edge that is in the circle but still smaller than the edge we added.
I believe it will take linear time.
Am I on the right direction?


texts: Is there a grammar for this language? $w^{m-1}aca^m$?

texts:
I have to form a free context grammar for this language $w^{m-1}aca^m$ where $w \in \{a,b\}$, so what I have been able to do is this:
$X \rightarrow SacA$
$S \rightarrow aS|bS$
$A \rightarrow aA$
But I don't know how to do it or if possible, condition the exponents as long as $ S $ is repeated $ m-1 $ times, and $ A $, $ m $ times.


texts:
So I thought this (though somewhat basic) question belonged here:

Say I have a graph of size 100 nodes arrayed in a 10x10 pattern (think chessboard). The graph is undirected, and unweighted. Moving through the graph involves moving three spaces forward and one space to either right or left (similar to how a chess knight moves across a board).

Given a fixed beginning node, how would one find the shortest path to any other node on the board?

I imagined that there would only be an edge between nodes that are viable moves. So, given this information, I would want to find the shortest path from a starting node to an ending node.

My initial thought was that each edge is weighted with weight 1. However, the graph is undirected, so Djikstras would not be an ideal fit. Therefore, I decided to do it using an altered form of a depth first search.

However, I couldn't for the life of me visualize how to get the shortest path using the search.

Another thing I tried was putting the graph in tree form with the starting node as the root, and then selecting the shallowest (lowest row number) result that gave me the desired end node... this worked, but was incredibly inefficient, and thus would not work for a larger graph.

Does anyone have any ideas that might point me in the right direction on this one?

Thank you very much.

(I tried to put in a visualization of the graph, but was unable to due to my low reputation)


texts: Is there a hierarchy theory for time-bounded Kolmogorov complexity?

texts: We know that there are languages in $DTIME(n^t)$ and not in $DTIME(n^s)$ for all $t>s$ due to simple diagonal arguments (i.e., the Time Hierarchy Theorem), but I'm wondering if there is any equivalent results known for time-bounded Kolmogorov complexity. That is, given polynomials $p(n)=n^t$ and $q(n)=n^s$ with $t>s$ is it always true that for any sufficiently large length $k$ there exists a string $x$, $|x|=k$ such that $C^p(x)<C^q(x)$? If this is not true, is it true for ${CD}^p(x)<{CD}^q(x)$?


texts: BosonSampling: $\# P \subseteq FBPP^{{NP}^{\mathcal{O}}}$ implies $P^{\#P}\subseteq BPP^{{NP}^{\mathcal{O}}}$

texts:
I am a complexity beginner, actually a quantum physicist.

In their famous BosonSampling paper, Aaronson and Arkhipov show amongst other things a polynomial time machine solving the problem of BosonSampling exactly, would result in the collapse of the Polynomial Hierarchy.

If you are not familiar with BosonSampling or any quantum physics at all, do not bother, it won't be necessary for this question: I am interested in one particular aspect of the argument, that I do not understand because of my lack of background: It seems to have to do with the relation of function/search problems and corresponding(?) decision problems.

Specifically, on page 33, in the the proof of Theorem 1, they show that a #$P$-hard problem is also contained $FBPP^{{NP}^{\mathcal{O}}}$ where $\mathcal{O}$ is an oracle to some problem called BosonSampling. From there, they immediately seem to get that
$$P^{\#P}\subseteq BPP^{{NP}^{\mathcal{O}}}$$

My question is: How? I understand that there is a difference between counting/function problem complexity classes like $\#P$ or $FBPP$ and classes for decision problems. But how to relate the results? In particular, why is it $P^{\#P}$ on the left?


texts: Better results for minimum vertex cover algorithms

texts:
Currently I'm using the well-known ratio-2 algorithm which is nice and fast, but I'm looking for an intuitive way to improve my results.

All the articles I read so far were way too complicated for me, I'm looking for simple ideas to improve the results.

What I got so far:

def approx_vc(g):
    """
    Find a vertex cover that in the worst case is twice the size of the mvc (ratio 2).
    :param g: Graph object
    :return: Set of integers as vertices.
    """
    c = Set()
    e = g.get_edges()
    while len(e):
        u, v = e.pop()
        c.update([u, v])
        for edge in list(e):
            if u in edge or v in edge:
                e.remove(edge)
    return c


texts: Natural deduction: understanding bottom elimination (¬e)

texts:
I am new to natural deduction and upon reading about various methods online, I came across the rule of bottom-elimination in the following example.

I do not understand the step in line 10.

Upon inspection, my initial thought would be that the assumption of ¬p and p both being true is absurd, hence anything can be inferred ( in this case 'p'). However, if this were the case where would you stop (this seems to be an overly powerful tool)? So I assume that this idea is wrong.

Could someone help me understand the rule?

NOTE: I came to StackExchange due to the lack of resources and specific information online.


texts: Why does the Huffman coding algorithm produce a valid tree?

texts:
I am not asking about the Huffman Code, but the most widely described algorithm for generating one, also described on the english wikipedia: https://en.wikipedia.org/wiki/Huffman_coding#Compression
Now, I am not really concerned with the code being optimal or not, because many proofs for this can be found, but there is one thing that bothers me - why can I be sure, that for any path on the Huffman Code tree, no string constructed from labels is a prefix of another string in the tree?
Considering a simple tree (source: http://homes.sice.indiana.edu/yye/lab/teaching/spring2014-C343/huffman.php):

It has these codes:
E - 0
U - 10
D - 01
L - 110
C - 1110
M - 11111
Z - 11110
K - 11111,
and it is obvious, that none of these codes is a prefix of another. However, I am looking for a general proof that this is true for any Huffman tree, which for some reason I am unable to find. I would be grateful for any sources.


texts: Turing machine that increments a binary number by 1

texts:
I was asked to construct a Turning Machine that computes the increment of a binary string by 1- The Turing Machine receives a binary string and accept a string which is an increment by 1 of the input, written to the left of the head . I was given the fact that the head first reads the MSB.

I thought of an Idea but I do not see how to put it into action:
My idea was to:

1.First put a $ sign at the beginning of the string

2.Place the entire string right side to it

3.Starting to increment from the end, switching $1$ with $0$

4.Once I stumble upon $0$ I replace it with $1$ and then accept it or Once I stumble upon $ I replace it with  1 and accept

I can't seem to find a way to put a $ at the beginning of the string without losing any information..any help with will be very helpful!


texts: Predicate Logic - negating the conclusion to prove logical consequence?

texts: In Predicate Logic, if you want to prove the logical consequence using the method of resolution, do you ALWAYS start off by negating the conclusion?


texts: Deciding on decidability of a problem and reducing it to halting problem if not decidable

texts:
Given are two following languages:

$L_1 = \{ w\#x \hspace{1mm} |  \hspace{1mm} w,x \in \{0, 1\}^* \text{ where } M_w \text{ with input } x \text{ visits each of its states at least once} \}$

$L_2 = \{ w\#x \hspace{1mm} |  \hspace{1mm} w,x \in \{0, 1\}^* \text{ where } M_w \text{ with input } x \text{ does not visit at least one of its states} \}$

Are the languages decidable/undecidable/semi-decidable?

The intuition tells me that both languages cannot be decidable, for the simple reason that if any of them ends up in a loop, it can never be decided whether all states were visited. Is my way of thinking correct in both cases?

I would also say that $L_1$ is semi-decidable - in case all states were visited after some finite number of steps, we could decide the language and if not, we still won't be able to say anything about it.

Is it possible to reduce the halting problem to this problem to prove that it's not decidable?

Thank you!


texts: How do you find the height of the recurrence tree $T(n,k)=T(\frac{n}{2},k)+T(n,\frac{k}{4})+nk$

texts:
I try to find tree height such that first i define:
$H(n,k)=H(\frac{n}{2},k)+H(n,\frac{k}{4})+1$
then find height of left branch of tree=logn & right branch of tree=logk,but now why height of tree is equal to logk+logn?i guess height of tree is Max(logn,logk)why my geuss is not true?


texts: Example of an algorithm where a low-order term dominates the runtime for any practical input?

texts:
Big-O notation hides constant factors, so some $O(n)$ algorithms exist that are infeasible for any reasonable input size because the coefficient on the $n$ term is so huge.

Are there any known algorithms whose runtime is $O(f(n))$ but with some low-order $o(f(n))$ term that is so huge that for reasonable input sizes it completely dominates the runtime?  I'd like to use an algorithm like this an an example in an algorithms course, as it gives a good reason why big-O notation isn't everthing.

Thanks!


texts: Constructing a data structure for a computer algebra system

texts:
In thinking about how to approach this problem I think several things will be required, some tivial:

An expression tree where non-leaf node is an operation (not sure if that part is redundant), but not every node has just two children.
All nodes for operations have a defined number of children that they must have (some operators are unary (like $!$) while others are binary ($*,+,-,$ etc) and still other are n-ary ($f(a,b,d)$ and versions with different amounts of variables).
All leaf nodes are some type of number

I am under the impression that the tree should not explicitly retain information regarding the order of operations, but rather that information should be used in the parsing stage to insert things into the tree correctly.

This leads to the question, how should inserting to a specific position in the tree be done? Simply passing a list of directions (from root, take node zero, then node 1, etc, then insert) will work, but it seems overly clunky.

Or should I avoid that situation entirely (not talking about editing an equation here, just building a representation of one) by using the fact that in some sense the tree must be complete (all binary operations MUST have two children, etc, and even operators that are seemingly ambiguous (the $_{^-}$ sign for example) but these ambiguities are resolved before this point. That would all me to insert "in order"

Am I taking a reasonable approach? Does it make no sense whatsoever?

Additionally, are there papers or articles that I should read about CAS systems?

Clarification: The tree will need to support three different compound operations.

Creation: (from a string, but how to actually do that is beyond the scope of this question)
Reduction: (to some type of canonical form) so that if $a+b$ and $b+a$ are both entered and reduced, they will form identical trees.
Evaluation: Be able to traverse the tree

These are all the operations that need to be supported. There are probably many other more basic operations that may need to be supported, but in this case it only matters that the three operations above are supported. My understanding is that search for example is not a property that will be required, but deletion will be (of a whole subtree).


texts: I would like to know how would one go about and answer this question. I know that a language is decidable if a turing machine exists that accepts the strings in that language, and rejects otherwise. Would I need to create a turing machine to show this or is it enough to create a PDA and claim a TM can be created from a PDA such that it accepts and halts all strings in it and rejects otherwise. Also, if anyone can refer a good post to learn how to create a PDA from CFL would be greatly appreciated. Thanks!


texts: fully homomorphic encryption with information-theoretic security?

texts:
An encryption algorithm with information-theoretic security is one which even with infinite amount of computation cannot be broken. That is, given only the ciphertext, no amount of computation can reduce your uncertainty about the plaintext.

Fully homomorphic encryption is, roughly, an encryption scheme where $\text{Encr}(T(x)) = T(\text{Encr}(x))$ for arbitrary transformations of the ciphertext and plaintext (this is not entirely accurate but that's not important for this question).

Is it theoretically possible to have an information-theoretically secure FHE scheme? That is, is it possible to encrypt a plaintext $x$, have an external party do computations on them in a fully homomorphic way, without them being able to gain ANY information about the plaintext even with infinite? computing power?


texts:
I'm new to information theory and I am struggling to understand this problem. Let $p(x,y)$ given by:

How can we calculate $H(X|Y)$? I know $H(X|Y)=H(X|Y=0)+H(X|Y=1)$ but then I don't know how to go further.


texts: Algorithm for answering queries of the type "largest interval contained in the given interval"

texts:
I have been wondering over the following problem:

Given a set $S$ of intervals on the number line. We can do two operations on them:

Add a new interval $[l_i,r_i]$ to $S$
Given an interval $[l_j, r_j]$, which is possibly not in $S$, find the longest interval from $S$ which is contained entirely in $[l_j, r_j]$

If I didn't have operation $1$ I have found a solution using a persistent segment tree.

For the full version, there is the trivial solution which runs in $O(QN)$ ($Q$ - number of queries, $N$ - total number of intervals added). I also found that  using interval tree, I can directly find which intervals intersect the query interval and then I can check them manually. However, is there an even better solution? Maybe $O(Q\log N)$ or $O(Q\log^2N)$?


texts: How can the Operating System run on the same chip it is supposed to be managing?

texts:
From my readings about Operating Systems (reading the basic material on Wikipedia, tech sites, etc) I've learned that the Operating System is a program that allows programs and applications to interact with the hardware in an efficient and safe way.

However I'm confused about how the Operating System oversees the computer's operation when it itself needs to be operated.

What do I mean? Well, the way I would imagine an Operating System to work, is that on a computer, there would be two CPUs. One that runs the OS all the time, and another that the OS uses to run the computer.
However, it turns out that the OS is running on the same CPU that the other processes are. This is like a manager having to work on the same production line as his employees, and only gets to use the power tools when another employee is done with them. He would not be a very effective manager, since he wouldn't have the ability to issue orders if his employee is even slightly undisciplined.

So how can it be that the OS only runs part of the time on the same CPU that has to be shared between all the other processes? How does this end up working out?


texts:
Solving the recurrence relation $T(n) = 2T(\lfloor n/2 \rfloor) + n$.
The book from which this example is, falsely claims that $T(n) = O(n)$ by guessing $T(n) \leq cn$ and then arguing

$\qquad \begin{align*} T(n) & \leq 2(c \lfloor n/2 \rfloor ) + n \\ &\leq cn +n \\ &=O(n) \quad \quad \quad \longleftarrow \text{ wrong!!} \end{align*}$

since $c$ is constant.The error is that we have not proved the exact form of the inductive hypothesis.

Above I have exactly quoted what the book says. Now my question is why cannot we write $cn+n=dn$ where $d=c+1$ and now we have $T(n) \leq dn$ and hence $T(n) = O(n)$?

Note:

The correct answer is $T(n) =O(n \log n).$
The book I am referring here is Introduction to algorithms by Cormen et al., page 86, 3rd edition.


texts: The minimization operator is an effective operator

texts:
Assume $\{f_i^{(n)}\}_{i=0}^\infty$ is a Gödel enumeration of the $\mu$-recursive functions of $n$ arguments, such that the $S^m_n$ theorem and the universal function theorem hold. Denote the set of (total and partial) functions $\{f:\mathbb N^k\to\mathbb N\
\}$ by $\mathfrak F^k$

Definition: We call an operator $G:\mathfrak F^n\to\mathfrak F^k$ effective, if $(\forall j\in\mathbb N)(G(f^{(n)}_j)=f^{(k)}_{g(j)})$ for some total recursive function $g$.

Claim: The minimization operator $\mu:\mathfrak F^{k+1}\to\mathfrak F^k$ defined by $$\mu(f)(\overline x)=\mu y[f(y,\overline x)=0]=y\iff (f(y,\overline x)=0\land(\forall i<y) (f(i,\overline x)>0))$$ is an effective operator.

Question: How can I go about proving the statement? Hints are welcome.

Thought: By definition the $\mu$-recursive functions are closed with respect to the $\mu$-operator. Therefore, $\mu(f^{(k+1)}_j)=f^{(k)}_{h(j)}$, for some unique total function $h$. But why is $h$ a computable function?

Note that I would really like to stay within the Partial Recursive Functions Formalism. Pseudo code means nothing to me. I cannot read it. I am not familiar with most of the notation from the programming world. I would also prefer not go into Register Machine Formalisms.


texts:
I recently learned about the Arthur-Merlin protocol, and we defined the complexity classes $AM,MA$.
We have also seen that there exists a theorem stating that $AMAMAM...AM=AM$, however we have not formally defined $AMAMAMAM...AM$.
We did give a brief definition for it as a protocol, but i would like to see a formal definition without protocols, just like $AM$ and $MA$ (and $MAM$)
A definition for $AMA$ should suffice for me, just to get the hang of how it should look.
Thanks!


texts: Best algorithm to make a smooth route through a raw set of GPS-points with some errors?

texts:
We're developing a mobile application where one of it's functions is tracking user driving route.
The app simply pushes GPS-coordinates to the server, which stores them into a route.

Then we need to display that route gracefully on a map.

There are 2 problems:

Too many points to draw it all. I solve this by applying my variation of RDP algorithm
GPS coordinates aren't ideal, sometimes there is an error up to 100-200 meters. Which causes loops or zigzags on the map and no one of the polyline simplification algorithms which I know can deal with it.

Do you know a way or an algorithm how to deal with errors in coordinates data to draw smooth routes?

The black is the actual polyline. The red is kind of my desired simplification.


texts: Help with question from Sipser chapter 1

texts:
Is this language regular?

$0^k10^k \ with \ k\geq1$

It needs to count the starting and ending zeros which is impossible with finite states.

Update:
This is the whole problem from the book:

Let $\sum = \{0,1\}$.
Let $A =\{0^ku0^k  \ | \ k \ge 1 \ and \ u \in \sum^*$}.
Show that $A$ is regular.

My reasoning is that $u$ can be $\{0,00,000,...,01,011,...,1,11,111,11111...etc\}$

So, the language $0^k10^k \ with \ k\geq1$ should be regular.

I don´t want a formal proof of the problem, but to check if my reasoning is correct.
Thanks.


texts: Using approximations to optimization problems for threshold problems

texts:
Many problems in computer science come in two flavors:

Optimization problem: "Find an object with the largest size".
Decision problem: "Given $n$, find an object with a size of at least $n$, or reply that such an object does not exist".

Given a solver for the optimization problem, the decision problem can be solved simply by checking if the optimal solution has a size of at least $n$. But this doesn't help if the optimization problem is NP-hard.

MY QUESTION IS: If we have a constant-factor approximation algorithm for the optimization problem, how can we use it for the threshold problem?

A possible way is: if the approximate solution has a size of at least $n$, return it; if it has a size of less than $n/c$ (where c is the approximation constant), return that an object of size $n$ does not exist; otherwise, return "I don't know".  This may return a correct answer in many cases, but not in all cases.

Is there a better way?


texts: Can a PDA guess more than once? L = {aⁿ bⁱ aⁿ | i,n > 0 }

texts:
PDA = Pushdown Automata

Let's assume I have this language:

$L = \{a^nb^ma^n | m,n \ge 1\}$

Would the first approach with one node be enough - in that case it guess twice the $\lambda$. In the second approach it's deterministic, which is fine.


texts: Solving $T(n) = 4T(n/2) + n^3$ with substituton method

texts: I am trying to solve the following recurrence $T(n) = 4T(n/2) + n^3$ with substitution method. My guess is $T(n) = \Theta (n^3)$ (I used master theorem) and I tried to show that $T(n) \leq cn^3$. But, when I substitute I got $T(n) \leq c \frac{n^3}{2} + n^3$ and that's it not the exact form of the guess, so it doesn't work. How can I solve this recurrence?


texts: Can we say anything about the complement of a regular language?

texts: Given a regular language $L$, can we say anything about its complement $\overline L$? One thing that is trivial to say is that the DFA's for both languages are equal in size as complementing the language is simply a matter of changing all accepting states into rejecting states and vice-versa. Are there any other things to conclude? Is there anything one can say about the number of states of a (minimal) NFA?


texts: Find a Context-Free Grammar for $L:=\{a^nb^mc^{n+m}\mid n,m\in\mathbb{N}\}$

texts:
I want to find a Context-Free Grammar for $L:=\{a^nb^mc^{n+m}\mid n,m\in\mathbb{N}\}$

I've tried the following:

$G=(V,\Sigma,R,S)$ with $\Sigma=\{a,b,c,\lambda\}$, $V=\{S,B\}$, $S=S$ and $$R=\{S\to \lambda\mid aSc\mid B,\;B\to bBc\mid \lambda\},$$
which would output $L:=\{a^nb^mc^{n+m}\mid n,m\in\mathbb{N}\}$, in my opinion. I've tried to test my grammar by applying the rules in different combinations and I didn't spot any error yet.

So I'm asking myself:
Is there a way to to see if $L(G)=L$ or do I need to assume, that I've done everything correctly after testing some cases?


texts: Matrix element value counting in O(1) space

texts:
The question arise from my customer's real-time system (RAM model, off-course), which has very limited resources.

Given an NxM matrix of integer values, we need to verify that the number of non-zero elements in every row and every column is maximum 2.
The matrix cannot be stored! It comes as a stream (M and N are known in advance but are not constants), row after row, and each element is accessed only once.
The space requirement is O(1), i.e. no additional array of size N or M can be used, only a constant number of variables.

Can this be done?
If not, can it be proved?
Can this be done in O(log(N) + Log(M)) space?

We were taught in undergrad school that if you are unable to provide an adequate solution, prove that no one else can... So I tried to prove to my customer that this can't be done in o(M) space, but was unable to.

Thanks allot


texts: Can a second process execute when the Operating System is performing a context switch?

texts: A process was running on a uniprocessor system. It is being context switched. While the scheduler is performing this context switch can another process be allocated the CPU while the context switch is being performed?


texts: Does there exist an algorithm to generate the production rules of CFG, given a sample production?

texts:
Lets say, we provide the algorithm a set of tokens.

e.g.

x + y - z
x - x - x

It will then try to generate a CFG which fits all the provided examples

S -> S O T | T
T -> x | y | z
O -> + | -

It feels like a data compression problem but I could be wrong.

Does anybody know any existing literature or a starting point to solve this problem?

Does this problem have a name? What should I Google?


texts: How to trace Subset from Boolean DP table in the Subset Sum Problem

texts:
I have seen that the Subset Sum Problem can be solved using Dynamic programming and we should look up the Last row's last column to return the result.

My questions are.

How did someone conclude that the Last row's last column will give us the result?
How can we trace from there to check the subset that can be added to get the Sum?
Finally, is there a way to trace all the possible subsets from this DP table?

Thanks in advance.


texts: Fundamental and essential matrices, value of intrinsic parameters

texts:
I observe a scene with two cameras, c1 and c2, that produce two images i1 and i2, respectively. What I ultimately want to do is to use information of image i1 and image2 simultaneously, e.g., for object detection.

As far as I understand it, I would not be required to find the intrinsic parameters of c1 and c2, also I do not need to know their relative position and rotation if I want to rectify i1 and i2. I can "simply" calculate F from a set of corresponding points - with no explicit relation in 3D of the points (like known distances). Which disadvantages would that have for me? I would not be able to do 3D reconstruction then, correct? But apart from that, there is no difference?

Or, asked differently, for rectification I do not need the intrinsic parameters. I only need them to do 3D reconstruction? What are the intrinsic parameters good for?


texts: In Universal Hashing- probability of poor performance is small and is the same for any set of keys of the same size

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

Universal Hashing uses randomization.For the example of a compiler's symbol table, we find that the programmer's choice of identifiers cannot now cause consistently poor hashing performance.
Poor performance occurs only when the compiler chooses a random hash function that causes the set of identifiers to hash poorly, but the probability of this situation occurring is small and is the same for any set of identifiers of the same size.

Now let us assume that in the general case( not specifically the compiler example) we have a "Universal class of Hash function" as $\mathscr{H}$ and the set of keys be $K$.
As the situation described ,the poor performance occurs if for a randomly chosen hash function $h\in\mathscr{H}$ the hash function causes collision for each $\binom{|K|}{2}$ pair of keys. Intuitively that the probability of this happening is quite "small" is justifiable. But that the probability is same for all sets K of size n and independent of the actual keys in it was not received by me in an intuitive manner and I thought of finding the probability of such an event and satisfy myself.
From the definition of universal class of hash function we know that,
For each pair of distinct keys $k,l$ the number of functions $h\in \mathscr{H}$ , such that $h(k)=h(l)$ is atmost $\frac{|H|}{m}$ where $m$ is the number of slots in the hash table .i.e. for the set $A=\{h \in \mathscr{H} : h(k)=h(l)\}$ ,
$$|A|\leqslant|\mathscr{H}|/m \tag 1$$
Now from the above we need to find the number of hash functions which causes collision for all pair of keys.
Let $A_{x,y} \subseteq \mathscr{H},$ for $\forall x,y \in K$ such that the keys $x\neq y$, $A_{x,y}$ contains those hash function $h$ such that $h(x)=h(y)$.
Now
$$\lambda = \left| \bigcap\limits_{(x,y\in K)\land (x\neq y)} A_{x,y} \right| (say) \tag 2$$
We know that,
$$\left| \bigcup\limits_{(x,y\in K)\land (x\neq y)} A_{x,y} \right| \leq |\mathscr{H}|\tag 3$$
So the required probability which I am asking for becomes,
$$p=\frac{\lambda}{|\mathscr{H}|}\tag 4$$
Now how to combine $(1), (3)$ to get a bound for $(2)$ and hence get a bound for $(4)$.

I thought of an alternative approach though.
Let $h$ be the hash function chosen at random during the start of the execution of our algorithm. Suppose $X_{x,y}$ be the indicator random variable defined as :
$$X_{x,y} = \begin{cases}
       1 &\quad\text{if $h(x)=h(y)$ }\\
       0&\quad\text{otherwise.}\\
\end{cases}$$
Where the randomness is due to the random selection of $h$ and not on the keys. Now by the definition of Universal Hashing, $Pr\{h(x)=h(y)\}\leq \frac{1}{m}$ where $h$ is randomly chosen hash function for keys $x,y$. So $E(X_{x,y})=Pr\{h(x)=h(y)\}\leq \frac{1}{m}$
Let $X$ be the random variable representing the total number of collisions.
$$X=\sum_{(x,y\in K)\land (x\neq y)} X_{x,y}$$
Taking expectations on both sides,
$$E[X]=E\left[ \sum_{(x,y\in K)\land (x\neq y)} X_{x,y}\right]$$
$$\implies E[X]=\sum_{(x,y\in K)\land (x\neq y)} E[X_{x,y}]= \binom{n}{2} E[X_{x,y}]\leq \binom{n}{2}.\frac{1}{m}$$
Now using Markov's Inequality we have,
$$Pr \left\{ X\geq\binom{n}{2}\right\} \leq \frac{E[X]}{\binom{n}{2}} $$
$$\leq \frac{\binom{n}{2}.\frac{1}{m}}{\binom{n}{2}}$$
$$=\frac{1}{m}$$
$$\therefore p=Pr \left\{ X\geq\binom{n}{2}\right\} \leq\frac{1}{m} \quad\text{(independent of the actual keys)}$$
Please help me out with the first approach or is my second approach legit?


texts: number of queries to recover the permutation

texts:
Imagine this game. I pick a permutation $p$ of $1..n$ and give you an oracle. When the oracle is queried with any sequence of $n$ numbers $\in 1..n$, it masks each number by applying some unknown bijection $f$ and then permutes the masked values using $p$. Your goal is to repeatedly query the oracle to recover $p$ with as few queries as possible.

A $\theta(\log(n))$ solution is obvious. First query $1, 2, 3, 4, \ldots$ and $2, 1, 4, 3, \ldots$, the second query reversing each of the $\lfloor \frac{n}{2} \rfloor$ pairs. As swapping a pair in the input swaps the corresponding pair in the output, we identify the $\lfloor \frac{n}{2} \rfloor$ pairs that they map to, albeit with unknown correspondence. (If $n$ is odd, the $n$th item is the one remaining in place so $p(n)$ is known.) Then query $1, 1, 3, 3, \ldots$ to identify which item in each output pair corresponds to the first item of an input pair. With 3 queries we have reduced the problem to one of size $\lfloor \frac{n}{2} \rfloor$ by querying from now on with identical pairs of items; recurse. We use $3\log n \pm O(1)$ queries.

Can we do better? For example, is there a strategy using $\log n \pm O(1)$ queries?

Regarding lower bounds, if $q$ queries is optimal for $\frac{n}{2}$ we can run the strategy twice in parallel, side-by-side, in $q$ queries for $n$ but we still lack information about which $\frac{n}{2}$ of the input maps to the corresponding $\frac{n}{2}$ elements of the output, suggesting we need at least one additional query for $n$. This argument seems to imply $\Omega(\log(n))$ query complexity - can it be made rigorous?


texts: Given a regular language, show another language is regular

texts:
I was hoping someone could help me with this question, since I'm having trouble determining what approach to take.

Let $L \subseteq \{0,1\}^*$ be a regular language. Show the language $\{w \in \{0,1\}^* | 1w \in L\}$ is also regular.

My idea is that whenever we're at the start state to compensate for the lack of the 1, you do an additional transition as if 1 was part of the input and then carry on reading the input as normal.

Since L is regular it has a NFA that accepts it $(Q,\Sigma, \delta, q_0, F)$. Then construct a new NFA $(Q,\Sigma, \delta', q_0, F)$ such that $\delta'(q,a) = \delta(q,a)$ for $q \ne q_0$ and $\delta'(q,a) = \delta(\delta(q,a),1)$ for $q = q_0$

Is this correct?


texts: Clarifying the definition of reduction with regards to NP-complete problems

texts:
In my logic class we started learning about the different complexity classes. In particular, we focused on the NP complexity class. A problem is in NP if it is solvable in polynomial time using a nondeterministic Turing machine. To show that a problem $L$ is NP-compelete, we have to show that: $1)$ $L$ is in NP, and $2)$ if $L$ is solvable in polynomial time, then all problems in NP can be solved in polynomial time.
In regards to $2)$ we can use reduction. So if you already know a NP-complete problem $M$, then it is enough to show that we can use a polynomial time algorithm that we can use for $L$, in order to solve $M$ in polynomial time.
I'm not sure I understand the explanation for the reduction section.


texts: Are there inherently ambiguous and deterministic context-free languages?

texts:
Let us call a context-free language deterministic if and only if it can be accepted by a deterministic push-down automaton, and nondeterministic otherwise.

Let us call a context-free language inherently ambiguous if and only if all context-free grammars which generate the language are ambiguous, and unambiguous otherwise.

An example of a deterministic, unambiguous language is the language: $$\{a^{n}b^{n} \in \{a, b\}^{*} | n \ge 0\}$$
An example of a nondeterministic, unambiguous language is the language:
$$\{w \in \{a, b\}^{*} | w = w^{R}\}$$

From Wikipedia, an example of an inherently ambiguous context-free language is the following union of context-free languages, which must also be context-free:
$$L = \{a^{n}b^{m}c^{m}d^{n} \in \{a, b, c, d\}^{*} | n, m \ge 0\} \cup \{a^{n}b^{n}c^{m}d^{m} \in \{a, b, c, d\}^{*} | n, m \ge 0\}$$

Now for the questions:

Is it known whether there exists a deterministic, inherently ambiguous context-free language? If so, is there an (easy) example?
Is it known whether there exists a nondeterministic, inherently ambiguous context-free language? If so, is there an (easy) example?

Clearly, since an inherently ambiguous context-free language exists ($L$ is an example), the answer to one of these questions is easy, if it is known whether $L$ is deterministic or nondeterministic. I also assume that it's true that if there's a deterministic one, there's bound to be a nondeterministic one as well... but I've been surprised before. References are appreciated, and apologies in advance if this is a well-known, celebrated result (in which case, I'm completely unaware of it).


texts: Uses of unary or sparse languages in other models

texts:
In the turing model we have the statements that if there is an unary or sparse language that is NP complete then P=NP and if there is a Turing reduction from an NP complete problem to an unary or sparse language then NP is in P/poly.

Is there an analog of these statements in the Valiant model and in the BSS model?


texts: Decidability of language containing strings of length equal to that of some substring of 1s in $\pi$?

texts:
I read that the following language is decidable.

$\{w | w \in \{0, 1\}^* \text{ and } 1^{|w|} \text{ is a substring in binary expansion of } \pi \}$

The proof has been given by considering the two possible cases

Suppose it is true that there exists a minimal integer $N$ such that the
binary expansion of $\pi$ only contains substrings of 1 having length at most $N$.
That is, it contains substring $1^N$ but not $1^{N + 1}$. Define a corresponding turing machine $M_N$ such that it accepts the input string if it is of length $N$, otherwise rejects it. This machine decides the given language.
Suppose the binary expansion of $\pi$ contains substrings of $1$s of all lengths. Then the Turing machine that accepts all strings decides the given language.

We are not able to construct a single Turing machine that decides the language given, but one of these machines thus constructed will decide it but we do not know which. I don't quite understand how this language is decidable?


texts: 2-tape TM that accepts words from $L := \{bin(n)$#$w \in \Sigma^* | n \in \mathbb N \land w \in \{0,1\}^* \land |w| \le n\}$ in $O(n)$

texts:
Let $\Sigma := \{0,1,$#$\}$ be the input-alphabet and $L := \{bin(n)$#$w \in \Sigma^* | n \in \mathbb N \land w \in \{0,1\}^* \land |w| \le n\}$ the alphabet. $|w|$ means the length of the word $w$ and $bin(n)$ the binary representation of $n$.

I need to construct a 2-tape TM which has $O(n)$ complexity and accepts the words from $L$, i.e. the machine terminates in an acceptable state iff the input is contained in $L$ und for all other input words the machine terminates in a not acceptable state.

EDIT: I already constructed a 1-Tape TM which reduces a binary number by 1 and which is supposed to help me with solving this problem but I don't know how.


texts: How to prove the outcome of both segment of code are equal

texts:
Is it possible to prove using induction? If possible what would be the steps to proof A=B?

Main thing i want to proof is outcome of two segments of code are same.

Below is the code:

Segment A:

int A (int x, int y) {
  if (y==0) return x;
  return A(y, x % y);
}

Segment B:

int B (int x, int y) {
   while (y!=0) {
      int t = y;
      y = x % y;
      x = t;
   }
   return x;
}


texts: Why is channel capacity of AWGN infinite?

texts: My professor taught us that channel capacity of AWGN channel is infinite without any input power constraints. The noise is $Z \sim \mathcal{N}(0,\sigma^2) $. There is no constraint on input signal. I don't understand how the professor can directly say the channel capacity is infinite. Don't we need to maximize mutual information between input and output to get the channel capacity? How to do that for continuous variables?


texts:
An edge-labelled directed graph is the data of $G = (V, E, l)$ where $(V, E)$ is a directed graph, and $l \colon E \to \mathbb{P}$ is some function. (For the graph I am considering, labels take values in $\mathbb{P} = \{1, 2, 3, \ldots\}$). To any path $v_0 \to v_1 \to \ldots \to v_n$ in $G$, we can associate a type $\alpha = (\alpha_1, \ldots, \alpha_n) \in \mathbb{P}^n$, where $\alpha_i = l(v_{i-1}, v_i)$. For a fixed source vertex $s$, destination vertex $t$, and type $\alpha \in \mathbb{P}^n$, let $P(s, \alpha, t) \in \mathbb{N}$ be the number of $s \rightsquigarrow t$ paths of type $\alpha$.
I have two counting problems, the first of which I can solve fairly efficiently, and the second of which I am hoping for some assistance. In the problem I am considering, the directed graph is acyclic, and satisfies other interesting properties: for example $P(s, \alpha, t) = P(s, \beta, t)$ whenever $\alpha$ is a permutation of $\beta$. Furthermore, in the problem I am consdiering $G$ is an infinite graph, but each of the following problems is finite.
Problem 1: Fix a source $s \in V$ and a type $\alpha$, and determine all of the numbers $P(s, \alpha, -)$.
Problem 2: Fix a source $s \in V$ and a destination $t \in V$, and determine all of the numbers $P(s, -, t)$.
For problem 1, we can take an approach very similar to counting paths in a DAG. Initialise an array $\mathtt{D}$ indexed by $V$ to zero, and set $\mathtt{D}[s] = 1$. Then perform a breadth-first search, at the first layer following all edges of type $\alpha_1$, and for each $s \xrightarrow{\alpha_1} v$ increment $\mathtt{D}[v]$ by $\mathtt{D}[s]$. Repeat for all the $\alpha_2, \ldots, \alpha_n$. At the end, the last layer contains all vertices $t$ reachable from $s$ via an $\alpha$-path, and $\mathtt{D}[t]$ is equal to $P(s, \alpha, t)$.
Problem 2 is more tricky, and the best strategy I have at the moment is essentially to iterate over the potential allowed types $\alpha$ and compute each $P(s, \alpha, t)$ individually. Another approach would be to do a breadth-first-search from $s$, but storing at each vertex the path type leading there, together with multiplicity - but this doesn't seem to be faster.


texts:
Reading this wikipedia article on B Trees, I have implemented the algorithm.

I got to the section on Initial construction and ran my algorithm implementation and it differed. With 8 being the root index.

Am I right in thinking, that when you bulk load your leafs are going to full, but when you add the indexes individually the leafs are going to be half empty?

Or have I got my, maximum indexes numbers and maximum children numbers the wrong way round. In my implementation I split the indexes when they reach a size of 4.


texts: Why sequential access is faster than random access?

texts:
I am currently getting really confused of two documents I read:

one is from Wikipedia that states:

  The opposite is sequential access, where a remote element takes longer time to access.

and this Microsoft's document says:

  Accessing data sequentially is much faster than accessing it randomly because of the way in which the disk hardware works.

I found the two documents contradicting with each other. Maybe they refer to different things. But I would like to know why sequential access is much faster than random access (I don't understand the Microsoft document as I don't understand the concept of seek operation)


texts:
I know how to verify whether grammar is LR(0) or not. But this particular case is little tricky and hence the question.

  Grammar:

  $SL \rightarrow SL ; S \space | \space \epsilon$

  $S \rightarrow s$

  (Note: $SL$ is single non-terminal.)

Now, LR(0) automaton for this grammar is as follow:

Now my question is whether to consider entry $start \rightarrow SL.$ in $State_1$ as SR conflict.

Because I previously came to know that we don't consider conflicts due to augmented production.

Thanks.


texts: Approximation Algorithm for Maximum-Cut (proving a bound on the optimum)

texts:
At the end of section 12.4 in the Local Search chapter from Kleinberg-Tardos's book "Algorithm Design" we are told that we can bound the running time of a proposed Maximum-Cut approximation algorithm via using "big-improvement-flips". The goal here is to use these flips to then place a bound on the running time of our approximation algorithm, but I have yet to understand how to prove statement (1) below.

A node flip is a big-improvement-flip if it improves the cut value by at least $\frac{2\epsilon}{n}w(A,B)$ where $n=\vert V \vert$ and $\epsilon > 0$.

We are given 12.6 as a result in the book (12.6 refers to the statement number in the book):

(1) Let $(A,B)$ be a partition such that no big-improvement-flip is possible. Let $(A^*,B^*)$ be a globally optimal partition. Then $(2+\epsilon)w(A,B)\geq w(A^*,B^*)$.

The claim is that by simply adding the term $\frac{2\epsilon}{n}w(A,B)$ to each inequality in the original proof, we can prove this. For original proof see slide 22 at this link, slides preceding slide 22 also describe the proposed approximation algorithm which allows us to find a local optimum by moving from a state $S$ to a state $S^*$ if and only if moving a vertex from one partition to the other increases the value of the cut: Princeton Kleinberg-Tardos lecture slides.

I had some difficulty simply adding the term and moving through the proof from beginning to end as Kleinberg-Tardos proposed. This has been very frustrating and I just want to prove to myself that that statement (1) holds.

My proof attempt:

For any node $u \in A$, we must have

$$\sum_{v\in A} w_{uv} \leq \sum_{v \in B} w_{uv} + \frac{2\epsilon}{n}w(A,B).$$

By summing the inequalities for each pair of vertices with both ends in $A$ and each pair of vertices with one end in $A$ and the other in $B$ we get

$$2 \sum_{\{u,v\}\subseteq A} w_{uv} \leq \sum_{u\in A, v \in B} w_{uv} + 2\epsilon w(A,B) = w(A,B) + 2\epsilon w(A,B).$$

*Note on above step: Since at most $n-1$ vertices are in $A$ we have on the RHS of the inequality $\frac{2\epsilon}{n}w(A,B) \leq (n-1)\frac{2\epsilon}{n}w(A,B) \leq n\frac{2\epsilon}{n}w(A,B) \leq 2\epsilon w(A,B)$

A similar argument follows for any $u \in B$ and hence

$$2 \sum_{\{u,v\}\subseteq B} w_{uv} \leq \sum_{u\in A, v \in B} w_{uv} + 2\epsilon w(A,B) = w(A,B) + 2\epsilon w(A,B).$$

Adding these inequalities gives

$$2 \sum_{\{u,v\}\subseteq A} w_{uv} + 2 \sum_{\{u,v\}\subseteq B} w_{uv} \leq 2w(A,B) + 4\epsilon w(A,B)$$
$$\sum_{\{u,v\}\subseteq A} w_{uv} + \sum_{\{u,v\}\subseteq B} w_{uv} \leq w(A,B) + 2\epsilon w(A,B)$$

At this point I would like to add $w(A,B)$ to both sides and conclude that $W = \sum_e w_e$ is now equal to the LHS (since the LHS now equals the sum total weight of all edges) and then have the RHS be equal to $2w(A,B) + \epsilon w(A,B) \Rightarrow (2+\epsilon)w(A,B) \geq w(A^*, B^*)$, but the bound I am getting is  $2w(A,B) + 2\epsilon w(A,B) \Rightarrow w(A,B)(2+2\epsilon)$.

What am I missing here? I seem to be double counting the term $2\epsilon w(A,B)$.


texts:
I have the following statement. I would say it's correct as it's either equal or higher than $\Omega(\log^{10}(n))$.

Because:
I know $\log(2^n) = n$.
By that I would guess the same goes for $\log(n^{10})$ unimportant if the number is higher or not. By that it should be n. With this knowledge we already know it's higher than our $\Omega(\log^{10}(n))$.

We also know $\log(n)^2 = \log(n)$ again it will be higher or equal to our omega.

Is this correct?

$$(3 \log^2 n + 55 \log(n^{10}) + 8 \log n) \cdot \log n = \Omega(\log^{10} n)$$


texts: I have R={A,B,C,D,E} with functional dependencies ABCD → E and AC → ABCD,with Axiom of transitivity rule is AC → E a transitive dependency? Thanks before and sorry for this simple question


texts: Find point with smallest average distance to a set of given points

texts:
Someone recently shared with me the following problem (which I guess appeared in some kind of past coding contest):

  Given $n$ points $P_i=(x_i,y_i)$ in the 2-dimensional plane, find the point $Q=(x,y)$ that minimizes the average distance from $P_i$ to $Q$.

In other words, we want to find $Q$ that minimizes the objective function $f(Q) = \sum_i d(P_i,Q)$.  Here $d(\cdot,\cdot)$ represents the usual Euclidean (L2) distance.  I'm told that in the coding contest this was phrased in terms of finding the best location to put a washroom somewhere in an office building, so that the average distance to all employees is minimized.

Is there an elementary solution to this problem?  In other words, a polynomial-time algorithm that does not require knowledge of advanced methods (say, beyond what undergraduate computer science majors could be expected to understand).

If we were on the 1D real line rather than the 2D plane, this problem would be easy.  In one dimension, the solution is exactly the median of $x_1,\dots,x_n$.  However, this does not seem to generalize to the 2-dimensional plane.  It's tempting to take $x$ to be the median of $x_1,\dots,x_n$ and $y$ to be the median of $y_1,\dots,y_n$, but this does not provide the optimal solution: a counterexample is to look at three points at three of the corners of a square.  (The component-wise median is at a corner, but the optimal location is somewhere inside the square.)

It looks like this problem is a special case of the two-dimensional Euclidean $p$-median problem, for $p=1$.  Apparently the two-dimensional Euclidean $p$-median problem is NP-hard when $p$ is part of the input (Megiddo and Supowit, SIAM J Computing 13(1) Feb 1984) -- but here we have the special case where $p=1$, so the NP-hardness result doesn't apply to this special case.  I haven't been able to use this search phrase to help find an algorithm.

If the distance metric was the Manhattan (L1) distance, there would be a number of clean solutions.  The component-wise median would be optimal, since the Manhattan metric is linearly separable in the $x$-coordinates and $y$-coordinates.  For similar reasons, we could solve it using linear programming.  However, here we have the Euclidean distance, which is not linearly separable, so those methods do not seem to apply.

See also Find the point with minimum max distance to any point in a set, which looks at a related but different problem, the smallest-circle problem, where the objective function is $g(Q) = \max_i d(P_i,Q)$.  However, the techniques used for that problem don't seem to apply here.

Right now the approach I can see is a heuristic algorithm: use standard black-box optimization methods such as hill-climbing or gradient ascent to find the point $Q$.  However, there is no guarantee that this finds the exact optimum.

If there's a solution that does not require understanding advanced computational geometry algorithms (e.g., Voronoi diagrams, Delaunay triangulation, etc.), even better!


texts:
I want to construct a loop-computable program for this construction:

IF x1 = c THEN P ELSE P'

I know how to transform if else construction in loop , but I can't understand how to check the equality.I have idea for x1 >= c , but how can I check if the both numbers are equal ?


texts: Self-balancing binary search tree optimized for insertion

texts:
I've written a "quiz" that prompts the user for comparisons between two items of subjective value, and once the position of all of the items is determined, displays an ordered list from most valuable to least.  The number of items is fixed.  The current implementation can be seen at https://dfdx.us/core-values-quiz/.

What matters most is minimizing the number of comparisons the user needs to input, or, more accurately, minimizing the amount of time the user requires to make each comparison times the number of comparisons.

Currently I offer two sorting methods: Quicksort and insertion into a binary tree.  Compared to a self-balancing BST, Quicksort will always require more comparisons, but because each consecutive comparison is against a single item (the partition item), the brain doesn't need to make much of a context switch and can answer the questions quicker.  The binary search tree will present fewer questions that take longer.  I let the user decide which method they want to use, given the pros and cons of each.

Since the comparisons required to rebalance the tree are handled by the computer, and not the user, those comparisons don't need to be optimized at all, only the number of comparisons required to determine the relative position within the current tree.  I believe this optimization is equivalent to, between each item's insertion, balancing the tree as perfectly as possible.  That is, requiring the strictest balancing constraint.

The best algorithm I've tested is the AVL tree.  While the AVL tree is pretty terrible for insertion/deletion times for most applications, it has a decent balancing constraint which results in great look-up speeds.  The rebalancing between each insertion/deletion is what makes it unperformant, but since, compared to human input, those comparisons are negligible, it is very good for my situation.

My situation requires one more constraint: the user must never be presented with the same comparison twice.  For the AVL tree, rebalancing breaks this constraint, so I've just memoized all of the user's answers in a dictionary.  I can't imagine a situation in which this case couldn't be handled with that memoziation, but I figured I'd mention it nonetheless.

I really have two questions:

Am I right with my assertion that balancing the tree as perfectly as possible guarantees the fewest number of prompts to the user?
Is there a better balancing algorithm than an AVL tree?

Given that before the quiz begins, the items' order is randomized, even using a non-auto-balancing BST should result in a roughly balanced tree.  I could see an argument being made that perfectly rebalancing after every insertion could actually produce a greater number of prompts, since each one will have as close to lg(n) prompts as possible; a slightly less balanced tree could potentially have a few "lucky" insertions that require a few less than lg(n), and a few "unlucky" insertions that require more, but that the lucky ones will, on average, outweigh the unlucky ones.  (I hope that made sense.)


texts: Determining whether a language $L_{a}$ is recursively enumerable

texts:
I'm trying to determine whether a language $L_{a}$ is recursively enumerable, but first I'm having trouble deciphering the definition $L_{a}$ given the following question:
Given an recursively enumerable language $L$, we can define $L_{a} = \{ x : \exists\langle M\rangle \in L \text{ such that } x \in L(M)\}$. Prove $L_{a}$ is recursively enumerable.
I understand it as the language $L_{a}$ is searching for a Turing Machine encoding $\langle M \rangle$ that exists in $L$, but I'm not sure this is correct.
Furthermore, for this problem would it be easier to create and algorithm that enumerates $L_{a}$ or to prove it's recursively enumerable through some sort of contradiction?


texts: Proving that language $ L = \{ a^{2n}: n \geq 1\}$ is regular

texts:
I was asked to prove that language described by $$ L =\{ a^{2n}: n\ge1\}$$ is regular using pumping lemma. Pumping Lemma states that for regular language we can break down language described by language into $xyz$ where pumping length $p \ge 1$ such that

$|y|>0$
$|x.y| \le p$
$x.y^{i}.z$ is in L for $i \ge 0$

taking pumping length $n = 3$ , my language becomes $L = \{ aaaaaa\}$ and then let
$$x = aaa$$
$$y = aa$$
$$z= a$$

clearly this violates condition 2 because $|xy| > p$ where $p=3$ and it also violates condition 3 for many values of $i$ thus this language cannot be regular but in the question I was asked to prove it to be regular, am I missing something?


texts: Ant colony optimization for continuous functions

texts:
I am trying to do optimization of a voice activity detection function, which is a function with continuous parameters. This is easily accomplished with genetic algorithms, simulated annealing, and tabu search, but I'm somewhat confused on how to accomplish this with Ant Colony Optimization (ACO).

From what I've read, ACO is mostly used for solving problems that can be formulated as a graph. I've searched for resources relating to multiple parameter function optimization, but the closest thing I found was this article for a single parameter on a continuous function and this long paper with no pseudocode which is contained in this PHD thesis. Are there any resources (websites or books) for accomplishing multiple parameter continuous function optimization with ACO that involve an implementation example?

Alternatively, is the key here to discretize the continuous inputs? If so, what methods exist to do this in a way that works well with ACO?


texts: What values do $y_i$ in training data for binary classification problems attain?

texts:
In case of binary classification problem, what are the $y_i$ 's in the training data set $\{(x_1, y_1), (x_2, y_2), \dots (x_n, y_n)\}$?

I guess they are from $\{1,-1\}$. Now I see a method for finding a scoring function $f(x) = w^Tx + b$ by minimizing the squared error between the $f(x_i)$'s and $y_i$'s over $w$ and $b$. Now is it correct to minimize the error between $f(x_i)$'s and $y_i$? The latter is a sign while the former is a value? They seem incomparable to me.


texts: Fine-grained security models for XML data

texts:
Access control models are typically very coarse-grained, allowing one access to a resource (possibly with some combination of read/write/execute permission) or exclude such access. Some models of database security allow access to be granted on a per row basis (though I don't have a reference handy).

Have fine-grained access control models been designed to limit access to parts of an XML document? What could/should a model look like? Has any work been done in this area? Are other security models applicable in this context?

For example, one could imagine that the model prevents access to a particular subtree. The subtree could either be removed or encrypted.

Note that this need not explicitly apply to XML. Any models devised for semi-structured data are also interesting.


texts: How can I compute the average weight of an undirected graph?

texts:
Given a weighted, undirected graph $G = (V,E)$, how can I compute the average weight of edges?
It seems an easy problem (divide the total weight to the number of edges!)
but I couldn't manage to find the sum of the edge weights since each
edge can be counted several times while iterating through the vertices.


texts: The equational theory of regular languages has no finite set of axioms for general alphabets

texts:
According to Redko the equational theory of regular languages with operations $+, \cdot, *$ over a single letter has no finite set of axioms.

  Why does this imply that it has no finite set of axioms over an arbitrary alphabet?

Suppose I have a finite set of axioms for the equational theory of an alphabet with more than one letter, how would this give a finite set of axioms for the single letter case? I mean in the single letter case we have additional equations which did not hold in the arbitrary case, for examle $AB = BA$ for two languages $A,B$, and therefore which could not be derived from the axioms, hence these axioms do not axiomatize the single letter case.

Some clarification as asked for in the comments: Given a fixed alphabet $\Sigma$ and a set of variables $X = \{A,B,C,\ldots\}$, the terms are inductively defined:

1) Every $a \in \Sigma$ is a term,

2) Every variable $X$ is a term,

3) If $s,t$ are terms, then $s + t, s\cdot t, t^{\ast}$ are terms.

The interpretation of the regular sets $\mathcal{Reg}(\Sigma)\subseteq \mathcal P(\Sigma^{\ast})$ is as usual. As written in the comments, as set of terms $\Gamma$ axiomises $\mathcal{Reg}(\Sigma)$, the regular languages over a given alphabet $\Sigma$, if
$$
 \Gamma \vdash t_1 = t_2 \mbox{ iff } \mathcal{Reg}(\Sigma) \models t_1 = t_2.
$$
Where $t_1, t_2$ are terms with alphabet letters from $\Sigma$, and variables are interpreted as universally quantified. The only rule of interference being substitution, that I mean by equational logic.


texts: Algorithm to get maximal selection set of a collection of sets with a binary relation

texts:
I have a finite collection of finite sets $\{A_i\}_{i \in I}$. There is a relation $R$ defined on the elements  of those sets (which is not transitive, it is irreflexive, and it is symetric). Suppose we define a related partial choice as a set $\{a_j\}_{j\in J}$ such that:

$J\subseteq I$
$a_j \in A_j, \forall j \in J$
$a_j R a_{j'} \forall j,j' \in J$

That is, it consists of choosing one element for each of some of the original sets, such that all elements are related to each other.

What I need is an algorithm that a computes a related partial choice with maximum cardinality.

An equivalet way  of seeing the problem would be as follows. Given the set $\{A_i\}_{i \in I}$, call a related selection partial function ($RSPF$, for short) any partial function $f : I \rightarrow \cup_{i\in I} A_i$ such that:

$f(i)\in A_i$ for all $i \in I$ where $f$ is defined.
$f(i)Rf(i')$ for all $i,i' \in I$ where f is defined.

If we define $N := max(\{ \#Dom(f) : f \in RSPF\})$. I need an algorithm to efficiently compute an $f$ such that $\#Dom(f) = N$.

In the algorithm, the $\{A_i\}_{i \in I}$ sets can be arrays or sets.

Any Ideas?


texts: Is this a induced sub graph of the the following graph G?

texts:
This is graph G:

I am required to find as much as 15 induced subgraphs, but so far I only found 3. Which are: a-b-d-e, b-c-e-f and a-b-c-e.

I was wondering if a-d-e-f would also be counted as an induced subgraph and other of this similar arrangement.


texts: Simplify closed-path points without intruding into the inside of the path

texts:
I want to:

Simplify a set of points that outlines a closed opaque image on a transparent background.
The simplified set of points should not intrude into the closed opaque image.

I use a Marching Squares Algorithm to fetch a set of points (x,y) that outlines the opaque pixels of an image.  This gives a valid set of points outlining the opaque image.

Original image (an opaque sun image on a transparent background):

Result of Marching Squares Algorithm (a set of points--red, around the opaque sun):

This set of points is fine--entirely outside the sun (no intrusion).  But the current set of points contains many points that can be eliminated because they are redundant. The redundant points are on the line segment connecting the previous and next point in the set.

For example in the illustration below, the middle red point is redundant and can be eliminated because connecting the first and last points results in the same line segment:

I've tried several path-point simplification algorithms like the Douglas-Peucker Algorithm.  This algorithm does reduce points, but it also lets the simplified path intrude into the original image.

For example in the illustration below, the middle point has been eliminated but the result causes the path to intrude into the image:

I have an array containing all pixel colors on the image, so this array can be used to determine if any pixel is transparent (outside the image) or opaque (inside the image).

I'm looking for an algorithm to simplify the path-points which does not let the resulting path intrude into the original image.


texts: State of the art of parser handling of offset errors

texts:
Say you are parsing a complicated binary file but there is 1 extra byte inserted somewhere. This could completely mess up the entire parse, but if you just looked ahead one token you would see the whole file is in tact minus that extra byte (or bit, whatever). You could have a record in the binary file like this:

header:
  name: foo
  offset: 12
  length: 100
item1:
  x: 10
  y: 20
  z: 15
item2:
  x: 0
  y: 0
  z: 15
...
header2:
  name: bar
  filter: abc
...

And it would end up looking something like this in the working case (in bit form):

foo 12 100 10 20 15 0 0 15 bar abc ...

But if you inserted another value or set of bits in there, it might look like:

foo 12 100 10 20 143901 15 0 0 15 bar abc ...

My question is what the state of the art is regarding how to print out helpful error messages that say stuff like "it looks like record 1 is split into two parts accidentally, by value 143901", or at least show that table "foo" and table "bar" are both present in the binary (even though that inserted value throws it off).

Wondering what sort of research exists on this topic and how far they've come in making the user experience better in terms of error messages. The naive approach is to say "Unknown token 143901 found in table foo", and not even recognize that table "bar" is present. But I've noticed some font parsers are pretty smart in that they can at least get notified of all the records/tables in the binary, and most of their fields, even if the fields have the wrong length or size or are misplaced. I'm wondering if this is just an ad-hoc thing or there is any science or research around it.


texts: Search a preprocessed text with online queries

texts:
We're given a fixed text, and we are presented with a series of online queries of patterns. For each query, the goal is to answer if the pattern exists in the text. Each pattern is a string, and we want to know if it appears as a substring of the text. The text can be preprocessed.

What's the optimal way to solve this?


texts: Is there any hope to use a computer to guess combinatorial formulas for a sequence of integer values, given some initial terms?

texts: So sometimes in combinatorics, you are computing the count $a_n$ of something that depends on a natural number parameter $n$. Either by hand or using a computer, you can often compute some initial terms in the sequence $(a_n)_n$. Now, you can enter those initial terms into the Online Encyclopedia of Integer Sequences, and if you are lucky you can get a match with a formula and info that will help you prove that your sequence satisfies that formula. But what if your exact sequence is undocumented but is directly related to a known sequence? Like if your sequence is double or the square of another known sequence? Or if your sequence can be expressed either directly or as a summation involving hypergeometric terms? If a computer could propose formulas for a sequence given some initial terms, it might help the mathematician immensely because when they finally look at the correct formula, it might become clear to them why the formula is true based on the structure of the problem and the formula. Has there been any progress in enabling computers to "guess" succinct formulas for integer sequences given some initial terms?


texts: Evolutionary algorithm - how to select the parents

texts:
I try to solve Physical Travelling Salesman Problem using evolutionary algorithm and I have diffucult to detemine how to choose the parent , on which we do the crossover.

Assume I have popultion of 100.
The parent should be selected randomally? or according to their fitness?
If I choose them randomally I don't think the result be enough good but in the other hand, if I will choose the 2 with the best fitness, I will always choose the same! (Maybe child  of them , but most of my population will never be choosed!).

What I miss?

I also need some advise on how to calculate fitness. The parameters are the amount of waypoints each van collect and the total time.

My problem here is becuase there are unit that don't manage to collect any points and thus thier fitness is 0 and step by step my array full with 0....(I am working with the code here : http://www.ptsp-game.net/ ant there is problem of time exceed..)


texts: Formal justification of the accounting method and its meaning

texts:
I'm reading through CLRS again and I was wondering if there's a formal justification or construction of the accounting method, explaining why it works. For some reason it seems to me that CLRS basically expose the method explaining the intuition behind it, but it doesn't seem rigorous to me.

Also is it correct to say that the accounting method is essentially a method to derive the actual cost of a sequence of $n$ operations by assigning a suitable ammortized cost to each operation?

This should differ from aggregate analysis, where we try to derive a worst case cost and then we derive the ammortized cost (kind of the inverse in some sense).

To this stage the accounting method seems to me like a "recipe" to derive a bound, in doesn't seem to convey anything else to be honest.


texts: Is the ability to do depth first search a proof of Turing Completeness? Can we write a non-TC automaton that does DFS?

texts:
As the title states. Let's say we have a set of inputs that define a tree structure. Is it possible to construct an automaton that can perform depth-first search on this data that is not Turing-complete? If so, can we state that the ability to do DFS a sufficient proof of Turing-completeness?

For the purpose of the question, you can have some leeway about how the data is represented. As long as you can come up with a combination of a tree representation and an automaton that can DFS it that is less than Turing-complete, that's good enough. If it simplifies anything, you can make assumptions about the nature of the tree (e.g. binary or not), but a more generalizable answer would be preferred.


texts: What is example of Kahr formula $[\forall\exists\forall, (\omega, 1), (0)]$ and what to do if such undecidable formula is encountered in practice?

texts:
There are mentioned many classes of undecidable formulas in the book "The Classical decision problem" http://www.springer.com/la/book/9783540423249. Kahr formulae is one class of undecidable formuls and it can be expressed in prenex normal form by $[\forall\exists\forall, (\omega, 1), (0)]$.

There are two questions. 1) how to understand this notation and is it possible to see one example of Kahr formulae. 2) What to do if such formula is encountered in pratice? Is it possible to construct more general theory which affirms of refutes this formula? Maybe more creativity is required - there is no automatic proof available, but creative approach can yield some proof for this class? Maybe theory can not say anything about this formula and in practice the additional assumptions outside from the theory should be made (discovered) and then the truth value of the formula can be decided?

There is practical basis for this question. SWRL (semantic web rule language) is the combination of OWL and RuleML and generally it is not decidable. Therefore reasoners implement only decidable subsets of SWRL. But businesses encounter and will encounter SWRL expressions that are undecidable. What to do with such expressions? Can excessively creative mathematicians find proofs for individual expressions and businesses simply need to make more investments? Laws can be formalized in SWRL and what the Supreme Court judges will do if the decision of tha case depends on the affirmation or rejection of undecidable formula? What practical approaches can be made? Who should give the answer?

One approach is use of approximation methods, e.g.
https://cstheory.stackexchange.com/questions/18716/good-reference-about-approximate-methods-for-solving-logic-problems but that works mostly for modal formules where the modal depth can be truncated. Maybe creative search for proofs can be the other answer, or not?


texts: Algorithm: How many symbols of occurence k fit into b buckets under condition

texts:
I have the following problem to solve:

Given a set of buckets $B=\{b_0,\dots b_n\}$ of known size, a constant $k$ < |B| and a set of symbols $S=\{s_0,\dots, s_?\}$ with unknown size.
Place a total of $k$ instances of each symbol into some of the buckets of B, whereas there must not be two symbols of the same kind within one bucket (for each pair of symbols $(s_i,s_j)$ within $b_k$, $s_i \neq s_j$) and there must not be the same pair of two symbols within more than one bucket.
How many symbols can I place into the $n$ buckets?

I am looking for:

A formula that provides $|S|$ depending on $n$ and $k$.
An algorithm to find the perfect placement of $S$ into buckets such that $|S|$ is maximized.
$K$ hash algorithms that provide (for fixed $n$, $k$) in constant time for each $s_i \in S$, the $k$ buckets $s_i$ should be placed such that the constraints above are fulfilled.

For 1. I believe the answer is 2^(log2(|B|) * 2 - k) which I derived from my current implementation but I don't have a good understanding of it.
For 2. I have designed the following algorithm:
Define a hashset for each bucket b. Try to insert a symbol in a certain bucket by looking up said bucket. If the symbol already exists move on to the next bucket. Now determine whether the collision list of said symbol contains any other symbol of the bucket (set), if not insert the symbol and add all other symbols of the bucket to the collision list. In the case of a collision try the next bucket. Repeat until k instances of the symbol are inserted. The algorithm works but does not produce optimal results. In particular, the way of choosing the next bucket in the case of a failed collision affects the quality of the result.
Pseudo Code:
while(true) {
  sym = new symbol;
  collision_list = new empty list;
  while(inserted_symbols < k) {
    for each s in collision_list {
      if(!current_bucket.lookup(s)) {
        current_bucket.insert(s);
        collision_list.insert(all elements of current_bucket);
      }
    }
    current_bucket = next_bucket();
  }
  break if no symbol can be inserted anymore
}


texts: Solving recurrence relation having square root

texts:
T(n) = 2T(√n) + n.

I tried putting n=2^m

T(2^m) = 2T(2^(m/2)) + 2^m.

If I subsitute T(2^m) = S(m) then,

S(m) = 2S(m/2) + 2^m.

This is same as (1*2^m) + (2*2^(m/2)) + (4*2^(m/4)) + ...

Now I am stuck in this summation as it's not a GP.

Can someone please help?


texts:
While reading the paper Effective Data-Race Detection for the Kernel  by
John Erickson and Madanlal Musuvathi. I was stuck on a slightly tricky sentence.

"Similarly, a range of kernel-address space, called session memory, is mapped to different address spaces based on the session the process belongs to. When a sampled access lies in the session memory space, DataCollider sets a data breakpoint but checks if the conflicting accesses belong to the same session before reporting the conflict to the user."

I can not figure out in practice what the session memory is at process level.
Is the session related to the user owning the process? Or is it something more specific of the Kernel?

I know that I am probably missing something important but this is not basically my field of study so, although I tried, I couldn't find substantial answers. Is there someone who can explain me briefly what I am missing?

Cheers


texts: The language of non-extendable strings of a regular language is regular

texts:
I recently came across this question in my textbook.

  $ \text{Let } L \text{ be a language over an alphabet } \Sigma \text{ that is accepted by some FSA.} $
  $ \text{Prove that the language is also accepted by some FSA.} $
  $ \operatorname{Max}(L) = \{x \in L : \forall y \in \Sigma^* - \{ \lambda \}.\ xy \notin L \}.$

Where $ \lambda $ is the empty string in this case.

It seems that any regular language that has any maximal length string must not contain any repetition operators $"{^*}"$. Hence the regular language only consists of characters, concatenation, and alternation. That means the FSA it generates cannot contain any cycles that contain a final state.

From the above, I decided to go with cases, where the language is generated by a regular expression that contains repetition or does not.

If the regular expression contains repetition, then the FSA that accepts the new language contains only one state, the starting state, and no final states.

If the regular expression does not contain repetition, then the FSA that accepts the new language is a copy of the original FSA with the final states restricted to the final states that were the largest number of edges away from the starting state of all the final states. That means only the longest strings that were accepted will be accepted.

This description intuitively makes sense, however, I cannot see how I might begin to prove any part of this, and I do not even know if this description is fully accurate. Is this description accurate and is there an easier way? If this description is accurate, how would I go about proving it?


texts: Choosing taps for Linear Feedback Shift Register

texts:
I am confused about how taps are chosen for Linear Feedback Shift Registers.
I have a diagram which shows a LFSR with connection polynomial $C(X) = X^5 + X^2 + 1$. The five stages are labelled: $R4, R3, R2, R1$ and $R0$ and the taps come out of $R0$ and $R3$.
How are these taps decided? When I am given a connection polynomial but no diagram, how do I know what values I should XOR?


texts: Hey I'm trying to prove that the following Language is regular so far couldn't find a way, hope someone can help me $L^{\prime}=\{x \# y \mid x y \in L, y x \notin L\}$ where $L$ is regular.


texts: Markov Chain Mixing Time of the Complete Graph

texts:
I'm having a hard time understanding mixing time for Markov Chains on Complete Graphs (Kn).

We can define the probability matrix for Kn where Pi,j=probability of going from i to j (technically 1/degree(vi). This is assuming the edges have no weights and there are no self-loops.

Also, the stationary distribution pi exists such that pi*P=pi.

For the complete graph, pi can be defined as a 1xn vector where each element equals 1/(n-1). I got this from defining each element to be deg(vi)/sum(deg(N(vi))) - the degree of node i divided by the sum of the degrees of its neighbors.

What would be the mixing time? I'm not sure how to go about finding it.


texts: Detected if an undirected graph G has a cycle

texts:
Trying to understand complexity well, I found myself with the following problem.

Consider the following algorithm to detect if an undirected graph $G = (V, E)$ has a cycle.

Imagine that $V = \{1 ...|V|\}$ (in other words that the vertices are numbered from $1$ to $|V|$ ).  An explorer plants a flag on point $1$ and then moves on the graph according to the following principle.

For each vertex $u \in V$ the different edges $(u,v)$ around the point $u$ can be ordered according to the size of $v$. So we can talk about the ith edge around $u$. . Note that if $(u,v)$ is the ith edge around $u$ it is possible that $(v,u)$ is not the ith edge around from $v$.
If the explorer reaches the point $u$ of degree $k$ using the ith edge around $u$ then it starts from $u$ using the $(i + 1)$ th edge around from $u$. If $i = k$ then the explorer starts from the first edge around $u$.

As a first attempt, the explorer leaves point $1$ using the first edge around $1$. If it returns to point $1$ by a different edge then he concludes that $G$ contains a cycle.

If on the other hand it returns to point $1$ to across the same edge, then it begins its exploration again, starting by the second edge of point $1$, then the third edge and so on.

If he has exhausted all edges around $1$ and has always returned to $1$ by the same edge, so he plants his flag on point $2$ and so on.

My questions are :

how can we show that $G$ contains a cycle if and only if there is a point $u$ and an edge $(u,v)$ around $u$ such that the explorer leaving $u$ by the edge $(u,v)$ does not return to $u$ by $(u,v)$.
What is the is the space complexity of the algorithm described here?


texts: Why Acceptance by Final sate and Empty Stack in PDA?

texts:
Why there are two ways of accepting the input in PDA i.e. Acceptance by Final sate and Empty Stack I have seen examples which are accepted by both rules?

There are some examples which are only accepted by empty stack but I found they are NPDA's, is there any relation between them


texts: Lack of time hierarchy theorem for probabilistic machines

texts:
The Wikipedia page on the time hierarchy theorem states:

  A similar theorem is not known for time-bounded probabilistic complexity classes, unless the class also has advice.

However, wouldn't the usual time-hierarchy theorem suffice in this case? For instance, we know that $BPP \subset EXP$, and since the ordinary time-hierarchy theorem implies that $EXP \subsetneq 2EXP$, we likewise know that $BPP \subsetneq 2EXP$. Could we not repeat with the bounded probabilistic version of $EXP$, and so on?


texts: If i use other peoples code for my final year project does that come under Plagiarism?

texts: I want to make a facial recognition project but my coding ability is very limited so I am going to be relying on other peoples code but if i use their code even if i change the variables and make different functions to add their code under would that still be considered plagerism ?


texts:
I'm trying to prove that a context sensitive language ⊊ Turing-acceptable language.
I was thinking of working out the complement of the language $A$, where $A$ consists of all words $w$ such that $M_w$ is a 1-NTM that accepts the input $w$ without leaving the input area.
Unfortunately, I can’t figure out how to really prove it.


texts: One time pad, get plaintext using ciphers encoded with the same key

texts:
I'm trying to solve a problem:

I have 11 ciphers encoded with the same key.
My aim is to decode target cipher.

If I do xor C1, C2 (ciphers encoded with the same key) I do get M1 xor M2 (where M1, M2 are plain text messages).

Please say what to do next. I don't understand how to get plain texts from M1 xor M2

UPD: it's a two time pad (i.e. the same key has been use more than one time)


texts:
So, while trying to dive into "recursion" and the like, I came across an epigram about recursion by Alan Perlis:

  Recursion is the root of computation since it trades description for time.

  -- Alan Perlis

Common to epigrams, this sounds like a deep insight. But I've already got stuck on "root of computation" and in which sense recursion "trades description for time".

Any explanation would be nice. : )


texts: Analogue of the topology-computability correspondence for computational complexity

texts:
There is an interesting correspondence between notions of topology and notions of computability theory originating from the ingenious idea of Dana Scott to identify computable functions with continuous functions (in fact it can perhaps be traced back to Brouwer).

Complexity theory can be seen as a refinement of computability theory: we are interested in not only whether a problem is solvable or not but also the efficiency with which it is solvable. Taking this view of complexity theory as a refinement of computability theory, I wonder if there is any research on analogous mathematical structures to provide efficiency-sensitive denotational semantics to programming languages.

The point of topology is that it is distance-blind which is in accord with the efficiency-blind approach in computability theory. So it seems to me that an efficiency-sensitive denotational structure should be a topological space with a notion of distance, i.e., a metric space or something like that.

Has someone worked this out or is this a nonsensical question? If it is the latter, please explain why.


texts: Is there an efficient test for if an NFA accepts a subset of another NFA?

texts:
So, I know that testing if a regular language $R$ is a subset of regular language $S$ is decidable, since we can convert them both to DFAs, compute $R \cap \bar{S}$, and then test if this language is empty.

However, since this requires converting to DFAs, it's possible that the DFAs, and thus the testing algorithm, will be exponential in terms of the number of states in the input NFAs.

Is there a known way to do this in polynomial time? Has this problem in general been proved Co-NP complete?

Note that the problem is in Co-NP since a word accepted by $R$ but not by $S$ would be a polynomial certifier that $R \not \subseteq S $.

EDIT: this is incorrect, as there is no guarantee that such a word would be polynomial in the number of states.


texts: Infinite languages and undecidable languages

texts:
I'm having a problem with proving the following statement:

For every infinite language $L$, does there exists an infinite language $L'  \subseteq L$ such that $L'$ is not decidable?


texts: Facial Recognition State of the Art Measurement

texts:
I would expect issues with the Facial Recognition technology to prompt evaluators to measure performance with metrics such as:

accuracy (e.g. false positives)
poor image quality input handling
speed of algorithm

What are the metrics used to gauge state of the art Facial Recognition?  Please feel free to add the list


texts: A special case for the subset sum problem: selecting from powers of two

texts:
Given a multiset $X=\{x_1,\dots,x_n\}$ where every element $w_i$ is a power of two, and given an integer $M$, I'd like to determine if there is any subset of $X$ that sums to $M$.

(This question is based on a previous question about the subset problem where every number in the set is a multiple of two, but this time $X$ consists only of powers of two.)

Can we find an efficient algorithm for this problem? Could we make it any better than standard algorithms for subset sum or knapsack?


texts: Aggregate text data of some particular column

texts:
I have a dataset as follows

Biodata
last_name  first_name  age   Description     Hobby
Smith       John       20    In high school  Music
Johnson     Robert     45  Software Developer Gardening
Williams    David      15     Junior school  Baseball
Davis       Michael    65     Traveler       Skydiving
Miller      Molly      25     Scientist      Cycling

Now I got a question from a assignment that Aggregate text data under “Description” and “Hobby”

I cannot understand what is the meaning of Aggregate text data?

If any one understand the question please share their view point. I want to know it theoretically how could any one aggregate text data depend upon description and Hobby column.

This is a coding assignment of python. But currently I don't bother about coding. I want to know the theoretical meaning of this question and want to solve it manually.

Thank you in advance


texts: Is there a dynamic programming solution to the student allocation problem?

texts:
The student project allocation problem I am trying to solve goes as follows.

There is a set $S$ of students and $P$ of projects such that $|S| \leq |P|$.
Each student makes a top $3$ of their preferred projects.
Each student should be allocated to exactly one project.
Each project has a maximum number of students which can choose it, $c$.

We want to find some combination of students being allocated to projects so that a maximum of students are allocated their preferred project. Of the students who didn't get their preferred choice, a maximum of them should be allocated their second choice.

This is a optimization problem with constraints. If we assign a priority weight $w_{ij}$ for the $i^{th}$ student choosing the $j^{th}$ project, where $w_{ij} \in \{0, 1, 2, 3\}$, and $w_{ij}$ is $0$ when the student $i$ did not include project $j$ in his top $3$, $1$ if it is his third choice, $2$ second choice, $3$ preferred choice.

We can also introduce a variable $x_{ij} \in \{0, 1\}$, which is equal to $1$ when student $i$ has been allocated to project $j$ and $0$ otherwise.

Now we can formulate an objective function, $o$, to maximize in order to reach an optimal allocation.

$$o = \sum_{\forall (i, j) \in S \times P}{x_{ij} \cdot w_{ij}}$$

We must maximize $o$ according to the problems constraints.

$$\forall i \in S : \sum_{\forall j \in P}{x_{ij}} = 1 \quad \textrm{every student is allocated to exactly one project}$$

$$\forall j \in P : \sum_{\forall i \in S}{x_{ij}} \leq c_j \quad \textrm{no project is allocated more than its maximum number of students}$$

I think there are no other constraints.

Now, I am stuck. How do I go about actually solving this on a computer given all of the above. Is there a relationship between the optimal allocation for $i$ students and $i + 1$ students? Can I use dynamic programming, and if so how? Or do I have to use some other method, and if so what method?


texts: Which option is most efficient for the design of my multi-peer connection (session)?

texts:
This is my first time working with peer to peer connections, Im using WebRTC. If possible I'd like to design my multi-peer connection (session) so that there's no limit to the number of peers who could potentially connect to this session.

The session handles the following data transfer:

video data from one of the peers
message data from all of the peers
audio data from all of the peers

I don't know how this is normally done, but I considered a few options that seem to differ fundamentally:

[Equal Load] Each peer connects to each other peer. So if there are 10 peers, each peer makes 10 peer to peer connections. All of the above data is sent from each peer to each of their connections.
[Host Burden] Each peer connects to only one peer, the host, who connects to all of the peers. The data is sent to the host peer, who reflects it back to each other peer as necessary.
[Static Reflection] Each peer is connected to exactly one other peer. The data is reflected from each peer until it has been shared with them all.
[Dynamic Reflection] Each peer is tested for a rough estimate of its bandwidth capabilities, and connected to a dynamic number of peers based on an algorithm to determine the number of peers it can transfer the session's data to without going beyond its bandwidth capacity. The data is reflected from each peer until it has been shared with them all.

Which of these connection structures is the most efficient solution for my multi-peer connection (session)? If there is no clear winner, or none of them are the correct structure, please explain the pros/cons or the explanation of a better structure.