texts:
Here is another GeeksforGeeks problem that asks how to find the shortest Uncommon Subsequence of 2 strings?

For example,

  Input : S = “babab” T = “babba”

  Output : 3The subsequence “aab” of length 3 is
  present in S but not in T.

  Input : S = “abb” T = “abab”

  Output : -1
  There is no subsequence that is present
  in S but not in T.

Can anyone explain this stuff with respect to recursively going from the start of the string rather than their from the back of the strings?

I think for the recursive solution, they have started from the back of both strings and then recursively gone to the start.

Can anyone transform this to start the recursion from the start of the strings and then go on until the end of the strings?

Later, I'll then try myself the DP solution out of it.

I'm unable to get their logic but tried it my way to write the code.

Here, is the partial solution written by me (which doesn't makes sense to me too) which isn't working but I want the solution in this form. ie - to send the first parts of both the string and not from their end parts.

Help me in correcting it. Please do mention the explanation for the developed code.

#include<iostream>
using namespace std;
typedef int ll;

ll fun(string s,string t,ll a,ll b){
    if(a>=s.length()){
        if(b==0){
            return 999999;
        }
        else{
            return 0;
        }
    }
    if(b>=t.length()){
        if(a==0){
            return 999999;
        }
        else{
            return 0;
        }
    }

    ll flag=0;
    ll i=0;
    for(i=0;i<b;++i){
        if(s[a]==t[i]){
            flag=1;
            //cout<<"->"<<s[a]<<" "<<t[i]<<endl;
            break;
        }
    }
    if(flag==0){
        return 1;
    }

    return min(1+fun(s,t,a+1,i+1),fun(s,t,a+1,i));
}
int main(){

    string s;s="sa";//cin>>s;
    string t;t="as";//cin>>t;
    ll b=fun(s,t,0,0);
    if(b>=999999){
        cout<<-1;
    }
    else{
        cout<<b;
    }

    return 0;
}


texts: Approximation algorithm question, clustering on n points

texts:
So the algorithm I thought of, is to iterate through the n points, centering a ball at each point, and keeping track of the point where we centered that encapsulated the most points. Then remove the encapsulated points from this max ball we found, then iterate through all the points again. Continue until there are no longer any points not encapsulated. Return all the centers we found.

I'm not sure if this algorithm is correct. O(1) approximation algorithm is in terms of O( $\frac{\Delta_{ours}}{\Delta}$). The requirement is a polynomial algorithm, which I believe mine is in the order of $n^{2}$.

I'm also not sure how to prove the correctness of an approximation algorithm either.


texts: Can the processor just turn off the interrupt request line?

texts:
I was doing some of the interrupts question online and found this Multiple choice question

How can the processor ignore other interrupts when it is servicing one

a) By turning off the interrupt request line
b) By disabling the devices from sending the interrupts
c) BY using edge-triggered request lines
d) All of the above

The answer was (D) but I wonder how are we allowed to turn off the interrupt request line ?

What if we have a high priority interrupt that comes after ? We just ignore it ?
I mean (a) seems counter intuitive for me, because I don't think under any circumstances we should be turning off the interrupt request line ?


texts: Combinations of elements with mutual relationships

texts:
I need to create the combination of 3 elements from a array of given n elements, however every of those 3 el. has to be in "relationship" with each other. Here is an example I can describe my issue better on:

We've got elements 1, 2, 3, 4, 5 & 6. We know following relationships:

1 <--> 2
1 <--> 3
1 <--> 4
1 <--> 6
2 <--> 3
2 <--> 5
3 <--> 5
3 <--> 6
4 <--> 5
4 <--> 6

A group {1,2,3} is viable, because 1 is in relationship with either 2 & 3 and 2 is in relationship with 3.

In a group {1,2,4} is 1 in relationship with 2 & 4, however 2 isn't with 4, thus this combination can't exist.

I programmed a functional solution(which involved the above mentioned creating of combinations, redirecting to the list of relations of every element) for small amount of elements and relationship, but I need to have one for approx. 500 000. I'm a high school student and I haven't met a branch of mathematics which would help me to understand or to solve this problem.

I've been searching the net and I think that a relational algebra (binary relations) might be the solution, yet I'm not quiet sure where to start.

Can you think of any hint, advice, web source or view that could help me?

Thank you


texts:
I've search on Google but still don't understand. I've read about it into arm book, but they don't define it.

Could you explain me what is it, where is it used, what's the point to have it and, if you can, its used into arm chips.

Thanks.


texts: Delivery Clustering based-on Pick-Drop & Driver locations

texts:
I'm reading some papers about Delivery Clustering to solve following generic problems:

  Given N orders (with its Pick-up and Drop location point) and M delivery-man (with his location). We are going to assign M' drivers (M' <= M) to handle that N orders. Each driver can handle some X orders (X >= 0, in case X = 0, driver is not assigned). Our goal is to minimize total driving cost of drivers, including driving time from his location to the first pick-up order's location, and whole driving time to delivery all X orders.

In mainly papers I've noticed that the authors just considered these N orders as one point (not separated as 2 pick-drop points) and for each cluster, they will find the best assignment to minimize total driving cost from current location to the first order in that cluster.

How can we treat two pick-drop points of order within same cluster?


texts: Time complexity of 1-d clustering recursive algorithm

texts:
I have the following code:

n - number of 1-d points (real numbers)
numbers[n] - array of numbers n
list, se_list - list variables to store cluster starting points
_____________

sort(numbers)

find_cluster(start, end, ci): \\ ci - cluster index
  best_se = +infinity \\ best squared eror
  list = {start}
  for i from start to end−ci+1:
    if ci > 1:
      (se, se_list) = find_cluster(i+1, end, ci-1)
    else:
      se = get_se(i+1, end)
      se_list += {i+1}
  new_se = get_se(start, i)
  if new_se + se < best_se:
    best_se = new_se + se
    list = list + se_list
  return (best_se, list)

\\ this computes variance of points from start to end
get_se(start, end):
  sum = 0
  for i from start to end:
    sum = sum + numbers[i]
  mean = sum/(end-start+1)
  se = 0
  for i from start_to_end:
    se = se + (numbers[i]−mean)*(numbers[i]−mean)
  return se

As far a my analysis goes, this algorithm take time O(n^(2k)), where k = ci, but I am not sure if I am correct. I first proved it to myself as

T(n) = n*(n + T(n-1)) = n^2 + n*(n-1)*((n-1) + T(n-2)) + ...

so it tends to n^k, but there are smaller arguments which are for sure smaller than n^k, so overall time is O(n^(2k)). But I am not very experienced so what is the running time of it?

Details: the original question for each I made this algorithm is "there are n points in 1 dimension (real numbers) which you need to cluster as k-means in polynomial time". K (i called it ci in this algorithm) is the number of clusters.

Details 2: By smaller arguments i meant that when we start opening parenthesis in T(n) = n^2 + n*(n-1)*((n-1) + T(n-2)) -> there will appear 1 argument n^k and a lot of smaller arguments. Though n^k is the largest power in this equation, if I take O(n^k) < O(n^2k), then this will also account for smaller arguments (just because), but i dont think that "just because" is a valid argument especially if a constant should do. But still the question holds  O(n^2k).

NB. I need to check the links in comments, but if I understood this well enough there wouldn't be a need to ask this question right? So I do not think that referencing me to other materials unless they site exactly the same algorithm is right. So I am asking someone with good understanding of algorithms either verify my claim (better with small proof) or just say i'm plain wrong and possibly provide an explanation why.


texts: The symbolic differentiation of univariate expressions

texts:
I was reading "Doug McIlroy: McCarthy Presents Lisp" and the phrase "symbolic differentiation of univariate expressions" triggered a faint memory of a demonstration of differentiation done in haskell using higher order functions.  (I think my memory is of using the language to produce a function that is the differential of a function given.)

However I haven't been able to find any other reference to the above phrase in lisp or ML-based languages.

Does anyone have more information on this, and is "symbolic differentiation of univariate expressions" the same thing as the memory I described?


texts: Constructing xor separable boolean upper bound

texts:
Problem statement Suppose I have a boolean function $f: \mathbb{F}_2^n \times \mathbb{F}_2^m \to \mathbb{F}_2$ where $\mathbb{F}_2 = \{0,1\}$.
I define two boolean functions $h: \mathbb{F}_2^n \to \mathbb{F}_2$ and $g: \mathbb{F}_2^m \to \mathbb{F}_2$ to be xor separable upper bound of $f$ if
$$f(\vec{x}, \vec{y}) \leq h(\vec{x}) \oplus g(\vec{y})$$ for all $\vec{x} \in \mathbb{F}_2^n$ and $\vec{y} \in \mathbb{F}_2^m$. (Here $\oplus$ is the logical xor operator).
Let $S$ denote the set of xor separable upper bounds of $f$.
I would like to like to optimize the following:
$$\min_{(h,g) \in S} |\# h^{-1}(0) - \frac{1}{2} 2^n|$$
In particular, I wish to find the optimal $h$ and $g$. However, this seems incredibly difficult.
Question: Is there a heuristical method to find $h$ and $g$ such that $|\# h^{-1}(0) - \frac{1}{2} 2^n|$ is "small" (doesn't have to be the optimal value)? Feel free to assume any nice boolean expression format for $f$ (such as CNF or DNF, etc...). I cannot come up with an algorithm better than brute force iteration. Here, $n$ and $m$ can be very big (order of hundreds)
Comments Note that $S$ is not empty since the constant function pair of $(h = 1, g = 0)$ is in $S$. Thus the minimization problem is well posed. Furthermore, I am not certain if this will help, but does the problem become easier if $\#f^{-1}(1)$ very small compared to $2^{n + m}$?
Edit Instead of optimizing $\min_{(h,g) \in S} |\# h^{-1}(0) - \frac{1}{2} 2^n|$, getting the tightest upper bound would be interesting as well.


texts: Confusion with first condition of Chomsky Normal Form

texts:
I had a very quick question when it comes to CFG (more specifically the attributes of CNF). I've been browsing over some examples and I've come across a few that confuse me. One such example is this:

$$\begin{align}S&\to XA|BB\\
B&\to b|SB\\
X&\to b\\
A&\to a\\
\end{align}$$

It is stated that this is indeed in CNF, but my confusion lies in the fact that under most rules it is stated that if the starting state $S$ exists in some RHS (in this case $B\to b|SB$) we must create a rule that states $S'\to S$.

Since that doesn't exist in this example, why is this considered to be in CNF? I also understand the rules of CNF, I also see that this example technically satisfies all those rules, so I am wondering if that is the reason?

Rules:
$$\begin{align}A&\to a\\
A&\to BC\\
\end{align}$$

Thank you for the help in advance!

Here is the link to the question for reference ( it deals with CFG TO GNF)
https://www.geeksforgeeks.org/converting-context-free-grammar-greibach-normal-form/


texts: What does it mean when we say that a run of Prim's algorithm is trivial? What are example graphs for either case, that is with and without trivial runs?


texts: What are the correct steps in solving polygon monotone triangulation?

texts: I am working out  step by step and I am stuck on vertex 7. I got that it was a regular vertex and helper(e_i-1) is not a merge vertex so I look for the leftmost edge in the sweep line. My question is, would e6 be considered to the left of it, or is it none? Any already completed examples that I could see would help me understand this greatly.


texts: Why not decide coNP language L with same NDTM used for $L^c$?

texts:
In Michael Sipser's book language is defined to be in NP iff it is decided by nondeterministic polynomial time Turnig machine. Why can't we use same machine to decide if language $L^c$ is in coNP? Just run every string x on same NDTM and if it accepts x then x is not in $L^c$ and if it rejects x then it is. What am I missing here?

In this book runnin time for NDTM is defind only for deciders, NDTM which halts in all branches.


texts: Is a circular linked list (of a finite set of nodes) considered to be an infinite list?

texts:
So, a circular linked list is a linked list where the next pointer of the last node points to the first node (forming a circle).
Now, a linked list comes with some standard methods, like size()/length(), toArray(), or traverse() (print out the nodes).
Clearly, the implementation of the above (and related) methods, depends on whether a circular linked list is assumed to be infinite or not, I think. For example, its size/length should be infinity if the list itself is assumed to be infinite.
However, I do not know what the general assumption is in this case (if it exists).


texts:
I'm having real trouble tracing some pseudocode for insetion into a Binary Search Tree. I need to understand this in order to be able to teach it, but I think there are flaws in the material.

For example,

CALL FindInsertionPoint(NewDataItem, Index, Direction)

is only meant to have one parameter according to the description in the question, and should return Index and Direction:

Doesn't this make the line before it in the code below:

Index ← RootPointer

redundant?

PROCEDURE AddToTree(BYVALUE NewDataItem : STRING)
// if no free node report an error
    IF FreePointer = -1
        THEN
            OUTPUT("No free space left")
        ELSE // add new data item to first node in the free list
            NewNodePointer ← FreePointer
            Tree[NewNodePointer].Data ← NewDataItem
            // adjust free pointer
            FreePointer ← Tree[FreePointer].LeftPointer
            // clear left pointer
            Tree[NewNodePointer].LeftPointer ← -1
            // is tree currently empty ?
            IF RootPointer = -1
                THEN // make new node the root node
                    RootPointer ← NewNodePointer
                ELSE // find position where new node is to be added
                    Index ← RootPointer
                    CALL FindInsertionPoint(NewDataItem, Index, Direction)
                    IF Direction = "Left"
                        THEN // add new node on left
                            Tree[Index].LeftPointer ← NewNodePointer
                        ELSE // add new node on right
                            Tree[Index].RightPointer ← NewNodePointer
                    ENDIF
            ENDIF
    ENDIF
ENDPROCEDURE

I've tried tracing the algorithm for the data from the question I get stuck quite early on because I can't tell what value for Index should be returned from FindInsertionPoint().

The input sequence is: Dublin, London, Berlin, Paris, Madrid, Copenhagen, Athens.

When all is done, the result should look like this:

I need help working out what is due to my own lack of understanding and what is due to problems with the material. It would be great to see a correct trace table for the algorithm using the data given.

In partcular, how can I work out the return values for the FindInsertionPoint() function?

Thanks in advance.

Below is an image of the algorithm given in the solutions (same as pseudocode above).


texts: Are JavaScript libraries “linked” like C++ libraries?

texts:
I'm trying to better understand the concepts of static and dynamic linking, in terms of the ways JavaScript libraries are used in modular systems.

Does it ever make sense to describe a JavaScript library run in a browser as "linked" in a technical sense, the way you would a C++ library?

For instance, in these examples:

a JavaScript library is included directly in html with a tag
a JavaScript library is imported using a module system like RequireJS or Node.js via npm
a JavaScript library is bundled using Webpack or Browserify

Could any of these situations count as either static or dynamic linking, either in the context of another JavaScript library or in terms of the browser as the "executable"?

Put another way (thanks @Gilles): is there a concept unifying what is called linking in typical C++ programs and these various ways of referencing and combining JavaScript?


texts:
I might need some help with the following question.

Given a Partial Combinatory Algebra, we can define the fixed point combinator $Y := [\lambda^{*}xy.y(xxy)][\lambda^{*}xy.y(xxy)]$. How does this relate to Kleenes recursion theorem, aka. fixed point theorem?

In the setting of Kleenes first PCA, ie. the PCA of computable functions on $\mathbb{N}$, given a (partial) computable function $f = \varphi_c$ the fixed point combinator satisfies $Yc = c(Yc)$. As I understand it this means that taking d := Yc it translates to $f(d) = \varphi_c(d) = cd = d$, ie. $f$ having a fixed point.

However Kleene's recursion theorem originally gives a weaker assertion, namely that for every total computable function $g$ there is some $n$ such that $\varphi_{g(n)} \simeq \varphi_n$ (cf. Odifreddi - Classical Recursion Theory, Theorem II.2.10).

This really confuses me and I couldn't make up my mind what to do about it. I hope someone can help me out. Anyway, thank you for your time.


texts: Checking whether there is k circles with common area

texts: I have N circles with different radius and position in the plane. The problem is finding k circles which have a common area.Obviously this can be solved using Brute-Force in $O(N^k)$. Is there a more efficient way to do such query?


texts:
i have found the equivalence classes of given $R_L$ and i need to find the separating words between the equivalence classes(which i don't know how to do). would appreciate if you could explain to me how to do so. also, if you can, would appreciate if you could check if i obtained the correct equivalence classes for both languages.

1)$L=\bigg\{w\in \sum^*\bigg| w\quad \text{starts and ends with} \quad aa\bigg\}$

equivalence classes i've obtained:

$S_1 = \epsilon$

$S_2 = a$

$S_3 = (b+c)\sum^*+a(b+c)\sum^*$

$S_4 = aa+aaa+aa\sum^*aa$

$S_5 = aa\sum^*(b+c)a$

$S_6 = aa\sum^*(b+c)$

2)$L=\{\sum^*-(\{\epsilon, a,b\}\cup \{bba^i|i\ge 0\})\}$

equivalence classes i've obtained:

after joining $\{\epsilon, a,b\}\cup \{bba^i|i\ge 0\}=\{\epsilon, a,b,bba^*\}$ and using the complementary, i've obtained:

$S_1 = \epsilon$

$S_2 = a$

$S_3 = b$

$S_4 = bba*$

$S_5 = c\Sigma^*+a\Sigma^++b(a+c)\Sigma^*+bb\Sigma^*(b+c)\Sigma^*$

how can i find the separating words? also, if you can, could you verify that i've obtained the correct results?

thank you very much!


texts: Why are the total functions not enumerable?

texts:
We learned about the concept of enumerations of functions. In practice, they correspond to programming languages.

In a passing remark, the professor mentioned that the class of all total functions (i.e. the functions that always terminate for every input) is not enumerable. That would mean that we can not devise a programming language that allows us to write all total functions but no others---which would be nice to have!

So how is it that we (apparently) have to accept the potential for non-termination if we want decent computational power?


texts:
Multi-label classification is a machine-learning problem where each sample can have zero or more labels from a closed set of possible labels. This task has applications in several fields. For example, in dialog systems, each sentence that the human says may have several intents, and the classifier should detect all of them. For example, the sentence "I want a cake and a drink" contains the two intents "WANTCAKE" and "WANTDRINK".

Theoretically, I expect a classifier to classify multi-label samples, even if the training data contained only single-label samples. For example, consider the following training set (where each word is considered a feature):

"I want a cake" -> WANTCAKE
"I want a drink" -> WANTDRINK
"I want a solution" -> WANTSOLUTION

I would expect a classifier to realize, that the words "I want a" are not relevant for classification, and the words cake/drink/solution are indicative of the classes WANTCAKE/WANTDRINK/WANTSOLUTION respectively, and classify the sentence "I want a cake and a drink" correctly as {WANTCAKE,WANTDRINK}.

This seems trivial to humans. Therefore. I was very surprised to find out, that many state-of-the-art multi-label classifiers fail miserably on this simple task!

For example, consider a multi-label classifier in the "Binary Relevance" method. In this method, there is a single binary classifier for each label. For example, there is a binary classifier for the "WANTCAKE" label, trained with I want a cake" as a positive sample, and the other two sentences as negative samples. When this classifier sees the sentence "I want a cake and a drink and a solution", it sees a single feature "cake" that is a positive signal of WANTCAKE, and two features, "drink" and "solution", that are negative signals of WANTCAKE, because they appeared in the training set with sentences that did not have the WANTCAKE label. Therefore, this classifier returns 'negative'. The same happens for the other two binary classifiers, and thus the multi-label classifier returns an empty set!

I also tried other approaches to multi-label classification, such as RF-PCT (Random Forest Prediction Clustering Trees), with a slightly larger example (7 labels instead of 3) and got similar results.

I sent this problem to machine learning experts, and they told me that I need more training data. They said that a classifier cannot tag multi-label instances, if the training data contains only single-label instances. In practice, they are right - adding more training data usually improves the accuracy of the classifier.

But I am still bothered with the theoretical issue - how can it be, that there is no state-of-the-art classifier that can solve this trivial, 3-instance problem?

I am looking for a classifier that provably solves such problems. I.e., a classifier for which there is a proof, that if it is given correct single-label samples, it can correctly solve multi-label cases.

Is there such a classifier?


texts: Who coined the term "artificial intelligence"?

texts: The most obvious (and commonly given) answer to this question is John McCarthy, but I have traced the first usage of this term to a 1955 paper, which McCarthy co-authored with Marvin Minsky, Nathaniel Rochester, and Claude Shannon. Although McCarthy was the lead author and probably the main organizer of the 1956 Dartmouth Summer Research Project on Artificial Intelligence, it could just as easily have been that one of these co-authors actually proposed the term "artificial intelligence". Does anyone know of any other evidence to suggest whose idea the actual term was? All of these individuals are now dead, but maybe some of their close associates or former students might be able to also shed light on the question.


texts: How to Find the minimum permanent which is pumping lemma for language context-free?

texts:
Suppose we have context-free language and we know the Context-Free-Grammar, how do i found the  minimum permanent which is pumping lemma for language ?

for example let sat i have this Grammar:
$$\begin{align}
S&\rightarrow AA\mid B\\
A&\rightarrow 0A\mid A0∣1\\
B&\rightarrow 00B0\mid 1\\
\end{align}$$
whats is the best way to find this Minimum permanent?


texts: What is the lower bound for the following equation

texts:
f(n) = 32n^2 + 17n + 1.

The lecture slide says that lower bound can be Omega(n^2) or Omega(n).

Some body please guide me why the lower bound can be Omega (n). i know the upper bound which is O(n^2).

Zulfi.


texts:
Is the language $\{a^{n^2-1} | n \in \mathbb{N}\}$ context free? and how to prove it?
I think it is, but I could not find a way to prove it by using push down automaton or any other way.


texts: Binary Search Tree Stability Data Structure

texts:
After constructing a binary search tree, you can read off the key values in ascending order by performing an in-order traversal.
Will the resulting sorted order be stable?
If so, how would the tree have to be coded to ensure this?
If it is not possible, why not?"

Just a review question I came across. From what I understand,
Stability ensures that if A and B share the same Key, if A comes before B originally, A comes before B after sorting as well.
Ascending order = Bottom up
Inorder = Left - Root - Right
if we have a BST that looks as such;
----5,a
--3,c  4,b
-1,d
and we insert a 1,e into the tree. We can get that 1,e on the left or right child of 1,d.
We want to return 1,d first then 1,e so that stability is retained.
How do we change the code for the BST to do this? My suggestion was to make a linked list that returns the head of duplicate values whenever duplicates are encountered. However I'm not sure this is entirely the best method here.


texts: Is there a combinator that introduces brackets to a combinatory logic expression using just B?

texts:
Suppose I have the expression $abcdef$ and I want a combinator $X$ that does this:

$Xabcdef=a(bcd)(ef)$.

Is it possible to express $X$ using just the $B$ combinator, defined by

$Babc=a(bc)$?

Is this possible in general? That is, if I have a string of letters without brackets, is there always a combinator in terms of $B$ only that parenthesizes my expression in the way I want, leaving the order of the letters unchanged?


texts:
How would one represent the number -4 as an 8-bit normalised, 2's complement, floating point, with 4 bits dedicated to the exponent?

As a normal 4-bit 2's complement number, it would be represented as 1100.

How would this be normalised, with the start of the mantissa being 1.0?

Would it be 1.000 0010, with the extra 1 on the left (after evaluation to a normal 2's compliment number) being filled in?

If so, how would you know to fill it with a 1, because it starts with a 1?


texts: General approach to randomized algorithm for equality problem

texts:
Using randomized approach we can guarantee that the equality problem has O(1) complexity (in communication).
With other definitions of of equality (not strictly equal), is there a general approach to design a randomized algorithm with bounded error? Or how to determine if there is no way such an algorithm can be designed?


texts: How to compute time complexity of a program if the time complexity of a function called inside a loop is known?

texts:
This is the question-

  Let $A[1,....,n]$ ba an array storing a bit $(1\,\,or\,\,0)$ at each location, and $f(m)$ is a function whose time complexity is $\theta(m)$. Consider the following program -

counter = 0;
for( i = 1; i <= n; i++)
{
    if(A[i] == 1)
        counter++;
    else
    {
        f(counter);
        counter = 0;
    }
}

  Options are :
  (A)$\Omega(n^2)$
  (B)$\Omega(n\log n)$ and $O(n^2)$
  (C)$\Theta(n)$
  (D)$\mathcal{O}(n)$

The solution says - "Since it contains only one loop, so compute with linear complexity, hence the complexity will be $\Theta(n)$".
My doubt is, what if the time complexity of the function $f(m)$ was given to be $\theta(2^n)$ or of the order that grows in exponential time? Would the solution given in the book be correct in case of exponential time?


texts: Chord algorithm - how to map nodes to keys?

texts:
I'm trying to understand Chord algorithm (for Peer-to-Peer systems) but I can't understand how it maps the documents to the nodes.

I have one example where we have:

keys with 4 bits
5 active nodes with the following identifiers: 1, 5, 7, 10, 13

After mapping the documents to the nodes, we have:

Key 0 - Node 1

Key 2 - Node 5

Key 8 - Node 10

Key 11 - Node 13

Key 15 - Node 1

If somebody could help me with the steps that lead to this results I'd be truly grateful.


texts: Is there any example of Regression Tree driven optimization (or active learning)?

texts:
Bayesian Optimization is the classic example of meta-model driven optimization where new observations are used to train a Gaussian process that provides a clue to where to optimize next.

LEM (Learnable Evolution Models) are evolutionary models where rather than recombining observations (like GAs) a population is fit to a classifier to find out which areas are more promising (although the method itself has quite a lot of non-statistical operations on top of this).

I was looking for something simpler where the optimization is driven by a simple regression tree (sample from most promising leaf or through some bandit algorithm on the leaves). However I can't seem to find any reference on the subject. It must have been tried before.


texts: Weighted Online Matching - randomized algorithms

texts:
Let's consider the edge weighted online matching problem.
The Vertices arrive online and reveal all their current edges and edge-weights $w_e>0$. The goal is to maximize the matchings weight. An edge can only be added once and irrevocably to the matching. As so often, we consider basically consider the setting from KVV.
It is obvious, that any deterministic algorithm can't be competitive against an oblivious adversary. Since any new edge could have arbitrary large weight.
Can a randomized algorithm improve upon this result?


texts: Construct a DFA from the regular expression (a)*+(aab)*

texts:
I've broken down the expression into two simpler DFAs but right now I'm stuck.

I don't know what to do with the expression a*, my solution currently (as presented above) is a NFA, not DFA.


texts: Can we understand SVM without knowledge of Machine Learning

texts:
I was told by my adviser (future one) to look into libsvm library or any other and try to get familiar with it.. to work on a programming project (on Machine Learning) (will start in a month).

my background: Programming knowledge in Python, C.. doing Java now.

So, where should I probably start? and How long it takes me to get into ML, SVM etc.. and be productive? Would I probably fit for this project? --considering my programming background (I so far have been much into Web development, wanted to take a change and have fun)


texts: Finding the grammar type of the programming language

texts:
How can someone find what type of grammar for a given programming language?

Formerly I'm looking for a grammar type for most popular programming languages: C, C++, C#, Java, List, OCaml, Haskell etc.


texts: Shortest path in a maze where you can break one wall

texts:
How would I solve the following problem?

You have maps of parts of the space station, each starting at a prison exit
and ending at the door to an escape pod. The map is represented as a
matrix of 0s and 1s, where 0s are passable space and 1s are impassable
walls. The door out of the prison is at the top left (0, 0) and the door into
an escape pod is at the bottom right (w−1, h−1).
Write a function that generates the length of a shortest path from the
prison door to the escape pod, where you are allowed to remove one wall
as part of your remodeling plans.

I know that without destroying the walls this could be easily solved with the use of Dijkstra. But how to take into account the fact I can destroy one wall?

The only solution I could come up with was to remember two distances for each node: one distance is the "real" shortest path, the second one is the shortest past when I break one (any) wall.

At first I would count all the "real" shortest paths with classic Dijkstra. In the second run I would use Dijkstra again to compute the second parameter of each node: shortest path with exactly one wall broken.

In each iteration the closest node to be chosen (I need to check even vertices that are "one wall away") in Dijkstra is the one with the shortest "real" path or path with a broken wall (whichever is smaller). In case the vertex is one wall away, I only check the "real" path property of course.

This seems correct to me. But is there a better (more efficient) solution?


texts: Out of these two algorithms. Is there always an input where A is faster then B? (Big theta notation)

texts:
I am currently learning landau notations and am stuck on the following True/False question.

What seems a little confusing to me is the use of big-theta notation to describe worst-case run-time.
What is the difference in saying "worst-case run-time Θ(n log n)" or simply "run-time O(n log n)"? Giving the worst case a tight limit seems a lot like simply giving an upper bound to the run-time.

If I go by that reasoning my guess would be that the statement is true. As an O(n) algorithm will be faster than an O(n log n) as n grows large enough.
But i am not sure if my reasoning is correct and if i get the big picture here.


texts: How to verify Hamilton-Path in log-space?

texts: Given an undirected graph $G$ and an undirected path $p$, Is it possible to verify $p$ is a Hamilton path in graph $G$ using logarithmic space? How is it possible to verify the path goes through all vertices without somehow save which one had been already checked?


texts: How to handle distribution of values with same attributes into different classes

texts:
I'm a student studying a data mining course and have come across a problem.
I need to explain the problem with the help of an example scenario as I do not know how to explain the problem in any other way.
I have n 'manufacture dates' (classes). On a particular day, y identical balls are to be segregated into these n classes based on their date of manufacture. I have x identical balls left for which I do not know the dates of manufacture (unclassified), i.e. y-x balls were classified.
Let us call the mean/standard deviation found when all balls were classified correctly to be the "true" mean/standard deviation (i.e. mean/standard deviation when all y balls are correctly classified)
Since we do not know the classes the x balls belong to, how can we distribute the x balls amongst the n classes so that we get a mean/standard deviation that is close to the true mean/standard deviation ?
My approach:

Case1: Value of x (i.e. number of balls not classified on a particular day) is relatively small to the  total number of balls given on the same day (maybe 1 out of 10 balls are not classified).
In this case, I considered ignoring the balls that haven't been classified as the difference between the final result (mean and standard deviation of the balls classified) and the true mean/standard deviation would be minute.

Case2: Value of x is relatively large (i.e 4 out of 10 balls are not classified OR 6 out of 10 balls are not classified).
In this case, I do not prefer ignoring the unclassified balls as the end result (mean, standard deviation) will be erroneous. Rather, I thought of performing an even distribution or weighted distribution of the unclassified balls into the classes, but I do not have good reasoning for why this would be a good approach other than the point of not ignoring majority of the balls.


texts:
I want to know 'What Computer Scientists Actually Do'. It is kind of a very vague thing to me. I don't know anything about it, actually.
I have many people in my family who chose and plan on choosing CS but I do not understand what they do after being done with their Academic Classes and perhaps after their placement too.
Do they continue with their job and work on their own projects too ? If so, then what kind of projects do they work on ?
And what if one doesn't go for business administration ? What designations do they get in companies ?

These may look like different questions but it is actually just one question and those may be parts of it. All of these make up that question.
What they study and how they apply their knowledge or do they even (I mean how many of them).

You can understand this I think. That first line is everything here.

Thank You !


texts: How can a computer run an infinite loop?

texts: I understand the concept behind for and do/while loops, but I am trying to understand what is happening at the hardware level that allows a loop to run infinitely. Technically wouldn't it have to stop at some point because there are only a couple billion transistors in a microprocessor? Maybe my logic is off.


texts: How to simulate a cellular automaton via a Turing machine

texts: It is rather easy to see that every cellular automaton can be simulated by a Turing machine: We can simulate a cellular automaton with an appropriate C program and every C program can be simulated by a Turing machine. But how would a concrete TM look like which simulates a CA?


texts: What is the difference between R precision and precision at K?

texts:
I am trying to understand the difference between these two but it looks like as if they are calculated the same way. What is the difference?

R precision:

  R precision is the precision at the Rth position in the ranking of results for a query that has R relevant documents.

Precision at K:

  Precision at K is calculate for only K documents. Documents ranked lower than K are ignored.


texts: Proving unsatisfiability of a propositional formula

texts:
I have a propositional formula $F$ and an assignment of truth variables $A$. The assignment $A$ assigns a truth value to each variable in $F$ and then it can be evaluated.

I have a function which for a given formula $F$ and a given assignment $A$ checks if both $A$ and $\overline A$ evaluate to the same truth value. It looks like this:

boolean checkSymmetry (Formula F, Assignment A) {

    if (evaluate(A) == evaluate((not A)))
        return true;
    else
        return false;
}

Now I want to use method checkUnsatisfiability to check if a given formula $F'$ is "symmetric" as described above. Something like:

boolean checkSymmetryWithCheckUnsatisfiability (Formula F) {

    /* The checkSymmetry problem is reduced to the checkUnsatisfiability problem to which I have a solution. */
    boolean result = cleverUseOfCheckUnsatisfiability(F);

    // result is true if Formula F is "symmetric", otherwise false
    return result;
}

All right, so there is no way to reduce checkUnsatisfiability to checkSymmetry since that would mean reducing an NP-Complete to an easy one which is impossible unless $P = NP$, thanks to @xavierm02 and especially @chi for clarifying this.

Since checkSymmetry is easy and checkUnsatisfiability is hard It should be possible to reduce checkSymmetry to checkUnsatisfiability in polynomial time, is that correct? If so, how would I do that?


texts: What's the difference between dynamic and static pipelines?

texts:
I was trying to understand what a reservation table is in the context of pipelining, when I found this reference here, where the author mentions that there are static and dynamic pipelines. According to him/her,

  There are two types of pipelines: static and dynamic. A static pipeline can perform only one function at a time, whereas a dynamic pipeline can perform more than one function at a time. A pipeline reservation table shows when stages of a pipeline are in use for a particular function.

This definition sounds confusing to me: is "function" a synonym for "operation" in this case? So, a static pipeline can only process a batch of instructions that use the same operator? Like if the pipeline had to be "rewired" every time a new operator is issued? It makes no sense to me.

In order to get lost a bit more, I resorted to Wikipedia which states that

  A linear pipeline processor is a series of processing stages and memory access. A non linear pipelining (also called dynamic pipeline) can be configured to perform various functions at different times. In a dynamic pipeline there is also feed forward or feedback connection. Non-linear pipeline also allows very long instruction words.

So, static pipelines are linear, dynamic ones are non-linear and functions are indeed a synonym for operations in this context? And, finally, are static pipelines really reconfigured every time a new function is processed?


texts: NFA state complexity for the complement of EPAL restricted to a fixed length

texts:
I've been having trouble proving the next statement:

  Let $L_n=\{ww, |w|=n\}$ (the set of equal-length palindromes (EPAL) restricted to length $2n$). Prove that $L^c_n$ can be accepted by an NFA with at most $O(n^2)$ states.

What I've been trying to do is that the complement of $L_n$ is

$\qquad\displaystyle L^c_n = \{w , |w| \not = 2n\} \cup \{ww', w \not = w'\}$.

I want a hint on what to think to prove this thanks!


texts: What untyped term inhabits induction on natural numbers in CoC?

texts:
Induction on Church-encoded natural numbers (which I will call indNat) can not be defined within the Calculus of Constructions.

If we assumed indNat as an axiom, is there an untyped term that would have the semantics of the induction function? What if we had Scott-encoded natural numbers and fix?

Can induction be inhabited in CoC + fix (such that the function would have the proper semantics, not an infinite loop)?


texts: Polynomially Equivalent Pairs of Minimization-Maximization Problems in Weighted Graphs

texts:
I am studying computational complexity using Papadimitrious's book: "Computational Complexity". I am trying to solve Problem 9.5.14, about polynomially equivalent minimization-maximization problems in weighted graphs:

Consider the following pairs of minimization-maximization problems in weighted graphs:
(a) - MINIMUM SPANNING TREE and MAXIMUM SPANNING TREE (we seek the heaviest connecting tree).
(b) - SHORTEST PATH (recall Problem 1.4.15) and LONGEST PATH (we seek the longest path with no repeating nodes; this is sometimes called the TAXICAB RIPOFF problem).
(c) - MIN CUT between $s$ and $t$, and MAX CUT between $s$ and $t$.
(d) - MAX WEIGHT COMPLETE MATCHING (in a bipartite graph with edge weights), and MIN WEIGHT COMPLETE MATCHING.
(e) - TSP, and the version in which the longest tour must be found.
Which of these pairs are polynomially equivalent and which are not? Why?

Let's denote an edge $e \in E$ that connects vertex $u$ and $v$ and has weight $w_e$ as $e = (u, v, w_e)$. Let $M = max(|w_e|) + 1$. I was able to solve some of them by using the following reduction: given a graph $G = (V, E)$ construct the graph $G' = (V, E')$ where you construct the set $E'$ as follows: for each edge $e = (u, v, w_e) \in E$ add the edge $e' = (u, v, M - w_e)$ to $E'$. For some of the mentioned problems, the minimization version in graph $G$ is equivalent to the maximization version in graph $G'$.
I was able to solve itens (a), (d) and (e) using this trick. I am not sure if this trick applies to (c), and I think it does not work for (b).
Can anyone tell me if my attempt at itens (a), (d) and (e) are correct? Also, how do I solve itens (b) and (c)? Thanks in advance.


texts: Using the pumping lemma for a proof by contradiction

texts:
I'm trying to prove that the set of even-length strings with the two middle symbols being equal cannot be accepted by finite automata.  I can explain why it cannot be accepted intuitively, but I'm having trouble with the proof.  Our symbols are {a, b}.

I allowed L = $\{(ab)^{*{\frac{n}{2} - 1}} aa (ab)^{*{\frac{n}{2} - 1}}\}$.  I know the format of the language is wonky, and will be talking to my professor about it tomorrow.  For the proof, I allowed $\frac{n}{2} - 1$ to be the combination of symbols before and after the two elements.  So, using the Pumping Lemma's condition that |uv|≤ n, I allowed $u = \frac{n}{2} -1$  and $v = n^2$ (for aa); this is obviously greater than n, but I'm having trouble understanding how to choose $u$ and $v$.  Is my assignment for these parameters correct?


texts: Is there a limit on transition function compositions in NFAs?

texts:
I want to prove regularity of a language that contains a known regular language $L$ using an NFA.

Say the transition function of the automation that accepts $L$ is $f$.

In my new transition function, is there a limitation on composition of $f$?
For example, can I make the following transition in the new function?

$$f'(q_i ,\sigma)=f(f(f(q_i, \sigma))))$$

If not, why?


texts: Is Math a MUST in computer science specificly in Software Development for Web servers

texts:
I know math is necessary for application development in simulation software and else.

But I'm learning Python and trying to go deep in PHP, and like to develop applications and extends web servers' capability.

I'm before a big dilemma that whether to learn math professionally or not. I have tried my best to avoid being general on my question.

I have asked this question here because I want to learn it from roots and deal with its scientific aspects.


texts: How to properly solve this Hidden Markov Model problem?

texts:
I got a an exercise problem which should be seen as a HMM scenario and argument some statements. However I'm quite confused about how to properly solve and argument my solutions.

Problem tells:

Imagine you want to determine the annual temperature centuries of years ago, when of course there wasn't any thermometer or records. So, nature as an evidence is a worth to try resource, we may achieve it by watching at tree's inside rings. There's reliable evidence suggesting that there's a relation among the rings inside trees and temperature.
There will be 2 different temperature states, WARM (W) and COLD (C) and three discretized tree rings sizes: SMALL (S), MEDIUM (M) and LARGE (L).
Some researchers have provided two matrixes:

$\begin{bmatrix}.7 & .3\\.4 & .6\end{bmatrix}$

As transition matrix, so the probability of remaining in COLD state if COLD is present is $.6$ and the probability of passing from COLD to WARM is $.7$.

Also, a second matrix with the relation among the ring's size and the temperature over the year:

$\begin{bmatrix}.1 & .4 & .5\\.7 & .2 & .1\end{bmatrix}$

So, problem asks what I should do to calculate the chance of a sequence (for example):

  SSSMMLLL

To happen. I considered multiplying the 4 distinct cases and so generate a Markov matrix with transitions among trees ring sizes. However I never got a matrix whose rows sum 1 as it should.

How could I solve this?


texts: Minimal Spanning Tree With Double Weight Parameters

texts:
Consider a graph $G(V,E)$. Each edge $e$ has two weights $A_e$ and $B_e$. Find a spanning tree that minimizes the product $\left(\sum_{e \in T}{A_e}\right)\left(\sum_{e \in T}{B_e}\right)$. The algorithm should run in polynomial time with respect to $|V|, |E|$.

I find it difficult to adapt any of the traditional algorithms on spanning trees(Kruskal, Prim, Edge-Deletion). How to solve it? Any hints?


texts:
From http://www.seas.gwu.edu/~rhyspj/spring09cs145/lab8/lab82.html

The lambda operator does not bind every occurrence of its variable because "shadowing" can occur. A variable is bound by its nearest enclosing lambda.
In $(\lambda (x) ((y\,\, x) (\lambda (x) (x\,\, y))))$, the $x$ in $(y\,\, x)$ is bound by the outermost lambda, whereas the $x$ in $(x\,\, y)$ is bound by the inner lambda. In this example, both occurrences of $y$ are free.

How shall I understand the lambda expression $(\lambda (x) ((y\,\, x) (\lambda (x) (x\,\, y))))$?

I wonder if the $x$ in $(y\,\, x)$ and the $x$ in $(x\,\, y)$ are the same
or different variables?
If I rename one of them,  will the renamed version be the same as
$(\lambda (x) ((y\,\, x) (\lambda (x) (x\,\, y))))$? E.g.

Is $(\lambda (x) ((y\,\, x) (\lambda (z) (z\,\, y))))$ the same as $(\lambda (x) ((y\,\, x) (\lambda (x) (x\,\, y))))$?
Is $(\lambda (z) ((y\,\, z) (\lambda (x) (x\,\, y))))$ the same as $(\lambda (x) ((y\,\, x) (\lambda (x) (x\,\, y))))$?

Do the two occurrences of $y$ mean the same variable?


texts: Use of Mizar for algorithm specification and automatic analysis and discovery of algorithms?

texts:
Is it possible to use Mizar Mathematical Library for the specification of algorithms at the same detalization level as the implementation of the algorithm in industrial programming language? Mizar should be able to describe constructive proofs in maths and therefore I guess Mizar should be able to specify algorithms as well..

If algorithm is formally specified then one should be able to do automatic analysis - e.g. of running time or space requirements. Halting problem is undecidable but there should be some classes of algorithms for which one can decide/automatically prove the termination conditions. Is that possible?

If algorithms can be formally specified as one formula then one should be able to do automatic search and discovery of such algorithms - something similar like automatic theorem discovery.

Is this possible and are the ongoing work about this? Maybe deep in Mizar community?

I am aware of only one work in the field of automatic algorithm construction http://www.graco.c.u-tokyo.ac.jp/labs/morihata/paper/morihata_phd.pdf and it is more connected with the optimization and parallelization of already existing algorithms and witout use of Mizar.


texts:
Stephen Cook presented his seminal paper "The complexity of theorem-proving procedures" at the 1971 STOC (Symposium on Theory of Computing) conference which was held May 3-5, 1971 at Case Western. How rapidly was this recognized as being revolutionary? The book "Computers and Intractability: A Guide to the Theory of NP-Completeness" by Garey and Johnson, published in 1979, begins with the lines

Few technical terms have gained such rapid notoriety as the appelation
"NP-complete." In the short time since its introduction in the early
1970's, this term has come to symbolize the abyss of inherent
intractability that algorithm designers increasingly face as they seek
to solve larger and more complex problems.

This suggests that it was rapidly recognized as being revolutionary. Furthermore, the Wikipedia article on NP-completeness contains the following tidbit:

The concept of NP-completeness was introduced in 1971 (see Cook–Levin
theorem), though the term NP-complete was introduced later. At the
1971 STOC conference, there was a fierce debate between the computer
scientists about whether NP-complete problems could be solved in
polynomial time on a deterministic Turing machine. John Hopcroft
brought everyone at the conference to a consensus that the question of
whether NP-complete problems are solvable in polynomial time should be
put off to be solved at some later date, since nobody had any formal
proofs for their claims one way or the other. This is known as "the
question of whether P=NP".

Unfortunately, there is no reference given in the Wikipedia article, and I have been unable to find any discussion (beyond that) of the conference itself. For example, Cook's Turing Award Lecture, which would be a natural place for reminiscences, contains no such discussion.
Does anyone know of any references which discuss the 1971 STOC conference in detail? I am mostly interested in the "fierce debate" that the Wikipedia article mentions, although an actual conference program which gives the exact date of Cook's talk would also be interesting. It would be fun to mention it in class next week.


texts:
I've got the following theoretical problem which puzzles me a bit:

I can obtain a string of n bytes (as octets, one byte = one octet = eight bits) of random data. I need to preserve the randomness while reducing the base from 256 to x where x is below 256 (and not 0, 1, 2, 4, 8, 16, 32, 64 or 128).

As I want to preserve the randomness, I don't want to cut-off (waste) any information from this string until I've obtained the number of chunks I need. This is for reason of randomness which can be a limited resource on the computer.

I had the idea to do this for base64 which is simple because I can just create 4 numbers out of a single byte (by shifting bits for example: encode64()). But how to do with a base like 254 for example? I can not cut off at bit-boundaries here, can I?

Do I probably need to create a number large enough out of base 2 based bits that can contain both bases? (This is one of the ideas I have so far).

Would be great to get some feedback, I normally paint pictures with such problems, however, just discovered this website here yesterday and I normally use Stackoverflow so I thought I give it a try :D

If you're interested in some non-theoretical background to my question, see "What is the meaning of the term “simple string” for the SALT string in Unix crypt using SHA-256 and SHA-512?", you might get an idea why I don't want to loose any information bits from the random source.


texts: Nash equilibria in 3-player game with symmetry

texts:
Consider 3-player game.

Players $x,y,z$, each player has two strategies. $x$: $x_1$ and $x_2$, $y$: $y_1$ and $y_2$, $z:z_1$ and $z_2$.

The outcome of the game are represented by the labels of the player who has playoff $1$, otherwise outcome is $0$.

The best way to represent the game is to depict two tables, the first one for the case when $c$ plays $c_1$ and the second one when $c$ plays $c_1$

$c$ plays $c_1$

╔════╦════╦═════╗
║ c1 ║ b1 ║ b2  ║
╠════╬════╬═════╣
║ a1 ║    ║ B   ║
║ a2 ║ A  ║ A;C ║
╚════╩════╩═════╝

$c$ plays $c_2$

╔════╦═════╦═════╗
║ c2 ║ b1  ║ b2  ║
╠════╬═════╬═════╣
║ a1 ║ C   ║ A;B ║
║ a2 ║ B;C ║     ║
╚════╩═════╩═════╝

The problem is to find all Nash equilibria (pure and mixed) and to show that there is no other Nash equilibria.

pure NE: There are three pure Nash equilibria $(x_2,y_2,z_1), (x_1,y_2,z_2), (x_2,y_1,z_2)$ (this is all I found, may be there is more).

mixed NE:Let's place equalities for mixed strategies. Assume that $p_x$ - the probability that $x$ will play $x_1$, therefore $(1-p_x)$- the probability that $x$ will play $x_2$ in the same manner define $p_y$ and $p_z$.

For $x$ to be indifferent between $x_1$ and $x_2$ - $(1-p_y)(1-p_z) = p_y \cdot p_z + (1-p_y)p_z$,

For $y$ to be indifferent between $y_1$ and $y_2$ - $(1-p_x)(1-p_z) = p_x \cdot p_z + p_x(1-p_z)$,

For $z$ to be indifferent between $z_1$ and $z_2$ - $(1-p_x)(1-p_y) = p_x \cdot p_y + (1-p_x)p_y$.

Apparently there is a symmetry, however it's not a symmetric game.

The main problem is how to proceed from this point. There are might be few cases either given one of the equalities we should consider only pure strategies of the rest two players or consider more complicated way when the rest two players play mixed strategies. May be because of the pattern we have symmetric solution? One more problem how to show that there are no other Nash equilibria.

Another approach: Let represent outcome in terms of vectors.

╔════════╦═════════╦═════════╗
║ number ║ outcome ║ winners ║
╠════════╬═════════╬═════════╣
║      0 ║     000 ║ -       ║
║      1 ║     001 ║ C       ║
║      2 ║     010 ║ B       ║
║      3 ║     011 ║ A,B     ║
║      4 ║     100 ║ A       ║
║      5 ║     101 ║ B,C     ║
║      6 ║     110 ║ A,C     ║
║      7 ║     111 ║ -       ║
╚════════╩═════════╩═════════╝

It looks like every player have exactly the same chances to win, every player has three permutations  that leads to payoff 1. $A=\{3,4,6\}, B=\{2,3,5\}, C=\{1,5,6\}$, among them the following outcomes appear twice $(3) 011, (5), 101 (6) 110$.

The problem is I don't know how to approach the solution, I would appreciate for ideas.


texts:
Do anyone have any idea how to solve this recurrence?$$T(k) = \sum_{i=1}^{k/2} {k \choose i}T(i)T(k-i)$$

I am working with this kind of recurrence for the first time and don't have much idea of how to proceed. But, for beginning I was trying to guess the solution and use substitution method. But, in the guessing part itself I am stuck. It seems like the solution should be exponential to $k$.


texts: Does every DAG have at most one "universal source"?

texts:
A "universal source" in a directed graph is a vertex v for which out-deg(v)=n-1 and in-deg(v)=0.
I know that any DAG has at least one source but can it have more than one for a universal?
I know there can be none, and there can be one (binary tree for example, root is universal source) but can there be two?


texts: Is the optimal order of graph vertices s.t. minimizes edges to later vertices a well-known problem?

texts:
I'm a little unfamiliar with graph theory, and I found an interesting problem in my work that I do not know if its already well-known or can be easily mapped to another one. If I were to express the problem more formally:

Given a directed unweighted graph $\langle V,E \rangle$, find a total order between vertices $v_1 < v_2 < \dots < v_n$ such that minimizes $\vert F \vert$, where $F = \{ \langle v_i,v_j \rangle \ \vert\ v_i < v_j , \langle v_i,v_j \rangle \in E \}$. That is find a total order between vertices such that it minimizes the number of edges that go "forward" in the order.

Lets suppose a simple directed graph:

The list of edges would be $[ a \rightarrow b $, $b \rightarrow c$, $a \rightarrow c ]$.

A bad order would be  $b < a < c$, because, for example, $c$ comes after $b$ in the order and we have the edge $b \rightarrow c $. Therefore, $F = \{ \langle b,c \rangle , \langle a,c \rangle \}$, $\vert F\vert = 2$.

A good order would be $c < b < a$, because $b < a$ and $c < b$. This gives $F = \emptyset$ and therefore the optimum: $\vert F\vert = 0$.

I have graphs that are dense, with some strongly connected components, and when trying to solve it using a SMT solver it works really bad with non-trivial instances. My intuition says that it's like a pigeonhole problem. So, my questions are:

Is this a well-known problem in the graph-theory community?
Can be easily mapped to any other problem?
If so, there is any good algorithm to solve it?
Can a good heuristic be computed easily?

Many thanks in advance :)


texts: how to solve recurrence T(n) = 2T(n/2)+n using substitution method

texts:
The required solution is given. I have to prove that its solution is $O(n\log n)$.

My idea is shown below:

I have to prove, $T(n) \le cn\log n$ for some constant $c$
$$\begin{align}
T(n) &\le 2c\log(n/2) + n\\
     &= 2c\log(n) - 2c\log(2) + n\\
     &= 2c\log(n) - 2c + n\\
     &= c\log(n) + ( c\log(n) - 2c + n )\\
     &\le c\log(n)
\end{align}$$
it will be true if $( c\log(n) - 2c + n ) \ge 0$.

Is my procedure is correct?

If no, can anyone tell me how I can solve this problem with appropriate value of $c$ and $n$?

If yes, then how I can find out appropriate value of c and n using this relation clog(n) - 2c + n ) >= 0.


texts: Why addition algorithm is not pseudo- polynomial?

texts:
There is something I don't understand.

In the Subset Sum problem, in the Dynamic Programming solution, because of  binary representation of the sum T, we say it is pseudo-polynomial in run time; we must sum in the worst case from 1 to T.

So I don't understand why the Addition algorithm is not pseudo-polynomial, when we can add great numbers too.


texts: How to evaluate all derivatives of a polynomial at a point with FFT?

texts:
I found this problem:

  Evaluating all derivatives of a polynomial at a point

  Given a polynomial A(x) of degree-bound n, its tth derivative is
  defined by

  From the coefficient representation $(a_0, a_1, . . . , a_{n-1})$ of A(x) and
  a given point $x_0$, we wish to determine A(t) ($x_0$) for t = 0, 1, . . . ,
  n - 1.

I know the vector of the coefficients has to be used and I also know that the derivative of a term $ax^n$ is $a*n*x^{n-1}$, but where do I go from there?

I can only think of the naïve scheme to evaluate this: Find the first derivative ($O(n)$), evaluate it using Horner's method ($O(n)$). Repeat this for all deterivaties, giving $(O(n^2)$).


texts: About NOP (NO Operation) for LC-3 instructions

texts:
0000 111 000011000
Will this instruction fail as a NOP? I think it is because it branches PC to a new address (incremented PC + 0x0018). If it were a branch that branches PC to itself like 0000 111 000000000, then this will work as a NOP though.
Am I correct in understanding this?


texts: Checking my understanding of right quotient

texts:
So I am trying to fully understand the concept of quotient languages.

I will give some examples, let me know if this is correct:
Say that

L1={} and L2 is {ot}, then L1/L2 is {carr}
Or if L1=ab*c and L2 is b*c then L1/L2 is a.

If this is it, I will then try to approach more complex concepts :)
Thank you!


texts: Codes for correcting a single deletion and re-ranking of a permutation

texts:
I was struggling with this paper about codes which can correct single deletion and re-ranking in permutations, http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=6875337

[Published in:
Information Theory (ISIT), 2014 IEEE International Symposium on
Date of Conference:
June 29 2014-July 4 2014, Page(s):
    2764 - 2768
INSPEC Accession Number:
    14515064, Conference Location :
    Honolulu, HI
DOI:
    10.1109/ISIT.2014.6875337
Publisher:
    IEEE]

I wonder if there is a longer and more explained version of Theorem 2 in this paper.
Or is there any other paper which explains this better?

The "Theorem 2" at the end is extremely difficult to follow!

For example at the top of the second column in page 5 even the authors state things like "it is straightforward (but tedious) to see that the set of possible values for x is exactly $\{u,u+1,..,v+1\}$".

Can someone help understand this?
Many of the things towards the end were not easy to follow : like why is $\{\sigma_i,..,\sigma_j\}$ an increasing run of $\sigma$ and why is $\{p,p+1,..,q\}$ an increasing sub-sequence of $\sigma$.

The above is not looking obvious from the initial definition :

In the beginning the $i$ and $j$ were defined such that from position $i$ to $j$ in the "signature" vector of the permutation $\pi$ is a sequence of $1$s. And $p$ and $q$ were initially defined such that from the position $p$ to $q$ is a sequence of $1$s in the signature vector of the permutation $\pi^{-1}$. And $\sigma$ is a permutation obtained from $\pi$ after a single deletion and re-ranking.


texts: Why discriminate the base case allows me to complete the induction proof?

texts:
I have a successful completed proof which used induction. but I essentially proved the goal on the base case by tactic discriminate.  Why is this induction proof still stands?
the principle of induction tells us induction involves three steps:
     - show that the P(O) holds, (* O stands for the first item *);
     - show that, for any n, if P(n) holds, then so does
       P(next(n));
     - conclude that P(n) holds for all n.

but if I finished proving subgoal P(O) by discriminate, that is, confirmed the subgoal is impossible, how does that constitue as a holding base case?
Here's the proof in question:
Fixpoint filter {X:Type} (test: X->bool) (l:list X) : (list X) :=
  match l with
  | [] => []
  | h :: t =>
    if test h then h :: (filter test t)
    else filter test t
  end.

Theorem filter_property : forall (X : Type) (test : X -> bool) (x : X) (l lf : list X),
filter test l = x :: lf -> test x = true.
Proof.
induction l.
- intros. discriminate.
- simpl. destruct (test x0) eqn:Etest.
 + intros. injection H. intros. rewrite -> H1 in Etest. apply Etestx.
 + apply IHl.
Qed.


texts: Determine if an NFA accepts infinite language in polynomial time

texts:
Question Statement: Given a NFA $N$, design an algorithm that runs in polynomial time such that it determines if $L(N)$ is infinite.
(Note that converting NFA to DFA is exponential time).

For any DFA, By pumping lemma, I am very sure that the following algorithm works:

T = Upon input <M> (a DFA)
  Accept if any state q in DFA has the property:
    1. There is a path from starting state to some final state through q
    2. There is a (directed) cycle that loops from q back to q.
  (Reject if neither property is satisfied)

I intend to prove that this algorithm can be directly applied to NFA. After all, if there is no loop in this NFA, then every accepted string is bounded by the number of states (by pumping lemma). Therefore to make sure the NFA accepts infinite language, a loop is necessary.

Is the thinking correct? Further, what would be the optimal algorithm to see if an NFA generates infinite language?


texts: Number of ways of making change in Big O notation

texts:
I have the following algorithm in ML:

fun change(till,0,chg,chgs) = chg::chgs
|   change([],amt,chg,chgs) = chgs
|   change(c::till,amt,chg,chgs) = if amt<0 then chgs else change(c::till, amt-c,c::chg, change(till,amt,chg,chgs));

The algorithm takes a list of currency denominations as till and returns all the combinations of denominations which produce the amount amt specified.

And I am trying to show that the number of ways for making change for some value n regardless of order with two change values is O(n). And then trying to figure out what it is for more change values.

It's clear that for one change value it is O(1) as there is only one possible way to make change but I'm not sure how to progress from there.

Any help would be much appreciated.


texts: In what ways can we distinguish between a human and bot behavior?

texts:
Updated based on comments:

In what ways can we distinguish a human being doing certain activities online and a bot programmed to do similar activities, say checking email, downloading some music files, shopping on ebay, searching on Google etc., or maybe trying to deface/hack a website, brute force a log-in password etc.

To limit the scope of the question and make it more clear, let us restrict our observations only to network-oriented behavior, some examples being- the amount of time spent doing XYZ thing online, the amount/type of data downloaded (say) from a file sharing website, the number of friends/followers on Social media websites, etc.

I guess it should possible to obtain some 'patterns' which will distinguish human behavior and programmed behavior.

The Turing test is not what I am looking for.

What techniques can be useful here? Machine learning? Game theory?

References to relevant academic/research articles will also be good.


texts: What is pass-by-value-result and its advantage and disadvantage?

texts:
I have searched on Google, but I can't quite understand what is pass-by-value-result. What is the advantage and disadvantage of using pass-by-value-result?

If I have a program code like this, what will be the result when parameters are passed by value-result?

#include <stdio.h>

int a=2;
int b=1;

void fun(int x, int y) {
    b=x+y;
    x=a+y;
    y=b+x;
}

void main() {
    fun(b,b);
    printf("%d %d\n",a,b);
}


texts: Brute force method to solve the 0-1 knapsack problem

texts:
I know that the brute force method is not the best way to solve the 0-1 knapsack problem. I'm not quite getting the dynamic programming idea, but would like to know the following:

If the brute force method can solve the problem with 20 items in 1 second - how many items can it solve in one day (2^16 s)?

I know that the time complexity of brute force is big O(2^n). But still I don't see how I can solve this.


texts: Do not understand a lemma regarding dinics algorithm

texts:
Here you can find the following lemma with its proof.

Lemma: In a network with unit edge capacities,
Dinitz algorithm terminates after $O(\sqrt{m})$
blocking flow computations.

Proof:
Consider the layered network after $\sqrt{m}$ iterations.
It has at most m edges. The average number of
edges between any two layers is $\frac{m}{\sqrt{m}} = \sqrt{m}$.
Hence, there must be at least one layer $i$ with
at most $\sqrt{m}$ edges. Now consider the cut
$S=\{v | level_f(v) < i\}$. It has capacity at most $\sqrt{m}$.
Since each blocking flow augmentation increases flow
by at least one, after $\sqrt{m}$ additional blocking
flow augmentations,  a maximum flow has been found.
Hence, no more than 2$\sqrt{m}$ = $O(\sqrt{m})$
blocking flow augmentations are needed.

I don't understand the proof. The layered graph $G_{L}$ has m edges. But how does it look like after $\sqrt{m}$ iterations? Is the average number of edges of $G_{L}$ between any two layers $\frac{m}{\sqrt{m}} = \sqrt{m}$ after $\sqrt{m}$ iterations? And the confusion continuous with the set $S$.

Could someone unfold this proof for better understanding?


texts: Difference between SRSW and MRSW safe Boolean registers

texts:
I'm reading The Art of Multiprocessor Programming and am currently trying to understand Chapter 4 — The Foundations of Shared Memory.

In section 4.2 it is shown how to build a multi-reader, single-writer (MRSW) safe Boolean register from a single-reader, single-writer (SRSW) safe Boolean register. So, the only difference is that the new register supports multiple readers, but the consistency guarantee (safe) is the same.

The implementation (figure 4.6) uses an array of SRSW safe Boolean registers, with one element for each reader. What I don't understand is why can't we treat a SRSW safe Boolean register as a MRSW safe Boolean register, already?

The definition for the safe consistency level says that a register is safe if:

A read call that does not overlap a write call must return the value written by the most recent write call.
A read call that overlaps a write may return any value within the register's allowed range of values (in the case of a Boolean register, just 0 and 1).

It seems to me that a SRSW safe Boolean register can already be treated like a MRSW safe Boolean register because any number of reads concurrent with a write will return either 0 or 1. Non-overlapping reads are obviously fine.

Is there a nuance I'm missing here or is it just a self-imposed limitation that a SRSW safe Boolean register can't be used with multiple readers, just by the definition? I understand this whole register derivation tower is pretty artificial and used mostly for theoretical considerations, so I'm thinking such an artificial limitation is very possible.


texts:
Is there a path finding algorithm that exploits a directed bipartite graphs' structure?

I found this: Shortest-Path for Weighted Directed Bipartite Graphs but it didn't seem like the OP needed a bipartite graph and the answer reflected that.

I also found this: https://www.degruyter.com/downloadpdf/j/comp.2013.3.issue-4/s13537-013-0110-4/s13537-013-0110-4.pdf
but it's not clear whether the solution is performant and I also don't have a APSP problem.


texts: Maximize area of light with 4 light sources on a diagram of a room

texts:
Given a diagram of a room with obstacles in it (like walls or furniture), find the 4 best places to put omnidirectional light sources in it so the area that is lighted is maximized.
Here is a simple example diagram so the problem can be better understood:

The solution I thought was to find the spot with most light and from there find the second one and so on. But something makes me think that it may exist a configuration which is better that doesn't need to be the best from the beginning, kinda feels like a special case of the knapsack problem, if so I'd think of implementing a greedy algorithm or using genetic algorithms to give an approximation of the best places.
The problem could be viewed as a particular case of "the Art gallery problem" but instead of finding the least amount of guards, you have 4 guards and you have to put them in certain places so they can observe the most area of the gallery possible.
I'd be grateful if at least someone points me in the right direction so I can do a better research, thank you very much!


texts: solving the recurrence t(n)=t(n-2)+d*(n^2)/2 with iteration method

texts:
How can I solve $$T(n)=T(n-2)+\frac {d}{2}n^2$$
I couldnt find $d$ (dont know if I have to) and after 3 iterations I got to $k= \frac{n-1}{2}$
but had trouble to continue.


texts: How to construct a CFG which generates {0, 1, #}⁺ - {b_1#b_2#b_3#… #b_n | n is a whole number} where b_i is i in binary without leading zeros?

texts:
This problem was originally given in "Introduction to Automata Theory, Languages and Computation" by John E. Hopcroft and Jeffrey D. Ullman as Exercise 4.3.

$$ \text {Let }b_i \text{ denote } i \text{ in binary without leading zeros.}$$ We need to construct a CFG which generates the following language: $$
\{0, 1, 2\}⁺ - \{b_12b_22...2b_n | \text{n is a whole number}\} \text{.}
$$

Firstly, I considered implementing such non-terminal
$$
U \mid \forall \text{whole n}. S \Rightarrow^+ U \Rightarrow^+ b_12b_22...2b_n\text{.}
$$
I believe that even if this could be done, it would have a fairly cumbersome structure:
$$
\{b_12b_22...2b_n | \text{n is a whole number}\}
$$
does not satisfy the Pumping lemma, therefore, is not a CFL. For the same reason, I can't see any way to apply any neat theorems like $$CFL - RL = CFL\text{.}$$

How could one construct such a grammar? I would really appreciate some hints, which could help me solve the problem, instead of a complete solution.


texts: Given asymptotic bounds, what can we say about small n?

texts: I am trying to wrap my head around these asymptotic notations. Given $f(n)$ and $g(n)$, one can write $f(n) = \Omega(g(n))$ as shorthand for $f(n) \geq c*g(n), n\geq n_0$. But what happens when $n<n_0$. What can we then say about $f(n)$ and $g(n)$? Do we just assume that $f(n)$ is a constant and the relation still works? Or does the question not even make sense to ask?


texts:
Let $f$ be a fixed time-constructable function.
The classical universal simulation result for TMs (Hennie and Stearns, 1966) states that there is a two-tape TM $U$ such that given

the description of a TM $\langle M \rangle$, and
an input string $x$,

runs for $g(|x|)$ steps and returns $M$'s answer on $x$. And $g$ can be taken to be any function in $\omega(f(n)\lg f(n))$.
My questions are:

What is the best known simulation result on a single tape TM? Does the result above also still hold?

Is there any improvement on [HS66]? Can we simulate TMs on a two-tape TM for $f(n)$ steps in a faster way?
Can we take $g(n)$ to be in $\omega(f(n))$ in place of $\omega(f(n)\lg f(n))$?


texts:
I always read that finding an independent set of size $k$ in a graph is $\mathsf{NP}$-complete. However, this only requires looking for all combinations of $k$ vertices and this is a polynomial procedure of order $k$.

I know that we can reduce directly SAT to independent set, with $k$ the number of clauses.

The problem is that I can't grasp correctly, as in 3-COLORING or 3-SAT, the required format to study the complexity of INDEPENDENT SET.

What is the decision version of independent set? And why isn't $k$-independent set in $\mathsf P$?


texts: implementing permutation and combination recursively

texts:
I am still in the early phase of getting comfortable with solving recursive problems. I was given
int p(int n) // number of permutations of n objects
int c(int n, int k) // number of unique combinations of k elements out of n elemnts

For instance, {"abc"} as the given string, permutation will be
{"abc"}, {"acb"}, {"bac"}, {"bca"}, {"cab"}, {"cba"}. However, combination (order does not matter) will be just simply {"abc"}.

A detail representation of Combination by using Pascal's Triangle from Eric Roberts' book.

I am having a hard time seeing how this pascal's triangle representation relate to the idea of combination.

My initial thought process was based on each of their formulae and using factorial to solve the problem. Clearly, that's not what I was asked to do. I was supposed to define them recursively and implement the recursive definitions for both counting techniques. So, basically, I am unable to solve the two functions without getting the help of factorial.


texts: Do Turing machines assume something infinite at some point?

texts:
In a previous question What exactly is an algorithm?, I asked whether having an "algorithm" that returns the value of a function based on an array of precomputed values was an algorithm.

One of the answers that caught my attention was this one:

  The factorial example gets into a different model of computation,
  called non-uniform computation. A Turing Machine is an example of a
  uniform model of computation: It has a single, finite description, and
  works for inputs of arbitrarily large size. In other words, there
  exists a TM that solves the problem for all input sizes.

  Now, we could instead consider computation as follows: For each input
  size, there exists a TM (or some other computational device) that
  solves the problem. This is a very different question. Notice that a
  single TM cannot store the factorial of every single integer, since
  the TM has a finite description. However, we can make a TM (or a
  program in C) that stores the factorials of all numbers below 1000.
  Then, we can make a program that stores the factorials of all numbers
  between 1000 and 10000. And so on.

Doesn't every TM actually assume some way to deal with infinity? I mean, even a TM with a finite description that computers the factorial of any number N through the algorithm

 int fact(int n)
 {
 int r = 1;
 for(int i=2;i<=n;i++)
 r = r*i;
 return r;
 }

contains the assumption that a TM has the "hardware" to compare numbers of arbitrary size through the "<=" comparator, and also ADDers to increment i up to an arbitrary number, moreover, the capability of representing numbers of arbitrary size.

Am I missing something? Why is the approach that I presented in my other question less feasible with respect to infinity than this one?


texts:
When one "downloads" a language (say, downloading the python file, or doing apt-get ruby or something), is it always the compiler/interpreter you are downloading?

In other words, does a "language" ever exist outside of its syntax and behavioral descriptions?

Perhaps standard libraries can be written in the language itself -- but other than that, would it be correct to say that we ever only "download" implementations of the language?


texts:
Have a question that requires me to write the rules for parsing a turing machine

This is the question

The PROBLEM involves writing a set of Turing Machine rules that will read and determine whether or not an input corresponds to the rules of a Turing Machine. This is the ﬁrst step of a Universal Turing Machine. For example, if the input is a legal set of rules, then the machine shall accept this input (and any other legal input that describes a Turing Machine).

The input would be
IO = current state with the number of  I's indicating what state
I = would be the current symbol being true with O being false
IIO  = next state
I = next symbol with O being false
I or O = direction with I being left and O being right

so a legal input would be

IOOIIOOI     which would be state 1 = current state false = next state 2 = next state false = left

How would I write the rule so that if I ran it through and it detected that the rules did not conform to the legal input it would place II at the beginning of the input and if its correct put OO at the beginning.


texts: Does O(1) communication complexity imply that a language is regular?

texts:
Let's say that we have a function $g(i,j)$, which is an arbitrary boolean-valued function over $i,j \in \{a,b\}^*$, such that $|i| = |j| = m.$ Moreover, we can also say that $g$ has communication complexity $c(m),$ and we let $L = \{ij \mid g(i,j) = 1\}.$
Would it be accurate to say that if $c(m) = O(1),$ then $L$ is regular? I'm not entirely sure that this is the case. I've been trying to think about counterexamples to this statement, but I can't really think of any. I do know that the converse is true, namely that if $L$ is regular, then $c(m) = O(1)$. I've been racking my brain over this in the past few days. Any ideas?


texts: Where does the assembler live inside a CPU? If, it indeed does?

texts:
Where does the assembler live in the system? I understand that assembly language gets converted to machine code (binary) and that the processor then follows these instructions.

Where does the assembler live? Does it live in some kind of Read Only memory?


texts:
Suppose we have a set $S = \{(a_1,b_1),...,(a_n,b_n)\}$ where $a_i < m$, $b_i = m-a_i$, $m \in \mathbb{Z}^{+}$, $m>2$ and $n$ is an even number greater than $3$. What is the most efficient algorithm to determine if it is possible to partition $S$ into two distinct subsets, $C$ and $D$, of equal size such that

$\sum_{a \in C} a > \sum_{b \in C} b$   and   $\sum_{a \in D} a > \sum_{b \in D} b$

or  $\sum_{b \in C} b > \sum_{a \in C} a$  and  $\sum_{b \in D} b > \sum_{a \in D} a$  ?

For example, if $S = \{(56,44),(48,52),(43,57),(60,40)\}$, $C = \{(56,44),(48,52)\}$, and $D = \{(43,57),(60,40)\}$.

I am considering iteratively matching a pair with the best value of $a$ with a pair with the worst value of $a$. Is there another algorithm?


texts: Could an alternating approach yield a fairer solution to the stable marriage problem?

texts:
With the G-S algorithm solution to the stable marriage problem, the proposers get the best possible stable matches, while the reviewers get the worst possible stable matches. This is because the proposers keep walking down the list from their best preference downwards till the stable solution is found, while the reviewers walk up the list from where they start.

To improve the fairness to both parties, consider an alternating variant of the algorithm, where in each cycle, proposers and reviewers exchange roles (for example, in each cycle, men and women switch between the role of proposer and reviewer). Would this terminate with a stable match? If yes, would the resulting stable match be fairer to both parties than the original G-S algorithm?


texts: Why doesn't diagonalization require taking a limit?

texts:
When we quantify infinite sums, we do so by taking the limit as $i$ goes to infinity. For example, we look at $\lim_{n\rightarrow \infty}\sum_{n\in \mathbb{N}}n$, and then we say that this diverges and does not have a sum.
When we do diagonalization, we iterate over an infinite list while indexing each list item by a natural number, and then talk about the result. Why can we do this instead of having to invoke limits?
In the same way, would it be fine to assign a value to $\sum_{n\in \mathbb{N}}n$ with the value being an infinite sequence?


texts: Efficient algorithms for finding a region in $\mathbf R^2$

texts:
This question is an extension of a previous question I've asked.

Consider the rectangle $a<x<b , c<y<d$ in the $\mathbf R^2$ plane. Each point in this rectangle can be of kind #1 or #2 (We have to check each point to know its kind).

Assume that somehow we know that the points of kind 1 (and so the points of kind 2) form a connected region (i.e. , 1s and 2s are not scattered in the plane arbitrarily). Given the condition of being of kind 1 or 2, The goal is to find the region occupied by 1s (a search problem). Consider somehow we know the following attributes of the region occupied by 1s: (one at a time)

The region occupied by 1s forms a convex set (so it is 1-connected too).

2.The region occupied by 1s forms a simply connected region , but not necessarily convex.

The simplest algorithm for finding the region of 1s is to simply start from bottom of the rectangle and sweep it and check all of the points in the rectangle to determine their kind and this way find the region.This is not an efficient algorithm, because we can use the known fact of convexity (or simply-connectivity) of the region of 1s to find it more easily without inspecting all of the points.

What more efficient algorithms are there to find the region , as fast as possible? (with an acceptable accuracy, which is about 0.001 in my work). The regions may have sharp edges. But their detection is limited to the mentioned accuracy too. (It is clear that finding the boundary of the region suffices)

Please don't forget that the problem is to find an unknown set of points, not bound a known set of points. i.e., it's a search problem , not a convex hull finding problem.

(also, speed is very important for me)

EDIT1:

After some suggestions (in the comments) I should say that I think we can take advantage of simply-connectivity of the region to write an algorithm that tries to find the boundary of the region instead of checking more points to find the region directly.


texts: Given three languages L1 L2 L3 that do not intirsect could one be TR and the other TD and the third neither

texts:
where $L_{1} \cup L_{2} \cup L_{3} = \sum^{*}$ and

$L_{1} \cap L_{2} = \emptyset$ and $L_{2} \cap L_{3} = \emptyset$ and $L_{1} \cap L_{3} = \emptyset$

is it possible that $L_{1}$ is decidable, $L_{2}$ is recognizable but not decidable

and $L_{3}$ is not recognizable?

If so please give an example, if not why?

By recognizable I mean Turing Recognizable.

To make things a little easier (I think!) I have reached a conclusion that it is very much possible, I only can't think of an example of such 3 languages.


texts: About the 'trick' for finding the diameter of an graph in $O(n^2)$

texts:
The diameter of an undirected, unweighted graph can be found in $O(n^3)$ with e.g. the Floyd–Warshall algorithm. However, there is an idea how to improve the runtime:

Pick a vertex $v$
Find $u$ such that $d(v,u)$ is maximum
Find $w$ such that $d(u,w)$ is maximum
Return $d(u,w)$

This idea fails; for instance, when starting at $v$ here:

However, it is not immediately clear to me if we can not amend the above algorithm with another indirection, and also consider all nodes with maximum distance instead of only one. That is:

Pick a vertex $v$
Find the set $U$ such that $u \in U \implies d(v,u)$ is maximum
For each node $u$ in $U$, find the set $W_u$ such that $w \in W \implies d(u,w)$ is maximum
Merge these sets $W_u$ into a new set $W$
Calculate the eccentricity of all nodes in $W$
Return the maximum eccentricity found this way

The improved algorithm works for the above counterexample as well as others (e.g. this one).

I assume it is still wrong. If it were not, it would offer a significant improvement for at least some kinds of graphs. Is there a counterexample? And how could a counterexample for further additional indirections be constructed?


texts: Trying to understand this Quicksort Correctness proof

texts:
This proof is a proof by induction, and goes as follows:

P(n) is the assertion that "Quicksort correctly sorts every input array of length n."

Base case: every input array of length 1 is already sorted (P(1) holds)

Inductive step: fix n => 2. Fix some input array of length n.

Need to show: if P(k) holds for all k < n, then P(n) holds as well

He then draws an array A partitioned around some pivot p. So he draws p, and calls the part of the array that is < p as the 1st part, and the part that is > p is the second part. The length of part 1 = k1, and the length of part 2 is k2. By the correctness proof of the Partition subroutine (proved earlier), the pivot p winds up in the correct position.

By inductive hypothesis: 1st, 2nd parts get sorted correctly by recursive calls. (Using P(K1),P(k2))

So: after recursive calls, entire array is correctly sorted.

QED

My confusion: I have a lot of problem seeing exactly how this proves the correctness of it. So we assume that P(k) does indeed hold for all natural numbers k < n.

Most of the induction proofs I had seen so far go something like: Prove base case, and show that P(n) => P(n+1). They usually also involved some sort of algebraic manipulation. This proof seems very different, and I don't understand how to apply the concept of Induction to it. I can somewhat reason that the correctness of the Partition subroutine is the key. So is the reasoning for its correctness as follows: We know that each recursive call, it will partition the array around a pivot. This pivot will then be in its rightful position.  Then each subarray will be further partitioned around a pivot, and that pivot will then be in its rightful position. This goes on and on until you get an subarray of length 1, which is trivially sorted.

But then we're not assuming that P(k) holds for all k < n....we are actually SHOWING it does (since the Partition subroutine will always place one element in its rightful position.) Are we not assuming that P(k) holds for all k


texts: When does a semaphore issue a wait and when does it issue a signal?

texts:
In my textbook, Operating Systems: Internals and Design Principles (9th Edition) by William Stallings in chapter 5, it explains how semaphores work:

The fundamental principle is this: Two or more processes can cooperate
by means of simple signals, such that a process can be forced to stop at
a specified place until it has received a specific signal. Any complex
coordination requirement can be satisfied by the appropriate structure of
signals. For signaling, special variables called semaphores are used. To
transmit a signal via semaphore s , a process executes the primitive
semSignal (s) . To receive a signal via semaphore s, a process executes
the primitive semWait (s) ; if the corresponding signal has not yet been
transmitted, the process is suspended until the transmission takes
place.

I can't find a description in chapter 5 of when a semaphore would issue a semSignal vs a semWait (which are also sometimes called signal and wait). Can anyone describe the conditions under which semSignal would be issued vs a semWait?


texts: Is my proof for the regularity of the language $A/B$ correct?

texts:
This problem is from Sipser's Theory of Computation 3rd Edition.

1.35 Prove that $A/B = \{\omega \ | \  \omega x \in A \ \mathrm{for\ some \ } x\in B\}$ is regular where $A$ is regular and $B$ is any language.

I want to verify that my proof is correct. It is as follows:
Let $A$ be a regular language. Then it has a DFA $N = (Q, \Sigma, \delta, q_0,  F)$ such that $L(N) = A$. We will construct a DFA $M = (Q, \Sigma, \delta, q_0, F^{\prime})$ that recognizes $A/B$ and only $A/B$.
Let $P = \{p_1, \dots, p_k\} \subseteq Q$ be the set of states of $N$ that have a path to a final state of $N$.  We will construct a DFA corresponding to each of these states.
Let $N_i = (Q, \Sigma, \delta, p_i, F)$ be the DFA identical to $N$ except the start state is $p_i \in P$. This means $L(N_i)$ contains strings $x$ where $\omega x \in A$ and $\delta^*(\omega, q_0) = p_i$.  Now we determine $F^{\prime}$:
$F^{\prime} = \{p_i \in P : \exists x\in L(N_i) \cap B\}$
We will now prove that $L(M) = A/B$.
$(L(M) \subseteq A/B)$:
Let $\omega \in L(M)$. Then by construction we have:
$$
\delta^*(q_0, \omega) = f^{\prime} \in F^{\prime} \\
\Rightarrow f^{\prime} = p_i \in P \ \ \mathrm{and} \ \ \exists x\in B\cap L(N_i) \ \ \mathrm{such \ that} \ \delta^*(p_i, x) = f \in F \\
\Rightarrow \delta^*(q_0, \omega x) = f \in F \\
\Rightarrow \omega x \in A \ \ (\mathrm{we \ also \ know \ } x \in B) \\
\Rightarrow \omega \in A/B
$$
$(A/B \subseteq L(M))$:
Let $\omega \in A/B$. Then $\exists x \in B$ such that $\omega x \in A$. Let $\delta^*(q_0, \omega) = p_i$. ($p_i \in P$ is unique because $N$ is a DFA.) We know $\omega x \in A$ so  $\delta^*(p_i, x) = f \in F$. Therefore $x \in L(N_i)$. We already know $x \in B$ so $x \in B \cap L(N_i)$. Hence $p_i \in F^{\prime}$. We conclude that $\omega \in L(M)$.
We have constructed a DFA that accepts $A/B$ and only $A/B$. Therefore $A/B$ is regular.


texts: Combine abstract factory with decorator pattern

texts:
I'm working on a simple project of software engineering that should combine two patterns.
I choose Abstract Factory and Decorator patterns to modify (dynamically) objects created with the concrete Factory classes.
My question is: is delegating object decorations to those Factory classes a design error?

Here's the UML scheme:


texts: Why algorithms calculating non-tirivial zeros can't be used as proofs of Riemann Hypothesis?

texts:
Recently I was reading again this propositions as types paper by Philip Wadler:

http://homepages.inf.ed.ac.uk/wadler/papers/propositions-as-types/propositions-as-types.pdf

It gives an impression, that programs are proofs. So my first question was that why they are not enough for mathematical proofs then, for example in case of Riemann Hypothesis. Billions of zeros on critical line have been calculated in many many ways. I suppose they use some sophisticated algorithms or computer programs in that sense.

http://mathworld.wolfram.com/pdf/posters/Zeta.pdf

So, I was just stuck there. Why aren't these programs, or proofs in the system of Curry–Howard correspondence, enought?


texts: How to store set of long char strings to search for long char string key

texts: I have a set of several thousand strings of max length 1024 (containing all visible ASCII chars plus space) I need to store to make it fast to search for an exact match of a key.  What is the best algorithm to store the set and to search for a match?


texts:
Question:
Let $A \subseteq $ {0,1}$^* $ be a language which satisfies $|A \cap ${0,1}$^n|=n^3 $ for all $n\ge 10$ Prove that $A \in NP$ implies $A \in coNP$.

Thoughts
I've been having difficulty with this problem. My idea is somehow showing that each set of $n^3$ words cannot be a verifier for A and therefore A is in coNP. The problem is that as I see it, proving this will take exp time as I have an exponential number of options for strings from which to choose n^3 from.  Would like some suggestions about how to prove this.


texts: How can I achieve this. Write a grammar for the language consisting of strings built only of the letters a and b. The strings may have any number of these letters, but the letter combinations bab must be in each string somewhere, and each string must start with a bb. For example, the strings bbababbbaa, bbbaaaababaa, and bbbab are in the language, while a, aabb, baaa, and bbba are not.


texts: that there would be no perfect strategy for poker

texts:
In my opinion, every imperfect information game where there is the possibility of bluffing lacks a perfect (or winning) strategy, for the simple reason that knowing your opponent's strategy will let you beat him easily (even if his strategy isn't 100% deterministic).

So why do the guys that developed 'Cepheus' claim that they made a program playing poker with a perfect strategy, claiming that their AI 'is guaranteed to not lose money in the long run' ?

I'm pretty sure I can create a strategy winning versus Cepheus, because I know its strategy.

Where am I wrong ?


texts: How does a Turing machine compute when its head is at the right-hand end of its configuration?

texts:
I'm reading Sipser's Introduction to the Theory of Computation (2nd ed.), and I am having trouble understanding one of the cases of Turing machine computation. Sipser describes the cases in terms of how one configuration yields another after a step of computation. For example, if the head is not at either end of the configuration and is moving leftward:

  Suppose that we have $a$, $b$, and $c$ in $\Gamma$, as well as $u$ and $v$ in $\Gamma^*$ and states $q_i$ and $q_j$. In that case $uaq_ibv$ and $uq_jacv$ are two configurations. ... $uaq_ibv$ yields $uq_jacv$ if the transition function $\delta(q_i,b)=(q_j,c,L)$.

where $\Gamma$ is the tape alphabet and $L$ means the head is moving leftward.

I understand this case, as well as the case where the head moves rightward without being at either end and the cases where the head is at the left-hand end. However, I don't understand the cases where the head is at the right-hand end. Here's how Sipser explains the end cases:

  Special cases occur when the head is at one of the ends of the configuration. For the left-hand end, the configuration $q_ibv$ yields $q_jcv$ if the transition is left-moving (because we prevent the machine from going off the left-hand end of the tape), and it yields $cq_jv$ for the right-moving transition. For the right-hand end, the configuration $uaq_i$ is equivalent to $uaq_i⌴$ because we assume that blanks follow the part of the tape represented in the configuration. Thus we can handle this case as before, with the head no longer at the right-hand end.

where ⌴ is the blank symbol.

I'm not sure how to handle this case as I don't know where "as before" refers to. I conceptualize the head like a text cursor stuck in overtype mode, and so my initial guess would be that $uaq_i⌴$ yields something like $uacq_j⌴$ when moving rightward and $uq_iac⌴$ when moving leftward, but I worry that I've missed something. Am I on the right track or am I way off base?


texts: Kolmogorov complexity of prefixes of computable sequences

texts:
Let the characteristic sequence of a set $A ⊆ \mathbb{Z^+}$ be the following infinite binary sequence:
$$χ_A = b_1b_2b_3\ldots,$$
whose $n$th bit is 1 if $n ∈ A$ And 0 otherwise.
Write $χ_{A,n}$ for the first $n$ bits of $χ_A$.
Prove for every decidable set $A \subseteq \mathbb{Z^+}$ there is a constant $c ∈ \mathbb{N}^+$ such that for all $n ∈ \mathbb{Z}^+$ the Kolmogorov complexity of $\chi_{A,n}$ satisfies
$$ C(χ_{A,n})≤\log n+c. $$

Since $A$ is decidable there is a lexicograhic enumerator. Given that, how would I construct a Turing machine $\pi_A$ satisfying $U(\pi_A)= χ_{A,n}$, where $U$ is the universal Turing machine, whose complexity is at most $\log n+c$?


texts: Can preorder and postorder traversals be used on any type of trees?

texts:
I could not find an answer to the question directly by google.
I think this question is rather simple but I am not really sure about it.
Any advice is welcomed.
Thanks


texts:
Can a pushdown automaton solve the halting problem for another Pushdown automaton?
It's already shown here turing machine can solve the halting problem for a pushdown automaton.
Decidability of halting problem for DPDAs with $\epsilon$-transitions?
But can a pushdown automaton do the same?


texts: Detecting a cycle in an undirected graph and printing the vertices if there is a cycle, printing no cycle otherwise

texts:
Problem: Find an O(E + V) time algorithm that outputs the vertices of a cycle of G, if it exists. If G has no cycles, the algorithm outputs no cycle. So if there is a cycle 1, ... 3, 1, it would print 1, ..., 3, 1.

So I was thinking of doing a BFS, and if the currently examined vertex's neighbor v has been visited prior, then there is a cycle. However, I am not sure how I might go about tracking the vertices in order to print. I believe I would have to view the BFS-Tree, but unsure.


texts: Term clarification: Establishing a domination

texts:
In the book "Approximation Algorithms" by Vazirani (legally available online), part of the hint to Exercise 9.6 (on page 77 of the book, page 95 of the PDF) says "Establish a domination". I've never heard this terminology before in the context of computer science/approximation algorithms/bin packing (I'm not so sure what the correct context is).

Perhaps someone here has familiarity with this terminology. If so, I'd love to hear the definition of "Domination" in this context.


texts: Is a supercomputer more powerful than the total of all the world's computers in 2004?

texts:
The supercomputer I am researching has 2.2 petaflops and boasts total memory of 1000 terabytes and disk space of 23.5 petabytes.

Is this more computing power than the total of the entire worlds computing power 10 years ago (2004)?