texts: CURE algorithm: what does moving the representative points towards the centroid do?

texts:
The CURE algorithm is a method of clustering data. An outline of it can be found here on slide 5: https://www.slideshare.net/ellepiu/cure-clustering-algorithm. I personally learnt it from this video: https://www.youtube.com/watch?v=JrOJspZ1CUw, where the algorithm is explained at 7 minutes.

This is my understanding of the process of CURE. Let's assume that the data set is large enough such that we have to store a portion of the data on disk.

Take an amount of the data set that fits onto the computer, and cluster (perhaps hierarchically) to initialise clusters.
For each cluster: pick k representative points, and move each a fixed distance, $\alpha$, towards the cluster centroid.
For each data point on disk, assign it to the cluster with the representative point it is closest to.

To me, this selection of representative points seems like a really arbitrary thing to do, and I don't really see the logical process behind choosing to do this.

For any two data sets representing the same thing, it could be possible (even likely) that one set of clusters pre-representative-point-moving for one data set would be the same as the set of clusters post-representative-point-moving for the other.

Could someone please help explain in more detail the reasoning behind doing this? (Beyond just the basic pseudo-algorithm I have seen.)

My thoughts

I think that when moving the representative points towards the centroid of each cluster, this is equivalent to shrinking the boundary of the cluster. Once this is done, the data points that remain outside of the boundary are eliminated as clusters. But I'm not sure if this is correct.


texts:
I tried to implement the lambda calculus successor function on my own, but it's different from the Wikipedia entry on Church encoding.  The entry wraps the 'b' around the rest of the expression after injecting the 'c', whereas I tried injecting 'b's application on 'c'.  Is there a fundamental difference between these two expressions, and what would be good practice when writing this stuff down?

Mine: increment = (λa.λb.λc.((a b) (b c)))

Wikipedia's: increment = (λa.λb.λc.(b ((a b) c)))

This is after I alpha-reduced to 'a', 'b', and 'c', so the article is different.


texts: Relation between Machine code and Von Neumann architecture

texts:
Since machine language executes instructions on ALU, CPU register and memory, is correct say that machine code abstract the Von Neumann model?

If exists, semantically, what is the relation between machine code and Von Neumann architecture?


texts: Are there techniques to know how many times loops like these will run?

texts:
How do you evaluate how many times some loops will run, when you start to complicate the boundaries conditions? For example, take this function:

def f(n):
    s = 0
    for i in range(n):
        for j in range(i, (n + i**2) // (n - i) + 1):
            s += 1
    return s

for i in range(10):
    print(i, "->", f(i))

Output:

0 -> 0
1 -> 2
2 -> 5
3 -> 10
4 -> 17
5 -> 28
6 -> 42
7 -> 60
8 -> 83
9 -> 109
```


texts: How to find a 2-wise independent hash family that is not 3-wise independent?

texts:
I'm trying to find a family of hash functions mapping $\{1, 2, ..., 2^n\}$ to $\{0, 1\}$ that is 2-wise independent but not 3-wise independent. Any ideas on that?

I know two 2-wise independent families but I think they are 3-wise independent as well:

1) Let x be a vector in $\{0, 1\}^n$. The hash functions are $h_{a, b}(x)=a^\top x+b \mod  2$ for all $a\in\{0, 1\}^n$ and $b\in\{0, 1\}$.

2) Consider $GF(2^n)$. The hash functions are $$h_{a, b}(x)= \text{the last bit of }a \cdot x+b $$ for all $a, b\in GF(2^n)$.


texts: Basic examples of static and dynamic RAM

texts:
What could be the basic examples (or the one that we are familiar of) of static and dynamic RAM?

My Thoughts:
First of all $\color{RED}{\text{RAM}}$ is something whose contents will be lost if power is removed
Now, in $\color{green}{\text{Static RAM}}$, the contents of the memory do not change with time and they hold data as long as the D.C. power is applied and here we do not require any refreshing
whereas, $\color{blue}{\text{Dynamic RAM}}$ needs to be periodically refreshed otherwise their stored information will be lost
so one basic example of Static RAM may be an unsaved Text file in MS Word or an unsaved screenshot in Paint software
And one basic example of Dynamic RAM may be this site  https://mbasic.facebook.com which require refreshing for seeing new News feeds
These are my thoughts and I am not $100 \%$ sure
so please help...


texts: What is the correct FSA representation of the following string sequence?

texts:
Based on this article, i am trying to imagine how i would construct an FSA based index for the following string sequence:

ABCDEF
ABDDDF
ABDDEFGHI

These are the representations that i found:

There are problems with each:

The first introduces a new key in the automata that really isn't in the set (ABCDEFGHI)

The second one is the closest to my heart but it is more trie-like, so it can be inefficient at a large scale.

The third saves a lot of final states therefore saves some space. However, state 9 has multiple "F" transitions which i think is illegal.

So the big question is: Which one of the above is correct? If none of them, please share what is the correct!

Thank you


texts:
In most bibliography, only cut(v) is defined.
More properly, only cut(v,v.parent) is defined, where (v,v.parent) is an edge in the represented tree.

The pseudo-code and code for this is:

cut(x):
   access(x);
   parent(left(x)) = null
   left(x) = null

void cut(Node *x){
   access(x);
   x->left->parent = 0;
   x->left = 0;
}

  How can we define cut(u,v) for an arbitrary (u,v)?

  I.e. how can we code cut(u,v) in such a way that

  If (u,v) is not an edge in the represented tree, then do nothing;
  If (u,v) is an edge of the represented tree, cut the edge in the represented tree.

The following function may help, it determines the root of the represented tree that contains the node x.

root(x):
   access(x)
   while(left(x) =/= null)
      x = left(x)
   splay(x)

LCT *root(LCT *x){
   access(x);
   while((*x).left != NULL){
       x = (*x).left;
   }
   splay(x);
   return x;
}

Additional reference (code): https://github.com/saadtaame/link-cut-tree

Thanks in advance.


texts:
If you have a long string of length $n$ and a shorter string of length $m$, what is a suitable recurrence to let you compute all $n-m+1$ Levevenshtein distances between the shorter string and all substrings of the longer string of length $m$?

Can it in fact be done in $O(nm)$ time?


texts: Show how a sentence can be produced from a grammar (Dragon book 2.1)

texts:
In the Dragon book (Aho, Sethi, Ullmann) there is one exercise I don't get.

  Chapter 2, Exercies: 2.1
  Given the context-free grammar
  $$S \to S S + \mid S S * \mid a$$
  Task: Show how the signs aa+a* can be produced from this grammar.

I understand the grammar, $S$ can have the form $S S +$… and so on. But I don't know what I'm supposed to do in this task. Sadly I can't find any solutions on the web.


texts:
For two languages over the same alphabet, if neither of them is context-free, can their union still be context-free?
If not, does one of the languages need to be context-free for this to happen? Do both need to be context-free?


texts:
Cryptographic security is usually proven against P/Poly adversaries as this encapsulates the possibility for someone to do heavy precomputation to be used later, eg. rainbow tables.

However actually finding this advice string is assumed very impractical for large instances, rendering the process generally infeasible.

Several questions on this site already ask about the power of P/Poly, but do we know anything more about feasibility if we restrict the non-uniform TM to only using logarithmic read-write space? I'm only concerned with a definition of L/Poly that includes well-formed languages, specifically not undecidable.

I'm also interested in results about randomization, or even potentially derandomization. A logspace variant of Adleman's theorem shows that BPL is contained in L/Poly, so probabilistic algorithms for a large subset of L/Poly could potentially be derandomized to fall in SC. However I'm unsure of the general case in between BPL and L/Poly (assuming a gap), and especially whether L/Poly is in any way relatable to P.


texts: Mathematical optimization on a noisy function

texts:
Let $f:\mathbb{R}^d \to \mathbb{R}$ be a function that is fairly nice (e.g., continuous, differentiable, not too many local maxima, maybe concave, etc.).  I want to find a maxima of $f$: a value $x \in \mathbb{R}^d$ that makes $f(x)$ as large as possible.

If I had a procedure to evaluate $f$ precisely on any input of my choice, I could use standard mathematical optimization techniques: hill-climbing, gradient descent (well, gradient ascent), etc.  However, in my application I don't have a way to evaluate $f(x)$ exactly.  Instead, I have a way to estimate the value of $f(x)$.

In particular, given any $x$ and any $\varepsilon$, I have an oracle that will output an estimate of $f(x)$, and whose expected error is approximately $\varepsilon$.  The running time of this oracle invocation is proportional to $1/\varepsilon^2$.  (It is implemented by a kind of simulation; the accuracy of the simulation increases with the square root of the number of trials, and I can choose how many trials to run, so I can choose the desired accuracy.)  So this gives me a way to get an estimate of any accuracy I desire, but the more accurate I want the estimate to be, the longer it will take me.

Given this noisy oracle for $f$, are there any techniques for computing a maxima of $f$ as efficiently as possible?  (Or, more precisely, finding an approximate maxima.)  Are there variants of hill-climbing, gradient descent, etc., that work within this model?

Of course, I could fix a very small value of $\varepsilon$ and apply hill-climbing or gradient descent with this oracle, keeping the same $\varepsilon$ throughout.  However, this might be unnecessarily inefficient: we might not need such a precise estimate near the beginning, whereas precision near the end when you are zeroing in on the solution is more important.  So is there any way to take advantage of my ability to control the accuracy of my estimate dynamically, to make the optimization process more efficient?  Has this kind of problem been studied before?


texts: How does in-order traversal in Binary search tree works (recursion)

texts:
I visit some question but their implementations are slightly different and my doubt is not like theirs. I have this code in Javascript.

The code is typical BST implementation with methods to support in-order traversal. The code that is the most relavant for this question is the the inOrderTraverse and inOrderTraverseNode. I cannot understand how this code work.

function BinarySearchTree() {

    var Node = function (key) {
        this.key = key;
        this.left = null;
        this.right = null;
    };

    var root = null;

    this.inOrderTraverse = function (callback) {

         inOrderTraverseNode(root, callback);
    }

    this.insert = function (key) {

        var newNode = new Node(key);

        if (root === null) {
            root = newNode;
        }
        else {
            insertNode(root, newNode);
        }

    }

    var insertNode = function (node, newNode) {

        if (newNode.key < node.key) {
            if (node.left === null) {
                node.left = newNode;
            } else {
                insertNode(node.left, newNode);
            }
        } else {
            if (node.right === null) {
                node.right = newNode;
            } else {
                insertNode(node.right, newNode);
            }
        }

    };

    var inOrderTraverseNode = function (node, callback) {

        if (node !== null) {
            inOrderTraverseNode(node.left, callback);
            callback(node.key);
            inOrderTraverseNode(node.right, callback);
        }
    }
}

The code that will use the BinarySearchTree "class".

function printNode(value) {
    document.writeln(value);
}

var tree = new BinarySearchTree();

tree.insert(11);
tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(3);
tree.insert(9);
tree.insert(8);
tree.insert(10);
tree.insert(13);
tree.insert(12);
tree.insert(14);
tree.insert(20);
tree.insert(18);
tree.insert(25);
tree.insert(6);

tree.inOrderTraverse(printNode);

This will generate a BST like this:

taken from the book Learning Javascript Data Structure and Algorithms by Loiane Grone

I will explain how I think the in-order functionality works.

    var inOrderTraverseNode = function (node, callback) {

    if (node !== null) {     //checks if the node is null, 11 is not null so it continues
        inOrderTraverseNode(node.left, callback);     //keep executing this code until it finds a node with left null
        callback(node.key);      //3, the node with left null is printed
        inOrderTraverseNode(node.right, callback);     // checks if the 3 node has a right node, it doesn't have, so the execution finishes
    }

}

11 the root node is passed to the inOrderTraverseNode, it checks to see if the left is a null, if it is not it continues passing the left node until the left node is null. When a left null node is found Then it prints the value, callback(node.key) will execute as callback(3), so the 3 will be the first item printed on the screen. The execution then continues to inOrderTraverseNode(node.right, callback), 3 don't have a right child so execution will go on and that's that.

in my mind the output would be 3 only.

How do the in-order traversal get from 3 to the 5?


texts: Does having one large L1 cache instead of L1 and L2 cache makes computation faster?

texts: Does having one larger L1 cache instead of L1 and L2 cache makes computation faster? Also will this make the CPU more expensive to make?


texts:
To keep througput close to 1/cycle when there is a multi-cycle stage that sends a command to a far module then gets answer(10 clocks per send or receive), could separating it in two(send + receive) and putting idle stages(18x1 clocks) between them solve the problem?

For example, with just a single stage that takes 20 clocks, it has throughput of 0.05 instructions per cycle. When idle stages are added, incoming instructions should randezvous with incoming answers from distant module at last stage and it should keep throughput at 1 instruction per cycle. So answer is received from bottom stage instead of same stage of sending. Is there a more elegant way than this? I'm writing a cpu-design and simulation game that drag-n-dropped-connected modules communicate and pass instructions from fetch to retire, but they all have multiple layers of communications that slow throughput and I need to keep a high throughput without giving simplicity away(for gamers) and doing it right (idle stages are right or not?)

If a pipeline stage is a combinatorial logic, than it could have communication with other circuits than its own(not just flowing data to next stage)(fetch wired to memory controller/cache, decode wired to decoder instead of accepting decoder module as a whole pipeline stage)


texts: How does value decompression work for Facebook's Gorilla in the case where count of leading zeroes is not stored

texts:
I am referring to this paper: http://www.vldb.org/pvldb/vol8/p1816-teller.pdf

My question is regarding section 4.1.2 where it says:

  When XOR is non-zero, calculate the number of leading and trailing zeros in the XOR, store bit ‘1’ followed
  by either a) or b):

  (a) (Control bit ‘0’) If the block of meaningful bits
  falls within the block of previous meaningful bits,
  i.e., there are at least as many leading zeros and
  as many trailing zeros as with the previous value, use that information for the block position and just store the meaningful XORed value.

When decompressing, how do we know if we should add leading zeroes or tailing zeroes? For example lets say we have following 48 bits numbers:

A = 0xfff ffff fffff
B = 0xfff 0000 fffff
C = 0xfff 0ff0 fffff

and

A xor B = 0x000 ffff 00000

B xor C = 0x000 0ff0 00000

If we follow the compression algorithm for A xor B we will store the number of leading zeroes , which is 12, as well as the meaningful bits ffff.

Now, for B xor C because "there are at least as many leading zeros and as many trailing zeros as with the previous value", so we only store the meaningful bits ff. When I want to decode ff, base on previous compressed bits, I know that I have at at least 12 leading zeroes and 20 tailing zeroes, but I still need to fill in 8 zeros; should I do ff00 or 00ff or other combination?


texts: monotone min 3-sat polynomial algorithm?

texts:
I know that 3SAT is npc but i wonder why my little algorithm won't solve this problem:

given positive 3SAT - meaning: each of the m clauses is a disjunction of 3 literals over the variables x1,…,xnx1,…,xn (nn variables) and each literal is a positive appearance of a variable (no  xi xi).

for example: (x1∨x3∨x7)∧(x5∨x4∨x2)(x1∨x3∨x7)∧(x5∨x4∨x2)

In other words: The problem is probably called MIN 3SAT, which every literal is positive but you must find minimum integer k such that there exists a truthful assignment of the variables which sets k variables to TRUE.

What is wrong with this "greedy" algorithm?:

run through all left clauses and find the variable that appears in most of them (can be implemented by counters array..). take this variable, give him truth assignment, remove all clauses which he appeared in, zero the counters array and do again the previous step. stop when no clauses left. it looks like this algo runs in O(m2n)O(m2n) time.

why isn't it an optimal algorithm?

UPDATE: Can someone give me an example to why the greedy algorithm won't give the optimal solution? I can't figure why the greedy approch is not good..


texts: Modifying the JPEG compression to use custom block patterns

texts:
recently, while watching a video about machine learning, I had an idea about creating an image compression algorithm, that works similar to JPEG, but is based on arbitrary bitmaps as blocks.

I should mention that I would not call myself a computer scientist, so my understanding of the math and algorithms involved are still limited at this point. I have an intuition for how deconstructing an image into blocks, which are represented as combinations of 8x8 px patterns (made up of cosine waves) works.

so my question is: is it possible to replace the standard JPEG patterns with something else? -- for instance the features that have been found by a neural network (see below).

I'd be very interested in what the results / artifacts of such a compression would look like, both applied to the original data set (the neural net was trained on) and random other images.

any ideas / directions on how to achieve this are very much appreciated.

thanks a lot in advance!


texts: Language to Generate Powers of 2 Using a Language Containing Decimal Numbers

texts:
For this question, I have the alphabet $\Sigma=\{0,1,2,3,4,5,6,7,8,9\}$. I also have the language $L$ over $\Sigma$ described as the language such that the strings $w$ contained in $L$ are powers of 2 and $w$ is treated as a decimal number. I then need to:

Design a grammar to generate $L$
Classify the grammar (Regular, Context-free, etc.)
Show that $L$ is not regular
Determine if $L$ is a context-free language (answering only yes or no)

The original question is in the image below, for reference.

I'm not entirely sure how to start on this question in particular. Most of the examples I had in my automata class consisted of much smaller alphabets and more precise languages. Any help with an explanation would be much appreciated.

Thank you in advance!


texts:
Are there any kind of graphs where Bidirectional Dijkstra would expand more than Dijkstra?

I tried to come up with an argument like this:

Let node $n$ be expanded by Bidirectional Dijkstra. Now there are two possibilites:

Node $n$ was expanded in the forward search
Node $n$ was expanded in the backward search

If $n$ was expanded in the forward search, then it would have been expanded in Dijkstra's algorithm also because forward search of Bidirectional Dijkstra is essentially just Dijkstra stopped earlier.

If $n$ was expanded in the backward search, there are two cases possible:

$n$ is on the actual shortest path between start and goal.
$n$ is not on the shortest path between start and goal.

If $n$ is on the actual shortest path between start and goal, then $n$ will also be expanded by Dijkstra.  If $n$ is not on the shortest path between start and goal, then $n$ might not be expanded by the Dijkstra.(I am not sure how to use this case. Does this suggest that Bidirectional Dijkstra can expand more nodes than Dijkstra?)


texts: NFA - string acceptance (decision problem) test

texts:
I am interested in testing for a given string (w) whether it is in the language (L) defined by a nondeterministic finite automaton (A). I have some blurry point in my mind.

What is the complexity of this test by using the NFA and backtracking? Assume my NFA has m states and string (w) has length n (|w| = n). For regular expressions, by using Thompson's algorithm, the resultant NFA has the same complexity (worst case) if I use backtracking?

What are the methods/algorithms other than backtracking and converting to DFA?


texts:
Assume that $L_1 \subseteq \Sigma^*$ is a CFL and that $y \in \Sigma^∗$ is a string.
I need to prove that the language $L_2 = \{x \in L_1 \mid x \text{ does not contain $y$ as substring}\}$ is a CFL.
I tried pumping lemma for CFLs, but it seems that is for disproving that languages are CFLs. I also tried to create a CFG for this language, but I'm having a hard time. I even took a look at the membership problem for CFGs.
Any ideas on how I would go about proving this?


texts: Is the Source Coding Theorem straightforward for uniformly distributed random variables?

texts:
Shannon's source coding theorem states the following:

  $n$ i.i.d. random variables $X_1,\dots,X_n$ each with entropy H(x) can be compressed into more than n⋅H(x) bits with negligible risk of information loss, as n→∞; conversely if they are compressed into fewer than n⋅H(x) bits it is virtually certain that information will be lost.

I was thinking about the easy case when the $X_1,\dots,X_n$ are uniformly distributed on the integers $[1,n]$. Now suppose I want to transmit a value of $(X_1,\dots,X_n)$.
Clearly, each $X_i$ has entropy $\log n$ and thus, if we were to send $o(n\log n)$ bits, we would lose information about some of the $X_i$, with high probability $1 - o(1)$.

The way to argue the Theorem for this case, is that it $\log n$ bits suffice to reconstruct any $X_i$, and conversely, if you receive, for example, only $(1/4)n\log n$ bits, then, you would need to correctly guess $3/4 n\log n$ bits, which happens with probability of only $2^{-3/4n\log n}$.
Is my reasoning correct?


texts:
I am dealing with a standard MIPS architecture. If I have a branch instruction, for instance, beq, I know the results of the comparison in execute. However, the branching logic is actually in memory stage. Hence, doesn't that mean that I am technically losing 3 cycles(if the branch is taken) since the correct instruction is fetched during the writeback stage of the branch instruction? See the diagram below to see what I mean:

beq ...
add ...
add ...
add ...
...
label: sub

    C1 C2 C3 C4 C5
beq F  D  X  M  W
add    F  D  X
add       F  D
add          F
sub             F

However, in this website: http://homepage.divms.uiowa.edu/~ghosh/2-14-06.pdf
it says we only lose 2 cycles. This is because they are assuming as soon as you know the results of the computation (in execute), you can also fetch the correct instruction. I believe this is false since branching logic actually happens in MEM.

Where am I mistaken?


texts: Finding a set of maximally different solutions using linear programming or other optimization technique

texts:
Traditionally, linear programming is used to find the one optimal solution to a set of constraints, variables and a goal (all described as linear relationships). Sometimes, when the objective is parallel to a constraint, there are infinite or many equally good optimal solutions. I am not asking about this latter case.

I am more interested in finding many solutions that are in the feasible region generated by my set of constraints. But I would like the solutions I find to be 'scattered' around the feasible region in the sense that they are maximally far from one another. Is there a known way to, without running a solver multiple times, generate multiple solutions and use the objective function to enforce that the solutions should be separated?

For example, any linear program with decisions a and b and constraints w <= a <= x and y <= b <= z can be 'duplicated' to find two solutions. Our new linear program has variables a1, a2, b1, and b2 and the constraints w <= a1 <= x and w <= a2 <= x and similar for b1, b2. However, when it comes to forming an objective function we run into trouble as we can not use norms other than the L1-norm without discarding linearity and we can not truly even use the L1 norm because it is not possible (so far as I know) to encode absolute values.

Perhaps I should look into convex optimization or semidefinite programming or something?

Is there a known way to generate a set of solutions to a linear program, and using an objective that enforces "distance" between the solutions?


texts: Efficient algorithm to generate undirected graph edges from 3D distribution of nodes based on distance

texts: I have a set of nodes where each node $n_i$ is associated with a cartesian coordinate $\vec r_i$ and a radius $\sigma_i$. I want to generate a graph data structure where nodes $n_i$ and $n_j$ are connected by an undirected edge if $|r_{ij}| < \sigma_i + \sigma_j$. This is not my field and I am interested in efficient algorithm/workflow/software suggestions. I am working in C++.


texts:
Why are computable numbers (in Turing's sense) enumerable?
It must be very obvious, but I'm currently just not seeing it.


texts: Why do functions containing `await` need to be `async`?

texts:
From what I understand, async/await enables to avoid the "callback pyramid of doom".
Let's say that I have funcA(), funcB() and funcC() that are async functions, now if I do something like that:

func someFunction() -> T {
let myValueA = await funcA()
let myValueB = await funcB()
let myValueC = await funcC()
return doSomething(myValueA, myValueB, myValueC)
}

Why do some languages (for instance JavaScript) require you to annotate your function with async ?
What would be the issue issue if the function wasn't asynchronous? I mean, since the function already contains awaits, can't it be already considered as a non blocking function ?

Thank you


texts: Is z-buffering the same as rasterization?

texts: I understand z-buffering as being "object-first" in contrast to "pixel-first" since the for loop starts with checking each triangle in the scene rather than each pixel. However, is this the same as rasterization,  or is rasterization just a general technique that encompasses z-buffering?


texts: Are there adversarial inputs for randomized quicksort?

texts:
Someone recently claimed that there's an adversarial input for randomized quicksort; he referenced this paper. This defies my intuition because there are results that say that randomized quicksort runs in $O(n \log n)$ time with high probability. (See, for example, the book Randomized Algorithms by Motwani&Raghavan.) I am refering to the version of randomized quicksort that picks the pivot uniformly at random at each recursive call.

So my question is: are there indeed adversarial inputs for randomized quicksort? Please give an intuitive reason as to why such an input can exist.

Update. It seems to me that the adversary in the paper is granted unrealistic capabilities (generate array on the fly), which explains why it can make any quicksort perform poorly. Under reasonable assumptions I would say there is indeed no adversarial input for randomized quicksort.


texts: Algorithm to extract the subgraph of all nodes with degree at least four

texts:
I have an undirected graph represented by a list of nodes and a list of edges. What I need to produce from this is a list of nodes and edges representing a new graph containing only the nodes which have degree of at least 4. I think I've developed an algorithm. It uses an object called Node, which can store an integer for the degree of the node and a list of that node's neighboring nodes.

For each node in the graph create a Node object in $O(|V|)$ time and store in a list.
Traverse the list of edges in $O(|E|)$ time. While doing so update my list of nodes with their appropriate degree and neighbors.
Search the list in $O(|V|)$ time and find the node with smallest degree. If >4, return. If <4, visit the node's neighbors, reduce their degrees by one, and remove this node from their list of neighbors. Then remove this node from the graph, in worst case $O(|V|)$ time.
Repeat step 3. At worst $O(|V|)$ times.

If anyone is wondering, I'm doing this for a Civilization-esque game I'm making. I want to be able to separate cities that are part of major trade routes from minor ones.

Now, I think this algorithm is correct, but I'm not happy with its running time. If I'm not mistaken, it's $O(|V|^2)$, correct? Is there a way to make this more efficient?


texts: Why is there no one to many Multithreading Model?

texts:
I am studying various multi-threading models. Here the user threads are mapped to Kernel Threads. They are -

Many to one model.
Many to many model.
one to one model.`

What kept me wondering was why there is no one to many model ?


texts: Why is the PageRank vector also the eigenvector of the web adjacency matrix?

texts:
From wikipedia:

  The PageRank values are the entries of the dominant eigenvector of the
  modified adjacency matrix. This makes PageRank a particularly elegant
  metric

Can anyone please elaborate on the connection between the eigenvector and the PR vector? Why are they related?


texts: Finding missing edge weights in the context of minimum spanning tree

texts:
I came across following problem:

  Problem 1
  Suppose that minimum spanning tree of the following edge weighted graph contains the edges with weights $x$ and $z$, then what are $x$ and $z$?

The solution given was as follows:

  There are two ways to reach node $F$, one from node $A$, other from node $G$. Maximum weight of the edge in MST is smallest of two. Hence 11.
  Similarly there are four edges incident on node $B$, having weights $13,14,8,z$. If $z$ is included in MST, then it should be at least $min(13,14,8)$, that is 8.

Then I came across another problem:

  Problem 2
  In below graph, the edge weights of only those edges which are in the MST are given. What are the weights of other edges?

Solution was:

  In every cycle, the weight of an edge that is not part of MST must by greater than or equal to weights of other edges which are part of MST. Since all edge weights are distinct, the weight must be greater. So $w(ED)=6, w(CD)=15$
   and $w(AB)=9$

First solution chooses min degree of a node, whereas second solution chooses max edge weight in cycle. This seems to be obvious since first problem has "unknown MST edge weights", whereas second problem have "unknown non-MST edge weights".

But, I have several doubts here:

In solution 1, why we examine edges incident on node $B$ only, but not node $C$? I guessed following procedure:

  If we start preparing MST using Kruskal's algorithm, we will go on adding edges in sequence $AG,IJ,CD,...$ and $C$ gets connected to MST. So in this particular example, it works by preparing MST using the known edge weights such that the edges chosen wont change whatever the unknown weights turn out to be. And then based upon vertices connected to the MST prepared so far, decide which of the vertices of unknown weight edge is to be reached by  that edge.

Is this procedure correct? Does it work in all cases / graphs? Is there any other standard approach to solve such problem?
Second solution used cycle $E-D-F-E$ to determine the weight of edge $ED$, but not cycle $B-E-D-C$. Though I understand that decision of choosing $EF$ and $DF$ are dependent on $ED$, doesnt decision of selecting $BE$ is dependent on total of weights of $CD$ and $ED$? What is exact rule/idea for deciding which cycle to consider while determining non MST edge weight?
Is there some standard well defined steps for both problems? Or its more sort of trial and error work?


texts: Find K least values in a Tree in which each node has 4 children

texts:
Here is an example tree:

Each node has either $0$ or $4$ nodes. The values $v(n)$ of the node $n$ is given by $v(n) = v(\operatorname{parent}(n)) + k(n)$, where $k(n)\in \{2, 2.5, 8, 50\}$, such that a parent has childs of each value. Find the $K$ least nodes in a given tree (always ignore the root node). For our example tree, we get

$K = 4$, values are: $2, 2.5, 4, 4.5$

$K = 6$, values are: $2, 2.5, 4, 4.5, 5, 8$

Parsing all the nodes and sorting is a straightforward solution. But is there a more optimum solution?

In particular, I tried to

parse the tree fully in a recursive fashion.
put each node into an array as we parse.
sort the array in increasing order.
take the first $K$ values.

If there are $N$ nodes in total, then this solution will be of the order of $O(N\log N)$.

Is there a more efficient method?


texts: Code arithmetic expression in a binary tree

texts:
How to present (code into) an expression consisting of brackets and following operations: +, -, / and * into a binary tree. Then, I need to write an algorithm that will derive that very tree.

Any hints or suggestions on how to do this?

I've tried placing brackets and operands into the leaves, but I'm not even precisely sure on what to do. Thanks in advance.


texts:
http://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method

What is the time complexity of the right to left method in modular exponentiation?

is it O(1) because we are going through the binary representation of e which is constant time? assuming e is a 32-bit integer

int mod(int b, int e, int m) {
    b = b % m;
    int result = 1;

    while (e) {
        if (e % 2 == 1) {
            result = (result * b) % m;
        }
        b = (b * b) % m;
        e >>= 1;
    }
    return result;
}


texts: How to reduce MaxUNSAT to MaxSAT in a (almost) direct way?

texts:
In question How to reduce MaxUNSAT to MaxSAT? I was asking, how to reduce the MaxUNSAT problem to MaxSAT. With help of the given answer I could give a polynomial reduction : $MaxUNSAT \leq decisionProblemMaxUNSAT \leq SAT \leq MaxSAT$.

Question: Is there a more direct reduction without much overhead from MaxUNSAT to MaxSAT (or to minUNSAT)?

Because the two problems are very similiar, it seems there is a more direct reduction, but I could not figure out one.

Something like $MaxUNSAT(\phi) = MaxSAT(\neg\phi)$ (which does not work).


texts: How does Tarjan's pseudocode work (explained to someone familiar with C or Java)?

texts:
The Short Story

A famous computer scientist, Tarjan, wrote a book years ago. It contains absolutely bizarre pseudocode. Would someone please explain it?

The Long Story

Tarjan is known for many accomplishments, including the fact that he was the coinventor of splay trees. He published a book, "Data Structures and Network Algorithms," during the 1980s.

All of the pseudo-code in Tarjan's book is written in a language of his own devising. The pseudo-code conventions are very regimented. It's almost a true language, and one could imagine writing a compiler for it. Tarjan writes that his language is based upon the following three:

Dijkstra's Guarded Command Language
SETL
ALGOL

I am hoping that someone familiar with one or two of the above languages, or the work of Tarjan, will be able to answer my question.

An example of a function written in Tarjan's language is shown below:

heap function mesh (heap nodes h1, h2);

    if key(h1) > key(h2) → h1 ⟷  h2 fi;

    right (h1) := if right(h1) = null → h2

                  |right(h1) ≠ null → mesh (right(h1), h2) fi;

    if rank (left (h1)) < rank (right (h1)) → left(h1) ⟷ right(h1) fi;

rank (h1) := rank(right(h1)) + 1;

return h1,

end mesh;

I have seen lots of pseudo-code, but I have never seen anything like Tarjan's. How does Tarjan's pseudocode work? How can examples of Tarjan's pseudocode be re-written as something which looks more like C or Java? It need not even be C or Java. The if-else construct in Tarjan's language is not only different from C-family languages, but also different from Python, MATLAB and many others.


texts: The relationship between degree and the number of leaves of a tree?

texts: What is the relationship between $\text{deg}(T)$ and the number of leaves of $T$, if $T$ is a tree?


texts: Finding the $k$th smallest element in union of two sorted arrays

texts:
I know that this problem is solvable in linear time with a merge but I want to get a sub-linear algorithm.
What I came up is that, if a[k] < b[k] then the $k$th element can not be in the sub array a[0..k-1] or in b[k+1..n].
But I am not able to construct the recursive relation.
What I came up is

find(i,A,B):
    k=i/2;
    if n=1:
       return min of a[0],b[0]
    else if A[k] < B[k]
       recursively compute find (k,A[k+1..n],B[0..k-1])
    else if A[k] > B[k] recursively compute find(k,A[0..k-1],B[k+1..n])

Can any one guide me possible flaws in this?


texts: Is there an easy way to see why NP is in EXPTIME?  It seems to me a priori conceivable that there could be a problem which requires super-exponential time to solve, but whose solution could be verified in polynomial time.


texts: Are neural networks a type of reinforcement learning or are they different?

texts:
Can neural networks be considered a form of reinforcement learning or is there some essential difference between the two?

By the same token could we consider neural networks a sub-class of genetic algorithms?

According to my current understanding the taxonomy is kind of like this:

   Reinforcement Learning
      Evolutionary Algorithms
         Genetic Algorithms
            Neural Networks

Is this right?


texts:
I am reading this book Asymptotic Methods in Analysis by N. G. de Bruijn. It describes the definition of $O$ symbol as

  A weaker form of suppression of information is given by the
  Bachmann-Landau O-notation. It does not suppress a function,
  but only a number. That is to say, it replaces the knowledge of a
  number with certain properties by the knowledge that such a
  number exists. The O-notation suppresses much less information
  than the limit notation, and yet it is easy enough to handle.
  Assume that we have the following explicit information

I don't under what does this means...

...That is to say, it replaces the knowledge of a
number with certain properties by the knowledge that such a
number exists...

Can anyone throw light on this passage of definition?
It will be a great help.
Thanks in Advance!


texts: Confused about proof that $\log(n!) = \Theta(n \log n)$

texts:
So I was able to show that:

$\log(n!) = O(n\log n)$ without any problems.

My question is when trying to prove that $\log (n!) = \Omega(n\log n)$.

I was able to show that:
$$\begin{align*}
\log n! &= \log(1 \cdot 2 \cdot 3 \cdots n  )\\
&= \log 1 + \log2 + \log3 + \dots + \log n \\
&= \log 1  + \dots + \log\tfrac{n}{2} + \dots + \log n\\
&\geq \log\tfrac{n}{2} + \log\big(\tfrac{n}{2} + 1\big) + \dots + \log n &&\text{(i.e., the larger half of the sum)}\\
&\geq \log\big(\tfrac{n}{2}\big) + \log\big(\tfrac{n}{2}\big) + \dots + \log\big(\tfrac{n}{2}\big)&&\text{(adding $\tfrac{n}2$ times)}  \\
&= \log\big(\tfrac{n}{2} \cdot \tfrac{n}{2} \cdots \tfrac{n}{2}) &&\text{($\tfrac{n}{2}$ times)}  \\
&= \log\Big(\tfrac{n}{2}^{\tfrac{n}{2}}\Big)\\
&= \tfrac{n}{2} log\big(\tfrac{n}{2}\big) &&\text{(by log exponent rule)}
\end{align*}$$

Thus, $\log(n!) \geq \tfrac{n}{2}\log\big(\tfrac{n}{2}\big)$, so we conclude that $\log(n!) = \Omega(n\log n)$.

I don't understand how finding the lower bound of $\log(n!)$ is found by getting the larger half of the sum. Why is that chosen to find $\Omega(n\log  n)$? I feel like it's probably something obvious but it's the only thing keeping me from fully grasping the proof. If someone can enlighten me, I would appreciate it!


texts: Calculate execution time from linear speedup

texts:
Given an execution time $t(c_1)$ and linear speedup $s$, how do you calculate the execution time for $c_2$ processor cores?

(Assuming Gustafson's law, or in other words, $t(\infty)=0$)

My ideas:

I haven't found any references that give formulas for calculating execution time, surprisingly. However, I think you can derive a formula from the speedup equation:
$$speedup = t(1)/t(c)$$
The problem is, I'm pretty sure this is not what people are referring to when they give you a "linear speedup" factor $s$. I haven't been able to find any exact definitions on what "linear speedup" is. I can be sure that linear speedup means that $speedup$ is linearly dependent on cores. But what is the equation?

I looked at the superlinear speedup values from the introduction of this paper. The data points $(c, speedup)$ are $(2, 2.46)$, $(4, 4.68)$, and $(8, 9.59)$. From these, it would seem the formula is:
$$s = speedup/c$$
This gives $1.23$, $1.17$, and $1.20$ for $s$; since $s$ should be constant, this seems like it could be correct. Assuming this is correct, you get:
$$
t(1) = s*c_1*t(c_1)\\
t(c_2) = c_1*t(c_1)/c_2
$$
But that can't be right, can it? It's not even dependent on $s$ anymore.

Perhaps one potential problem is that $s$ is only linear for $c>1$; so maybe you cannot estimate $t(1)$ using that formula. I've thought of a way to correct for this, by devising this formula:
$$s*(c-1)+1 = speedup$$
This makes sure speedup is one for $c=1$, as you'd expect. With the modified formula, you get $1.46$, $1.23$, and $1.23$ for $s$. There is a greater variance in $s$, but not by much. So it seems like it could
be a correct model. Both models work for linear speedup of one. I tried to find more datasets of non-one linear speedup, but couldn't find any. So I can't confirm whether this model works universally. Assuming this model, we get:
$$
t(c_2) = \frac{t(1)}{s*(c_2-1)+1}\\
\text{given: } t(1) = t(c_1)*(s*(c_1-1)+1)
$$
This formula is at least dependent on $s$, as I would expect. But I feel like my corrected formula for $s$, from which this was derived, was rather arbitrary. For one thing, $s$ is undefined at $c=1$, even if it does make sure $speedup=1$. Secondly, the final equation for $t(c_2)$ is not very intuitive; given $s=.7$ you'd think $t(2)$ would get a $1.4x$ speedup, not a $1.7$ speedup.

What are your thoughts? What am I doing wrong here? What is the correct derivation?


texts: What is the difference between modulo and modulus?

texts:
Throughout my education in computer science, I feel like I've heard the terms "modulo" and "modulus" used interchangeably.  It looks like even Wikipedia claims that "modulo" is "sometimes called 'modulus'" (see the first sentence of the page on 'modulo').

I've looked into this issue a little and it seems that "modulo" finds singular use in modular arithmetic (e.g. "19 and 64 are congruent modulo 5").  In addition, I've seen the symbol % be referred to as "modulo."

Meanwhile, "modulus" appears to have several definitions, including "absolute value" and "constant factor" as well as referring to the "5" in "modulo 5."

Is it ever correct to use these terms interchangeably in the context of computer science?  Are they simply different types of words that represent the same idea (such as "run" and "runner")?  Are there important differences in other disciplines?

Bonus: Etymologically, what gave rise to these two terms?


texts: Methods to evaluate a system of written rules

texts:
I was trying to come up with a system that would evaluate bylaws for an organization as to determine their underlying logic.

I think a first-order predicate system would work for representing the rules, which could be translated from the text via part-of-speech tagging and other NLP techniques.

Is there a systematic way to interpret the first-order logic rules as a whole, or some type of ML architecture that would work as a second layer to find similarities between the elements.

For example,

  List of fun activities:

  golf
  coffee break
  pizza

  Bylaws:

  On Friday, we play golf
  On Friday or Saturday, we take a quick coffee break, and if it's Saturday, we get pizza

Conclusion: our group has fun on weekends

It sounds far fetched, but I'm curious if it's possible.  I also realize that perhaps more first-order logic would be a better fit for driving the conclusions of the second layer.


texts: P decision problem that potentially requires at least $\Omega(n \log n)$ in the Turing model?

texts:
Currently, it is not proven that $NP \geq O(n \log n)$ in the Turing Machine Model.

The weakness of this statement can be illustrated by NP-complete problems, which we think require way more time. But I'm looking for the easiest-to-solve decision problem in P that probably has $\Omega (n \log n)$ as lower bound in the Turing machine model (I say "probably", because proving it would be a scientific breakthrough). Such a problem would best illustrate the power of the statement "$NP \geq O(n \log n)$".

It inspired me to ask about a candidate: Deterministic linear time algorithm to check if one array is a sorted version of the other, but it may not be the simplest because Yuval pointed out it probably requires more than $O(n \log n)$ in the Turing machine model.


texts: Step by step of a modification of the Beame-Pitassi Algorithm

texts:
I am reading the paper Measuring the hardness of SAT instances by Ansótegui, Bonet, Levy and Manyà (Proc. 23rd AAAI Conf. on AI, pp. 222–228, 2008) (PDF). I am trying to understand the decision algorithm beame_pitassi described in the Figure 1 in paper and showed below. This algorithm searches for the space of an UNSAT formula.

I am studying that algorithm using the following formula $\Gamma = (a\vee b)(a\vee \lnot b)(\lnot a \vee c)(\lnot a \vee \lnot c)$. Below, the steps using this $\Gamma$.

function beame_pitassi
$proved := false$
$s:= 1$
while $s \leq 3$ and $\lnot proved$

$s = 1$
$<false,-> =$ try_strahler($\Gamma$, $1$, $[\,]$)

foreach $x \notin [\,]$ and $b \in\{true, false\}$

$<false,->=$try_strahler($\Gamma$, $0$, $[a\rightarrow
0]$)
$<false,->=$try_strahler($\Gamma$, $0$, $[a\rightarrow
0, b\rightarrow
0]$)
$<false,->=$try_strahler($\Gamma$, $0$, $[a\rightarrow
0, b\rightarrow
0, c\rightarrow
0]$)

$s = 2$
$<true,cut(b,t_1?,t_2?)> =$ try_strahler($\Gamma$, $2$, $[\,]$)

foreach $x \notin [\,]$ and $b \in\{true, false\}$

$<false,->=$try_strahler($\Gamma$, $1$, $[a\rightarrow
0]$)
$<true,hypothesis((a+b))>=$try_strahler($\Gamma$, $1$, $[a\rightarrow
0, b\rightarrow
0]$)

$s:=s+1$

I know that the steps of my example could be hard but these say that the algorithm stops when happens the next assignment $[a\rightarrow
0, b\rightarrow
0]$ for $\Gamma$. Specifically, when $[a\rightarrow
0, b\rightarrow
0]$ falsifies the clause $(a\vee b)$ of $\Gamma$.

For me the output of this example is

$\langle$ unsat, cut(hypothesis($a\vee b$), hypothesis($a\vee\neg b$))$\rangle$.

In other words two clauses ,$(\lnot a \vee c)$ and $(\lnot a \vee \lnot c)$, of $\Gamma$ are losses in the proof, please Is correct the steps that I make in that example? and Could you help to understand why these clauses are losses?


texts: What's the relationship of $n^n$ and $n!$ complexity with respect to EXPTIME?

texts:
We know that:

$k^n = o(n!)$
$n! = o(n^n)$

where $o$ refers to "little o notation" (i.e. bounds that are asymptotically not tight).

With that in mind:

Are there any defined or academically established classes for problems with complexity of at most $O(n!)$ and $O(n^n)$?
What is the set relationship for these classes of problems with respect to $\mathsf{EXPTIME}$ or e.g. $\mathsf{2\mbox{-}EXPTIME}$?


texts: For a given shape, find set of points with the maximum average distance

texts: Within some shape, I want to find a set of points where the distance between each point is maximized. This seems similar to sphere packing to me except that part of the sphere can be outside the shape.


texts: What does the $^*$ operator do in the theory of parsing?

texts:
I'm currently reading through Aho's "Theory of parsing, translation and compiling" on my own and I got a bit confused about the closure operator on language $L$ with alphabet $\Sigma$ ($L^*$). The book defines it recursively as follows:

\begin{align*}
1)\ L^0&=\{e\}\\
2)\ L^n&=LL^{n-1}\quad \text{for } n\ge1\\
3)\ L^*&=\bigcup_{n\ge0}{L^n}
\end{align*}

What sort of set does this operation define? It seemed to me that it defines something like "the set of all possible concatenations of strings of language $L$". There wasn't an actual example in the chapter, I can't figure it out.


texts: Maximum independent set given approximate oracle

texts:
Let $A$ be a polynomial time algorithm which receives a graph $G$ and returns a stable set $SA(G)$ of $G$ with the property: $\alpha(G) - |SA(G)| \leq k$, for some constant $k$.
Prove that $A$ could be used to determine, in polynomial time, a stable set of maximum cardinality in a certain given graph.

I have tried by taking a graph $G_1$ which is formed by disjoin union of $k+1$ copies of $G$. $\alpha(G_1) = (K+1) \alpha(G)$. I need to prove that
$|SA| = |SA(G_1)| / (k+1)$ in order to complete the proof.
But I got stuck at this point. Any hints or help would be appreciated.


texts: Quick sort worst case complexity improvement

texts: Can the worst case time complexity of quick sort be changed from $O(n^2)$ to $O(n\log n)$ by modifying it?


texts:
I ran into an interview two days ago and came across one strange definition of safe edge.
We are given an undirected weighted Graph $G = (V,E)$ with all distinct edge weights. Assume that the graph is connected.

Safe Edge Definition: if an edge $e \in E$ is not contained in any cycle, we called it a safe edge

Following is a theorem based on the above definition.

Theorem: All the safe edges must be in Minimum Spanning Tree (MST).

Please compare the definition of a "safe edge" on this interview with the classical definition of safe edge at all courses like here: MAIN SAFE EDGE THEOREM.


texts: Number of ways to connect sets of $k$ vertices in a perfect $n$ -gon

texts:
This is a copy of my post at Mathexchange.com, as my question is still not fully answered and I really wanna find a solution to this. Feel free to refer to there for useful comments and partial solutions:
https://math.stackexchange.com/questions/1294224/number-of-ways-to-connect-sets-of-k-dots-in-a-perfect-n-gon
Let $Q(n,k)$ be the number of ways in which we can connect sets of $k$ vertices (dots), in a given perfect $n$-gon, such that no two lines intersect at the interior of the $n$-gon, and no vertice remains isolated.
Intersection of the lines outisde the $n$-gon is acceptable. Obviously, $k|n$, and $n$ can't be prime because otherwise there will be vertices/dots left unconnected. The $n$-gon itself is an acceptable solution to a connection of $n$ vertices, and in the case of $k>2$, these aren't lines, but a set of connected lines, a sort of a network formed by connected planar graphs with straight edges with $k$ vertices, which are required to be vertices of the $n$-gon itself.
There must always be $S =\frac nk$ sets of lines. For $k=2$, there are exactly $\frac nk$ lines, and for $k>2$, there are exactly $\frac nk$, not lines but sets of such connected planar graphs.
Take for example $Q(6,2)$. We have a perfect hexagon. By brute-forcing with pencil and paper, I found that there are 5 ways to connect sets of 2 vertices (dots) such that no two lines intersect inside the hexagon and no vertice remains unconnected. Hence, $Q(6,2) = 5$.
The following image depicts the case of $Q(6,2)$:

For generality I ask about any amount of $k$ dots, even though I've recently found the solution for $k=2$.
Now let's move one step further:
Let $U(n,k)$ be the number of unique ways to connect sets of $k$ dots in a perfect $n$-gon, such that no two lines intersect, and rotational symmetry is neglected, i.e, every possible arrangement is unique and can't be formed by rotating another arrangement in any way. $U(6,2)=2$.
Note that $U(6,2)=2$ because the arrangements of the first line in the image are not unique, and can be formed by rotating one another. The same happens for the second line of arrangements. Hence $U(6,2)=2$.
I'm pretty clueless about both functions $U$ and $Q$, and I couldn't derive an algorithm or formula to any of them. Hence I'm posting this here.
I'm pretty sure there's a pure combinatorial approach to this problem, perhaps involving Polya's Enumeration Theorem (PET).
Is there an elegant solution to these functions? Can they even be solved for $k>2$?
Any light shed on any of the functions will be very much appreciable, as I haven't been successful in deriving a formula for any of them. Also, both formulas and algorithms will be great!
I can program in Java and Mathematica.
Thanks a lot in advance.
EDIT - Temporary Solutions + Relevant questions AND progress
$$Q(n,2) = C_{n \over 2}\quad\text{where}\quad C_n = \frac{1}{n+1} {2n\choose n}$$
And $C_n$ denotes the $n$'th Catalan number.
Now let us denote $W(n) = U(n,2)$. Can you find a formula for $W(n)$? Perhaps a connection between $Q(n,2)$ and $W(n)$?


texts:
I recently came across the concept of "forwarding pointer" and have not been able to find sources of a precise definition. In my case this was mentioned and briefly (but poorly) explained during a discussion on distributed systems.
Could you elaborate on the concept, its usual context(s) and possible other names by which this is also known as?


texts: How many languages exist over a finite alphabet?

texts:
I'm currently reviewing my Automata and Languages Theory course and I stumbled upon the following exercise exams.
Link

In "Exercises for ACS 1, Fall 2004, sheet 1", exercise 1 item C, the question is,

  How many languages exist over the symbol sets from (a)?

Question (a) describes the alphabets $S=\{a,b\}$ and $S=\{1\}$. The answer to the question as provided in the same link is

  In both cases, $|Σ^*| = \mathbb N$, that is, there are $2^{\mathbb N}$ many languages over these alphabets – indeed, over any finite alphabet there are $2^{\mathbb{N}}$ languages.

Here $\mathbb{N}$ is the set of all natural numbers. I am confused as to how the author came to this conclusion.

Update:
In my understanding, since {a,b} is a set of strings of {a,b}, it follows that it is a subset of {a,b}* or the set of all strings over {a,b}. So, as per set theory, the cardinality of a set containing the subsets of all strings over {a,b} = powerSet({a,b}*) whose cardinality is equal to $2^{\mathbb{N}}$. Is my understanding correct?


texts: Can the shortest path problem be solved using Monte Carlo Tree Search?

texts:
I think Monte Carlo Tree Search could be used to find the shortest path, but it seems that this method is only used considering win/lose outcomes in the simulation step.

If we consider the path length as the outcome for the simulation step, how would the back propagation work? It seems that one of the nodes along the optimal path could be penalized if a child ends up with long path in the simulation step.


texts: k-way set partition problem--dynamic programming solution

texts:
I was reading up on the set partition problem on this site of Wikipedia: https://en.m.wikipedia.org/wiki/Partition_problem
Among other things, they present a DP approach to solving the equal subset sum problem for 2 subsets by finding a subset that sums to half the total sum of the set. Below the algorithm they state that it is possible to generalize this algorithm to k subsets of equal sums but it is very impractical even for modest input sizes.

However I can't see how this generalization works: with two subsets we have the nice property that if we find a subset that sums to the half of the total sum then we know that the other subset also has to have the same sum and we can answer the question positively.

With the number of subsets bigger than two, however, I don't see how we can find a similar property: let's say the sum of all elements is $S$ and we want to split the set into $k = 3$ subsets. We could see if there is a subset summing to $S/3$, but I'm not sure if this lets us easily split the remaining elements summing to $2S/3$ into two equal parts.

How else could I approach this problem using Dynamic Programming?


texts:
I have a really specific problem to solve and i'm looking for an existing algorithm to help me (i hope i'm in the right section of stackExchange).

I would have to make "random" association between items but all association need to have to answer to specific conditions.

Below, an simple exemple in javascript.

INPUT

var items = [12, 32, 25, 11, 8, 2, 4, 3, 8, 9];
CONDITION

All couples sum need to be between "20"(include) and "27"(include).

OUTPUT

result = [[12,9], [11,9], [25,2], ...];

This is a really "simple" exemple. I need to implement this with at least 3 or 4 items by couples but the conditions is almost the same.

Is it an algorithm that existing to easly do this kind of stuff ? Or did i need to iterate all couples possibilities to pick up randomly after ? Even a way to iterate less for the generation of all couples would be nice.

Thank you a lot for your help.


texts:
Let's say I have a graph $|G|$ with $|E|=O(V^2)$ edges. I want to run BFS on $G$ which has a running time of $O(V+E)$.

It feels natural to write that the running time on this graph would be $O(O(V^2)+V)$ and then simplify to $O(V^2)$.

Are there any pitfalls to using such a "remove-the-nested-O" shortcut (not just in this case, but more generally)?


texts: Vapnik-Chervonenkis Dimension: why cannot four points on a line be shattered by rectangles?

texts:
So I'm reading "Introduction to Machine Learning" 2nd edition, by Bishop, et. all.  On page 27 they discuss the Vapnik-Chervonenkis Dimension which is,

  "The maximum number of points that can be shattered by H [the hypothesis class] is called the Vapnik-Chervonenkis (VC) Dimension of H, is denoted VC(H) and measures the capacity of H."

Whereas "shatters" indicates a hypothesis $h \in H$ for a set of N data points such that it separates the positive examples from the negative.  In such an example it is said that "H shatters N points".

So far I think I understand this.  However, the authors lose me with the following:

  "For example, four points on a line cannot be shattered by rectangles."

There must be some concept here I'm not fully understanding, because I cannot understand why this is the case.  Can anyone explain this to me?


texts:
Given two regular languages $A,B$ on the same alphabet $\Sigma$, I want to show that the following language is regular:
$$
\{a_1b_1 \ldots a_kb_k \in \Sigma^* \mid a_1,\ldots,a_k,b_1,\ldots,b_k \in \Sigma,a_1\ldots a_k \in A, b_1\ldots b_k \in B\}.
$$

However I simply do not understand how I'm supposed to do this. Simply put, my confusion is what $w = a_i b_i$ means. Is it concatenation? Does it mean that the word $w$ is the concatenation of $a=a_1\ldots a_k$ with $b=b_1 \ldots b_k$?


texts: Is there constraint on reducibility while defining $\Sigma_i^p$?

texts: Sanjeev Arora and Boaz Barak define $\Sigma_i^p$ to be the set of languages such that if $L\in \Sigma_i^p$ then for every $x \in L \Longleftrightarrow \exists u_1 \forall u_2\ldots Qu_i M(x,u_1,u_2,\ldots,u_i) = 1  $ where $Q_i$ is $\exists$ or $\forall$ depending on whether $i$ is odd or even and $M$ is a Turing machine that runs in polynomial time. But there is no mention whether the reduction of membership of $x$ to the truth value of the statement $\exists u_1 \forall u_2\ldots Qu_i M(x,u_1,u_2,\ldots,u_i) = 1 $ takes place in polynomial amount of time. Am I misunderstanding something ?


texts: I am trying to prove the theorem that ZPP = RP $\; \cap \; co-RP$. If $L \in \; \subseteq RP \; \cap \; co-RP$ then I can see that it belongs to $ZPP$. But I am unable to prove the reverse direction, as definitions of $RP$ and $co-RP$ don't include Turing machines whose expected running time is polynomial, but $ZPP$'s definition does. Am I missing something ? How should I proceed ?


texts: Complexity classes: What if different algorithms exist for different sizes of input?

texts:
If I understand(*) correctly, a decision problem is some function $f(x)$ whose function argument $x$ can be represented by data of a limited length (e.g. not an irrational number) and whose value is either 0 or 1.

If there exists some algorithm which can calculate the function value $f(x)$ in less than $\sum_{i=0}^{i_\text{max}}K_in^i$ steps (while $i_\text{max}$ and $K_i$ are constant) for every function argument with a length of $n$ (bits, bytes, digits, characters...), the decision problem belongs(*) to the complexity class $P$.

My actual questions:

Let's say for every "length" $n$ there is an algorithm that takes less than $\sum_{i=0}^{i_\text{max}}K_in^i$ steps to calculate $f(x)$ for a function argument $x$ which has a length of exactly $n$ (bits, bytes, ...).

(However, these algorithms do not necessarily work for every function argument $x$, but depending on the "length" $n$ of the function argument $x$ we have to use different algorithms.)

Would this imply that there exists one single algorithm that can calculate $f(x)$ for any argument $x$ in polynomial time?
If the answer is "no": Would the decision problem belong to the complexity class $P$ or not?
If either of the two answers is "yes": How is the situation in other complexity classes than $P$?

(*) Please excuse me if I use wrong terminology or my premises are wrong. I'm not a mathematician and my interest about complexity theory comes from the field of computing device development.


texts:
Given an array we need to find maximum equal sum $K$ subsequences, i.e. we want the sum to be maximized such that there are exactly $K$ non-overlapping subsequences each having the same sum.
Example:

A = [1, 2, 3, 4, 6] & K = 2
Maximum Sum Subsequence = 8 = [2, 6] & [1, 3, 4]

If, K = 3 and A = [1, 2, 3, 4, 6, 8, 9]
Maximum Sum Subsequence = 11 = [9, 2] & [8, 3] & [6, 4, 1]

It is not necessary that all the elements of the array need to be a part of the subsequences but each element can only be part of 1 subsequence.

I tried a brute force approach with Knapsack but that doesnt work.
Any better approaches or optimizations?


texts: Why do we set conditions f(n) ≥ n resp. f(n) ≥ log(n) the Time resp. Space Hierarchy?

texts:
In the Space (Time) Hierarchy Theorem and also fully space (time) constructibility of two function we have the condition: being greater than $log(n)$ (being greater than $n$).

Why do we have these conditions?


texts:
Is it possible to calculate the average between n numbers in a static random access array of some size in less than $O(n)$ time?
I know that the trivial approach is $O(n)$, but can I do it in less time using a data structure or a certain preparation? or both?
I am asking for hints, not a solution.

Note: The array is of some length. What and I mean by between is when given 2 indexes a and b, I have to calculate the average of the sub array $[a+1,b-1]$. And I have to keep it updated while the data structure is managed, that's why I said it was a dynamic set, in other words a random access array. I do not know of any restrictions, just asking if it's possible in less than $O(n)$.


texts: Genetic Algorithms - Tournament Selection

texts:
I know this should be a fairly simple concept but I have been Googling a lot and can't seem to find a definitive definition.

If we had the following random population:

[12,2,3,99,73,32,53,8]

And a tournament size of 3. What could be a possible outcome?

Is there lots of variations of Tournament Selection?


texts: How are CPU architecture and word size related?

texts:
I did lot of research on internet but couldn't get my answer. I want to know what is the difference between the word size and CPU architecture?

For eg.- I read that CPU of 32-bit architecture can address 2^32 memory locations. Now if we consider that one address points to a single byte, then it means we can have memory size of 2^32 Bytes. We can call it byte addressable memory.
Now, I also read that word size is the size of register in a CPU, i.e., it is the minimum no. of bits on which a CPU works upon.

So, help me understand here what is the word size of this computer organization? Is it 32-bit or 1 Byte (as memory is byte addressable)?

What if one address could point 2 Bytes of data instead of 1 Byte? What would be word size then?

Consider the following link.

GATE CS Questions on computer organisation

Question no. 3 from this link is as follows-

  A machine has a 32-bit architecture, with 1-word long instructions. It has 64 registers, each of which is 32 bits long. It needs to support 45 instructions, which have an immediate operand in addition to two register operands. Assuming that the immediate operand is an unsigned integer, the maximum value of the immediate operand is

Now, the very first line of the solution says-

  As machine has 32-bit architecture, therefore, 1 word = 32 bits = instruction size

How can we say that since CPU is 32-bit, word size is also 32 bit. Doesn't 32-bit architecture just mean that the no. of addresses in the physical memory is 2^32? And also doesn't the word size mean the size of memory each  of those 2^32 addresses would point to?


texts: Are all hypothetical machine models for calculating runing time of an alogrithm same?

texts:
Im learning about time complexity analysis, and cant seem to figure out why do we consider a hypothetical machine that takes 1 unit of time for arithemitic and logical instructions and 1 unit of time to for assignment and return statements.

Q) why does it have to be 1 unit of time?

Q) Also is it upto to the analyzer to define such parameters for hypotheical machine models or is there some sort "standard/convention" used instead ?


texts: Proving that a context-free grammar is unambiguous

texts:
I have to find an unambiguous context-free grammar that generates the following language. $$L= \{ w \in \{a,b\}^+ : |w|_a = |w|_b\}$$
I think I have found the context-free one, it should be this one.
$$S \to aS'bS'|bS'aS'$$
$$S' \to aS'bS' | bS'aS' | \lambda$$
Now I am stuck with proving whether it is unambiguous or not. I think it is but how should I do that?


texts: How to use Artificial Intelligence in Computer Chess

texts:
In some (historical) papers, chess has been referred to as the drosophila of artificial intelligence. While I suppose that in current research, the mere application of a search algorithm is at best advanced computer science, I believe that there are still area's where can apply (and practice) AI-techniques.

A simple example would be opening book learning where one can teach the program whether to use or to not use certain moves in the opening because the program is unsuited to certain types of position. We can use a form of re-inforcement learning and automate this: I suppose I could play the program against itself and increase the probability of winning lines and decrease the probability of losing lines.

The more complex example is to use a learning evaluation function (for example, one could tweak the values of piece-square tables). However, I'm thinking:

given all the noise due to there being an enormous amount of realistic positions (as opposed to the amount of realistic opening lines)
and with the cost (duration) of a computer chess game, and the need to play loads.

How can one do this effectively? (or should I look at other techniques, for example neural networks.)


texts:
So I was wondering something about the Chomsky hierarchy.

DFAs (and NFAs) accept regular languages, while NPDAs accept context-free languages.

Right-regular or left-regular grammars produce regular languages, while context-free grammars produce context-free languages.

Regular expressions represent regular languages - but is there a context-free equivalent?  i.e. is there some additional term we could allow to appear in a regular expression such that regular expressions with that functionality now represent context-free languages?


texts: why recursive languages does not come under Chomsky hierarchy?

texts:
why recursive languages does not come under Chomsky hierarchy ? why Chomsky did not classified
 it? any real life resemblance of recursive language something that i can connect it with like regular language are ones which needs finite memory or context free languages are those which can be parsed using single stack .something like that .


texts: Is $\{a^mb^nc^n \mid m,n \geq 0\} \cup \{b,c\}^*$ regular or not?

texts:
Show if $L = \{a^mb^nc^n \mid m,n \geq 0\} \cup \{b,c\}^*$ is regular or not.
My attempt:
I think the Pumping lemma won't work in that constellation, so I'm working with "The intersection of regular languages is regular".
Assuming $L$ is regular. I already know that $S=\{ab^* c^*\}$ is regular. I'll now look at the intersection $L \cap S$.
$$(\{a^mb^nc^n \mid m,n \geq 0\}\cap \{ab^* c^*\}) \cup (\{b,c\}^*\cap \{ab^* c^*\})$$
$$\{ab^nc^n \mid n \geq 0\} \cup \emptyset = \{ab^nc^n \mid n \geq 0\}$$
Which is not regular according to Pumping lemma. Is this idea correct?


texts: Why would $NP^ {SAT} \subseteq P^{SAT[O(\text{log }n)]}$ imply that $PH \subseteq P^{SAT[O(\text{log }n)]} $

texts:
I was reading the following paper by Jim Kadin, "$P^{NP[O(\text{log }  n)]}$ and sparse Turing complete sets for NP"

The main result is that if there is a sparse set $S \in NP$ such that $coNP \subseteq NP^S $, then $PH \subseteq P^{SAT[O(\text{log }n)]} $.

In the proof of this result he author claims that it is sufficient to prove $NP^ {SAT} \subseteq P^{SAT[O(\text{log }n)]}$ and this will imply that $PH \subseteq P^{SAT[O(\text{log }n)]} $.

I could not figure out why this is true. Perhaps this is trivial and there is some minor point (some inclusion of complexity classes) that I am missing. Please do point out why the above claim is true.


texts: Algorithm to get any spanning tree not necessarily a minimum spanning tree

texts:
Is there an algorithm to find a spanning tree. I know that there are $n^{n-2}$ of them and we have algorithms to find a minimum spanning tree.

But what if I just want any spanning tree? It doesn't have to be minimum.

For a graph with no edge weights, should I just assume that the edge weights are all 1 and then use a Kruskal's or Prim's algorithm for minimum spanning tree?


texts: Set cover problem with constant size subset

texts: Consider a variation of the set cover problem in which the size of the subsets is no larger than a constant $k$. Is this variation still NP-hard?


texts: How is the Time Complexity of a Function Problem different than its corresponding Decision Problem?

texts:
Every function problem has a corresponding decision problem, which is simply the graph of the function problem, according to

https://en.wikipedia.org/wiki/Decision_problem#Function_problems

which reads that the time complexity of a function problem and decision problem underlying decision problem "...may not be considered equivalent in some typical models of computation".  This seems to be the case with the Greatest Common Divisor decision problem, according to

https://en.wikipedia.org/wiki/Greatest_common_divisor#Complexity

So I'd like to use this as an example.  I am having a difficult time understanding why the complexity of the GCD function problem is different than its corresponding decision.  If the Decision Problem is simply the graph of the Function problem, which is solvable in under quadratic time, how could the decision problem be solvable only in polynomial time?


texts: Compute e^x given starting approximation

texts:
I have been looking for an algorithm to calculate $e^x$ to arbitrary precision (millions of digits).  The best way I know is to use Taylor polynomials.  However, the Taylor polynomial algorithm seems to have no way to enhance the precision of already existing estimates of $e^x$.

For example:

I already have an exact approximation for $e^{0.7}$ calculated to 1000 decimal places, but now I want an exact approximation of $e^{0.700000001}$ calculated to 100000 decimal places.

Because $e^{0.7}$ is very close to $e^{0.700000001}$, I should be able to use $e^{0.7}$ as a starting estimate for $e^{0.700000001}$.  However, using Taylor polynomials, I know of no way to input a starting approximation.

Does anyone know of an algorithm that efficiently converges to $e^x$ given an initial estimate?

To clarify, I'm looking for an algorithm that can actually surpass the accuracy of the given estimation.  For example, if I give it an estimate to 1000 digits, it should still be able to converge accurately beyond 10000000 digits.  This rules out the optimization $e^{0.70001} = e^{0.7} \cdot e^{0.00001}$.


texts: References on teaching introductory programming courses

texts:
As the new semester starts soon, I am interested in research regarding the teaching of introductory programming courses. I would like to improve my university course and I am looking for scientific papers on that topic.

One trend I have seen is that some students (a smaller group) are interested in computers or they have already some programming background. They are fine and learn a lot. But the majority of students struggle at the first step of programming (hard to set up Eclipse, a lot of errors at the beginning, etc.). Is this just my view or is this documented in literature?

I would like to make this 'first step' into programming as easy as possible for students. As a first start I found "A Gentle Introduction to the Art of Object-Oriented Programming in Java"


texts: find the union of all min cuts of a flow network

texts:
I'm trying to solve the following question :

  Given a flow network $N = (G=(V,E),c,s,t)$. Let $\mathcal F$ be the set of all minimum cuts. Prove that $\mathcal F$ is closed under intersections and unions, i.e. for every $ S_1,S_2\in\mathcal F , S_1 \cup S_2 \in \mathcal F$  and $ S_1 \cap S_2 \in \mathcal F $.

that part I took care of just fine using the min-cut-max-flow theorem.

the other part is the one that I had trouble with :

  Given a max flow $ f $,find $S_{\min} = \bigcap_{S\in\mathcal F} S \text{ and } S_{\max} = \bigcup_{S\in\mathcal F } S $.

I realized that when considering a min cut $(S,T)$ , and given the residual graph (which can be built from the given maximum flow) , every vertex that's reachable from $s$ (source node) , must be in $S$ , so I was able to use that to come up with an algorithm to find $S_{\min}$.

But as for finding an algorithm for $S_{\max}$, I'm kinda having trouble putting my finger on a property of a min cut edge, i.e. what does it take to be a cut edge (or for a vertex to be in $S$) of some min cut?

I'm not looking for the full answer but rather a hint.. any help is appreciated.


texts: Does there exist a context-free language $L$ such that $L\cap L^2$ is not context-free?

texts:
I can see that $L$ has to be context-free but not regular here as regular languages are closed under concatenation and intersection. But $L\cap L^2$ looks too weird. I couldn't think of any $L$ that gives rise to meaningful $L\cap L^2$.

Any hint would be appreciated!


texts: Finding a hamiltonianISH path in a graph

texts:
Problem statement

Given a graph of all the blue squares in the following image where each blue square is connected to other blue squares in all 4 cardinal directions.

Given any starting node.

What algorithm will allow for finding the longest(ish) path.

Considering that each node can only be visited once.

Considering that we don't care where the path ends.

Considering that speed is more important than necessarily visiting each node.

Example

I have traced an example of the desired result in the image below. As you can see, the path does not visit each node and that is fine. I'm looking for a fast algorithm that will give me one of the longest possible path on this graph. 80% coverage or more is what I'm shooting for.


texts: Does upgrading after all locks and before all unlocks violate 2PL?

texts:
2PL's rule says:

Upgrading of lock (from S(a) to X (a)) is allowed in growing phase.

But what if upgrading lies after the last lock and before the first unlock? Does it still count "in the growing phase"? For example, is the transaction below a 2PL?
begin
lock-S(X)
read(X)
lock-S(Y)
read(Y)
**upgrade(Y)**
write(Y)
unlock(X)
unlock(Y)
commit


texts: Catching ball - finding the maximum number of caught balls

texts:
I'm attempting to solve the following problem:

  Balls are falling from the sky. We know at which location (on a
  straight line) will each ball drop, and we know the time (in seconds)
  at which will the ball reach the ground. We are trying to catch them
  into a ball net, which we can move left or right, but each movement
  costs 1 second. The initial position of a ballnet is always on the left (position 0). We are allowed to > drop (not catch) $k$ number of balls.

  What is the highest score we can achieve?

My first attempt at solving this was a greedy algorithm:

if the |next ball position - current position of the ball net| > (time of the next ball - current time)
     then attempts++
     if attempts>$k$
           print game over
else
     current ball net position = next ball position
     current time = time of the next ball
     score++

however my algorithm doesn't take into consideration that sometimes it's better to sacrifice some number of balls in order to reach a higher score in the long run. This needs an approach via dynamic programming, I think.

Is this problem a known one so I can find some help? Could you help me with this problem? I can solve this in a greedy way, however I am failing to do it dynamically.

Thanks!


texts:
Let me start off by noting this is a homework problem, please provide only advice and related observations, NO DIRECT ANSWERS please.  With that said, here is the problem I am looking at:

  Let HALF-CLIQUE = { $\langle G \rangle$ | $G$ is an undirected graph having a complete
  subgraph with at least $n/2$ nodes, where n is the number of nodes in $G$
  }. Show that HALF-CLIQUE is NP-complete.

Also, I know the following:

In terms of this problem a clique, is defined as an undirected subgraph of the input graph, wherein every two nodes are connected by an edge.  A $k$-clique is a clique that contains $k$ nodes.
According to our textbook, Michael Sipser's "Introduction to the Theory of Computation", pg 268, that the problem CLIQUE = {$\langle G,k\rangle$ | $G$ is an undirected graph with a $k$-clique} is in NP
Furthermore, according to the same source (on pg 283) notes that CLIQUE is in NP-Complpete (thus also obviously in NP).

I think I have the kernel of an answer here, however I could use some indication of what is wrong with it or any related points that might be relevant to an answer.  This is the general idea I have so far,

  Ok, I'd first note that a certificate would simply be a HALF-QLIQUE of $\text{size} \geq n/2$.  Now it appears that what I would need to do is to create a verifier that is a polynomial time reduction from CLIQUE (which we know is NP-Complete) to HALF-CLIQUE.  My idea would be that this would be done by creating a Turing machine which runs the turing machine verifier in the book for CLIQUE with the additional constraint for HALF-CLIQUE.

This sounds correct to me, but I don't really trust myself yet in this subject. Once again, I would like to remind everyone this is a HOMEWORK PROBLEM so please try to avoid answering the question.  Any guidance which falls short of this would be most welcome!


texts: Generating a set of divergence-free basis

texts:
I'm trying to derive an algorithm that would generate a set of divergence-free vectors, which shall be used as basis vectors later on. Using a simple example, a 2D second-order divergence-free basis would look like this:

$$
\begin{bmatrix}
1 \\
0
\end{bmatrix},
\begin{bmatrix}
0 \\
1
\end{bmatrix},
\begin{bmatrix}
x \\
-y
\end{bmatrix},
\begin{bmatrix}
y \\
0
\end{bmatrix},
\begin{bmatrix}
0 \\
x
\end{bmatrix},
\begin{bmatrix}
x^2 \\
-2xy
\end{bmatrix},
\begin{bmatrix}
xy \\
-\frac{1}{2} y^2
\end{bmatrix},
\begin{bmatrix}
y^2 \\
0
\end{bmatrix},
\begin{bmatrix}
0 \\
x^2
\end{bmatrix}.
$$

So far, I have manually implemented these calculations, but it will be quite tedious to work it out for 3D cases and for higher order. As of now, my pseudocode for 2D case looks like this:

switch (order):
  order=1:
     // manually calculate vectors for first order
  order=2:
     // manually calculate vectors for second order
  [...]

I would imagine things to be nastier in 3D... Currently, I am trying both to derive the whole basis manually and to come up with an algorithm to do it. Any suggestions?


texts: NP-Hardness of Hamiltonian cycle with $|V|$ divisible by 3

texts:
Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph $G=(V,E)$  with $|V|$  divisible by 3 and DHAM3  be the problem of determining if a Hamiltonian cycle exists in such graphs. Are DHAM3 and SHAM3 $\mathcal{NP}$-hard?

What I tried is I proved that the problem of finding Hamiltonian cycle is in $\mathcal{NP}$ and that 3-SAT problem, which is $\mathcal{NP}$-Complete, is reducible to Hamiltonian cycle problem which makes it $\mathcal{NP}$-hard, but I am not sure what's the purpose of $|V|$ divisible by 3, does that change anything?


texts:
The PDA has to recognize the language $L = \{w\in \{a,b,c\}^* \mid |w|_a = |w|_b$ or $ |w|_a=|w|_b\}$.
Currently I have an automaton which recognises that language if $|w_a|=|w|_b$ xor $|w_a|=|w|_c$. It looks like this:

It is xor because it is going to empty the stack before it could check next letter's  occurence. My question is how can I divide this into two PDAs (one recognises $|w|_a=|w|_b$ and the other one recognises $|w|_a=|w|_c$) and take the union of those PDAs?  Or is there any better solution?


texts: What language can be created from a regular expression with nulls?

texts:
The usual regular expressions I have seen are those with non-null inputs (e.g. $a$, $b$). A few days ago, I saw, for the first time, a regular expression that has a null ($∅$) in it.

$$ r_{1}= (cε + d∅)^{*}, Σ = \{c,d\} $$

This confused me since I do not know how a language would be created from $r_{1}$.

What would a language created from a regular expression be like if that regular expression has a null (like $r_{1}$ above)?

Additionally, what would a language be like if the regular expression from which the language is created from contains $ε$ (for example, like $r_{2}=(aε)(bε)ε, Σ = \{a, b\}$, and again, like $r_{1}$ above)?


texts: Time analysis of $m$ search operation in a Splay tree of nodes who have subtrees of size at least $\frac{n}{\log n}$

texts:
I know that the Worst-case for $m$ search operations in a Splay-tree is $O(m\log n +n \log n)$
The thing I'm not sure of is how this runtime depends on the size of the subtrees of the searched nodes.
I tried reading the proof of this runtime to understand the relation between the size of the subtrees to the runtime but things don't add up so well.
Will be glad for any help.


texts: What are internal clustering index for binary data ? And if possible applicable to massive cluster ?

texts:
I was wondering what are the current existing internal clustering index for binary data.

I know already the silhouette and Davis Bouldin for euclidian space, i suppose they work as well in binary space using Hamming distance for example, tell me if i'm wrong.

We can use the distance to points from centroid per cluster as an indication compared to the average distance point to point, but the cost of the computation of the similarity matrix is a bit restrictive when it comes to deal with Big data so if it exist :

Any binary internal clustering index
Applicable to Big data
Other internal index even in euclidian space

Thank you in advance for your wise suggestions

Peace


texts: Determining recursive enumerability of given languages

texts:
I came across following problem:

  $L=\{M$ is a turing machine $M$ accepts two strings of different length $\}$
  $L=\{M$ is a turing machine $M$ accepts atleast two strings of different length $\}$

Which one Recursively Enumerable (RecEn)? Which one Recursive (Rec)?

I feel both are not recursively enumerable and hence not recursive. We may list strings in some order and run Turing machine on them. But we may never come across two strings of same length accepted by same TM. So we cannot answer both questions "accepts two strings of different length" and "acceptes at least two strings of different length". Am I correct? Also is my approach correct?


texts:
The PARTITION problem:
$\{\{x_1,...,x_n\}: \exists I\subseteq[n], \sum_{i\in I}x_i=\sum_{i\notin I}x_i\}$
is well known to be NP-complete.

  My question: does the partition problem remain NP-complete (as a promise-problem) if we are given that $\sum_{i=1}^n x_i=0$?.

A problem that arises in this assumption is that one can always take the empty-set, so we also need to require that $I$ is nontrivial.

Note that for the related SUBSET-SUM problem, it is easy to show that the problem remains NP-complete (reduce from subset-sum of positive numbers by adding the negation of the sum).

My guess is that the problem remains NP-complete, but no proof yet.


texts: Check for balanced parentheses in an expression in log-space

texts:
Given an expression (a word in the one-sided Dyck language), I want to write a program to examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[“,”]” are correct in the expression.  For example, the program should print true with begin-end pair of symbols indices for exp = “[()]{}{()()}” and false for exp = “[(])”.

The naive solution with a stack has O(n) time-complexity and O(n) space-complexity.  Can we solve this problem in O(log(n)) space-complexity?  In other words, can we parse Dyck languages in logarithmic space?


texts: Understanding the relations between O(g(n)), Θ(g(n)) and Ω(g(n))

texts:
I was reading the Cormen, Leiserson, Rivest and Stein textbook, Introduction to Algorithms.

The book explained the three asymptotic notations literally very well.
However, there was this paragraph:

  Technically, it is an abuse to say that the running time of insertion sort is $O(n^2)$,
  since for a given $n$, the actual running time varies, depending on the particular
  input of size $n$.

and this one:

  It is not
  contradictory, however, to say that the worst-case running time of insertion sort
  is $Ω(n^2)$, since there exists an input that causes the algorithm to take $Ω(n^2)$ time.

I understand why did the author said that "it is an abuse to say $O(n^2)$ is the running time", as there are the inputs with best cases causing linear time and there are also inputs with worst case causing quadratic time.
I don't understand why it is not contradictory to say that the worst-case running time of insertion sort
is $Ω(n^2)$. Isn't $\Omega(g(n))$ supposed to be the best running time? So should it not be $Ω(n)$?

It confuses me. Can you please explain why $Ω(n^2)$ is possible for insertion sort when it should be $Ω(n)$?


texts: Distance query in trees with integer edge weights (Constant time, linear space)

texts:
Consider an unrooted tree with integer edge weights. I'm looking for a linear space data structure which allows for constant time distance queries (finding the distance, i.e. the sum of edge weights, between any two vertices).

Is this possible? If yes, how? I have an idea that it should be possible using some Lowest-Common-Ancestor or Range-Minimum-Query approach.


texts: What's the average number of clauses modern SAT solvers can handle?

texts:
It's already known that size doesn't matter always (for SAT problems).

But is there evidence (from real data from: benchmarks or real cases) on how many clauses an average SAT solver can handle nowadays?

Another issue that derives is that once they find a solution, most don't stress the fact about finding alternative solution. Is there a reason?


texts: Can radix sort reach exponential time complexity?

texts:
For example, assume the input array is $$[121212,212121]$$
Say we are in base 10, so count sort will work in $O(n)$ time. We have 6 iterations which is approximately $n^2$. Is this a worst case example for radix sort?

If so, can I generalize this and say that given $k$ is the total number of digits, a worst case for the sort would be $\frac{k}{2}$ elements to sort?


texts: Closure of Star-Free Languages under Substitution

texts:
Let $L$ be a star-free language over finite alphabet $\Sigma$.  A substitution will be a map $\sigma : \Sigma \to \mathcal{P}(\Sigma^*)$.  It seems obvious that if $\sigma(a)$ is star-free for every $a \in \Sigma$, then $\sigma(L)$ will be star-free.
($\sigma(L) = \{ w_1 ... w_n | w_i \in \sigma(a_i) \land a_1 \ldots a_n \in L \}$)
Take a star-free regular expression for $L$, and substitute star-free expressions for $L_i$
for each $a_i$ in that expression.  The result will still be a star-free expression.

Now, my question is this: why is the following not a counterexample?
$\Sigma = \{ 0, 1 \}$. $L = 1^*$ and $\sigma(1) = 0^* 1 0^* 1 0^*$.
Both of these languages are star-free:
$L = L( (\emptyset^c 0 \emptyset^c )^c )$ and similar tricks can be given to show that $\sigma(1)$ is star-free.

Now, the reason it seems like a counterexample: a word in $L$ contains only 1s. The substitution replaces each 1 with a word from a language whose words contain exactly 2 1s.
So won't $\sigma(L)$ be the set of words with an even number of 1s, which is known to be non-star-free?

(Note: my proof suggestion of closure under substitution is a bit sketchy.  The star-free expression for $1^*$ only has 0s in it.  But I could then substitute
the star-free expression for $\sigma(1)$ under a complement, no?)


texts: Big O of multiple variables in a logarithm: is $(2n+m)\log(2n+m) = O((n+m)\log(n+m))$?

texts: I am computing the count of the amount of intersections between disjoint horizontal line segments and disjoint vertical line segments. The algorithm I have come up with runs in $(2n+m)\log(2n+m)$ time. I was wondering if the Big-O for this is $O((n+m)\log(n+m))$? I don't know how constants in the interior of logs with multiple variables could be bounded, if at all. How would I prove this?


texts: Which is the proper algorithm to figure repeated substrings of longest total length?

texts:
Given a string $S$ and a substring $T$, define the value of $T$ to be the total length (in characters) of all non-overlapping instances of $T$ in $S$.  In other words, the value of $T$ is the length of $T$, times the number of times that $T$ occurs in $S$ without overlap.

I need an algorithm that does the following:

Given a string $S$, find the substring $T$ whose value is maximal, out of all substrings of length at least two; the index of each location where $T$ appears in $S$; and the value of $T$ (the total number of characters across all of those occurrences of $T$).

You can assume the string $S$ is ANSI encoded, where each character is one byte.

Example:

String => "AOOISDF000923RJJASPDFIJJ1023ASPD499FJJDSJIK"

Has the following repetitions:
1 - "DF", two times, total characters (4)
2 - "23", two times, total characters (4)
3 - "JJ", three times, total characters (6)
...
N - "ASPD", two times, total characters (8)

The desired output would be ASPD, because it has produced the largest total amount of characters (8).

Is there an efficient algorithm for this problem?  Is there a search term or name for this that I could use to search for it, or papers in the literature that describe techniques for this problem?


texts: Finding first/last intersection in a set of lines

texts:
I am given $n$ lines, in the form $y=ax+b$, where

there are no two lines with the same $a$
no three lines intersect in the same point
no vertical lines

I need to find in time $O(n\log n)$ an $x'$ such that for any $x>x'$ there are no line intersections with that $x$ value.

For example consider the lines on the image above, the thick blue line is $x=0$, and the red line is $x=x'$.

Is that possible? Any hints or ideas on how to solve this?


texts:
I've a problem where I have to prove the following statements:

(i) if $SPACE(n) \subseteq P \implies SPACE(n^2) \subseteq P$

(ii) if $P = SPACE(n) \implies SPACE(n) = SPACE(n^2)$

For the Space Hierarchy Theorems we have that $\forall f(n) = o(g(n)) \implies SPACE(g(n)) \nsubseteq SPACE(f(n))$

Using this result and the statements (i) and (ii) I have to prove that (iii) $P \neq SPACE(n)$.

I'm using the following post as reference: https://mathoverflow.net/questions/40770/how-do-we-know-that-p-linspace-without-knowing-if-one-is-a-subset-of-the-othe/333956#333956

I suppose that I can use Thomas Klimpel's proof in the abovementioned link to prove the statement (i).
But how can I prove the statements (ii) and (iii)?

Accept my apologies for this question, but I'm a rookie in Theory of Complexity :)


texts:
I'm literally so confused on how to even start this problem of proving that the given language is not Context Free.

L = {a^i b^j c^k d^l | i = k and j = l}

I know that we have to find cases where it contradicts the three conditions of the pumping lemma in all cases, but I'm not good in doing so.

Thanks for the help!


texts: Decidability of Unary Languages / One-to-One Mapping

texts:
I'm trying to prove that there exists an undecidable subset of {1}* by showing a one-to-one correspondence between it and {0, 1}* (which would imply a one-to-one correspondence between their power sets), but I'm struggling with how to do the one-to-one mapping. Isn't it just surjective? That is, there's one unary representation of potentially many binary strings (e.g., 1 = 01 = 0000000000001).

What am I misunderstanding here? Or am I just taking the wrong overall strategy?

(This isn't homework; I'm reviewing for a midterm, and it's a little concerning I'm getting tripped up here)


texts: If a language has a regular grammar, is it regular?

texts:
If L has a regular grammar, is L always a regular language?

A regular grammar is a formal grammar that is right-regular or left-regular. Every regular grammar describes a regular language.

So would this answer be true?


texts: Why sum of two binary numbers cannot be determined in $NC^0$ but in $AC^0$?

texts: Why sum of two binary numbers cannot be determined in $NC^0$ but it can be determined in $AC^0$?


texts: Approximation algorithm for Feedback Arc Set

texts:
Given a directed graph $G = (V,A)$, a feedback arc set is a set of arcs whose removal leaves an acyclic graph.  The problem is to find the minimum cardinality such set.

I want to find out about is there some approximation algorithm around this problem.


texts: Complexity of set partition generation while equivalence relation is given

texts: Given a binary equivalence relation, R on a set A, Let P be the resulting partition. I want to generate the partition means each subset in the partition. What would be the fastest algorithm for this purpose? please help.


texts:
I've been stuck with this problem for 2 weeks. Any idea of how to aproach it?.

  Let $L$ be a list of $n$ different integer numbers, assume that the elements of $L$ are in the range $[1,750]$. Design a linear ordering algorithm to order the elements of $L$.

I already tried with insertion sort. But I'm not sure if my approach is right:

Construct an array of bits. Initialize them to zero.
Read the input, for each value you see set the respective bit in the array to 1.
Scan the array, for each bit set, output the respective value.

Complexity: $O(2n) = O(n)$

I also wanted to use radix sort but I can't understand how to apply it, any idea?


texts: Spliting strings into groups of similar strings

texts:
I would like to group a list of strings into groups of strings differing by max 1 character:

For instance, given:

[John, Alibaba, Johny, Alidaba, Mary]

I would expect three groups:

[John, Johny],
[Alibaba, Alidaba],
[Mary]

My first thought was about using some clustering algorithm with Levenshtein distance but that seems like an overkill to me.

Is there a better approach?