texts: Is this passage from the textbook Artificial Intelligence: A Modern Approach incorrect?

texts:
On page 383, section 10.2. of the Algorithms for Planning as State Space Search chapter of the textbook Artificial Intelligence: A Modern Approach, the following passage appears:

In this passage, the authors write that in the air cargo example they use there are $50^{10} \times 200^{50+10} \approx  10^{155}$ states.

Is this incorrect? Shouldn't there be $10^{50} \times 60^{200}$ states?

As far as my understanding of probability goes, there is a different state for all the different arrangements of the 50 planes, which can each be at one of 10 airports, which would give the result $10 \times 10 \times ... = 10^{50}$, and then the same reasoning applied to the placement of the packages on an airplane or at an airport gives $60 \times 60 \times ... = 60^{200}$, which together give  $10^{50} \times 60^{200}$.

Is the textbook incorrect or is my reasoning incorrect?


texts: When would best first search be worse than breadth first search?

texts:
I am studying best first search as it compares to BFS (breadth-first search) and DFS (depth-first search), but I don't know when BFS is better than best-first search. So, my question is

  When would best-first search be worse than breadth-first search?

This question is one of the back exercises in Artificial Intelligence by Rich & Knight, and it asks for an answer in terms of time & space complexity and allows you to define any heuristic function.


texts: Algorithm to find the intersection of non-convex polyhedra

texts:
Context:

I have two polyhedra, $A = V_1\times F_1$ and $B=V_2\times F_2$ where $V_i$ is set of vertices (which are just coordonate in $\mathbb R^3$) and $F_i$ is a set of faces (tuples of length $\geq 3$ such as $(i_1,...,i_k) \in F_i$ iff there is a face formed by the $i_1$-th,...,$t_k$-th vertices of $A_i$).
Then, if I want to draw a cube, I will have 8 vertices in $V$ and 6 tuples of length $4$ that define the vertices of each square that makes the 6 faces of my cube.

These are not necessarily convex (but at least they are connected).

The problem:

Find an algorithm that takes $A,B$ and return $C$ the intersection of the two polyhedra.

My research:

I found this on the stack network:
https://mathoverflow.net/questions/141703/intersection-of-polyhedra

But the answers focuses on collision detection rather than returning the intersection of the two bodies.

The other articles I found online seem also to be all about collision detection rather than intersection.

My attempts:

I first imagine to approximate polyhedra with voxels, since it is pretty easy to find intersections of 0-1 arrays. But In my case, I would need too many voxels, then it would lead to too much memory use.

I do not have any other idea to solve efficiently my problem.


texts: Is it impossible to truly emulate a system if its actual clock speed is the same?

texts:
As I understand emulation a rule of the thumb says that a computer must be around a order of magnitude more powerful to emulate another system without resorting to tricks. This is because for every clock cycle of the system to be emulated, the host machine must process that cycle in the correct time and also process its own cycles.

A Xbox 360 uses a 3.2GHz PowerPC Tri-Core Xenon processor, would this mean that emulating the console on a 3GHz PC CPU would be impossible, even if the host CPU was more powerful but not faster for clock cycles?

To give a more straightforward example. A i7 that runs at the same clock speed as a Pentium 4 will not be able to emulate the Pentium 4, even though the i7 is many times more powerful.

In addition, does this mean that to emulate the Xbox 360, The host computer must run at a speed of between 9GHz and 3.2GHz to be able to truly emulate a Xbox 360?

If this is the case, surely there must be a way around this limitation? If we had a host computer with 10x3GHz CPU's could this system use parallelzation to somehow emulate a 3 core 3.2GHz system.

Also the emulate should run at the speed that the user expected of the emulated system, I know if you slowed down the Xbox 360 on the emulator by a few times then it would be easier, I want to know if we can emulate a system at the speed it was meant to run.

If this is not possible does that mean that for emulation, clock speed is king? And there is no way around this? Even if your host machine had a thousand CPU's running at 2GHz it could never ever emulate a Xbox 360 at its native speed?

By the way I am sure this is in the domain of computer science. I am not sure exactly what it comes under but the simulation of a system within a system and inherent limitations is certainly applicable to computer science.

What about this: could a 4 core 3GHz i7 CPU emulate in proper time a 3.8GHz single core Pentium 4?


texts: Turing Machines: What is the difference between recognizing, deciding, total, accepting, rejecting?

texts:
I have seen a remark saying "we usually say that a turing machine accepts/rejects a string, while it decides a language" Is this correct?

As I have also seen places where we mention a Turing machine "accepting a language"

See comment on OP's answer here, then the answer by Jan Hudec : What is the difference between a TM accepting and deciding a language?

I have also seen the definition of total/decider to mean, the Turing machine halts on all inputs. Is this all inputs in the language the Turing Machine is defined over?


texts: How to feel intuitively that a language is regular

texts:
Given a language $ L= \{a^n b^n c^n\}$, how can I say directly, without looking at production rules, that this language is not regular?

I could use pumping lemma but some guys are saying just looking at the grammar that this is not regular one. How is it possible?


texts: What is Herbrand interpreration and model?

texts:
I was reading the book "Foundations of Logic Programming" written by J.W. Lloyd. In the book, there were definitions of interpretation and model, and when it comes to herbrand interpretation and model, I am having difficulties. It provided an example, but I did not understand it.

Example. Let $S$ be $\{ p(a), \exists x \lnot p(x) \}$. Note that the second formula $S$ is not a clause. We claim that $S$ has a model. It suffices to let $D$ be the set $\{ 0,1\}$, assign 0 to $a$ and assign to $p$ the mapping which maps 0 to true and 1 to false. Clearly this gives a model for $S$.
However, $S$ does not have an Herbrand model. The only Herbrand interpretations for $S$ are $\emptyset$ and $\{ p(a)\}$. But neither of these is a model for $S$.

In my understanding, by assigning 0 to $a$ and 1 to $x$ to the formulas of $S$ make them true:

$$ p(0) = true $$

$$ \exists x \lnot p(x)[x/1] = \lnot p(1) = true $$

Therefore, $\{ 0,1\}$ is a model for $S$
But I did not really understand how do we know $[a=0,x=1]$ is not a herbrand model for $S$.

I asked the question in Theoretical Computer Science section, however was advised to post in CS. Could anyone explain it to me?
Thanks in advance.


texts: "strongly relational m-consistency when the domains contain at most m elements implies satisfiability" plain wrong?

texts:
Wikipedia states

  A constraint satisfaction problem may be relationally consistent, have
  no empty domain or unsatisfiable constraint, and yet be unsatisfiable.
  There are however some cases in which this is not possible.

  The first case is that of strongly relational
  m-consistent problem when the domains contain at most m elements.

This would imply that any problem with domains of size m that is stongly m-consistent, is satisfiable. However on the same page they mention 3-colorability. It is NP-complete and consists of binary constraints on variables with domain size 3. Generally it should be possible to achieve strong-3-consistency in about $O(n^3)$, so the above statement should be wrong as it implies P=NP. What did they mean to say when the wrote the above statement? Or am I interpreting it in a wrong way?


texts: Why does Radix sort require stable digit sorts?

texts:
I'm reading the CLRS book and have a question about the following quote from the book.

  In order for radix sort to work correctly, the digit sorts must be stable.

Why is stability required? Wouldn't Radix sort still produce correctly sorted output even if there was no consistency in ordering of identical values, since Radix sort sorts on every digit position?


texts: DFA multiple accepting states to Regular expression

texts:
I am trying to find the regular expression that defines this DFA, I am finding this particular case difficult since it has multiple accepting states.

If I understand this DFA correctly, it recognises:

empty strings or strings with any number of b => b*

or

a followed by any number of b => ab*
or
aa followed by any number of b => aa(b*)

So the closest I have got is b*+(a+aa)+(a+aa)b* but I know this is not correct, since it doesn't recognise strings such aabaabab.

I have been using http://ivanzuzak.info/noam/webapps/fsm_simulator/ so I can see I don't know how to make the transition back to  Q0 from Q1 or Q2 when there is a b.

I took a look to How to convert finite automata to regular expressions? but the explanations are way above my current level of understanding.

Could anybody help me finding where I'm going wrong and how could I fix it?

Many thanks in advance.


texts: Which goes first stl or data structures and algorithms?

texts:
So I'm a newbie to c++. I know the basic concepts of c++ as I have already learnt c language. For competitive programming DSA is very important. But I don't know any STL functions.
Is it possible to learn DSA without knowing STL?
Which one is advisory to learn first(STL or DSA) so that it will be easy further?
Also suggest some good references for both stl and dsa.


texts: How come computer science books are so relaxed about specifying which set variables/values belong too?

texts:
How come computer science books are so relaxed about specifying which set variables/values belong too ?

I've read several books on algorithms like CLRS's Introduction to Algorithms, Sedgewick's An Introduction to the Analysis of Algorithms etc.

  How come these kind of books are so sloppy about telling which set values/variables belong too ?

To give some examples:

Introducing Big-O notation books don't mention the domain and co-domain of the functions $f(N)$ and $g(N)$. Neither, is it mentioned which set the constant $C$ belongs too.

Introducing Generation Functions nothing is said about the values of the sequence $a_0, a_1, \ldots$. In mathematics these are complex numbers, but nothing is said here.


texts: What is the name of a rooted tree whose nodes may have edges to their descendants?

texts:
A tree is a special kind a graph.

However, I came across a data structure which is a like a rooted tree, but where nodes are authorized to have direct links to any of their descendants. Shortcuts if you will.

This is not a tree anymore.

This is a specialized DAG that has more restriction. That is, it has a single root (or source)

Does this type of graph have a name?

CLARIFICATION:

By 'tree', I'm referring to the tree data structure, not a tree in graph theory. It seems crazy to me that such related objects have the same name even though they don't mean the same thing.
The tree data structure is always rooted but there are rooted DAG that are not trees.

{1→2, 2→3, 1→3, 4→2} doesn't qualify because 4→2 is an edge toward an ancestor, not a descendant.
{1→2, 1→3, 2→4, 3→4} doesn't qualify.

{1→2, 2→3, 1→3} and {1→2, 1→3, 2→4, 3→5, 3→6, 1→4, 1→6} both qualify.


texts: Multipoint evaluation of a given polynomial

texts:
You are given a polynomial of degree n. We have to find the value of the polynomial at n different points in O(n(log(n))^2). The answer should be modulo 998244353.
I have read various blogs on it and a research paper but none could help me implement it.
If anyone could provide some insight it would be really helpful.


texts: Modern vs. original formulations of Rice's theorem

texts:
Rice's theorem states that any nontrivial semantic property of Turing machines is undecidable.
However, when I opened “Classes of recursively enumerable sets and their decision problems” by H. G. Rice, I found a text far away from the above.  Which result in the article corresponds to the above (slightly informal) formulation?


texts: Finding the last substring in lexicographical order in O(n) time

texts:
Given a string s, return the last substring of s in lexicographical
  order.

  Example 1:

  Input: "abab" Output: "bab" Explanation: The substrings are ["a",
  "ab", "aba", "abab", "b", "ba", "bab"]. The lexicographically maximum
  substring is "bab".

More specifically, I am looking for an accompanying proof/intuition. I can find many solutions, but none provide a proof of their technique and I cannot convince myself.

source: https://leetcode.com/problems/last-substring-in-lexicographical-order/


texts: Can User Level Thread read/write Kernel thread?

texts:
As far as I read in a OS text book (Operating Systems by Silberschatz) Kernel mode is for privileged task, so it it true to claim that "User Level Thread can read/write Kernel threads" ?
Generally speaking, Is there any kind of protection between user and kernel level threads?


texts: Choosing Fitness function for float output in Genetic algorithm

texts:
I have a NN that has ten outputs. The output values range between 0 and 1. The elements in the target array are all zeros except one element, which is "one".

I am searching for a Fitness Function that will correctly evaluate (score) the Neural Networks.

Currently, I am trying to calculate the distance between the target and the output arrays. The issue is that at the beginning all my NNs return results that are very close to each other and I can't properly choose the fittest individuals.

For Example:

NN1 -> FF score:0.10030096 -> Rank?
NN2 -> FF score:0.09996143 -> Rank?
NN3 -> FF score:0.10015215 -> Rank?

Any suggestions?


texts: Context Free Grammar Prove Un-/Ambiguity

texts:
I know, it is not possible to decide whether a context free grammar is ambiguous or not. However, I am having a really hard time preparing for an upcoming exam in which I'll have to give a prove of un-/ambiguity for a given grammar.

Up until now,
the first thing I'd do is to look for a word (via try and error) which could be build up from more than just one tree. Despite the fact this takes quite some valuable exam-time, it hardly leads to a successful outcome for me. In addition I'm not really sure what to do if it actually is unambiguous.

What would be a proper way to prepare for such a problem without feeling like having to solve a pointless crossword puzzle you can not prepare for?


texts: Difference between intended interpretation and extended interpretation in first-order logic

texts:
I am currently reading "Artificial Intelligence - A modern approach" and I really do not get the difference between intended interpretation and extended interpretation in first-order logic.

Are extended interpretations all possible assignments from a symbol in my knowledge base to an object in the world? And is the intended interpretation the interpretation the "author" of the sentences wanted to have?

So when there is a symbol like "John" in my sentences does that mean that it really refers to the human being John in the real world (if I have intended interpretation).

And the extended interpretation could be: "John" in my sentences refers to the human being Mary in the real world.

Are the extended interpretations a set of all possible interpretations and is the intended interpretation one specific interpretation in this set?

So do I interpret my sentences either intended or extended?

And if I say in my interpretation that John and Mary (as constants) refer to the same object in my model can I unify them then, i.e. UNIFY(John,Mary) = {John/Mary}?


texts: Polynomial Time Algorithm for Steiner Tree Problem

texts:
I know about Steiner Tree Problem. It is stated as

  Input to Steiner Tree Problem is a weighted graph G and a subset T of the nodes (called terminal nodes) and goal is to find a minimum weight tree that spans all the nodes in T.

Can we give a polynomial time algorithm to solve the Steiner Tree Problem such that |T| ≥ n−1 where n is the number of nodes in the original graph. I've done a lot of RnD on it but it is still confusing. Can any one help me out?


texts: Relevant subtree and relevant leaf in Machine Learning Decision Trees

texts:
I'm currently studying Decision Trees and the definition of a decision tree in our course is somewhat obscure for me. Nowhere in other online definitions of decision trees do I find something about relevant subtrees and relevant leafs...

The course is based on the book Machine Learning from Tom Mitchell, so I'll have a look in that book for more information.

I wanted to know if someone can explain to me in English a relevant subtree and a relevant leaf...

If the question is too vague or abstract, I'll first read the chapter in Tom Mitchell's book and then come back to this forum.


texts: What is the correct time complexity of the following code

texts:
I was wondering what is the correct time complexity expressed in terms of big O on this type of loop:

for(i=1;i<=n;i++)
    for(int j=1;j*i<=n;j++)
        // O(1) code here

The inner loops will make $n + \frac{n}{2} + \frac{n}{3} + \dots + \frac{n}{n}$. I know that this type of formula is $O(n \log n)$, so is this the correct time complexity on this piece of code?


texts: Djikstra's shortest path vs Brandes algorithm for betweeness centrality

texts:
I have a couple of Python scripts that calculate various network measures.

Given a graph (G), the first script calculates the average shortest path from each node to all other nodes and stores this in an Nx1 matrix (L). An implemntation of Djikstra's algorithm from the NetworkX Python library is used for this:

for i in range(num_nodes):
    for j in range(num_nodes):
        dj_path_matrix[i,j] = nx.dijkstra_path_length(G, i, j)

L = np.sum(dj_path_matrix, axis=0)/(num_nodes - 1)

Given the same graph (G), the second script uses an implementation of Brande's algorithm in the NetworkX library to calculate betweenness centrality and stores this in an Nx1 matrix (BC):

BC = nx.betweenness_centrality(G, normalized=True)

My question is: why does it take so much longer to calculate L compared to BC?

The way I understand it, BC of a node is a measure of how often a shortest path travels through that node. As such, to calculate BC, surely you would need to calculate all possible shortest paths in the graph. And surely then, BC should take at least as long as L? Using my scripts, given the same graph, it will take a couple of seconds to calculate BC, but up to half an hour to calculate L.


texts: Is there an algorithm to find all connected sub-graphs of size K?

texts:
I was just wondering if there is an efficient algorithm that given a undirected graph G, finds all the sub-graphs whose size is k (or less)?

I searched around, and only found problems about finding the connected components. But I am interested in the smaller and more local connected sub-graphs.

To clarify, the graph of interest (road networks) has n vertices, and has a relatively low degree (4 to 10). I am interested in finding/enumerating all connected sub-graphs with size k(in terms of nodes), e.g. by listing the vertices of each. k is relatively small.


texts: Calculating product of totient functions

texts:
Suppose that i need to compute product $~\phi(1) \dots \phi(n)~$ modulo prime $500009$ as fast as possible. Memory limitations are rather tough: $64$ mb so i can't just keep all the values of totient function. $n$ can be as large as $10^9$ and time given is $2$ s.

My main idea is to somehow estimate the prime factors and their exponents in factorization of this product. And then apply fast modular exponentiation. But i don't understand yet how to do such estimation.

Any ideas are highly appreciated. Thanks in advance.

P.S.
This is not a hometask or a problem from a current contest. I'm just surfing number theory problem bank and solving them for fun.


texts:
Currently learning about topological sorting.
My teacher gave us this problem.

The answer given to us is : B,A,C,E,D,G,F,H in lexicographical order.

Why does the order go from B,A,C THEN go to E and then D IF it is in lexicographical order?
Also, can another topological sort of this graph be: B,A,C,D,E,G,F,H?


texts: Closure against the operator $A(L)=\{ww^Rw \mid w \in L \wedge |w| \lt 2007\}$

texts:
I would like your help with the following question:

  Let $L$ be a language, and operator $A(L)=\{\,ww^Rw \mid w \in L\ \wedge\ |w| \lt 2007\,\}$ where $x^R$ is the  reversed string of $x$. Which of the
  following statements are correct?

  If $L$ is regular so $A(L)$ is regular.
  If $L$ is a CFL which is not regular then $A(L)$ is CFL which is not regular.
  If $L$ is a CFL which is not regular, then $A(L)$ is a CFL which may or may not be regular.
  If $L$ is not a CFL then $A(L)$ is not CFL.

What does the fact that $|w|< 2007$ help me with the decision?
For (2) I can choose $O^n1^n$ and I get that $0^n1^{2n}0^{2n}1^n$, which is not regular, but for (3),(4) I can't find an examples to refute it. The answer is 3, but I can't understand why, since $A(L)= ww^R \circ  w$  but $ww^R$ is not regular.


texts: Maximizing the boolean combination of given real numbers with dependencies

texts:
Let $x_i,x_{ij}\in\mathbb{R}$ and $b_i\in\{0,1\}$ for all $i,j\in\{1,2,\ldots,n\}$ and $j>i$. I want to know which of all the possible boolean combinations make(s) the following expression maximal: $$\sum_i b_ix_i+\sum_{j>i}b_ib_jx_{ij}$$

I can think of greedy heuristics (for example, identify the $x_{ij}<0$ and then set either $b_i$ or $b_j$ to zero if $x_i<0$ or $x_j<0$, respectively), but these don't necessarily have always to give the best answer. Is there any optimal algorithm for this or, at least, an approximation one?


texts:
I'm trying to connect cylinders with a sphere in 3D smoothly.

The sphere is given by a single 3d point-diameter data and the cylinders
are given by point-diameter data as well for the start of the cylinder
and the end of the cylinder for each cylinder respectively.

I would like to describe the cylinder by a spline,
and potentially the sphere also by a spline.

I'm not too familiar with computational geometry,
thus I wonder if this "algorithm" might be reasonable:

Create spline data for sphere
Create spline data for cylinders
Create the sphere and cylinders
Calculate intersection between the splines of the cylinder with the sphere
"Remesh". By this I mean use the intersections from the 4th step as the  new vertices for the cylinders and sphere.

Best wishes,
S.


texts: Runtime of Divide and Conquer Flavored Bogo Sort

texts:
Here we propose a way to reduce Bogo Sort's runtime from factorial to exponential using a divide and conquer approach. This is something we have likely all pondered on extensively.

https://en.wikipedia.org/wiki/Bogosort.
Input: An unsorted array A[1...n].
Output: A sorted array.

Let's remind ourselves of why normal Bogo Sort's runtime is O(n!).

Let's say we were to randomly guess the smallest element of an array. What are our odds of guessing right? Our odds would be 1/n of course. Let's say we guessed right! Now let's try to randomly guess the second smallest element of an array, after guessing the first right. What are our odds of guessing right? Our odds would be 1/(n-1) of course.

$$\frac{1}{n}*\frac{1}{n-1}*\frac{1}{n-2}\; * \;... \;*\; \frac{1}{n-n+1}$$
Expectation is n!

Let's use a Divide and Conquer strategy on Bogo Sort to improve the runtime. We will use a modified Merge Sort to achieve this. We recall that merge sort merges two sorted arrays recursively. Can Bogo Sort take advantage of the fact that we are merging two already sorted arrays? Let's say we were to randomly guess the smallest element of two sorted arrays. We know that the smallest element of both can only ever be the first element of one of these two arrays. If we randomly guess from just the first two smallest elements in each array, what are our odds of guessing right? Our odds would be 1/2. This sounds better than 1/n, but let's look at an example recurrence tree.

Example Recurrence Tree:
n = 4               brackets [ ] represent a merge being performed.

$$[\frac{1}{2}*\frac{1}{2}*\frac{1}{2}*\frac{1}{2}]$$
$$[\frac{1}{2}*\frac{1}{2}]\;+\;[\frac{1}{2}*\frac{1}{2}]$$
$$[\frac{1}{2}]+[\frac{1}{2}]+[\frac{1}{2}]+[\frac{1}{2}]$$

[Depth 0] Expectation is 16
[Depth 1] Expectation is 4 + 4 = 8
[Depth 2] Expectation is 1 + 1 + 1 + 1 = 4

Note, that in our base case we only need sort two values, guess between two values, a total of n times.
From the above, we see the expected runtime of D&Q Bogo Sort:

Runtime: $$O(\sum_{i=0}^{log(n)}2^{\frac{n}{2^i}} * 2^i)$$
Recurrence: $$T(n) = 2T(n/2) + O(2^{\frac{n}{2^i}} * 2^i)$$ i++ each recurrence

  I need help confirming the runtime. My assumption originally was that
  the runtime is simply O(2^n). However, I believe I need a log( ) in
  there somewhere. I am unsure how to apply the Master Theorem to O(2^n) in my
  hypothesized recurrence:

$$2T(\frac{n}{2}) + O(2^n)$$

We have successfully reduced Bogo Sort from factorial runtime to exponential runtime using divide and conquer. Let me know how I can improve my analysis.


texts:
I stumbled across the optimization problem described below and I am looking for how to approach it efficiently. I have the feeling that the problem at hand might be known, but I was not able to find its name or further information on it. So any help to find an efficient algorithm for its solution or a pointer to the name of the problem at hand would be very helpful.
Given $ n \times m $ matrix $ M $ of integers from $ [0, w) $ and a set $ P $ of $ w $ points (i.e. tuples of indices in the matrix),
find a permutation $ M' $ of the values of $ M $, such that the global distance function $ f(M') = $
$ \sum_{i=0}^{n-1}{  \sum_{j=0}^{m-1} } {  \left(i - x\left(P[M'[i, j]]\right)\right)^2 + \left(j - y\left(P[M'[i, j]]\right)\right)^2  } $ is minimal.
Explained in a different way, consider an image with $ n \times m $ pixels, where each pixel is of one of $ w $ distinct colors. We then want to rearrange the pixels such that all pixels of the same colors from a group around the seed point of the same color. We are allowed the swap the colors of pixels as long as the total number of pixels for each colors stays constant. Below you find an example of the resulting image from a random initial image with a hundred equally likely color as starting point located around randomly pixed seed points. The result was obtained by iteratively picking two points at random and swapping them if the global distance function after swapping is reduced. Doing this for millions of times approaches (at least a local) optimum depicted in the images. However this approach is rather slow for larger values of $ n $ and $ m $. So I am looking for a faster solution to obtain the result. Also a non-discrete solution where polygons would describe the final areas would be appreciated. I was also considering Voronoi tesselations (which can be computed much faster), however they do not work in my case due to the fixed area constraint (i.e. the colored sections should be of equal size in this example).


texts: Minimizing the total variation of a sequence of discrete choices

texts:
My setup is something like this: I have a sequence of sets of integers $C_i (1\leq i\leq n)$, with $|C_i|$ relatively small - on the order of four or five items for all $i$.  I want to choose a sequence $x_i (1\leq i\leq n)$ with each $x_i\in C_i$ such that the total variation (either $\ell_1$ or $\ell_2$, i.e. $\sum_{i=1}^{n-1} |x_i-x_{i+1}|$ or  $\sum_{i=1}^{n-1} \left(x_i-x_{i+1}\right)^2$) is minimized.  While it seems like the choice for each $x_i$ is 'local', the problem is that choices can propagate and have non-local effects and so the problem seems inherently global in nature.

My primary concern is in a practical algorithm for the problem; right now I'm using annealing methods based on mutating short subsequences, and while they should be all right it seems like I ought to be able to do better.  But I'm also interested in the abstract complexity — my hunch would be that the standard query version ('is there a solution of total variation $\leq k$?') would be NP-complete via a reduction from some constraint problem like 3-SAT but I can't quite see the reduction.  Any pointers to previous study would be welcome — it seems like such a natural problem that I can't believe it hasn't been looked at before, but my searches so far haven't turned up anything quite like it.


texts: How to ensure connectedness in a masterless gossip protocol?

texts:
This is a theoretical question about how gossip protocols work; I am not asking about any specific implementation or piece of software.

I've read the wikipedia page https://en.wikipedia.org/wiki/Gossip_protocol on gossip protocols, and the idea seems like an excellent way to avoid having a master node in a cluster (say, because traffic is too heavy to all direct it through any particular node, no matter how quickly that traffic is redirected). I would imagine you could register a new node by pointing it to any particular node in the cluster, having the knowledge of the new node shift through the cluster through gossip, and have it make a few edges with a few neighbors.

I would assume that no particular node has complete knowledge of the entire network, as the cluster could be large enough to make this prohibitive.

However, in this case one would imagine that through random behaviors, nodes adding and dropping, eventually the network could become disconnected (in the graph-theoretic sense), after which point it could never become reconnected without outside intervention.

Is this correct? And if so, what can be done about it? I can think of a few answers but I feel like none of them are satisfactory, and I wonder if one of them is standard, or there is another possibility I haven't thought of:

There is a central registry, and new nodes must contact this registry in order to be connected to the cluster. But this seems to invalidate the masterless idea, even if it's only registration traffic that flows through it.
Every node knows about every other node (modulo the time spent propagating the nodes' information). This prevents disconnectedness and makes a lot of things easy to implement, but puts an upper limit on the size of the cluster (or a lower limit on the power of the connecting machines).

Are either of these "standard?" Is there another possibility I didn't think of? Wikipedia doesn't address it and my googling hasn't gotten me any kind of answer.

Note: Apologies if this fits better on stackoverflow; it seemed like a tossup as to which site it better belonged on, as it's theoretical and certainly within the scope of CS research, but based on the lack of relevant tags below, it may not be part of the typical scope of the site.


texts: Can Eve impersonate Alice or Bob by using a replay attack?

texts:
For my computer science study, I have to design a replay attack (if possible) for the following authentication protocols.

I use the standard security protocol notation.
In these protocols, $A$ is Alice, $B$ is Bob and $E(A)$ is for example Eve impersonating Alice. $K_{AB}$ is a shared secret key only Alice and Bob know, $K_{AB}\{x\}$ is the data $x$ encrypted with this key, and $N_A$ and $N_B$ are fresh random nonces generated by $A$ and $B$. We assume that Eve cannot simply break the encryption.

a)
$1. A \rightarrow B : A, K_{AB}${$N_A$}
$2. B \rightarrow A : B, N_A, K_{AB}${$N_B$}
$3. A \rightarrow B : A, B, N_A, N_B, K_{AB}${$N_A, N_B$}

For this, I designed the following replay attack:

$1. A \rightarrow E(B) : A, K_{AB}${$N_A$}
$2. E(A) \rightarrow B : A, K_{AB}${$N_A$}
$3. B \rightarrow E(A) : B, N_A, K_{AB}${$N_B$}
$4. E(B) \rightarrow A : B, N_A, K_{AB}${$N_B$}

Is this gonna work?

The next example is this:

b)
$1. A \rightarrow B : A, N_A, K_{AB}${$A, N_A$}
$2. B \rightarrow A : B, N_B, K_{AB}${$B, N_A, N_B$}
$3. A \rightarrow B : K_{AB}${$A, B, N_A$}

I have no idea how to solve this one. Could you please help me with that?


texts: How do Context Sensitive Grammar systems work?

texts:
The Quest: Use context sensitive grammar (CSG) to produce an equal N number of repeating a, b, and c using the alphabet {a, b, c}. For example, if N = 5 use CSG and a, b, and c to produce a result such as 'aaaaabbbbbccccc'.
What I (think I) understand so far:

CDG == CSG (context sensitive grammar)
Linear bounded automata are a form of Turing machine
Pushdown automata are related in function to a computing stack
CSG uses linear bounded automata to find and replace portions of text or language
The above automata result in stacks that should be worked through sort of like code
Steps in the stack are called productions
A production is basically a substitution rule
Productions go opposite the expected direction, pasting the text after the arrow in place of the text before the arrow
The automata apparently iterate through until the first step is met, and then works through the automata stack until it is done

What I know I do NOT understand:
(I don't expect these questions to be answered - they are only included for detail why I can't seem to solve The Quest)

Is the stack iterated over to produce multiple repetitions?
For example, having some programming experience I expect that to produce a result for The Quest I could start with abc and end with aaaabbbbcccc by creating [if ... then] style statements like:
 a → aa
 b → bb
 c → cc

If starting with {abc} then the above might produce {aabbcc}, iterated again to produce {aaabbbccc}, and again to produce {aaaabbbbcccc}

Can production replacements happen while skipping above productions? In the above attempted solution, I would not expect to skip a step or do them out of order, but steps 3 and 4 on the wiki appear to be doing exactly that.

Can infinite loops result? In comparing the above example to the wiki example, it would seem to me that completing the first step would cause an infinite loop in which 'a' repeats indefinitely because the first 'a' is converted to 'aa', then the second 'a' that now exists needs the rule to be applied and so on resulting in a → aaaaa∞.

I have been researching for hours, and all searches thus far have resulted in only complicated answers that assume I already have a deep understanding of language processing. I find it ironic that Chomsky's system for describing how language works is apparently so difficult to communicate.
In short, I need programmer syntax to explain how automata stacks should be laid out in order to solve The Quest. Thank you for reading.


texts: Finding two words of lengths that are relatively prime in a regular language?

texts:
Given a regular language $L$ over a unary alphabet $\Sigma = \{ a \}$.

How to decide whether there are two words $w,w' \in L$ such that
the length of $w$ is relatively prime to the length of $w'$ ?


texts: Improve minimum spanning tree with new edge, with better running time than O(|V|)?

texts:
The problem gives a MST $T$ and a series of $Q$ queries, each one with a new edge $e = \{u,v\}$ such that no edge between $u$ and $v$ exists in $T$. For every query, we have to improve $T$ with $e$ and print the new weight of $T$.

The best I can do is run a DFS ($O(|V|)$) to find the current path $P$ between $u$ and $v$, and find the heaviest edge $e_\text{max}$ in $P$. If $w(e) > w(e_\text{max})$, we improve $T$ removing $e_\text{max}$ and inserting $e$. The overall running time for a test case is $O(Q|V|)$.

Does anybody know an asymptotically faster algorithm for this problem?


texts: Given a moving ball in a grid, which squares does the ball reach?

texts:
You are given an m x n grid. A dimensionless ball is placed at the centre of one of the grid squares and starts moving in one of 4 directions: north-east, north-west, south-east, or south-west. The ball continues moving until it reaches the edge of the board at which point, it bounces back in accordance with the laws of Physics.

Given m, n, the initial position and direction (NE / NW / SE / SW) of the ball, is it possible to determine whether the ball will ever reach a specified target grid square (x0, y0)?

It is possible to answer the question by exhaustively tracing the movement of
the ball, but is there any easier more efficient alternative? Any pointers to related literature would also be much appreciated.


texts: Confused about constructing the "failure table" in Knuth-Morris-Pratt algorithm

texts:
I'm trying to learn how the "failure table" is constructed in the Knuth-Morris-Pratt algorithm since it seemed nontrivial to me that you could do it in $O(k)$ time (where $k$ is the length of the pattern, $W$). To be clear, we let the failure table $T$ be a length $k$ array where $T[i]$ is the length of the longest proper prefix of $W$ which is also a suffix of $W[1]\cdots W[i]$.

I was trying to understand it better by reading the following code:

    vector<int> T(pattern.size());
    T[0] = 0;
    int j;
    for (int i = 1; i < pattern.size(); i++) {
        j = T[i - 1];
        // Find largest j s.t. T[:j+1] == T[i-j:i+1]
        while (j > 0 && pattern[j] != pattern[i]) {
            j = T[j - 1];
        }
        T[i] = (pattern[j] == pattern[i]) ? j + 1 : j;
    }
    return T;

The part I'm confused about is why pattern[j] == pattern[i] is enough to guarantee that $T[i] = j + 1$. I was trying to prove this inductively but have had no luck. I've phrased the problem as follows:

Suppose $W[1]\cdots W[T[i - 1]] = W[i - T[i - 1]]\cdots W[i - 1]$. If $W[i] == W[j]$, then is it true that $W[1]\cdots W[j] == W[i - j + 1]\cdots W[i]$?

I can't make any headway with this, nor can I see why it should be true. It still seems like we have to check $W[\ell] = W[i - j + \ell]$ for all $\ell = 1...j$. I can't figure out how to use the inductive hypothesis to prove this result. Do I have to use strong induction (where we assume all prior steps are true and not just the previous step) to prove this?


texts:
Consider all strictly decreasing functions from {1,2,3,4} to {1,2,3,4,5,6}, or in other words, all functions defined on {1,2,3,4} such that f(1)>f(2)>f(3)>f(4). Draw a decision tree so that the leaves are in lexicographical order when read from left to right. Then answer the following questions:

(a) What is the rank of 5431?

(b) What function has rank 0?

I have been looking all over the internet but I could not find a good resource for decision tree. I would be very appreciate it if anyone could show me how to approach this problem. Thanks


texts: How many layers should a neural network have?

texts:
Are there any advantages of having more than 2 hidden layers in a Neural Network?

I've seen some places that recommend it, others prove that there is no advantage.

Which one is right?


texts: Does a graph always have a minimum spanning tree that is binary?

texts: I have a graph and I need to find a minimum spanning tree to a given graph. What is to be done so that the output obtained is a binary tree?


texts: How can I prove $P \rightarrow (Q \rightarrow R)$ is equivalent to $(P \wedge Q) \rightarrow R$

texts:
I'm a freshman CS student at my university and i'm struggling with understanding my professor through his thick accent. I've asked him to explain the proof for this multiple times and still have trouble comprehending what he's trying to tell me.

The question is:

Prove that:  $P\rightarrow(Q\rightarrow R)$ is equivalent to $(P \wedge Q) \rightarrow R$

He wants us to prove it using math and goes on to tell me that $P \rightarrow (Q \rightarrow R) = \neg P \vee (\neg Q \vee R)$

From that point on, I was completely lost and unable to follow along.


texts: Decision problems with verifiable proofs but not in polynomial time

texts:
NP is a class of decision problems for which one can present a "certificate" that can be verified in polynomial time.

Are there any decision problems that have such "certificates" that can be verified faster than solving the problem(*), but verifying still takes superpolynomial time(*)?

(*) using the best-known method


texts: Application of set theory subjects as ordinals, forcing, generic filters in software engineering

texts:
I am going to teach a course in set theory for software engineering students.
I am going to talk in this course about: ordinal numbers, partial orders, well ordering, generic filters and maybe some cardinal invariants (such as $\mathfrak b$, $\mathfrak d$). I might also give a gentel introduction to forcing theory.

I was asked by the head of the department, to add to this course some application of this theory to software engineering.

Since my main area is math and not computer science, I don't have an idea for such an application.

Any ideas for such an application? If there is I would be greatfull if you could give me a detailed source.

Thank you!


texts: What are good algorithms for virtual machine benchmarking?

texts:
I am comparing execution efficiency of the same code compiled to JVM and Node, locally and on AWS Lambda. Not looking for precision, but just a rough notion of performance in difference virtual machines and execution environments.

I started with Fibonacci flavors (recursive, tail recursive, iterative, memoized, ...) are there any algorithms that would be particularly adequate for systems benchmarking?


texts: Find the smallest summed distances by uniquely pairing elements of one set to elements of another set

texts:
As input I have two sets of points in RN, typically for large N, for example N=40. Supose both sets have m elements:

S = s1 ... sm

T = t1 ... tm

Semantically both sets are equal, but due to noise (of whatever kind) on the R^N points, elements which should be semantically the same still have a distance larger than 0.

What I want to find is m tuples (si, tj) such that the sum of distance(si, tj) is minimized and such that sk and tk exactly occur once in the set of tuples for k=1...m. Basically (i,j) have to be chosen as towers on a chessboard which can not hit each other while minimizing the summed distances.

In other words, I want to find an onto one-one map between S and T which 'is sort of an identity map, but robust to noise'. We assume that the distance measure is a good indication of how similar elements are.

Basically I need to find a permutation of 1...N, and hence I think this problem is either NP-hard or NP-complete, since it 'feels' quite similar to the TSP; however I have not been able to rewrite the TSP problem to a subset of my problem here.

Is this problem realistically solvable for large N? Is there a name for this problem? What would be a feasible solution? Is there another criteria which might be better than the summed distances?

I thought of a greedy approach, let D be a matrix of the distances, dij = distance(si, tj).

T = {}
while D is not empty:
    (i,j) = argmin-(i,j) dij
    append (i,j) to T
    set row i and column j to infinity.

This does not result in the optimal solution, but finds a solution. Would this be my best bet? Should I use simulated annealing, or is it overkill?

PS: from my point of view, this is just a minor problem in a bigger ML problem, however, I am very much interested in the CS background of it.


texts: Applying the Parameter Theorem to show that a function is not computable

texts:
Show that $g: \mathbb{N} \to \mathbb{N}$ such that
  $$g(x)=\begin{cases} 1 & \text{if halt}(2833,x) \\ 0 & \text{otherwise} \end{cases}$$
  is not computable.

We know that

$$g(x)=\begin{cases} 1 & \text{if }\Phi_x(2833)\downarrow \\ 0 & \text{if }\Phi_x(2833)\uparrow \end{cases}$$

How can I use the parameter theorem to reduce $g$ to $\text{halt}(x,x)$? I'm very confused.


texts: Expected space consumption of skip lists

texts:
What is the expected space used by the skip list after inserting $n$ elements?

I expect that in the worst case the space consumption may grow indeﬁnitely.

Wikipedia says space $O(n)$.

How can this be proven one way or another?


texts: Show that checking if there exists word not containg patterns from list is in $PSPACE$

texts:
There are given:

alphabet $Σ$ with some symbols $a,b$.
list of forbidden patterns

Result:   Is there exists word of form $a\Sigma^*b$ such that it doesn't contains (as subword) any of word from
list (list contains many words, expressed by patterns).   Show that
this problem is in $PSPACE$.
Example to better understand patterns:
$bbaaacb$ contains a word $a??c$, but $aacba$ doesn't contain $a??c$,
where $?$ is some special symbol in $\Sigma$
So patterns are like words with holes (?)

My approach is follwing:
Let $k$ will be max length among all patterns.  There is no sense to consider longer words than $k$ because if exists word longer than $k$ such that it contain none of words from forbidden list then also exists word of length $k$.
So, using the fact that $PSPACE = NPSPACE$ we can guess word of length $i=1...k$ and check if it contains subword from forbidden list. Matching is easy to do in $NPSPACE$.
I am not sure about corectness of using nondeterminism. What do you think ?


texts: How to calculate the number of weights for a CNN?

texts:
Can somebody help me with the formula needed to calculate the number of weights for a CNN, using the following sample question as the basis for it?

Suppose we have a convolutional neural network with a 5x5x1 input
volume, followed by one convolutional layer with 5 filters that have a
2x2x1 receptive field, followed by one fully connected output layer
with 5 neurons.  How many weights does the network have in total?

Any help appreciated because I keep getting the wrong answer. I think the first part is:
5 * (5 * 5 * 1) + 5
And this gives 130, it might be completely wrong anyway I am doing:
filters * (5 x 5 x 1) + filters
For the second part (2 * 2 * 1) with five filters I get:
filters * ( 2 * 2 * 1) + filters = 25
So now I have a total value of 155 and after this I am unsure how to factor in the output neurons and arrive at the answer (which I know is 430).


texts: Is a Turing Machine able to reduce a grammar by chomsky hierarchy?

texts:
If given a grammar, for example, a context-sensitive (type 1) can it always be "reduced" to a equivalent context-free grammar (type 2) and so on for grammars type 2 to "reducing" and getting a type 3?

How can I prove or show that this is undecidable? (if this is the case)

I know that is undecidable whether a context-free grammar has a equivalent regular grammar. And so on for a sensitive-context having a equivalent context-free grammar, but don't know how to generalize it.

P.s.: When I say "reducing" I mean the lower level in Chomsky Hierarchy, considering type 0 the top and the lowest is the type 3.


texts: Understanding proofs Lemma 11 & 10 in this specific Computer Science Scheduling Paper

texts:
I'm having a hard time wrapping my head around the proofs Lemma 11 and Lemma 10 (Pages 10 and 11) in this paper called: Preemptive and Non-Preemptive Real-Time UniProcessor Scheduling.

Generally the proofs have very few steps in between and I can't seem to understand how the author continues from one step to another. Therefore, I would be very gratefull in a more step by step detailed explanation of the proofs mentioned.

Thank you in advance!


texts: Are there any countable sets that are not computably enumerable?

texts:
A set is countable if it has a bijection with the natural numbers, and is computably enumerable (c.e.) if there exists an algorithm that enumerates its members.

Any non-finite computably enumerable set must be countable since we can construct a bijection from the enumeration.

Are there any examples of countable sets that are not computably enumerable? That is, a bijection between this set and the natural numbers exists, but there is no algorithm that can compute this bijection.


texts: For every 'evil' regex, does there exist a non-evil alternative, or is the devil in the grammar?

texts:
Apparently, ReDos attacks exploit characteristics of some (otherwise useful) regular expressions ... essentially causing an explosion of possible paths through the graph defined by the NFA.

Is it possible to avoid such problems by writing an equivalent 'non-evil' regex?  If not (thus, the grammar can't be handled in practical space/time by an NFA), what parsing approaches would be better?  Why?


texts:
If we've got this expression:

FGa

where F and G are functions (as well as a, of course; but let's treat a as a constant).
It must be understood that:
first apply F taking G as input; then apply the previous result with a as input. This is

FGa = (FG)a

conventionally expressed:

( F(G) )( a )

Or is it this instead:

FGa == F(Ga) == F(G(a))

Thanks.


texts:
Given a planar graph $G=(V, E)$

I am looking for a max cut algorithm with the following conditions : some vertices are in one  of the partition sets?

Is the algo is still polynomial ?

I mean a selected subset of vertices should be in one set of the parttions.


texts: PAC learnability given information about the expectation of the training/true error

texts:
Let $ \mathcal{X} $ be a domain set, $ \mathcal{Y}=\{0,1\} $ and $ \mathcal{H}$ an arbitary hypothesis class.

Assuming that there's an algorithm $ \mathcal{A} $ such that for every distribution $ \mathcal{D} $ realizable by $ \mathcal{H}$, it holds that
$ \mathbb{E}_{S \sim \mathcal{D} ^M}[L^{0-1}_{\mathcal{D}}(\mathcal{A}(S))] \leq \mathbb{E}_{S \sim \mathcal{D} ^M}[L^{0-1}_S(\mathcal{A}(S))]+\epsilon_m$ where $ \epsilon_m \rightarrow0 $.

Does that mean that $ \mathcal{H} $ is PAC-learnable?

($L_\mathcal{D}(h) $ is the true error of hypothesis $h$ with respect to the 0-1 loss function)

Well, I think that it's not, but I lack the knowledge to put a finger on the exact reason why.

My intuition is that even though $ \epsilon_m \rightarrow 0 $, there still may be an arbitrary gap between $ \mathbb{E}_{S \sim \mathcal{D} ^M}[L^{0-1}_{\mathcal{D}}(\mathcal{A}(S))] $  and $ \mathbb{E}_{S \sim \mathcal{D} ^M}[L^{0-1}_{\mathcal{S}}(\mathcal{A}(S))] $. Thus, we still don't know how approximately good $ \mathcal{A}(S) $ is.

Can I deduce any promises whether $ \mathcal{A}(S) $ "probably" good (something about $\delta$)?

There's no need for formal proof. Rather, intuition will be appriciated.


texts: LTL: Show $\neg(aUb) \Leftrightarrow \neg b U (\neg a \land \neg b) \lor G \neg b$

texts:
I got as far as
\begin{align}
w \vDash \neg (a U b) &\Leftrightarrow  \neg (w \vDash a U b)
\Leftrightarrow \neg (\exists_{i\geq0} : w^i \vDash b \land \forall_{0\leq k < i} : w^k \vDash a)  \\
&\Leftrightarrow \forall_{i\geq0} :  \neg(w^i \vDash b) \lor \exists_{0\leq k < i} : \neg(w^k \vDash a)
\end{align}

but got stuck.

If you could offer some advice as on where to start I would very much appreciate it. Thanks in advance


texts: Finding $t$, $r$ and $w$ in Cache - Direct Mapping

texts:
I had a question in my past System Architecture exam and I am not sure how to solve it.

Question was this:

  Consider a 16-bit addressable memory and a direct-mapped cache sized 64 bytes. MAR is 10 bits and a block in memory is 8 bytes sized. Find $t$, $r$ and $w$ (they are Tag, cache index, and block offset respectively.)

Can you show steps of solution of this and such questions? Should I divide cache size by 2 since it is 2 byte addressable? Thanks.


texts: Confused by extremely high autocorrelation

texts:
I have the following python code

x = [100.0 for _ in range(1000)]
for i in range(1, len(x)):
     x[i] = x[i-1] + (2*randint(0, 1)-1)*step_size
import numpy as np
print np.corrcoef(x[:-1], x[1:])

I am getting extremely high correlation values, over 99.9%, more precisely

[[ 1.          0.99785636]
 [ 0.99785636  1.        ]]

Does anyone know what's going on? How can I get such large autocorrelation? Can anybody help me get better intuition and understanding of this?


texts: Solving Subset Sum Without the Use of Dynamic Programming

texts:
I am looking for algorithmic techniques to solve the Subset Sum Problem in pseudopolynomial time. There is, of course, a textbook dynamic programming approach for Subset Sum. Have any other algorithmic techniques (Randomized, Linear Programming...) been successfully applied to this problem?

In [1], the authors state that "[T]the only algorithm known to solve subset sum (in time polynomial in the numbers involved) is dynamic programming" (page 3). This paper, however, is 8 years old and it might be possible that some progress has been made in the recent past.

[1] Reid Andersen, and Uriel Feige. Interchanging distance and capacity in
probabilistic mappings. Available at https://arxiv.org/abs/0907.3631v1


texts: Is the While programming language with bounded number of variables Turing complete?

texts:
In our lecture it was proven that WHILE-Programs are turing-complete. In short a WHILE-Program only allows the following:
Variables             x1,x2,...  (initially all 0 and can only be positive)
Constants c           0,1,2,3,...
Assignment            xi := c
Addition/Subtraction  xi := xj + c, xi := xj - c
while-loops           while(xi != 0) { ... }

Now we restrict the Language to k-VARIABLE-WHILE meaning that only a bounded number of variables can be used.
Is 100-VARIABLE-WHILE turing-complete? I think it isn't but I am not quite sure which function I can construct that needs more than 100 variables.


texts: Algorithm to find piecewise circular curve around object made of non-overlapping circles

texts:
Introduction
I have an object which consist of loosely packed, non-overlapping circles, of radius r.
Part of such an object is seen below, the object consist of the bold blue circles, and it extends further than shown on the figure.
The dashed blue circles of radius 2r (concentric with the bold blue circles) make up a unique piecewise circular curve around the object. The curve consist of all the dashed pieces of arc not overlapped by any bold blue circle or dashed blue circle. It is marked in green on the figure.
That green curve is what I want to find.

Inputs and constraints
Given a point P on the green curve, and the centers (x,y) of all circles, I want to find the green curve shown on the figure.
I don't need to find the curve surrounding the whole object, which is very large (10k-10M circles), just part of it. If the green curve is a parametric curve with parameter t, I just need to find it for p < t < q centered on the point P.
The object constantly grows as more circles are added to it, and each time a circle is added I need the green curve centered on the point P, which is the location of the newly added circle.
A complexity of O(n^2), for finding the green curve, where n is the number of circles, would kill the simulation, for which this is needed.
I am hoping to find something which is O(p-q), i.e. linear in the length of arc I want to find.
Current suggestions for algorithms
First of all, most problems with O(n^2) complexity can be reduced to O(1) by utilizing lookup grids, which keep a list of circles currently residing in a given square region.
Intersections from scratch
Circles close by the point P are found via the lookup grids, and all intersections between all circles are calculated. All intersections which lie inside a bold or dashed circle are invalidated/removed (e.g. the red intersections on the figure) since these can never be the intersections lying on the green curve. All intersections belonging to circles with only one intersection left are discarded as well, since circles with only one intersection on the perimeter contribute with zero arc length. Finally the remaining intersections (e.g. the green intersections on the figure) are used to construct the parametric green curve.
Maintaining a list of perimeter circles
If an ordered list of the circles sitting in the perimeter is kept (i.e. --15-13-2-0-7-8-6-5-9-12-- for the figure) one could from the point P find circle #8, and from circle #8 find the the sequences 7-0-2-13-14 and 6-5-9-12. From these two sequences one could easily compute the parametric curve by calculating the intersections between neighboring circles, and discarding interior intersections. The challenge with this algorithm is to update the perimeter list each time a new circle is added. As an example of the challenge imagine a circle added between #5 and #12, touching one of them. This circle would remove #9 from the perimeter list changing it from -6-5-9-12- to -6-5-P-12-, and this is just a very simple example. The number of cases needing to be covered quickly gets out of hand.
Any other suggestions?
Do you have any suggestions other that the two mentioned, or do you have an improvements to the two methods?


texts: Graph Has Two / Three Different Minimal Spanning Trees?

texts:
I'm trying to find an efficient method of detecting whether a given graph G has two different minimal spanning trees. I'm also trying to find a method to check whether it has 3 different minimal spanning trees. The naive solution that I've though about is running Kruskal's algorithm once and finding the total weight of the minimal spanning tree. Later , removing an edge from the graph and running Kruskal's algorithm again and checking if the weight of the new tree is the weight of the original minimal spanning tree , and so for each edge in the graph. The runtime is O(|V||E|log|V|) which is not good at all, and I think there's a better way to do it.

Any suggestion would be helpful, thanks in advance


texts: Can the semantics of a numeric hierarchy be faithfully represented in Haskell?

texts:
I am trying to represent a fragment of a number hierarchy using the Haskell concepts of value, type, and type class. I would like the Haskell code to reflect the mathematical semantics $\vdash ((x \in \mathbb{N}) \land (\mathbb{N} \subset \mathbb{Z}\subset \mathbb{Q}) \Rightarrow (x  \in \mathbb{Q}))$. In words, given that the set $\mathbb{N}$ of natural numbers is a subset of the the set $\mathbb{Z}$ of integers and integers are a subset of rationals $\mathbb{Q}$, we can deduce that every natural number is an rational number. I omit the constraint that natural numbers are actually a proper subset of integers.

Below is my attempt at relating the math and Haskell semantics. I am unsure whether a class is a set of types as stated by GAST (Section 3.5) and hence a type can be considered as an element of a class $(T \in TC)$.

Note it is possible that $V_1=V_2$ (e.g. 1:Nat=1:Int)

Below is my flawed attempt to capture the mathematical meaning using Haskell.
I am aware that implementing rationals would lead to a situation where rationals were represented by both a type and a type class (not good!). Please note for research purposes I am restricted to only using values, types,and type class. I am not intentionally seeking to impose Object Oriented class semantic on Haskell.

data Natural = One | Suc Natural deriving Show
data Integers = Zero | Succ Integers deriving Show

class RationallNumbers x where
  plus::x -> x -> x

instance RationallNumbers Integers where
 plus  x  Zero = x
 plus  x  (Succ y)  = Succ (plus x  y)

instance RationallNumbers Natural where
 plus  x  One = Suc x
 plus  x  (Suc y)  = Suc (plus x  y)

twoPlusTwoNat = plus (Suc One)  (Suc One)
twoPlusTwoInt = plus (Succ (Succ Zero))  (Succ (Succ Zero))

To sum up my question is:

Can the numeric hierarchy described be represented in Haskell using the semantic concepts  of values, types, and classes?

Related questions: A mathematical (categorical) description of type classes, Is there a model theory for Haskell type classes?


texts: Algorithm - True shortest path for triangulated 3d-surface

texts:
I need to find true shortest path between two points.
true means that shortest path can be laid both through the vertices, and through the edges.

Input

Set of triangles, given by coordinates of 3D-points.
Source and target points.

Output

Sequence of 3D-points representing a true shortest path from source to target.

I found video with visualization here. But I couldn't find ready algorithm, so I tried to create my own. Please make my algorithm review and let me know whether it is correct or it has issues. Also I will be gratefull if you have ready algorithm.

My algorighm

Find the shortest path via only vertices (E.g. by Dijkstra).
Get triangles (faces) that go along the path. In the next steps we will consider vertices that belong only to these triangles.
Find another vertices that can lie on true shortest path but are not known vertices. These are the points that are placed on edges.

foreach startVertex in vertices
{
    foreach finishVertex in vertices
    {
        // Create line segment between two vertices.
        lineSegment = ToLineSegment(startVertex, finishVertex);

        // Make lineSegement-projection on edges.
        // Return points that are the intersection of the projection and the edges.
        additionalVertices = FindIntersectWithEdges(lineSegment);
        result.AddResult(additionalVertices);
    }
}

Find the shortest path via all vertices that received in previous two steps (E.g. by Dijkstra).


texts: Can we say we reduced a rule if we reduced an equivalent set of smaller rules?

texts:
I have constructed an SLR(1) parsing table with the following rules.

S -> S + S + S (rule 1)
S -> S + S (rule 2)
S -> y

Is reducing rule 2, then shifting + and y, then again rule 2, equivalent to reducing rule 1? Can I claim to have reduced by rule 1, even though I did so indirectly?


texts: A Good Resource for Christofides' Heuristic

texts:
Is there an explanation Christofides's Heuristic for solving TSP which does not simply state the algorithm and go ahead to prove the bound?

To be specific:
(Disclaimer : I am an engineer who knows very little about graph theory but need this for a logistics course)

I understand that I first create an MST. So far, so good.
Now, I need to find a perfect minimum weight matching on all odd degree nodes. I have no clue what this is; googling this tells me this is a set of edges containing maximum $n/2$ edges such that no node is shared by 2 sets. I don't see why I am doing this..... I am not even sure I understand what this statement means.
Now, I need to merge the MST and the matchings to create a "multigraph" and then find an Eulerian tour on this. No clue what I am doing here.
Run the shortcut algorithm exploiting the triangle inequality. (No clue what happened till now and this obviously then makes no sense either)

Can someone point me to a good resource with possible examples and illustrations for why Christofides works in a language that isn't full of graph theory terms (or alternately, provide me an answer here)?

I have already looked at :

A Berkeley PDF
Wikipedia


texts: Graph theoretical approach to compare n pair of variables along a set of interval

texts:
I am dealing a bioinformatics problem and need help in approaching it in the right direction.

I have a set of variables that represent different kinds of genomic data and are real valued. I am trying to compare all these different variables among two species (though in the future I might be interested in generalizations to more than 2 species). What I need to do is to develop a graph theoretical method to calculate an entropy measure (or a better evolutionary distance measure) among all different genomic interval and cluster the pairs according to a high/low entropy measure.

So in genomics in the case of multiple species/two species there would be genomic regions which have a similar DNA sequence (known as orthologus regions). These regions would have a epigenetic/epigenomic mark associated with them. Such marks generally affect the gene expression/the overall chromatin make up of the genome or chromosome. What I want to do is identify regions of orthologus DNA which have high evolutionary conservation and high epigenomic conservation. I also want to identify regions of DNA between 2 or multiple species which have high evolutionary and epigenomic conservation or low evolutionary conservation and high epigenomic conservation and vice versa. What I want to do at the end  is to develop a method that would help ,make multi-species /pairwise comparison at the end. Since I am not a formally trained Computer Scientist I don't know what would be a good approach/algorithm to use.

PS: epigenomic data would generally be in the form of counts (normalized to RPKM (https://wiki.nci.nih.gov/pages/viewpage.action;jsessionid=5265E39473A073390CF868D3E56E619A?pageId=71439191). While RPKM of epigenomic signals is available for a span of regions (say 200 base pairs) the evolutionary conservation data is available for every base of DNA (the evolutionary conservation value of a base lies between 0 and 1)


texts:
I have a question of understanding about the Delta Rule:

$\Delta w_i = (y - \hat{y}) \times x_i$

Why does $x$ have to be multiplied again after the difference? If the input is $0$, the product of $w$ and $x$ remains $0$ anyway. Then, it should not matter if the weight changes with an input of $0$.

Let us take the following example:

$w_i$ = the ith weight of the weight vector
$\Delta w_i$ = the change in weight $w_i$
$y$ = the desired output of the neuron for the learning example
$\hat{y}$ = the actual, calculated output for the learning example
$x_i$ = the input

Step $t$:

Input $x = \begin{bmatrix} 1 & 0 & 0 \end{bmatrix}$
Random weights = $\begin{bmatrix} 0.1 & 0.1 & 0.1 \end{bmatrix}$
Scalar product $\to 0.1$
Step function outputs $1 \to \hat{y} = 1$

BUT we want as output $y = 0$
So the weights have to be adjusted as follows:

Step $t+1$:

$\Delta w_0 = (0 - 1) \times 1 = -1$
$\Delta w_1 = (0 - 1) \times 0 = 0$
$\Delta w_2 = (0 - 1) \times 0 = 0$

$w_i^{new} = w_i^{old} + \Delta w_i$

New weights: $ \begin{bmatrix} -0.9 & 0.1 & 0.1 \end{bmatrix}$
Scalar product = $-0.9$
Output $(y = 0)$

You can totally skip the multiplication by $x$, can't you?
Because at the latest when the scalar product is created, the weight which is multiplied by $x = 0$ is still not included.
So why multiply by $x$ in $\Delta w$?


texts: Mutation and crossover operations in discrete differential evolutionary operations?

texts:
I need to use discrete differential evolutionary algorithm for assigning discrete values from set size $L$ to vectors of size $D$ where $L$ could be smaller, equal or larger than $D$. Elements of vector $X$ could take the same values of other elements.  My question is if we have a population of size $NP$ with each vector $X$ in the population of size $D$. How do we actually apply the mutation operand:

$$V_{j,i}^{G+1} = X_{j, r_1}^{G} + F\cdot (X_{j, r_2}^{G}-X_{j, r_3}^{G})$$

where $i$, $r_1$, $r_2$, $r_3$ are references to vectors in $NP$ and none is equal to the other, $J$ is an index in vector $X$, and $F$ is a random number between $0$ and $1.2$.

Suppose $X_{r_1}^{G}$ is equal to $\{4, 1, 3, 2, 2, 0\}$ and  $X_{r_2}^{G}$ is equal to $\{2, 2, 3, 0, 4, 2\}$ and $X_{r_3}^{G}$ is equal to $\{1, 2, 3, 3, 0, 1\}$
Could anyone explain in detail the steps (through example if possible) on how to get the mutant vector $V_{j,i}^{G+1}$


texts: What kind of language does the following DFA accept?

texts: can anyone please describe the language this FA accepts? thank you


texts: Algorithm for solving planar constraint problem ("Pokemon Go monster finding")

texts:
[Note: This problem was inspired by Pokemon Go. I will first explain the problem in mathematical terms, then explain the connection to Pokemon Go. My goal is not to cheat in the game. If I wanted to cheat, better information would be available more easily.]

Suppose there are $N$ points (the "unknown points") in a plane, call them $n_1,\dots,n_N$, with unknown coordinates. Moreover, we have $M$ measurements taken at known locations $m_1,\dots,m_M$.

Let $\text{dist}(m_i, n_j)$ be the (generally unknown) Euclidean distance from measurement point $m_i$ to the unknown point $n_j$.

For each measurement $m_i$, we have the following information:

The exact coordinates of each unknown point $n_j$ for which $\text{dist}(m_i, n_j)<d_\text{min}$ for some known constant $d_\text{min}$; and
A list of all indices $j$ for which $\text{dist}(m_i, n_j) < d_\text{max}$ for some known constant $d_\text{max}>d_\text{min}$, sorted by $\text{dist}(m_i, n_j)$.

Is there an efficient algorithm for calculating the areas of the plane where the unknown points, or a given unknown point $n_j$, can be?  The algorithm is given the coordinates $(X_i,Y_i)$ of the measurement points, the measurement information listed above, and the number $N$ of unknown points; the goal is to narrow down the region of possible locations for each of the unknown points $n_1,\dots,n_N$ as much as possible.

The Pokemon connection:

In Pokemon Go, an augmented reality game, the goal is to find Pokemons in nature. Every now and then, the game shows the Pokemons in a "visible range" ($d_{min}$) of the player's position. Moreover, it has a "Pokemon finder" which shows a list of nearby ($dist<d_{max}$) Pokemons, sorted by distance. (It's also supposed to show an approximate distance as one, two or three footsteps, but apparently there's a bug and it always shows three footsteps.)


texts: As the title states, I would like to know what a hashing routine is. I found online about hashing algorithms but I heard it, being used in a different context.


texts:
I'm studying about representing fractional numbers as floating-point values. It is going to be an 8-bit representation. Somewhere in the text, it is said that:

  "We use the first bit to represent the sign (1 for negative, 0 for
  positive), the next four bits for the sum of 7 and the actual exponent
  (we add 7 to allow for negative exponents), and the last three bits
  for the mantissa's fractional part"

Now the question is:
Why "7" -and not another value- must be added to the actual exponent ?


texts:
I need to show that $H_1(x)$ defined as follows is partially computable.

\begin{equation}
H_1(x)=
\begin{cases}
1 \;\;\;\;\;\text{ if } \Phi(x,x) \downarrow \\
\uparrow \;\;\;\;\; \text{ otherwise}
\end{cases}
\end{equation}

The thing is my textbook, that is  "Computability, Complexity, and Languages" by Davis, Sigal and Weyuker, lacks of examples and walkthroughs so, personally, I find hard solving even the easiest exercises.

I think I can prove $H_1(x)$ partially computable, if I can find a program $\mathcal P$ that executes it.

First of all for the Universality Theorem:

$$\Phi(x,x) = \psi^{(1)}_{\mathcal P}(x) \text{ and } \# (\mathcal P)=x$$

so I can write a program that computes $\psi^{(1)}_{\mathcal P}(x)$:

\begin{array} \\
\;\;\;\;\;\;\;\;\;Y \gets 0 \\
\;\;\;\;\;\;\;\;\;\text{IF } X \neq 0 \text{ GOTO } A \\
[E] \;\;\;\text{ GOTO } E \\
[A]\;\;\;\; Y \gets Y+1
\end{array}

I don't know if I am on the right track. I would greately appreciate every comment, suggestion, nudge in the right direction, because I really feel kind of lost.

Attempt #2: First of all I am so very sorry for not providing you enough details. Basically:
$$\Phi^{(n)}(x_1, \ldots, x_n, x_{n+1}) = \psi^{(n+1)}_{\mathcal P}(x_1, \ldots, x_n, x_{n+1})$$

in plain English $\psi^{(n)}_{\mathcal P}(x_1, \ldots, x_n)$ is the value of the output at the terminal snapshot; $\Phi^{(n)}(x_1, \ldots, x_n, y)$, where $\#(\mathcal P) = y$  is the universal program $\mathcal U_n$, which works as an interpreter, it keeps track of the current snapshot by decoding the number of program being interpreted, decides what to do next and do it. So $f(x) = \Phi^{(1)}(x,y)=\psi^{(2)}_{\mathcal U_1}(x,y)$. So my answer would be:

\begin{array} \\
\;\;\;\;\;\;\;\;\;\text{IF } \Phi(x,x) \text{ GOTO } C \\
[A] \;\;\;\text{ GOTO } A \\
[C]\;\;\;\; Y \gets 1
\end{array}

or

\begin{array} \\
\;\;\;\;\;\;\;\;\;\text{IF STP}^{(2)}(x,x,y,k)  \text{ GOTO } C \\
[A] \;\;\;\text{ GOTO } A \\
[C]\;\;\;\; Y \gets 1
\end{array}

where $STP^{(n)}(x_1, \ldots, x_n, y, t)$ is a primitive recursive predicate that happens to be true if the program with number $y$ on input $(x_1, \ldots, x_n)$ eventually stops after $t$ steps.


texts:
I am working out with the rooks problem. If there are m rooks on an nxn chessboard,i have to give describe a polynomial (in m and n) time algorithm that ﬁnds a maximum-sized subset of the rooks such that if we leave this subset on the chessboard and remove all other rooks, then no two rooks attack one another. (Two rooks are said to attack one another if and only if they are either in the same row or in the same column with no other intervening rooks between them.)

My idea for solving this problem is to consider a bipartite graph (X,Y) where X is the rows in the chessboard and Y is the columns. if a row and column have a rook placed at their intersection, then there is an edge between the those vertices from x to y. This can be converted into a maximum flow network and the value of max flow is the max matching.

In order to find a polynomial time algorithm i can run maybe BFS.

I wanted to know that if i build my solution on this idea shall it be correct. Is there a better algorithm (polynomial in m and n)?

Any help is appreciated.


texts:
finding the index of first zero entry in a binary string:

Input: binary string ($0$'s and $1$'s)

Output: index of first zero entry

Can you give a circuit for finding the index of first zero entry in a binary string with minimum depth and polynomial many processors?

1) Is this problem in $AC_0$?

2) Is this problem in $NC_1$?

Can point me at references?


texts:
Shannon's entropy [plog(1/p)] for an image is a probabilistic method for comparing two pixels or a group of pixels.Suppose an image with a  matrix of 3x3 has pixel intensity values

1 1 2
2 3 3
4 4 5

and another image with 3x3 matrix has group of pixels having intensity values

5 5 6
6 7 7
8 8 9

Then shannon's entropy for the images would be the same.So in this case the entropy values would point out that the images are same though in actual they are different.So image matching using this technique doesn't help.On basis of supervised classification where I classify an image based on trained databases of shannon's entropy ,we use the concept of entropy to find similarity between two images.Is there any method or research paper where this entropy can be used or modified for image matching for the above case..?


texts: I have a printed answer to a math problem which has weird symbols on it. I figured out that the symbols were just incorrect renderings of usual symbols. Do you know what might have caused this?


texts: Finding an element in a infinite unsorted doubly linked list

texts: Is there any way to find an element in an unsorted doubly linked list given an element and pointer from which we can navigate? (we can't use head/tail pointers since the list is infinite)


texts: Raft algorithm: What's the meaning of concept `index`?

texts:
When reading the description of Raft algorithm from Wikipedia, I noticed there is a special word index.

For web developer, index usually refers to database index.

When it comes to Raft algorithm, what does index mean? Is it similar with database index? e.g. B+ tree.
What is raft index used for?

Wikipedia: Raft

  Log Matching: if two logs contain an entry with the same index and
  term, then the logs are identical in all entries up through the given
  index.

https://en.wikipedia.org/wiki/Raft_(computer_science)#Safety_rules_in_Raft


texts:
I try to express the following statements in first order logic:

X is a subset of Y.
A set can be uniquely characterised by its elements.
The power set p(X) contains all subsets of X.
A set X is the union of all its subsets containing just one element.

Thus far I managed:

$\forall x \in X \Rightarrow x \in Y$
$X=Y \Leftrightarrow (\forall x \in X \Rightarrow x \in Y \land \forall y \in  Y \Rightarrow y \in X)$
$ x \in p(X) \Leftrightarrow (\forall y \in x \Rightarrow y \in X) $

However now I don't know to express the 4th problem via FOL.

I tried: $ X = \cup x.(\forall z \in X \exists t. z \in t \land t = x \land z \not \in \forall y. y \neq t)$

If possible I would also like to convert 3. in an expressing $p(X)$ with $=$ rather than $\Leftrightarrow$

Any form of constructive comments are welcome. Thanks in advance.

EDIT: Regarding problem 4.: My main problem is that I am not really sure, how to express or write down the solution - I am not too sure, what is allowed, what not. Thus I take any idea that seems remotely right or constructive.

$ X = \underset{|x| = 1, x \subset X} \cup  \Leftrightarrow  \forall y \in X \exists x . (y \in x \land \lnot \exists z .(z \lnot = x \land y \in z) ) $

On the LHS of $\Leftrightarrow $ I simply tried to express the property given in the problem above and on its RHS I tried to express this property in terms of FOL.


texts:
I understand "escaping data" as making an exception when matching data; for example, if a program can't match data wrapped in some character/s (such as single and/or double quotes) without an exception, than we make an exception when "escaping" such character/s to be matched.
Is escaping a concept in CS?
Is it "part of how any computer would work" or just a technical implementation in human-developed programming languages?


texts:
I have a set of elements. Each element is connected with every other element by a path of length $l_i,_j\geq0$ (where i$\neq$j).

I have to calculate the maximum sum of path length such that I should take each vertex only once (i.e. if $l_i,_j$ is taken then I should not take $l_i,_k$).

I've thought of brute force algorithm but it would take too much time. I also thought of sorting in decreasing order of path lengths but it doesn't work in many cases.

In which direction should I think?


texts: How to understand DFA's and how to understand how to construct them based on a given regular language?

texts: I have practiced DFA's for an upcoming test and I haven't been able to grasp how to construct more difficult DFA's. An example would be this question :  Construct a deterministic finite state automata that recognizes the set of bit strings not containing 010 (With three states).


texts: Is there any algorithm that finds the time complexity of another algorithm provided that it halts?

texts:
Let us suppose that we have some algorithm A that halts for all valid inputs, can we prove the existence of another algorithm B that takes A as input and calculates the time complexity of A.
Are there any examples of existing algorithms/programs that do this?


texts:
In order to calculate the effective access time of a memory sub-system, I see some different approaches, a.k.a formulas. All are reasonable, but I don't know how they differ and what is the correct one.

Assume a two-level cache and a main memory system with the following specs:

h1 = 80%       t1 = 10ns    L1 cache
h2 = 40%       t2 = 20ns    L2 cache
h3 = 100%      t3 = 100ns   Main memory

t1 means the time to access the L1 while t2 and t3 mean the penalty to access L2 and main memory, respectively.

I see two formulas as described below:

1-   Teff = t1 + (1-h1)[t2 + (1-h2)t3] which will be 32. The logic behind that is to access L1, first. So, t1 is always accounted. Then with the miss rate of L1, we access lower levels and that is repeated recursively. I agree with this one! You can see further details here.

2- As discussed here, we can calculate that using Teff = h1*t1 + (1-h1)*h2*t2 + (1-h1)*(1-h2)*t3 which yields 24. However, that is is reasonable when we say that L1 is accessed sometimes. You can see another example here. Although that can be considered as an architecture, we know that L1 is the first place for searching data. So, the L1 time should be always accounted.

Is there any suggestion for that?


texts: Now that many computers use UEFI instead of BIOS to boot the computer, and UEFI instructions are usually stored in a hidden hard disk partition, does this mean the newest computers do not need to have ROM, which is used to store BIOS program in the old days? Or, was ROM unnecessary long ago even before UEFI existed, as BIOS program and settings were stored in flash memory (so as to store the changes in settings by user)?


texts: Minimum Degree Spanning Tree Without Restricting Vertices Searched

texts:
I am currently self studying approximation algorithms from The Design of Approximation Algorithms (Williamson and Schmoys; page 50 here), specifically the minimum-degree spanning trees (MDST) problem. Given a graph $G$, we need to find a spanning tree $T$ that minimizes the maximum degree of any vertex in $T$.
I understand that the local search algorithm attempts to look at vertices with degree at least $\Delta(T)-\lceil \log_2(n)\rceil $ and try to improve it, and only stops when one cannot improve any such vertex. I understand that this restriction is done to polynomially bound the run time of the algorithm.
My question is, what approximation ratio can we get if we try to improve any vertex? I understand that we cannot show that it runs in polynomial time, but what approximation ratio would hold? Obviously the $2OPT+\lceil \log_2(n)\rceil$ still holds, but can we improve the ratio by trying all vertices? I tried to read the original paper which had another local search algorithm with cost $OPT+1$, but I am not able to prove that this locally optimal tree for all vertices is also an $OPT+1$ algorithm.


texts: Is the Art of Computer Programming actually used as a college text?

texts:
The Art of Computer Programming by Donald Knuth is kind of styled like a collegiate text with exercises at the end of each chapter. However, the material is not in any recognizable form for a standard curriculum, so it is hard to imagine the text actually being used for a particular course. Also, the problems are quite hard, not the usual test-your-understanding exercises normally found in textbooks.

Has the ACP ever been used as a primary text in an actual computer science course? If so, which one?


texts: number of random sets needed to generate subset

texts:
Let $A\subseteq \{1\ldots n\}$ with $|A|=\alpha n, 0<\alpha\leq1$. Now we start generating random sets $B_i \subseteq \{1\ldots n\}$ with $|B_i|=\beta n$ where $0<\beta\leq\alpha$.

How many $B_i$ do we have to generate, so that there exists a $j: B_j\subseteq A$ with decent probability (constant or overwhelming in $n$).

It holds that $\Pr[B_i\subseteq A$ for a fixed $i$]=${\binom{\alpha n}{\beta n}}/\binom{n}{\beta n}$. If the probabilities for all $B_i$ would be independent we could make use of the geometric distribution to calculate (or at least bound) the probability that after generating $N$ random $B_i$ there is no $B_i: B_i\subseteq A$. But as soon as the $B_i$ start intersecting the probabilities seem not to be independent anymore. Any help would be appreciated.

Edit:

Ok, I guess my problem is, that I do not understand, if we are facing dependencies or not. So let me give some more details: The set $A$ is unknown, but we get access to an oracle $\mathcal{O}(B_i)$, that for input $B_i\subseteq \{1,...,n\}$ with $ |B_i|=\beta n$ outputs true, if $B_i \subseteq A$ holds and false otherwise. The $B_i$ are generated independently at random and tested sequentially for being a subset.
So if the probabilities for all $B_i$ being a subset of $A$ are independent it must especially hold, that $$\Pr[B_2\subseteq A | B_1\not\subseteq A]=\Pr[B_2\subseteq A]$$

But doesn't the probability of $B_2$ being a subset of $A$ conditioned on $B_1$ being not a subset of $A$ depend on the size of the intersection of $B_1$ and $B_2$? So for example if $|B_1\cap B_2|=\beta n \Leftrightarrow B_1=B_2$ than $\Pr[B_2\subseteq A | B_1\not\subseteq A~\wedge~ B_1=B_2]=0$. Or does this just mean that all three events $(B_2\subseteq A, B_1\not\subseteq A, B_1=B_2)$  are not independent, but $B_2\subseteq A$ and $B_1\not\subseteq A$ can still be independent? If so, can we give a formal proof, that these events are indeed independent?


texts: What kind of operations can we do with bits?

texts:
I wonder if there are more things we can do with bits aside from NOT, AND, OR, XOR operations? I got this question from my teacher and I'm not really sure. How about bit shifting ">>"? Could we count this?
Thanks for replying.


texts: Space-unconstructable function in the proof of Savitch's theorem

texts:
I'm learning about the Savitch's theorem, and while the construction proof is straightforward, I still don't understand one part about it.

The proof I'm talking about is the same as is currently on Wikipedia. It starts by describing a function - let's call it CAN_YIELD(start, end, limit) for now.

It is then said that the non-deterministic Turing Machine can be simulated by a deterministic Turing Machine by calling CAN_YIELD(start_state, end_state, f(n)).

The proof then continues by describing that the function takes O(f(n)) space for one configuration and O(f(n)) for the recursion of the function. This nicely results in O(f(n)^2) which is the result we want.

The issue is that if the f(n) is not space-constructible, we don't know what limit number we should input into the CAN_YIELD function. I've seen some proofs saying that we can add something like a 'size' parameter and check if it is large enough - but again, we don't know the actual f(n) value, so I don't understand how this works.

One example of such proof can be found here. Another instance is this answer that states that we can replace the space-constructability requirement of the function by using a fixed space bound, which we increase after every iteration. Same issue as before, I don't see how that might work without knowing when to stop.

I'd be happy for any insight into this issue, or any corrections made to my statements!


texts: Given a set of integers $D$ and a positive value$P$, find an algorithm to find set of integers satisfying a condition

texts:
Given a set of positive integers :

$ \\ D = \{ D_1, D_2, ..., D_n\}$

and a non-negative integer $P$, where $P$ is divisible by every element in $D$, then find a set of non-negative integers:

$C = \{ C_1, C_2,..., C_n\}$

such that

$S > P $

where
$S = \displaystyle \sum_{i = 1}^nC_iD_i$
and for all $i$ where $C_i > 0 $,

$\ S - D_i < P$

There can be multiple solutions, any solution can suffice.

For example, if

$D = \{2, 6, 9 \}$
$P = 18$

$ C $ can be:

$C = \{0, 2, 1 \}$

since $ S = 0*2 + 2*6 + 1*9 = 21 > 18 $
and $ 21 - 6 = 15 < 18 $ and $ 21 - 9  = 12 < 18 $

What can be some approaches to tackle this?
For starters, is there a way to ensure that there even exists a solution? There can be examples where there is no solution.


texts: Minimum number of words to define any other

texts:
I'm interested in finding the minimum number of words needed to define some fraction (perhaps 95%) of the words occurring in an English dictionary (while ignoring the challenges of disambiguating conjugations & contractions, questions about what is and is not a word, etc).

My approach to this problem was to program a vertex cover solution after taking a historical Websters dictionary available online, as the following diagram shows (the definitions of the words "area", "extent", "big" and "size"):

However, the problem differs from vertex cover in one important way: a if a new word defined by already defined words like "extent" and "area", this word would not need to be 'colored' (selected) because it can be defined exclusively with reference to other statements. However, a basic vertex cover solution would require that word be covered.

With all this in view,

Does this problem have a formal name?
Is this problem exactly solved by taking the existing vertex cover and then progressively eliminating any entries which are already otherwise covered?
Is there a well-known, performant way to solve this generally?


texts:
i'm a little bit lost ... can you help me ?

So I have this table of date (each row give a point with its group)

So i took a random weight let's say : [1, -2]
H = 1 if n =< 0
    0 otherwise

a= H([1,-2][6,3]) = H(0) = 1 but the target output is 0 ... so we have to update the weight:
w -> w - p = [5 , -5] .
Next :

a= H([5,-5][3,3]= H(0)=1 the problem is : there the target output is 1 so we don't have to update the weight , but that's strange because the [5 -5] vector doesn't draw a linear separation between the 2 groups ...

Thanks for your help ? :)


texts: Finding all possible simple directed graphics given a set of nodes

texts:
Is it possible to find all simple directed graphs given a set of nodes? I was thinking of just finding all permutations of an adjacency list of lists. For example, given nodes A, B I can have the adjacency lists:

A | \
B | \

A | B
B | \

A | \
B | A

A | B
B | A

The constraints are: no self loops, simple graph, directed edges

I can probably code up the way I described above, but I wanted to make sure doing this wasn't hitting some sort of fundamental boundary of graph theory or cs.

I was also thinking about using an adjacency matrix where I can store the matrix in row-major or column-major order in a uni-dimensional array of 0s and 1s - permute the uni-dimensional array (which has to be possible) and rebuild the NxM matrix to represent the graph that way.

Apologies that this is more of a discussion than a question, but any advice would be much appreciated!


texts: Find a node with maximum distance from query node in a tree

texts:
I solved this problem from codechef:
problem link

and now I want to change it a bit. Instead of find out the distance between node $u$ and $v$ I want to answer $k$ queries of the form: find node $u$ to which distance from node $v$ is maximum but I'm not able to see fast enough algorithm for it.
I think that heavy light decomposition is still my best option. Do you have any ideas?

Finding node to which distance is maximum in this way is $O(n)$ but the challenge here is that I have to answer to $k$ queries so the total complexity is $O(nk)$. I believe that this can be done in $O((n+k)\log n)$.


texts: Hoare logic, proving conjunction rule from basic rules, possible or not?

texts:
(This is HW.) Suppose I have these following proof rules given.

I am currently considering if I can prove the conjunction rule (given below) from the above given Hoare logic rules.

My answer would be "no", because from the proof rules of Hoare logic, I can neither use the Implied rule to prove it (because from $A$ I cannot infer $A \wedge B$) nor introduce it anywhere from the first four proof rules (the only one which introduces conjunction in the post-condition requires a while). I am fairly confident that this line of reasoning is correct, but am I missing anything? For example, can I argue on a the propositional logic level that since I have $P$ as a precondition, and I have $Q_1$ and $Q_2$ as postconditions, I can simply introduce conjunction on the propositional logic level (instead of inferring purely on Hoare logic)?


texts: Graph Databases vs Relational Databases(Possible applications)

texts:
Apart from the fact that there isn't really a language as SQL  and they are less standardized , i was wondering (in terms of their applications) where graph databases are (or can be) more efficient than Relational Databases.
More precisely, if there are some specific kinds of Data sets where the graph organization performs better than the Relational one.


texts: Why isn't plus_assoc rewriting correctly?

texts:
First I have plus_assoc ready.
Theorem plus_assoc : forall n m p : nat,
  n + (m + p) = (n + m) + p.

for simplicity we omit the proof of plus_assoc.
now I want to prove plus_swap:
Theorem plus_swap : forall n m p : nat,
  n + (m + p) = m + (n + p).
Proof. intros n m p. rewrite -> plus_assoc. ...

the equation was rewritten into n + m + p = m + ( n + p ),  rather than the expected (n + m) + p = m + (n + p). why?


texts: Computational Model for learning Computability and Complexity

texts: I was reading the book by Kozen-Theory of Computation. There is a statement that Turing machine is the best model for  defining basic time and space complexity because atleast for higher levels of complexity the definitions are robust  and reflect fairly accurately  our expectations of real life computation. I did not clearly understand the statement. Why is definition said to be robust?


texts: How to write an EBNF grammar for Java float literals?

texts:
I've got this question on my study guide: "Write an EBNF grammar description for Java float literals and one for Java double literals."

I've browsed the Oracle site and found the grammar for java float literals, but I'm not entirely sure how to convert that to EBNF grammar. I understand EBNF notation but for some reason I'm stuck on this.

I was hoping/wondering someone would be able to get me started? It would be highly appreciated.


texts: Kolmogorov randomness for Pseudo random number generator

texts:
I am working on pseudo random number generation for one of my projects. My goal is to prove that the output is almost Kolmogorov Random since Kolmogorov complexity is uncomputable.
So would appreciate any help or guidance for this subject matter.


texts: Which word could I use for the pumping lemma?

texts:
I have a problem to start my proof because I do not find a word $w$ where I can use the pumping lemma.

Task:

Be
$\sum { =\left\{ a,b,c \right\}  } $ and $S=\left\{ bx{ c }^{ m }|x\in { \left\{ a,b \right\}  }^{ * }\wedge m\in N\wedge { |bx| }_{ a }-{ |bx| }_{ b }>m \right\} $

Proof with the the pumping lemma, that S is no regular language.

What I know is, that the word has to start we one $b$ following from n times $a$ or $b$ but $w$ needs to have one more $a$ than $b$ in it and $w$ also needs to have one more $b$ than $c$ in it to  fulfill the condition.
So it has to be something like this $W=b{a}^{2m+2}b^mc^m$?
This language is very difficult for me, hope you see more than I.

P.S. Please no complete solutions of the full task.


texts: Proof Complexity of a Proof or Disproof of P = NP

texts: Has there been any research on the proof complexity of a resolution to the P=NP problem?  If not, given the lack of progress on the problem, would it be unreasonable to conjecture that any proof that resolves the P=NP problem will require a super-polynomial number of steps?


texts: System restarted before transaction is committed

texts:
Consider the following log sequence of two transactions on a bank account, with initial balance 12000, that transfer 2000 to a mortgage payment and then apply a 5% interest.

T1 start
T1 B old=1200 new=10000
T1 M old=0 new=2000
T1 commit
T2 start
T2 B old=10000 new=10500
T2 commit

Suppose the database system crashes just before log record 7 is written. When  the system is restarted, which one statement is true of the recovery procedure?

(a) We must redo log record 6 to set B to 10500

(b) We must undo log record 6 to set B to 10000 and then redo log records 2  and 3

(c) We need not redo log records 2 and 3 because transaction T1 has committed

(d) We can apply redo and undo operations in arbitrary order because they are idempotent

According to me, the answer should be (a), as transaction T1 has been committed and has been written back into memory. But my solution says that the answer should be (b).

Am I right or what am I doing wrong?

Thanks in advance!


texts: What is the complexity class of finding vertex cover number of a simple graph?

texts: Suppose we have a simple graph $G$. We know that finding the minimum vertex covering set for $G$ is in the NP-hard class. But, what about the complexity class of finding the size of the set, i.e., the vertex cover number denoted by $\tau(G)$. Is there any previous result about this research question?


texts:
I would like to build an online web-based machine learning system, where users can continuously add classified samples, and have the model updated online. I would like to use a perceptron or a similar online-learning algorithm.

But, users may make mistakes and insert irrelevant examples. In that case, I would like to have the option to delete a specific example, without re-training the perceptron on the entire set of examples (which may be very large).

Is this possible?


texts: Weaker, but similar conditions to Turing completeness?

texts:
A model of computation is called Turing complete if it can simulate any Turing machine.

This rules out for example a combinational logic circuit.

However, there is a sense in which combinational logic circuits can solve all problems that Turing machines can: while it is not the case that we can find for Turing machine $T$ a circuit that computes the same function $\{0,1\}^*\to\{0,1\}$ as $T$, it is nevertheless the case that we can find for each $n$, a circuit that computes the same function $\{0,1\}^n\to\{0,1\}$ as T does for inputs of size $n$.

Is there a term for whether a model of computation can compute the same functions as arbitrary Turing machines in this less restrictive sense?


texts: Most efficient way to calculate log base 2

texts:
I recently started learning stuff with bits and now while I was solving one problem, I started thinking what is the most efficient way to calculate $$\lfloor \log_{2}K\rfloor$$

What I started thinking

It is clear that we can calculate log in $O(\log K)$. Here is my code for example

long long a;
long long result = 0;
for(long long i=0;i<63;i++) {
    if((1LL<<i)<=a) {
        result = i;
    }
}

Then I started thinking that something with bits can help, actually we want to find the leftmost bit in the whole binary number, then I found out about the function __builtin_clz(x): this function returns the zeroes at the beggining of the binary number, so if there are $x$ zeros at the beginning we can say that the log is $N - x$ where $N$ is the total number of bits in the number. I don't know the complexity of this function, but I think that it is $O(\log K)$.

Is there better way to calculate log in c++?