texts:
Problem:

I'm looking for an algorithm to find the maximal Euclidean distance between points in a set $R$ and another set $S \subseteq R$.

Specifically, given a finite set of points $S$ in $n$-dimensional space, let $R$ be the minimal bounding box of $S$ (so the product of the bounds across all dimensions). I'm only interested in this type of set $R$, for now, and am ignoring the more general question of finding a solution for any set $R$ containing $S$.

I want to find a distance D such that $d(r, S) \le D$ for any $r \in R$, where $d(r, S)$ is the Euclidean distance from the point $r$ to its nearest point in $S$. I call the point in $R$ that is maximal distance from $S$ the loneliest point in $R$, but I'm not interested in finding this point, just a rough estimate for the distance. In other words, I am looking to estimate:
$$
\max_{r \in R} \min_{s \in S} d(s,r)
$$

A solution:

I have an exhaustive solution, as follows: Construct Voronoi diagrams for $S$ in $R$, find the distance from each point $s$ to the furthest vertex in its Voronoi polyhedron, and take the max of all these.

This reduces the continuous space $R$ to a discrete and finite set of candidate points whose nearest point in $S$ I know, and over which it's easy to take the max.

Why this is inadequate:

This works fine for low-dimensional data, but it does not scale well to bigger data sets. I'm sure there must be a better, approximate solution. I don't need exact values, I just need an estimate to some predefined degree of accuracy.

Use case:

The use case here is that I am trying to fix an upper bound for the Euclidean distance that a point can be from a given data set in a design space, so that I can have a constistent scale across the space.

Problem:

Is anyone aware of such an algorithm? It seems like it should be an established problem but I haven't so far found an easy solution. Feels like it should be related to nearest-neighbour somehow.


texts: "Given an algorithm, decide whether it runs in polynomial time" is this problem in NP?

texts:
This problem is not decidable (reducible to halting problem) but is semi-decidable and therefor verifiable (as those two definitions are equivalent: How to prove semi-decidable = verifiable?).
However, is this problem poly-time verifiable?
A decision problem $P$ is poly time verifiable iff there is an algorithm  called verifier such that if $P(w)=$ then there is a string $c$ s.t. $(w,c)=$, if $P(w)=$ then for all strings $c$, $(w,c)=$ and V runs in $O(w^{k})$ for some constant $k$ for all inputs $w$.


texts: How to prove that the expected depth of kth smallest element in a complete binary heap (min-heap) is O(logk)?

texts:
How to prove that the expected depth of kth smallest element in a complete binary heap (min-heap) is O(logk)
this is part of answer:

my problem is that how do we say the last line?
how do we know ${p_{j,k}}= {p_{k - j,k}}$
and how did we find
$\frac{1}{{{2^{k - 1}}}}\left( {\begin{array}{*{20}{c}}
  {k - 2} \\
  {j - 1}
\end{array}} \right)$


texts: How to use succinct circuits to construct an EXPTIME complete problem?

texts:
When reasoning with NP-completeness, I find SAT and k-clique more convenient to reason with than generalized games that are NP-complete or the Turing machine model. I'm looking for something similar for EXPTIME-completeness. Wikipedia mentions:

  Another set of important EXPTIME-complete problems relates to succinct
  circuits. Succinct circuits are simple machines used to describe some
  graphs in exponentially less space. They accept two vertex numbers as
  input and output whether there is an edge between them. For many
  natural P-complete graph problems, where the graph is expressed in a
  natural representation such as an adjacency matrix, solving the same
  problem on a succinct circuit representation is EXPTIME-complete,
  because the input is exponentially smaller; but this requires
  nontrivial proof, since succinct circuits can only describe a subclass
  of graphs.[8]

  8:  Papadimitriou (1994), section 20.1, page 492.

I understand the concept that you can describe some graphs using exponentially less space and use that as input, but I can't find the mentioned resource or find out how succinct graphs work exactly or how to construct an EXPTIME-complete problem.


texts: Paired resolution and $\mathsf{NP}$ vs. $\mathsf{coNP}$?

texts:
Let we resolve only two clauses at time and then get rid of them. Such resolution clearly takes $O(n)$ steps.

Sequence is a set of instructions in the form $(C_{S_1}\cup C_{S_2},v\cup\overline v),...$, where $S_i$ denotes a set of merged clauses, $v\in C_{S_1},\overline v\in C_{S_2}$.

Of course such resolution taken deterministically or randomly is wrong with high probability.

For example, let's consider $\varphi=(x\oplus y)(x\oplus z)(y\oplus z)$.

Clearly this formula is unsatisfiable. But what can I get using resolution:

$(x\oplus y)\Leftrightarrow(x\lor y)\land(\overline x\lor\overline y)$.

Resolving $x$ and $\overline x$: $(y\lor\overline y)=1$.

Doing this for other clauses gives us tautology.

So, this means, that sequence $(C_1\cup C_2,x\cup \overline x),(C_3\cup C_4,x\cup \overline x),(C_5\cup C_6,y\cup \overline y)$ is wrong.

But there is a correct sequence:$(C_1\cup C_4,x\cup\overline x),(C_2\cup C_3,\overline x\cup x),(C_{\{1,4\}}\cup C_5,\overline z\cup z),(C_{\{2,3\}}\cup C_6,z\cup\overline z),(C_{\{\{1,4\},5\}}\cup C_{\{\{2,3\},6\}},y\cup\overline y)$

Showing this:

Initial formula: $(x\lor y)(\overline x\lor\overline y)(x\lor z)(\overline x\lor\overline z)(y\lor z)(\overline y\lor\overline z)$

$(x\lor y)(\overline x\lor\overline z)\mapsto(y\lor\overline z)$
$(\overline x\lor\overline y)(x\lor z)\mapsto(\overline y\lor z)$
$(y\lor\overline z)(y\lor z)\mapsto y$
$(\overline y\lor z)(\overline y\lor\overline z)\mapsto\overline y$
$y\land\overline y\mapsto0$

There are exponentially many sequences for any formula. Same applies for number of possible assignments.

But what I'm asking: is such type of resolution is proved not to be refutation-complete? In other words have someone proved that not every unsatisfiable formula has a sequence that results in empty clause? Or is it an open question? (Otherwise we'd know that $\mathsf{NP=coNP}$)

P.S. This type of resolution is sound, so only thing that I do not know is refutation-completeness.


texts:
How can prove that $2^n \nmid n!$
using binary representation for $n!$ and $2^n$.


texts: How can I find the pattern with one mismatch at most by modifying Naive Algorithm?

texts:
I want to modify the Naive algorithm to find out if there is any occurrence of the string P in T as a substring with at most one mismatch - where a mismatch is either one of the following: INSERT, DELETE, OR UPDATE. Let jTj = n; jPj = m.

What will be the worst-case complexity in modified version? Can I use memoization to improve the complexity?


texts:
I'm currently going through past paper questions and was wondering if I could get some help answering this one?
'Consider a classification model which is applied to a set of records, of which 100 records belong to class A (the positive class) and 900 records to class B. The model correctly predicts the class of 20 records in A and incorrectly predicts the class of 100 records in class B. Calculate the values of the confusion matrix, the accuracy, and the error rate.'
My current idea is that the 20 correctly predicted values fall into TP and the 100 values that were supposed to be in class A but were classified as class B fall into FN?
Any recommendations or ideas are much appreciated, thanks.


texts: Standard Parameters for Genetic Algorithms

texts:
I'm currently writing my thesis, which uses genetic algorithms at some point.
Now I need to define some parameters for the genetic algorithm

I know that, because of the No Free Lunch Theorem there is no optimal parameter configuration for all problems.

However I do need some default parameters, because finding the optimal parameters is out of scope of my paper.
Also I don't want to use random values as these parameters.

I would prefer to reuse parameters used in some well trusted sources in the field of genetic algorithms.
Then I could rely on these cited sources and reuse these parameters.

I need default values for these parameters:

population size
mutation rate
number of generations

I searched for papers, but am not sure which paper is well-known.
I'm looking for papers that are well-known and have these parameters used.
A online available pdf is preferable.


texts:
I'm creating a webapplication in which I render multiple objects using Three.js. These objects are saved in a list and can be connected to each other (but don't have to be), and when they are, they are rendered next to each other.
The user can select an object in this list using the UI that I made.
An example of how the objects can be positioned is in the image below.
When I select the most left object I want the whole chain to be rendered, but not the 'singular' objects that are in the same list.

I hope this is clear enough, if not I will gladly elaborate.
Now the problem that I'm having:
The (simplified) list can look like this:
  {
    id: 1,
    connectedObjects: [{ id: 2 }, { id: 5 }],
  },
  {
    id: 2,
    connectedObjects: [{ id: 1 }, { id: 3 }],
  },
  {
    id: 3,
    connectedObjects: [{ id: 2 }, { id: 4 }],
  },
  {
    id: 4,
    connectedObjects: [{ id: 3 }],
  },
  {
    id: 5,
    connectedObjects: [{ id: 1 }],
  },
  {
    id: 6,
    connectedObjects: [],
  },
  {
    id: 7,
    connectedObjects: [],
  },
  {
    id: 8,
    connectedObjects: [],
  },
];

Now I want to write an algorithm that checks which objects are all in the same 'group' as the selected object. So the last three (6, 7, 8) will not be rendered.
This is in JavaScript but if someone points me in the right direction with some pseudocode or a general idea that would be great!


texts: Questions on the definition of polynomial time

texts:
I been reading Wikipedia for polynomial time, and it says:

  An algorithm is said to be of polynomial time if its running time is
  upper bounded by a polynomial expression in the size of the input for
  the algorithm, i.e., $T(n) = O(n^k)$ for some constant $k$.

My questions are:

Why do we have addition and multiplication but no division?
Why do we have both multiplication and addition, couldn't we express one with the other?
What is the difference between polynomial time and exponential time by definition?


texts: How can I implement a data structure which calculates the number of nested intervals in sub-linear time?

texts:
Is there a data structure which can maintain a list of intervals and the following operations?
insert(l, r): Inserts an interval [l, r] into the list
query(l, r): Return the number of intervals in the list which are completely nested in [l, r]

I need the data structure to handle inserting and querying without brute force (which would take linear time).
I saw this algorithm for counting the number of nested intervals for each interval here:
https://stackoverflow.com/questions/12946497/sub-on2-algorithm-for-counting-nested-intervals
but it appears to only calculate the answer for a static array of intervals.


texts: How do garbage collectors avoid stack overflow?

texts:
So I was thinking about how garbage collectors work and I thought of an interesting issue. Presumably garbage collectors have to traverse all structures in the same way. They can't know weather they are traversing a linked list or a balanced tree or whatever. They also can't use up too much memory in their search. One possible way, and the only way I can think to traverse ALL structures, might be just to traverse them all recursively the way you would a binary tree. This however would give a stack overflow on a linked list or even just a poorly balanced binary tree. But all the garbage collected languages that I have ever used seem to have no problem dealing with such cases.

In the dragon book it uses a "Unscanned" queue of sorts. Basically rather than traversing the structure recursively it just adds things that need to be marked too a queue and then for each thing not marked at the end it is deleted. But wouldn't this queue get very large?

So, how do garbage collectors traverse arbitrary structures? How does this traversal technique avoid overflow?


texts: How can I convert a for loop to a recursive function?

texts:
My loop is pretty simple. The function takes in two parameters, a and b; both are integers where a<=b. The function will then create a list of numbers from a to b.

This is what I created:

 def cat(a,b):
     j = []
     for i in range (a,b):
     j.append(a+1)
     a +=1

I honestly cannot figure out how to turn this into a recursive function.. I have tried things which I realize don't make any sense and I'm not really sure where to start. Any help would really be appreciated :) Thanks


texts: Which algorithm can I use to allocate human resources?

texts:
I have to manage shifts of a variable number of people inside several rooms for a week.
Every shift must be at least 1h long and the number of hours per person for the week should be nearly the same for everyone.
Every person could ask for specific shifts and this could be accepted if a suitable solution can be found.
I could have other constraints, but let's face this very basic situation.

Now the questions:

Which algorithm should I study and use?
Is there some free library I can use for this purpose?
Is there something I can use for C#?


texts:
Consider the following decision problem :

  Cycle:
   Given a directed graph G, does G contains a directed cycle?

It is very clear why Cycle belongs to NL.
My question is - how to show Cycle is also NL-hard?
it seems almost obvious to show logarithmic reduction from stCON. I thought about the following reduction:

  Given a tuple (G, s, t), return G with a new edge (t,s).


texts:
We have a broken stick. For every part, we know it's length. Our task is to connect all parts (glue them), that we will use as small amount of glue as possible.

The amount of glue need to connect two parts equal the maximum from their sizes. We can only glue two parts at one time.Can we solve this problem in the time complexity smaller than $O(n^3)$? I know only the answer, using dynamic table in this complexity


texts: How do you prove the Natarajan's Lemma intuitively?

texts:
Let $H$ be a hypothesis class of multiclass predictors; namely, each $h\in H$ is a function from $X$ to $[k]$.

Denote the Natarajan dimension of $H$ by $Ndim(H)$. Hope you can give me an intuitive proof of the following lemma .

$|H|\le |X|^{Ndim(H)}\cdot k^{2Ndim(H)}$

The lemma is in the book "Understanding Machine Learning: from theory to algorithms". You just search keywords "Lemma 29.4".


texts: Curry-Howard, void, and type checking in Haskell

texts:
I am trying to understand an example of theorem proving via type checking in Haskell given here. The example is as follows.
Using the Curry-Howard isomorphism, construct an inhabitant of the type and prove that $N= (A\vee (B\rightarrow A))\& (C\&(C\rightarrow B))\rightarrow ((\neg B\& A)\vee ((A\rightarrow B)\&(B\rightarrow A)))$ holds.
The author provides a following code.
data Void
nnot :: Void -> a
nnot = undefined
proposition :: (Either a (b -> a), (c, c -> b)) -> Either (Void -> b, a) (b -> a)
proposition (Left x, (y, f)) = Left (nnot, x)
proposition (Right g, (y,f)) = Left (nnot, (g (f y)))

The implication $(A\vee (B\rightarrow A))\& (C\&(C\rightarrow B))\rightarrow (\neg B \& A)$ does not hold. But the constructed term is claimed to prove it, and the type checker is satisfied by it. Why?
I feel that the transcription of the initial formulae to the type of proposition is incorrect, since the negation of b is represented with Void -> b which is the absurdity (and it is defined as nnot). I.e. from the logical point of view, the pair (Void -> b, a) corresponds to the term $\bot \& A$. But that does not give an answer why the type checker verifies the code above. Thus, I will greatly appreciate any hints on the following two questions.

Why does the Haskell compiler approve the type of proposition?
If that is the case when Curry-Howard is not in place then how I can actually use the type checker to prove formulas with negation via Curry-Howard?

I do not know either this question is more appropriate on cs or stackoverflow, so please sorry if it is off-topic.
EDIT: Given the following corrected proposition:
proposition :: (Either a (b -> a), (c, c -> b)) -> Either (b -> Void, a) (b -> a)

I have written the following "proof" for it, and the type checker was satisfied. I do not know whether I can believe that the proposition can be counted as being proved after the type check.
proposition (Left x, (y, f)) = Right ((\z1 z2 -> z1) x)
proposition (Right g, (y,f)) = Right ((\z1 z2 -> z1) (g (f y)))

And still I have no idea whether it is possible to prove any negation by the type checking procedure.
Edit2: I thought I had got some understanding of the topic, but then I tried the following:
prop1 :: ((Either a b), c) -> b
prop1 (Right x, y) = x

This code is Ok for Haskell (for example, there). But it seems to be ill-typed from the point of view of logic: the corresponding type is $(A\vee B)\& C\rightarrow B$. It is obvious that the case given in prop1(Right x, y) = x has the right (heh) type, but I did not define the case for prop1(Left x, y), thus the proposition is not proved for this case.
Hence, I can have problems with the disjunction as well.


texts: Which computational model is used to analyse the runtime of matrix multiplication algorithms?

texts:
Although I have already learned something about the asymptotic runtimes of matrix multiplication algorithms (Strassen's algorithm and similar things), I have never found any explicit and satisfactory reference to a model of computation, which is used to measure this complexity. In fact, I have found three possible answers, neither of which seems to me as absolutely satisfactory:

Wikipedia says that the model used here is the Multitape Turing Machine. This does not seem to make much sense to me, since in the analysis of matrix multiplication, scalar multiplication is supposed to have a constant time complexity. This is not the case on Turing Machines.
Some texts describe the complexity only vaguely as the number of arithmetic operations used. However, what exactly are arithmetic operations in this context? I suppose that addition, multiplication, and probably subtraction. But what about division, integer division, remainder, etc.? And what about bitwise operations - how do they fit into this setting?
Finally, I have recently discovered an article, which uses the BSS machine as the model of computation. However, this also seems little bit strange to me, since for, e.g., integer matrices, it does not make much sense to me to disallow operations such as, e.g., integer division.

I would be grateful to anyone, who could help me to sort these things out.


texts:
I'm trying to better understand the min-cut problem for directed acyclic graphs. I understand that the minimum capacity cut has equal capacity to the max flow of a graph by the max flow-min cut theorem (https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem). This makes some sense to me but I'm confused as to what happens in a DAG with unit edge weights. In this case, there's three claims I'm trying to make:

The max flow of a DAG with unit edge weights has an upper bound equal to the sum of the number of edges entering all sinks. In other words, max flow is bounded by the sum of the indegree of all sink nodes.
Because all edges have the same weight, there are $\binom{n}{\text{max flow}}$ possible min-cuts where $n$ is the number of edges. In essence, if the max flow for a DAG is 3, then choosing any 3 edges would give you a min-cut.
If you apply the Ford-Fulkerson to identify a min-cut, it will effectively always include edges connected to the source node because those will immediately have their capacity maxed out and the algorithm returns the cut closest to the source(s).

These feel unintuitive to say the least but seem to hold true for the few small examples I tried to run through. In particular, the second statement seems very wrong to me. It seems to imply that any set of edges with capacity equal to max flow constitute a min-cut. While a min-cut definitely has capacity equal to max flow,  I'd guess the reverse statement that any set of cuts with a capacity equal to max flow is a min-cut isn't necessarily true (though I can't quite come up with a counter-example).

My question is, are any of the 3 claims above true?

Edit:

After thinking about it some more, I think I found a counterexample to my 2nd claim. In the DAG below, the max flow is 2 but cutting any two of the dotted edges wouldn't yield a partition.


texts: what's the meaning of LOC(X[j]) = $L_0$ + cj in TAOCP's 5.4.1R?

texts:
in TAOCP vol3 2nd Edtion's 5.4.1R Replacement Selection, there is a paragraph describing a data structure and example for Replacement Selection as follows:
the algorithm below uses a data structure containing $P$ nodes to represent the selection tree; the $jth$ node $X[j]$ is assumed to contain $c$ words beginning in $LOC(X[j]) = L_0 + cj$, for $0$ $\le$ $j < P$, and it represents both internal node number $j$ and external node number $P + j$ in Fig.63.

There are several named fields in each node:
$KEY$ = the key stored in this external node;
$RECORD$ = the record stored in this external node (including $KEY$ as a subfield)
$LOSER$ = pointer to the "loser" stored in this internal node;
$RN$ = run number of the record pointed to by $LOSER$;
$PE$ = pointer to internal node above this external node in the tree;
$PI$ = pointer to internal node above this internal node in the tree.
For example, when P = 12, internal node number 5 and external node number 17 of Fig.63 would both be represented in $X[5]$, by the fields $KEY = 170, LOSER = L_0 + 9c$ (the address of external node number 21), $PE = L_0 + 8c, PI = L_0 + 2c $
for $LOC(X[j]) = L_0 + cj$, 4 questions:

I need TAOCP's $MIX$ machine knowledge for understand this formula?

it seems that $LOC(X[j])$ is not meaning of the array or pointer, its goal is to find $X[j]$'s beginning addrss?

$cj$ is equal to $c * j$?

what's the meaning of $L_0$ ?

$LOC(X[5] = L_0 + 5c, LOSER = L_0 + 9c = LOC(X[9]), PE = L_0 + 8c = LOC(X[8]), PI = L_0 + 2c = LOC(X[2]) $,
what's the meanings about them $LOC(X[9]),LOC(X[8]), LOC(X[2])$?

according to $LOSER = L_0 + 9c$ indicates that the address of external node number $21$, so that $PE = L_0 + 8c$ indicates the address of external node number $20$, and $PI$'s address of external node number $14$, but int this case of internal number 5 and external number $17$, $20$ and $14$ are unrelated to them?


texts: Does this A-Star heuristic already exist?

texts:
I've been thinking about the A* algorithm recently. For context, A* is a graph-navigating algorithm most often used to solve problems that go "What is the shortest path from point A to point B?". It's based on a distance-estimating heuristic you provide to it. The heuristic you provide must be able to tell the program, for any given position: 'This position is at least this far away from the destination'. The most simple heuristic being to use Pythagoras's theorem to get the distance "as the crow flies" between said point and a destination.

Now, the thing that interested me is that A* efficiency is tied to the preciseness of your 'getMinDistance' function. If it returns a value too low, the algorithm takes longer. If it returns a value too high, A* may return a non-optimal path. If it always returns 0, you have Dijkstra's algorithm. (also the heuristic must be monotonic, read the wikipedia articles for more details)

The heuristic I thought about goes like this:

Using any method of your choosing, split the graph into regions. Designate a node of each region as the region's center (ideally, its centroid). The graph traversal distance between any node and its region's center should be trivially computable (or cached).
Store the exact graph traversal distance between the centers of every single region. If you have N regions, you should end up with N² distances.
For any two points A and B, and their respective region's centers Ra and Rb, the graph traversal distance AB is superior or equal to RaRb - (RaA+RbB)

The smaller the regions are, the closer this heuristic gets to the actual traversal distance AB.

My questions are:

Is this algorithm actually admissible? I have no idea how to formally prove it.
How efficient is this heuristic? My guess would be "Very if you have a lot of small groups, because A* only examines nodes within the groups that include the optimal path", but again, I'm not sure it's true and I don't know how to prove it.
Was this idea ever published before? If so, what is it called and where can I read about it?
In the same vein, are there video games which are known to use this heuristic?


texts: Why more and more languages do not have link stage when compiling?

texts:
As far as I know, only C, C++, and Objective-C (in most used languages) need a linker when compiling, languages like Java and C# don't have one, and it seems more and more modern languages do not have a linking stage nowadays.

Why?
If there's no linker, the code cannot turn into machine code, so languages without a linker must have a virtual machine to run on(things like JIT still need a vm), right?
Languages can call each other by using abi if both them has a linking stage, right?


texts: How to find number of combinations of choosing one from k subsets

texts:
Consider we have set S:

S = {1,2,3,4,5,6}

and 3 (say k) subsets of S:

S_1 = {1,2,3}

S_2 = {2,3,4,5}

S_3 = {1,3,6}

What is the total number of cases choosing one element from each subsets?

Same element cannot picked from different subset, and the order is not considered.

For example,

S_1 = {2}, S_2 = {3}, S_3 = {6}

and

S_1 = {3}, S_2 = {2}, S_3 = {6}

considered as same. And

S_1 = {3}, S_2 = {3}, S_3 = {1}

is invalid since S_1 and S_2 choose the same element.

How can I formulate this?


texts: Shortest paths in weighted graphs, and minimum spanning trees

texts:
I stuck in one challenging question, I read on my notes.

  An undirected, weighted, connected graph $G$, (with no negative
  weights and with all weights distinct) is given. We know that, in this graph,
  the shortest path between any two vertices is on the minimum spanning tree (MST). Verify the following:

  1) shortest path between any two vertices $u$, $v$ is unique.

My question is, is this statement (1) is false or True?

Other details is not mentioned in the old exam question, But I think:

1) if this means that for any pair of vertices and for any shortest path between them, it lies on MST So this statement is False. for example Let's assume that we have a graph with two vertices $\{1, 2\}$ and one edge between them with zero weight. There are infinitely many shortest paths between the first and the second vertex ($[1, 2]$, $[1, 2, 1, 2]$, ...)

2) if this means For each $a,b\in V$, for each shortest path $P$ from $a$ to $b$ in $G$ there exists a minimum spanning tree $T$ of $G$ such that $p$ is contained in $T$. this statement is True.


texts: What would you call an algorithm that finds $R$ % of the time the optimal solution to an NP-hard problem?

texts:
According to Wikipedia,

A $\rho$-approximation algorithm $A$ is defined to be an algorithm for which it has been proven that the value/cost, $f(x)$, of the approximate solution $A(x)$ to an instance $x$ will not be more (or less, depending on the situation) than a factor $\rho$ times the value, $OPT$, of an optimum solution.

I am interested in a situation where we would like to measure the performance of $A$ by how often it finds the optimal solution. For example, the algorithm $A$ finds the optimal value $R$ % of the time and finds a strictly larger (or less) solution $100-R$ % of the time. What would such algorithm be called? Is this notion known in the literature?


texts: Does the underlying computational calculus in type theories affect decidability?

texts:
I'm looking for a high-level explanation although if that isn't possible or difficult, I'd prefer references to books/papers.

I understand that modern type theory is inspired by Curry-Howard correspondence. From the Wikipedia article on Curry-Howard correspondence:

  The correspondence has been the starting point of a large spectrum of
  new research after its discovery, leading in particular to a new class
  of formal systems designed to act both as a proof system and as a
  typed functional programming language. ... This field of research is usually referred to as modern type
  theory.

Looking at the various type theories proposed and under development, I have a few basic questions:

1. Most modern type theories marry a type system with lambda calculus. Are there examples where a type theory uses a computational calculus other than lambda calculus?

2. At a very high level, if every modern type theory is a bundle of a type system and a computational calculus and the computational calculus is turing-complete (like lambda calculus), does the computational calculus in any way affect the decidability of decision problems like type checking, type inference, etc.? (AFAIK modern type theories tweak the type system while keeping the associated turing-complete computational calculus intact and just tweaking the type system affects decidability of type checking, type inference, etc.)

EDIT

NB: The distinction between Type Theory 1 and Type Theory 2 is based on their application in formal verification of programs and not based on the philosophy of type theory research. Also, the Program/Computation/Dynamic blocks are bigger as I guess existing programming languages have higher computational complexity than the type theories used for formal verification of their programs.

W.R.T. to the illustration above:

1) In type theory 1 methods, are type theories used both consistent and complete (w.r.t. Godel’s incompleteness theorem)? If there are type theories in proof assistants that are incomplete; leading to undecidable decision problems, how does the undecidability manifest in practical applications (like proving the correctness of a complex distributed systems protocol)?

2) In type theory 2 methods, what are the limitations of type theories in static analysis (w.r.t. Rice’s theorem)? Here, is decidability in type theories also affected by the computational model of programming language (eg. imperative vs functional languages)?


texts: How do you prove that $A = \{ x \in \mathbb{N} | W_{x} = [0..x]\}$ is a productive set through functional reduction?

texts:
As the title states, how do you prove that $A$ is productive? With $W_{x}$ I mean the set of points in which the turing machine with index $x$ halts.

The standard approach that I follow is functional reduction: first I construct a partial recursive function $\psi(x,y)$. Then through the s-m-n theorem I build a partial recursive function $\varphi_{g(x)}(y) = \psi(x,y)$ with $g$ total recursive. Then I proceed to show that $\overline{K}$ reduces to the set I'm studying through $g$. The problem is that in this set the condition includes the index of the partial function ($x$) so I don't know how to construct a suitable $\psi$ function. As you can see from the appendix, I can't reach $g$ in $\psi$, so I can't build $g$ to behave like a member of the $A$ set.

How can I overcome this problem?

APPENDIX: example of proof with functional reduction

Let's show that $B = \{ x\in \mathbb{N} | W_x = \emptyset \}$ is productive.

We do this by proving that $\overline{K}$ reduces to $B$, so equivalently we can show that $K$ reduces to $\overline{B} = \{x\in \mathbb{N} | W_x \neq \emptyset \}$.
Consider the function:
$$
    \psi(x,y) = \left\{\begin{array}{lr}
        1, & \text{for } x \in K\\
        \uparrow, & \text{otherwise} \\
        \end{array}\right\}
$$

(Notice that $\psi$ is computable since $K \in RE$).
We can now build $\varphi_{g(x)}(y) = \psi(x,y)$ with $g$ total recursive (s-m-n theorem). At this point:

$x \in K \implies \forall y\in \mathbb{N}. \varphi_{g(x)}(y) \downarrow \implies W_{g(x)} = \mathbb{N} \implies W_{g(x)} \neq \emptyset\implies g(x) \in \overline{B}$.

$x \notin K \implies \forall y\in \mathbb{N}. \varphi_{g(x)}(y) \uparrow \implies W_{g(x)} = \emptyset\implies g(x) \notin \overline{B}$.

So $K$ reduces to $\overline{B}$ thorugh $g$: $B$ is productive. $\square$


texts: What is the smallest time/space complexity class that is known to contain complxity class $\mathsf{SPARSE}$

texts: Is it known if complexity class of all sparse languages is contained within e.g. $\mathsf{EXP}$ or $\mathsf{EXPSPACE}$? Or what is the smallest time or space complexity class that contains complexity class $\mathsf{SPARSE}$?


texts: How to apply the Ford Fulkerson algorithm to the assignment problem

texts:
I am quite familiar with Ford-Fulkerson algorithm but I am having a trouble to apply the algorithm to the following problem. Can someone please give me some hints or better instructions how to use FF method to this problem?
Let O be a set of n objects. It is required to form a set G of m groups. There are three possibly overlapping subsets of objects: A, B and C. Each object belongs to one or more of these subsets. Each object can be assigned to at most one group. It is required that every group must have at least ten objects: two are from subset A, three others are from subset B, and one other is from subset C; the remaining objects can be from any subset.
It is required to explain how to apply the Ford-Fulkerson algorithm to determine whether it is possible to assign n objects to m groups according to the given rules.
Small addendum (See below the idea suggested by @D.W.):
In case of only two subsets A and B, the flow network could look like that (?).
I assume that capacities c1, c2, c3 can be found from subset A and B


texts: How to prove that $3$-Spanning-Tree decision problem is $NP$-Complete

texts:
I am not sure what problem may reduce to $3$-Spanning-Tree where $3$-Spanning-Tree is defined as a decision problem which given an undirected graph $G$ determines if there is a spanning tree of $G$ in which every vertex has degree no larger than $3$.

I have already done this for $2$-Spanning-Tree using a reduction from Hamiltonian paths as this reduction seemed clear. A spanning tree where each node has degree at most $2$ is essentially a Hamiltonian path in the given graph.

I am not sure if I can extend this idea to $3$-Spanning-Tree or need to try a different approach entirely, any help would be welcome.


texts: maximum distance in between points in taxicab metrics - inserting and deleting points

texts:
Let's define distance (taxicab metrics) between two points $(x_1, y_1)$ and $(x_2, y_2)$ as
$$|x_2-x_1| + |y_2-y_1|$$

Initially, there are given empty set of points.
I think how to find maximum distance between two arbitrary points (among inserted points). Possible operations are:
1. Insert point
2. Delete point
3. Find maximum distance (taxicab metrics) between two points.

I can do it using AVL tree (augmenting). Then I can insert and delete point in $O(\log n)$, whereas find costs $O(n\log n)$ where $n$ is number of points.

However, I consider is it possible to speed up operation Find.
Any ideas ?


texts:
For the problem described in Ex. 15.9 about breaking a string
a) Prove optimal substructure
b) Write the recursive definition for defining the least cost solution
c) Write the algorithm (either the memo-ized version or bottom-up version)

If you could help me get started on any of the above three questions (or all three), I would greatly appreciate it.


texts: Find ellipsoid that contains intersection of an ellipsoid and a hyperplane

texts:
I have an $n$-dimensional ellipsoid $E$ and a hyperplane $H$. This hyperplane cuts $E$ into two parts: $E_1$ and $E_2$ (whose disjoint union is $E$). I want to find another ellipsoid $E'$ that has minimal hyper-volume and contains $E_1$.  Is there an efficient algorithm to do this?

My first thought was to formulate it as an optimization problem, but I am having difficulty with formulating it, as I don't know how to formulate the containment ($E_1 \subseteq E'$) constraint.

An approximation for the minimal hyper-volume ellipsoid is also good for my needs.


texts: Complexity of solving LP with a non-linear growth in variables/constraints

texts:
It has been shown that any Linear Program (LP) can be solved in a polynomial number of steps. An example of such algorithm is the ellipsoid method.

  To solve a problem which has $k$ variables and can be encoded in $L$ input bits, this algorithm uses $O(k^4L)$ pseudo-arithmetic operations on numbers with $O(L)$ digits.

I have a problem that can be formulated as a LP, but yet has been proven to be NP-hard. The proof is rather hard and complicated for my understanding, so I just want to argue why it is, at least, not in P.

Consider the following excerpts from here.

I can see why the ellipsoid algorithm (or any LP solving algorithm) would take exponential amount of steps because the number of variables $k$ is exponential in $n$ ($k = m^n$).

Now the number of variables is not exponential anymore ($k = nm^2$) and I can not argue why solving the Dual LP would take an exponential number of steps. The only thing I could come up with is that $L$ (number of input bits) could be exponential in size because of the exponential number of constraints ($m^n$). But that is just a wild guess.

Additionally, if the statement about $L$ is true, than it is exponential in the primal LP as well, meaning that both $k$ and $L$ in $O(k^4L)$ are exponential. Does that mean that solving the dual LP is more efficient than solving the primal one, in which only $L$ is exponential but not $k$?

NB: The context is finding optimal correlated equilibria in succinct games.


texts: If the decision problem can be solved in poly time, show the optimization problem also can

texts:
Here is a problem I am trying to solve:

  The bin packing decision problem is defined as follows: given an unlimited number of
  bins, each of capacity equal to $1$, and $n$ objects with sizes $s_1$, $s_2$, $\dots$, $s_n$ ($0 < s_i ≤ 1$), do the objects fit in $k$ bins (where $k$ is a given
  integer)? The bin packing optimization problem is to find the smallest
  number of bins into which the objects can be packed. Show that if the
  decision problem can be solved in polynomial time, then the
  optimization problem can also be solved in polynomial time.

I know what it is asking but I don't know what the "optimization" problem for this is. Is it the grouping of all the objects into different bins (for instance, $s_1$, $s_3$, and $s_6$ are in bin #$1$, $s_2$, $s_4$, $s_5$ are in bin #$2$, etc.)? Or is it simply the number of bins you need to store them? I feel like the number of bins is the decision problem...


texts: What's the time complexity of this function?

texts:
Consider the below function:

Considering that print(a) and swap(a, b) are of complexity $\theta(1)$, what is the time complexity of the above code?
The answer that comes to my mind is $\theta((n-k)!)$ or $\mathcal{O}(n!)$.
However in the book that I'm reading it says it's of order $\theta(n!)$. What am I missing here?


texts: Choose the best classifier to predict the label of strings of a regular language

texts:
I have to tackle this problem:
I have some strings that are my training set. These strings belong to a regular language corresponding to a deterministic finite automata (hidden namely I don't now it, neither the language nor the automata). A string is labeled like positive if belong to hidden language and negative otherwise. The strings of training set are correctly labeled.
I have to build a statistical classifier from training set that predicts the label of strings not seen (generalization) in the best way (better accuracy, respect to actual labeling of hidden language/automa).
I have to choose between Support Vector Machine (SVM), Recurrent Neural Network and Convolutional Neural Network.

What could be the best choice and why?


texts:
Let's say I have an algorithm, MyAlgo(n) as follows:
for i: = 1 to n do
   (something)
Where in the i-th iteration, (something) executes i^2 steps.
How can I determine an asymptotic tight bound (Big-Theta) on the running time of this algorithm? I know I have to determine Big O and Big Omega, but since the actual algorithm isn't shown, I don't know where to start.


texts: Efficient map data structure supporting approximate lookup

texts:
I'm looking for a data structure that supports efficient approximate lookups of keys (e.g., Levenshtein distance for strings), returning the closest possible match for the input key. The best suited data structure I've found so far are Burkhard-Keller trees, but I was wondering if there are other/better data structures for this purpose.

Edit:
Some more details of my specific case:

Strings usually have a fairly large Levenshtein difference from each other.
Strings have a max length of around 20-30 chars, with an average closer to 10-12.
I'm more interested in efficient lookup than insertion as I will be building a set of mostly static data that I want to query efficiently.


texts: Why are recursive types needed as primitives for proofs in dependent type systems?

texts:
I'm relatively new to type theory and dependent programming. I've been studying the calculus of constructions (CoC) and other pure type systems. I'm particularly interested in using it as a proof-preserving intermediate representation for a compiler system.

I understand that (co-)recursive types are representable, computationally, using $\Pi$ as the only type constructor. I've read, though, that they cannot be used to build proofs by induction (forgive me, I can't find where now!), e.g., that I couldn't prove that $0\neq 1$ in plain CoC (even though $\texttt{Nat}$ is typeable as $\Pi(\mathbb{N}:*).\Pi(S:\mathbb{N}\rightarrow\mathbb{N}).\Pi(Z:\mathbb{N}).\mathbb{N}$).

I assume this is why they built the calculus of inductive constructions (CIC). Is this correct? But why? I couldn't find any material explaining why such proofs cannot be represented without using (co-)inductive types as primitives. If this is not true, then why add them as primitives in CIC?


texts: What happens when you don't use a metric in k-means?

texts:
K-means is a clustering algorithm which works like this:

def kmeans(int k, Coordinate[] points):
    Step 1: initialize k cluster centers to any (distinct) coordinates
    Step 2: check which points are closest to which cluster centers
    Step 3: move the cluster centers so they are central to their nodes
            e.g. by taking the average coordinate
    Step 4: back to step 2 (with some stop criterion)

Usually, the Euclidean metric is used in Step 2. What happens when no metric,  but only a (symmetric) function $d: points \times points \rightarrow \mathbb{R}$ is used? Can k-means still produce meaningful results?


texts: Is it decidable whether a given Turing machine moves its head more than 481 cells away from the left-end marker, on input ε?

texts:
So, while reading some problems on decidability, I came across the following resource:
https://www.isical.ac.in/~ansuman/flat2018/tm-more-undecidable.pdf

Here, on page no 12, it is written that the problem is decidable and with the following argument:

  "Yes, Simulate M on  for upto m^481 · 482 · k steps. If M visits the
  482nd cell, accept, else reject."

I am quite confused with the step count. Can anyone please explain what does this mean, or maybe point to some resources where I can find a proper explanation!!!!
Image of the slide


texts: How is the oracle function for Grover's Search algorithm obtained?

texts:
I've been using the IBM quantum experience to learn about and simulate Grover's algorithm. When they create the algorithm, they use a different set of gates depending on which oracle function $f(x)$ they want to use. In other words, they are explicitly putting in a set of gates of what they want to find before they look for it, then they get what they want -- a self-fulfilling prophecy.

How is the oracle function really implemented so that by simply looking at the choice of oracle function you don't immediately know the answer without evaluating it?


texts:
I am working 1 with a certain structure,
and I wonder if someone has seen it before.
I am no mathematician, so all I can say is that
I will do my best to describe this structure.
It is actually very simple.
I am sure I have seen it (and its interpretation) somewhere, years ago,
perhaps in some old first year university textbook on the philosophy of language,
but haven't been able to find it.

The structure is a first order theory, with predicates similar to those
of a formal set theory (of the ZFC type).
The main difference with set theory is that it doesn't incorporate
the axioms Fraenkel called "constructive"
(e.g. in the introduction to Paul Bernays' "Axiomatic set theory" [2]),
and limits itself to the basic axioms of equality and extensionality
and definition of subset.

Appart from this, the theory only defines a tuple operator and a few primitive atoms (see 1, the "words" section). This, and a few relations among these atoms (given by the quasy-set-theoretic predicates outlined above),
result in a very simple and limited structure,
consistent and complete - as its full expansion is just a handful of sentences.

This structure is used by extending it with new ad hoc atoms, relations among the atoms, and rules (implications),
to model natural language "texts".
The interesting thing here is to model assertive, factual natural sentences
as tuples, instead of as actual formal sentences.
As an example, we might have

(john loves sue) belongs_to fact.

Here, 'john', 'loves', 'sue', and 'fact' would be atomic terms,
individuals; '(john loves sue)' would be an operation, valued as an individual;
'()' would be the tuple operator; and 'belongs_to' would be a predicate symbol.

This allows us to reason about (sufficient enough) sentences of the natural language
without any restriction,
and use first order variables indistinctly for "facts", "verbs", "nouns", or "names".

I oppose this to the idea of representing natural sentences
as formal sentences, using predicate symbols to represent all verbs,
and running to limitations with classes, quantification of predicates, and Russell's paradox.

"Copular" sentences (formed with copular verbs, such as "to be")
are excluded from the above, and are represented as formal sentences;
i.e., the formal predicates are interpreted as the copular verbs.
So "a person is a thing", or "john is a person", might be expressed as:

person subset_of thing.

john belongs_to person.

And that's it, more or less.

Does this make any sense?
My memory may have failed me and I may have implemented some deranged half baked scheme;
On the other hand, I do think that my work with it is allowing me to express some "ontologies" that,
in my (limited) experience, cannot be easily expressed with other systems.

Terms knowledge store
Axiomatic Set Theory by Paul Bernays (1958)

Edit in response to the comment:

You are making Triple Knowledge Base. You may find this interesting: ILP & Triple Knowledge Bases
Anton

@Anton:
What I see as a technological advantage is the separation
between copular verbs and other verbs. Consider this:

john isa man.
(john loves sue) isa fact.

It allows you to take advantage of the obvious
and hard earned correspondence between "to be" and set theory,
and at the same time allows you to use other verbs without problems -
without running into fundamental antinomies.

In your references, I see the the possibility of saying:

john isa man.
john loves sue.

Inmediately after this, you need unrestricted comprehension;
you need variables ranging over verbs and predicates. Google for "OWL Full semweb" if you want proof of that need.

That is what Gottlob Frege was doing that
Bertrand Russell showed was wrong.

With the first expression, you don't need
unrestricted comprehension to keep talking.
It's amazing, see [3] for an example.

3.- https://github.com/enriquepablo/terms/blob/master/terms/core/tests/shegets.test


texts: What algorithm should I use to find the closest solution to a given total using a list of integers?

texts:
My problem is this:
Let's say I have an arbitrary list of integers A[2013, 54, 3, 32 1, 23...]
What is the best strategy to find which of those numbers I should add together to have a sum equal or closest to a given number ?
Obviously there is always the brute force method but I'm interested in knowing if there is a more optimised one.


texts: Evaluating the average time complexity of a given bubblesort algorithm.

texts:
Considering this pseudo-code of a bubblesort:

FOR i := 0 TO arraylength(list) STEP 1
    switched := false
    FOR j := 0 TO arraylength(list)-(i+1) STEP 1
        IF list[j] > list[j + 1] THEN
            switch(list,j,j+1)
            switched := true
        ENDIF
    NEXT
    IF switched = false THEN
        break
    ENDIF
NEXT

What would be the basic ideas I would have to keep in mind to evaluate the average time-complexity? I already accomplished calculating the worst and best cases, but I am stuck  deliberating how to evaluate the average complexity of the inner loop, to form the equation.

The worst case equation is:

$$
\sum_{i=0}^n \left(\sum_{j=0}^{n -(i+1)}O(1) + O(1)\right) = O(\frac{n^2}{2} + \frac{n}{2}) = O(n^2)
$$

in which the inner sigma represents the inner loop, and the outer sigma represents the outer loop. I think that I need to change both sigmas due to the "if-then-break"-clause, which might affect the outer sigma but also due to the if-clause in the inner loop, which will affect the actions done during a loop (4 actions + 1 comparison if true, else just 1 comparison).

For clarification on the term average-time: This sorting algorithm will need different time on different lists (of the same length), as the algorithm might need more or less steps through/within the loops until the list is completely in order. I try to find a mathematical (non statistical way) of evaluating the average of those rounds needed.

For this I expect any order to be of the same possibility.


texts: How to stop genetic algorithm population converging to a single value

texts:
I've written a genetic algorithm (GA) that solves a 7-dimensional optimisation problem.  All seven variables are floating point numbers.  The problem is that the entire population seems to converge to very nearly the same point in the solution space within about 20 generations, even if I increase the population size by 10x.

Attempted solutions

Starting with a parent population $\vec{x}^{(j)}$, where $j$ is the individual's index in the population, I take the best 10% (i.e. highest fitness scores) to reproduce.  First I perform cross-over producing 2 children for every randomly selected pair of parents.  The parents can be re-used (is that a problem?).  About 5% of the children get mutated randomly.

I've tried two variations of cross-over but both have the same problem:

Calculating a 7 element weights vector $[w_i]$ and calculating the children's elements as $c_i^{(1)}=w_i x_i^{(1)} + (1-w_i)x_i^{(2)}$ and $c_i^{(2)}=(1-w_i)x_i^{(1)} + w_i x_i^{(2)}$.  The parents ith elements are $x_i^{(1)}$ for parent 1 and $x_i^{(2)}$ for parent 2.  Each weight is a sample from a uniform random variable in $[0.0;1.0)$.
Confining the weights $w_i$ to be either $0.0$ or $1.0$, i.e. randomly exchanging elements of the two parents genomes to create the children.

The mutation operation consists of randomly choosing one of the child's 7 elements and adding some Gaussian noise to it.  The standard deviation of that noise differs for each element since the elements have different physical units.

Afterwards, I evaluate the fitness of the children and keep the best few hundred or thousand (setting that I choose at the start of the algorithm) out of the combined population of parents and children to give the next generation.  Note that the parents do not get mutated, especially since I want to preserve the best from the parent generation in case none of the children improve on it.

I've tried population sizes from 1024 to 20480 and have also tried increasing the probability of mutating a child from 5% to 50% but I still have the problem that all the individuals in the population become very similar within the first 20 or so iterations.  Please advise on what I'm doing wrong.

I should point out that the algorithm, despite this problem, does get fairly close to the optimal solution.  I know this because the quantity to maximise is the correlation between between two things (no more details, sorry) and I can get to about 0.94 (the maximum physically possible is always 1.0).  However, I am concerned that the GA is not covering enough of the solution space, causing it to miss the global maximum.

My questions

Are either of the above cross-over methods correct?
Is it ok to re-use parents in cross-over?  Stated another way, is polygamy a good idea in this algorithm or should I change that part to ensure that no parent gets used more than once?
Should I mutate the parents as well?
What should I do with the 90% of parents that did not get used in the reproduction?


texts: What is the relation between arithmetic circuits and straight line programs?

texts:
One definition of arithmetic circuits is as follows:

  An arithmetic circuit $\Phi$ over the field $\mathbb F$ and the set of variables $X$  usually, $X = \{x_1, \dots , x_n\}$) is a directed acyclic graph as follows. The vertices of $\Phi$ are called gates. Every gate in $\Phi$ of in-degree $0$ is labeled by either a variable from $X$ or a field element from $\mathbb F$. Every other gate in $\Phi$ is labeled by either $\times$ or $+$ and has in-degree $2$.

A straight-line program seems to be a succession of basic operations without any if or while statement. So it seems to be a term from the associated free algebra expressed suitably "compressed" as an acyclic graph. But a (reference to a) nice definition of straight-line programs would already help me a bit with respect to this question.

What I really want to know is whether an arithmetic circuit is a special case of a straight-line program? If yes, then why is arithmetic circuit complexity considered so important, while even finding a reference for a proper definition of straight-line programs seems to be quite challenging? (I found a definition in The Extraordinary Power of Division in Straight Line Programs, but this is a paper from 2012, and the notion itself seems to be much older.)


texts:
Question : Are my justifications correct? Im very confused and im not sure im getting this correctly.

Pumping Lemma - $B = {0^n1^n | n >=0}$

Prove $B$ is not regular :

Suppose $S = 0^p1^p$

Suppose $p = 3$,

Therefore, $S = 000111$

Case 1 :

$s -> xyz$

y is in the "0's part.

Therefore, $xy^iz \notin A $ for $i = 3$, because:

if $i = 3$, then :

$S_i = 0 000 111$
Therefore, theres an addional zero, so $xy^iz \notin A $

Case 2 :

y is in the "1's part.

Therefore, $xy^iz \notin A $ for $i = 3$

if $i = 3$, then :

$S_i = 000 111 1$
Therefore, theres an addional '1', so $xy^iz \notin A $

Also, $|xy| > p$, because as $i$ increases from 0 to infinite(?), the amount of 1's is not equal to amount of '0s' ?

Case 3 :
y contains '0's and '1's, i.e : '01'

Therefore, $xy^iz \notin A $ for $i >= 1$ ? or for any $i$ ?

Also, $|xy| > p$, because as $i$ increases from 0 to infinite(?), the order of the language (0's before 1's) is not respected!

---

Would someone please clarify? Im confused at when $i$ makes $xy^iz \notin A $ happen


texts: Number of ways of tiling a 3*N board with 2*1 dominoes problem

texts:
I came across this problem,
 Tiling with Dominoes
and initially I faced difficulty in understanding the logic behind recurrence relation, but after reading it from here , I understood it. But I had a doubt, why aren't we considering the below cases for the above problem?

In the solution only these cases are mentioned,

********   AA*******   AA******   A*******
******** = BB******* + B******* + A*******
********   CC*******   B*******   BB******
  f(n)   =  f(n-2)   +  g(n-1)  +  g(n-1)

But my question is there can be other case as well, like below, why aren't we adding them, because the problem asks for the number of possible cases-

********   AA*******   AA******   A*******   AB******   CC******
******** = BB******* + B******* + A******* + AB****** + AB******
********   CC*******   B*******   BB******   CC******   AB******
  f(n)   =  f(n-2)   +  g(n-1)  +  g(n-1)  +   f(n-2) +  f(n-2)

Why aren't we adding them? Thanks for your help.


texts: Meaning of: "'If factoring large integers is hard, then breaking RSA is hard,' is unproven"

texts:
I was reading CLRS and is said:

  If factoring large integers is easy, then breaking the RSA
  cryptosystem is easy.

Which makes sense to me because with the knowledge of $p$ and $q$, it is easy to create the secret key which the knowledge of the public key. Though, it explains the converse statement, which I don't quite understand:

  The converse statement, that if factoring large integers is hard, then
  breaking RSA is hard, is unproven.

What does the statement above formally mean? If we assume factoring is hard (in some formal way), why does that not imply that breaking the RSA crypto system is hard?

Now consider that if we assumed that factoring is hard...and that we discovered that it meant that the RSA cryptosystem is hard to break. What would that formally mean?


texts: How do multiple branches from one node occur with the Monte Carlo Tree Search?

texts:
I think I understand the Monte Carlo Tree search. It goes through the tree until it reaches a leaf node, where it branches (creates a child node). However, the branching only occurs at the leaf nodes (right?). So, a branch never comes out from a non-leaf node. So how could one node have multiple branches (multiple child nodes) coming out of it? Here's a picture, for clarity:

So wouldn't that process just keep getting repeated? It's not a leaf node, so the algorithm won't branch (create another child node)... so it has to pick the next node. And since it only has one option, it must pick that one. It just continues down, until it reaches the end. What's the point of that?

I'm probably missing something big here, but all the pages I've look at don't really explain this. It just magically repeats selection, expansion, simulation, and back-propagation, until it constructs a nice tree at the end. How?

EDIT:
I figured it usually creates only one child node because of this taken of this source:

  In its simplest and most memory efficient implementation, MCTS will add one child node per iteration.

Also, even if you create just two or three, would that really be enough to cover all the possible moves, especially if the branching factor is large? How would one determine how many child nodes to create?


texts: How to reduce the number of crossing edges in a diagram?

texts:
I am working on a diagram editor.
Diagrams display 2D shapes (nodes) connected with connectors (edges).

I'd like to add an operation that, given a selection of nodes, "disentangles" them: it repositions them to reduce the number of crossing edges, if possible
(and it's OK if the edges will have to be drawn with bend points).

So I want a graph algorithm that, given a (topological) graph embedding and a subset of its nodes, modifies the embedding (its topology) on only those nodes so as to minimize the number of crossing edges.

From reading about apex graphs and browsing Cabello and Mohar (2013), I suppose this problem is NP-hard.
So I'll be happy with a parametrized algorithm (e.g. on the number of crossing edges) that has a known, polynomial, time complexity for any given parameter value. This seems feasible, but I don't find it easy to come up with such an algorithm on my own.

Questions:

Where do I look for such an algorithm?
Does it exist?
In existing software?
Is there any significant practical experience with such an operation? (What looks good in theory may not be so good in practice, or vice versa.)

(I am not sure where best to ask this question: here, on StackOverflow, or MathOverflow?)


texts: Why is subarray $A[p..k-1]$ empty when $k=p$?

texts:
I'm working through a proof of correctness for merge sort.

I'm given a loop invariant for a for loop, which makes reference to a subarray $A[p..k-1]$. During the initialization step of the correctness proof, my textbook says "Prior to the ﬁrst iteration of the loop, we have $k=p$, so that the subarray $A[p..k-1]$ is empty".

In other words we're saying $A[p..p-1]$ is empty. Suppose $p=1$, then it's saying $A[1..0]$ is empty. Why is this considered empty? Is it just an axiom that subarray $A[a..b]$ is empty if $a>b$?


texts:
$$L = \{a^{m+n}b^{m+k}c^{n+k}\mid m,n,k\ge 1\}.$$

Is $L$ DCFL or not?

According to me it should be DCFL since we can write $L$ as $\{a^{n}a^{m}b^{m}b^{k}c^{k}c^{n}\mid m,n,k\ge1\}$. So, now after push and pop on the stack, it will be empty. So, according to me it will be DCFL but I have doubt since DPDA can't count $n$ and $m$ after reading symbol $a$ so machine can't know how many $a$'s should have to be popped. According to this logic, one stack is not enough for this language. So, it should be CSL. Please tell me whether it should be DCFL or CSL?


texts: As the title states, I am asking for how the big-O in asymptotic analysis is used in theoretical computer science. It would be helpful if an example would be given.


texts: Computing a pre-topological sort using a BFS/a queue

texts:
Computing a topological sort in a DAG using a queue simply amounts to putting the nodes with indegree 0 in a queue, and going through the queue removing these nodes from the graph and adding the nodes that are newly with indegree 0.

This of course does not apply to computing a pre-topological order in a general graph, that is, an order satisfying:

    If $u\leadsto v$ and not $v \leadsto u$, then $u$ appears before $v$.

Such an order is used for instance in Kosaraju's algorithm, and the wikipedia page states:

  As given above, the algorithm for simplicity employs depth-first
  search, but it could just as well use breadth-first search as long as
  the post-order property is preserved.

I believe that what is meant by "the post-order property" is just the pre-topological property.

Question:  How can one compute a pre-topological order using a BFS(-like) algorithm?


texts:
I have a programming assignment that says we should use the MVC architecture but we never really learned what that is.

I looked up MVC architecture on google but nothing was helpful. So can someone explain MVC architecture?


texts: Proof that probability that hashing with open addressing needs more than $k$ attempts is $2^{-k}$ at most

texts:
There are $n$ elements in a hash table of size $m \geq 2n$ which uses open addressing to avoid collisions.

The hash function was chosen randomly among a set of uniform functions. A set $H$ of hash-functions $h:U\to\{0,\dots,m-1\}$ is called uniform, if for every tuple of different keys $x,y \in U$ the number of hash-functions $h \in H$ with $h(x) = h(y)$ is $\frac{|H|}{m}$ at most.

Show that the propability that for $i = 1, 2, \dots,n$ the $i$-th insert operation needs more than $k$ attempts, is $2^{-k}$ at most.

This is an assignment, which I got as homework. What I already worked out:

The propability $p_1$ for a collision is 0 of course for an empty table.

The propability $p_i$ for a collision after k attempts should be $\frac{i - 1}{2n}\cdot k$ assuming that the table is filled with $i-1$ elements to this point and the tables size is $2n$ as worst case.

So I have
$$
p_i= \frac{i-1}{2n} \cdot k \leq 2^{-k},
$$

but I don't know where to go from here.

The method of open hashing used here simply iterates over different hash-functions until a free place is found (for example $h(x) = (x \bmod j) \bmod n$ with increasing prime numbers for $j$.


texts: Solving a recurrence relation involving square roots

texts:
Give an asymptotic upper bound for $$T(n) = \sqrt{n}·T(\sqrt{n})+n+n/\log n. $$

How can I solve this recurrence relation, which involves square roots?


texts: Getting ALL negative weight cycles of a graph using Bellman-Ford

texts:
I'm doing a min cost assignation problem to assign doctors to their working days for a hospital.

After correctly getting the max flow with Ford-Fulkerson algorithm, I would like to use the cycle canceling algorithm to minimze the flow's cost. I'm basically using the Bellman-Ford algorithm from the sink of the residual graph with the max flow.

The problem is that Bellman-Ford gives me one negative weight cycle (the one that reduces more the cost), and in a given example, such cycle has a bottleneck capacity of 0, so I cannot send flow around it. However in the very same example, other negative weight cycles exist with a bottleneck capacity strictly greater than 0. Sending the bottleneck flow among these cycles would certainly reduce the cost of my assignment, nevertheless the Bellman-Ford implementation does not seem to be capable of yielding such cycles.

How might I get all the graph's negative cycles, to finally get the min cost assignation?

For this university project, the algorithm's performance is not relevant.


texts: Is it possible to prove Language L context-free?

texts:
Give a question:
Language L= {a^n b^(n+m) a^m}, where both n and m are >=0. Is L context-free or not.

If the answer is yes, can I use the following PDA to prove it?

Since {a^n b^(n+m) a^m}={a^n b^n b^m a^m}, in the PDA, we first push n a's onto the stack. Then, we pop n a's from the stack by reading n b's. Next, we push m b's onto the stack, and we pop m b's from the stack by reading m a's. Finally, the strings will be accepted in q5.

Conversely, if the language is not context-free, should i use pumping lemma to prove it?

Thank you!


texts:
This is precursor to my other, more advanced question about Stack Inspection.

Stack Inspection is a security mechanism introduced in the JVM to deal with running code originating from locations having different levels of trust. This is question aims at finding a simple description of its functionality. So:

  How does stack inspection work?


texts: Multicommodity flows with minimum congestion: NP-hard?

texts:
I have a question related to a paper of Chen, Lovasz and Pak [1].

The paper concerns the construction of the Markov chain with optimal mixing time on an arbitrary graph.
They prove the optimal bound (conductance bound) can be reached by "lifting" the Markov chain, this comes down to extending the local node features without violating the graph connectivity. The construction of this lift is, as they put it, "closely related to explicity constructing multicommodity flows with minimum congestion".

My first question is: Is the explicit construction of multicommodity flows with minimum congestion NP-hard?

And my second question: In case anyone is familiar with the paper, does the construction of the optimal lifted Markov chain indeed require solving such a multicommodity flow?
Otherwise put, is constructing the optimal lifted Markov chain an NP-hard problem?
I find the authors to be a bit vague about this.

[1] Chen, Fang, László Lovász, and Igor Pak. "Lifting Markov chains to speed up mixing." Proceedings of the thirty-first annual ACM symposium on Theory of computing. ACM, 1999.


texts: What would be the over all speed-up achieved?

texts: Suppose we are using a dual core processor and we run 2 applications (1 with 80% resource requirements and the other with 20% resource requirements).Now the first program is parallelizable for 40% and the second one not parallelizable.My question is what would be the speed up achieved in this case.By speed-up i mean the ratio between the execution times before and after parallelization.


texts: What does "yields" mean in the phrase *yields no back edges* in DFS?

texts:
What does yields mean in the phrase yields no back edges in the context of DFS?
procedure DFS(G, v) is
    label v as discovered
    for all directed edges from v to w that are in G.adjacentEdges(v) do
        if vertex w is not labeled as discovered then
            recursively call DFS(G, w)

As you see, the line if vertex w is not labeled as discovered then makes DFS never run back to a node that has already been labeled. So what does yields no back edges mean? Because I think that DFS never touches labeled nodes.


texts: How to find the cost of pseudocode with a nested loop and a nested if statement?

texts:
How can I find the cost of pseudocode with a nested loop and a nested if statement?

On the left hand side is an example from a textbook I am following. On the right hand side is pseudo code that I found. I took a guess, but I don't know what the time would be for the inner code fragments.

I am especially unsure what the code segments inside the if statement would be because the if statement doesn't always occur.


texts:
The problem I have is like this bin packing problem, but instead I have $n$ bins and a collection of items with discrete masses. I need to put at least $m$ kg of stuff in each bin.

Is there an efficient way of doing this? Is there a way that will assure there is approximately the same amount in each bin? Does having a good guess at the probability distribution of the masses help?

More explicitly:

I have $q$ objects $\{o_1...o_q\}$, each has a size $w(o_i) \in \mathbb{N}$.

I need to find a collection of $n$ disjoint bins $B = \{b_1...b_n\}$ containing the objects such that

$$\forall b_i \in B: \sum_{o \in b_i}w(o) > m$$

for some $m$. When it is possible that is.


texts: Is there any recent research on $(2+p)$-SAT?

texts: I've read a few papers (searched by Google Scholar) about $(2+p)$-SAT, but they're all quite old (2001 and earlier). Do newer publications exist? I'm looking for solvers, theorems and so on. I want to examine this topic thoroughly.


texts: How can one come up with reasonable IP subnet allocations?

texts:
An ISP has following chunk of CIDR-based IP addresses available with it: 245.248.128.0/20
The ISP wants to give half of this chunk addresses to Organization A,
and a quarter to Organization B, while retaining the remaining with itself.
Which of the following is a valid allocation of addresses to A and B?

  A) 245.248.136.0/21 and 245.248.128.0/22
  B) 245.248.128.0/21 and 245.248.128.0/22
  C) 245.248.132.0/21 and 245.248.132.0/21
  D) 245.248.136.0/24 and 245.248.132.0/21

It is easy to make out that option 'C' and 'D' are wrong. Option 'B' is not possible due to address overlapping. The answer is 'A' for sure, but I'm unable to understand how. How is 245.248.136.0/21 and 245.248.128.0/22 calculated? I've been trying to solve this the
whole day but found no solution to it, any help on how to solve this problem would be appreciated.

Also, how can I determine the range of addresses that can be allocated to organizations A and B?


texts: How to self-learn automated theorem proving?

texts:
Year 12 high school student here, but my ambition is set on Automated Theorem Proving. I wish to apply it to, of course, mathematics and computer science, and maybe if possible other applied subjects like physics, chemistry or even analytic philosophy.

I have yet to go to university to do a bachelor degree in Computer Science, but I would like to know what steps should I take to teach myself Automated Theorem Proving. Advice and tips from the ATP experts and what online resources and books are there available, etc. And how should I actually practice and do it? Also, should I jump straight to ATP or learn Computer Science in general first?

Thanks in advance


texts:
I know the answer to the question, but I still can't understand.
I have the max flow and I need to determine whether there is more than one min-cut.
I know that I need to run BFS from s in the residual network, and from t in the residual net work (after changing each (u,v) to (v,u)).
What I can't understand: why would I get different results?
Every example I am trying shows me the same: Any vertex reachable from s (not include s) is a vertex that is reachable from t.
Am I wrong? and if I'm wrong, what is the reason some other case can happen?


texts: Examples of context sensitive syntactic constructs (statements)

texts:
So, I am implementing a context sensitive syntactic analyzator. It's kind of an experimantal thing and one of the things I need are usable syntactical contructs to test it on.

For example, the following example isn't possible to parse using standard CFG (context free grammar). Basically it allows to declare multiple variables of unrelated data types and simultaneously initialize them.

int bool string number flag str = 1 true "Hello";

If I omit few details, the language used can be formally described like this:

L = {anbncn | n >= 1}

So, I would appreciate as much of similar examples as you can think of, ideally something from the area of programming languages.

Also, I am aware that current programming languages and their compilers are context sensitive, mainly thanks to semantic analysis, so I would like to state I am not looking for things like:

type checking
is variable declared?

I would preffer the examples to be actual syntactic constructs like the shown declaration example above.

Thanks in advance ;).


texts: clustering with uncertain number of clusters

texts: I detect a unmanned aerial vehicle(UAV) in a picture using template matching. The template library only contains targets with different scales, rotations and other differences.I want to simplify the template library using clustering. I learned the k-means and Gaussian mixture model（GMM）but they all need determine the value of k.Are there any approaches which can solve my problem?


texts:
I know that we can visualize a Non deterministic TM as a TM which splits into multiple copies of itself whenever it sees a non deterministic path (Yes, I also know that this is just a visualization and is usually used by beginners like me for understanding non determistisism).

Further, I also know that a Decider is a TM that halts on all possible inputs.

Now, my question is how can I visualize a Non determistic Decider? Does a non-determistic decider mean a TM where

All the copies must halt, (OR)
At-least one copy halts.

Kindly explain in detail why so. Thanks.


texts: Understanding Cyclic Dependencies when using Soft Update for Filesystems

texts:
We recently delved into the concept of "Soft Updates" as a mean of maintaining a Filesystem as consistent. The solution, as we learned it, calls for 3 basic rules:

We'll create a pointer to a file only after the file (Inode) has been created.
To reuse a block, we will first remove all Inode pointers to it.
For rename() operations, we will first create the new pointer, and only then remove the previous one.

While all of it is mostly understood, I had difficulty understanding why cyclic dependencies occur. The example that's always being given is the one where two actions are needed to take place, both creation and deletion, using the same Inode Block of a directory and its contents. The series of actions is as follows:
1. Create File
2. Remove File

My question is: why would this cause cyclic dependency? Since these are two seperate actions, why can't we complete the first one, in the relevant order of steps it needs, and only then do the other? Can someone please describe step for step why eventually we would enter a loop, and why both of these actions cause it?

I've searched for deeper explanation in many places, but no clear answer has been given.
Any help would be appreciated!


texts:
I'm reading a paper for school and I have come across a passage that I don't understand. It says "If we allow the query to access the entries of the array through an oracle, it is possible to obtain a data structure of sublinear size".

Searching for information on what Oracle Access is has given me nothing but stuff about Oracle Databases, which is obviously not what I'm looking for. I can't really wrap my head around what this means.

Can anyone point me in the right direction?


texts: The difference between compiler and interpreter

texts:
I am reading dis, It reads:

The dis module supports the analysis of CPython bytecode by disassembling it. The CPython bytecode which this module takes as an input is defined in the file Include/opcode.h and used by the compiler and the interpreter.

In wikipedia

In computer science, an interpreter is a computer program that directly executes, i.e. performs, instructions written in a programming or scripting language, without requiring them previously to have been compiled into a machine language program.
A compiler is computer software that transforms computer code written in one programming language (the source language) into another programming language (the target language).

I really unable to figure out the difference.


texts: JIT, AOT, Interpretation: What are differences between them?

texts:
I'm a beginner in Compilation.
My understanding is that Interpretation means Interpreter takes source program as input and produce the result of this program.(source -> Interpreter -> run on the machine) Compilation means Compiler take source program as input and the front-end translate them into intermediate representation and then the back-end treats intermediate representation as input and produce machine code as output.(source -> front-end -> IR -> back-end -> machine code -> run on the machine) However, I'm confused when I learn Java and JVM. JIT seems more complicate than compilation what I understand. And I'm find some new terminologies like AOT. What differences between these terms?


texts:
The page on descriptive complexity theory in Wikipedia states the following:

"First-order logic defines the class FO, corresponding to AC0, the languages recognized by polynomial-size circuits of bounded depth, which equals the languages recognized by a concurrent random access machine in constant time."

How can we show that first order logic is equivalent to AC0?

In Clote and Kranakis' book Boolean Functions and Models of Computation (Springer, p. 34), it is states that symmetric boolean functions are in AC0.

Could we the state that symmetric functions are equivalent to AC0 and first order logic? I am guessing that no, but still...


texts: Line graphs of Powers of Cycles are powers of cycles

texts:
Are line graphs of powers of cycles again a power of cycle? I think yes, this is because the line graphs of cycles are cycles of the same order, and moreover, since powers of cycles consist of edge disjoint cycles which are packed within a distance given by the value of the power, their line graphs also must be powers of cycles. Am I right?
The definition of power is use this one. Thanks beforehand.


texts:
I've been reading for a few weeks about the Lambda Calculus, but I have not yet seen anything that is materially distinct from existing mathematical functions, and I want to know whether it is just a matter of notation, or whether there are any new properties or rules created by the lambda calculus axioms that don't apply to every mathematical function. So, for example, I've read that:

"There can be anonymous functions":
Lambda functions aren't anonymous, they're just all called lambda. It is permissible in mathematical notation to use the same variable for different functions if the name is not important. For example, the two functions in a Galois Connection are often both called *.

"Functions can accept functions as inputs":
Not new you can do this in with ordinary functions.

"Functions are black boxes":
Just inputs and outputs are also valid descriptions of mathematical functions...

This may seem like a discussion or opinionated question but I believe that there should be a "correct" answer to this question. I want to know whether lambda calculus is just a notational, or syntactic convention for working with mathematical functions, or whether there are any substantial or semantic differences between lambdas and ordinary functions.


texts:
Note: I figured this out, but haven't had the time to write an answer for it: see the comment.

For reference: the discussed material appears in http://www.cs.ru.nl/B.Jacobs/CLG/JacobsCoalgebraIntro.pdf
page 111.

On page 285 of "Introduction to Coalgebra" by Bart Jacobs, Proposition 5.3.3 is stated as follows:

  Let $\mathbb{C}$ be a dcpo-enriched category. Assume an $\omega$-chain
  $$X_0 \overset{f_0}{\longrightarrow} X_1 \overset{f_1} \longrightarrow X_2 \overset{f_2}{\longrightarrow} \cdots$$
  with colimit $A \in \mathbb C$. If the maps $f_i$ are embeddings, then the colimit $A$ is also a limit in $\mathbb C$, namely the limit of the $\omega$-chain of associated projections $f_i^p : X_{i+1} \to X_i$.

In order to prove this theorem, Jacobs first gives a partial proof of the following lemma:

  The coprojection maps $\kappa_n : X_n \to A$ associated with the colimit $A$ are embeddings, and their projections $\pi_n = \kappa_n^{p} : A \to X_n$ form a cone, i.e. satisfy $f^p_n \circ \pi_{n+1} = \pi_n$.

Here is the partial proof:

  For each $n \in \mathbb N$ we first show that the object $X_n$ forms a cone: for $m \in \mathbb N$ there is a map $f_{mn} : X_m \to X_n$, namely:
  $$f_{mn} \overset{def}{=} \left \{ \begin{array}{ll} f_{n-1} \circ \cdots \circ f_m : X_m \to X_{m+1} \to \cdots \to X_n & \text{if}~~m \leq n \\  f_n^p \circ \cdots \circ f_{m-1}^p : X_m \to X_{m-1} \to \cdots \to X_n & \text{if}~~m > n \end{array} \right \}$$
  These maps $f_{mn}$ commute with the maps $f_i : X_i \to X_{i+1}$ in the chain: $f_{(m+1)n} \circ f_m = f_{mn}$, and thus form a cone. Since $A$ is a colimit  ,
  there is a unique map $\pi_n : A \to X_n$ with $\pi_n \circ \kappa_m = f_{m n}$. In particular, we get $\pi_n \circ \kappa_n = f_{n n} = \mathit{id}$. We postpone the proof that $\kappa_n \circ \pi_n \leq \mathit{id}_A$ for a moment.

It seems to me that the above proof doesn't go far enough: it does not prove that the proposed projections $\pi_n$ actually form a cone, i.e. that $f^p_n \circ \pi_{n+1} = \pi_n$. This fact is used immediately in the proof of the next lemma, so it cannot be postponed! Can anyone explain to me how to prove
$f^p_n \circ \pi_{n+1} = \pi_n$? If our embeddings were epic then this would be straightforward, but I don't think that they are.


texts: How to solve this max contiguous subarray sum with a twist?

texts:
How to solve the max contiguous subarray problem, where we have an addition parameter $M$, and the contiguous subarray must include both $A[M]$ and $A[M-1]$?
For example, for the zero-indexed array $1, -4, 2, -2, 4, 1, -1, 1$, if $M=1$ then the contiguous subarray must include the first two elements, and so the answer is $-1$ (corresponding to the contiguous subarray $1,-4,2$).
The code I have right now without this "twist" is:
procedure MaxSubarraySum(A):
    current_sum <- 0
    max_sum <- (-infinity)
    N <- A.length
    for i <- 0 to N do:
        current_sum <- current_sum + A[i]
        if current_sum > max_sum then:
            max_sum <- current_sum
        endif
        if current_sum < 0 then:
            current_sum <- 0
        endif
    endfor

    return max_sum

But I'm stuck on how to change it so that max_sum always include $A[M]$ and $A[M - 1]$.


texts: Grover algorithm for known number of solutions

texts: I am reading Computational Complexity book and specifically Grovers search algorithm. I am aware that if we knew in advance exact number of solutions $K$, then the basic algorithm can be tweaked to find an input $x$ in $O(\sqrt{2^{|x|}/K})$ time. I found some material but, as I am new to quantum computing, I have problem connecting it to the explanation given in this book. Can anybody present the basic idea?


texts: Is the memory usage of total languages deterministic?

texts:
I'm interested in the memory usage of various programming languages when implemented on actual hardware.

I believe that a Turing-complete programming language has, in general, unknowable memory usage since object lifetimes are not statically analyzable [1]. It also seems like a regular expression language (in the deterministic finite automata) has statically known memory use.

What is the most complex programming language for which that is true? And where do total languages [2] fall in relation to that?

[1] Given the caveat that we're implementing that programming language on a physical computer with all its requisite limitations.

[2] A total language is, for the purposes of this question, a language where all programs written in it are guaranteed to terminate.


texts: are regular languages closed under division

texts:
I am trying to solve this question which appeared in previous exam paper

Can someone help me what i am failing to understand

For languages $A$ and $B$ define $A \div B = \{x \in \Sigma^{\ast} : xy \in A \text{ for all } y \in B\}$.
If $R$ is regular and $L$ is any language, is it always the case that $R\div L$ is regular? Explain.

I am thinking as regular languages closed under right quotient hoping we can use the same proof here but I understand that in right quotient we prove it for any $y$ that belongs to $B$ but for division it is for all $y$ in $B$ .

Also if I have  $L_1$ is regular and $L_2$ is context-free, is $L_1/L_2$ Always regular? Always context-free but not always regular? Or not always context-free? Which one is true?

When $L_1$ is context-free and $L_2$ is regular, is $L_1/L_2$ always regular? Always context-free but not always regular? Or not always context-free?

Any ideas will really help me in preparing for my test.


texts:
Seems very trivial but I'm confused which one of these correctly define transmission time.

Time taken by a message to reach receiver.
Time taken to push message on the link by the sender.

Which one is correct one?


texts: Sometimes I read that an algorithm works on constant size alphabet and it is clear for me but what means that an algorithm works with a non constant size alphabet? I would like to see an example.


texts: Relationships between centrality metrics?

texts:
I am studying graph centrality, and came across a very nice table in here (reproducing it below, all credit goes to the original authors Shaikh Arifuzzaman and Md Hasanuzzaman Bhuiyan).

I have computed some correlations between centrality metrics based on a network that I have, but I'm having trouble interpreting what I'm finding. Specifically:

Correlation degree vs eccentricity is negative, but degree vs closeness is positive: this means that many central nodes are very "close" to most nodes in the network, but how to interpret this with respect to eccentricity (i.e. longest paths)?
Correlation eccentricity vs closeness is negative: can this mean that some nodes are very close to most of the nodes in the network, but many longest paths pass through those nodes? I'm having a hard time interpreting this.
Eigenvector centrality correlates positively with degree and closeness (understandably), but shows no correlation with eccentricity or betweenness.

I would really appreciate any help in understanding this.


texts: have new discoveries been made in linear algebra since the dawn of AI or was it all "laid out" for the computer scientists by former mathematicians?


texts: Reinforcement learning without self-play

texts:
Self-play seems to be very important for reinforcement learning algorithms. Can we train reinforcement learning algorithms without self-play (or learn mostly from past experiences)?

For example, let's say that I want to build a TRPG AI, which involves natural language and physical interaction between heterogeneous players. I can't do self-play this game so many times. But I happen to have a lot of match log of past human games.

Can I achieve higher score than humans using reinforcement learning using these logs (maybe like Experience Replay)?


texts: Fast algorithm for clustering groups of elements given their size/time

texts:
I don't know if there is a canonical problem reducing my practical problem, so I will just try to describe it the best that I can.

I would like to cluster files into the specified number of groups, where each groups size (= the sum of sizes of files in this group) is as close as possible to each other group in this cluster (but not in other clusters). Here are the requirements:

The first group always contain one file, which is the biggest of all groups in the cluster.
Any other group but the first can have multiple files in it.
The number of groups in each cluster is constrained to a maximum specified by user (but there can be less groups if it's better or there's not enough files).
There's no constraint on the number of clusters (there can be as little or as many as necessary).
Goal (objective function): minimize the space left in all groups (of all clusters) while maximizing the number of groups per cluster (up to the maximum specified).

The reason behind these requirements is that I am encoding files together, and any remaining space in any group will need to be filled by null bytes, which is a waste of space.

Clarification on the objective and constraints that follow from the requirements and the problem statement:

Input is a list of files with their respective size.
Desired output: a list of clusters with each clusters being comprised of groups of files, each group having one or several concatenated files.
There must be at least 2 groups per cluster (except if no file is remaining) and up to a maximum of G groups (specified by user).
Each file can be assigned to any group whatsoever and each group can be assigned to any cluster.
The number of clusters can be chosen freely.

Here is a schema that shows one wrong and one good example of clustering schemes on 5 files (1 big file, and 4 files of exactly half the size of the big file) with a number of groups = 2:

The solution needs not be optimal, it can be sub-optimal as long as it's good enough, so greedy/heuristics algorithms are acceptable as long as their complexity is good enough.

Another concrete example to be clear: let's say I have this list of 10 files with their sizes, this is the input (in Python):

['file_3': 7,
'file_8': 11,
'file_6': 14,
'file_9': 51,
'file_1': 55,
'file_4': 58,
'file_5': 67,
'file_2': 68,
'file_7': 83,
'file_0': 85]

The final output is a list of clusters like this (constrained here to 3 groups per cluster):

{1: [['file_0'], ['file_7'], ['file_2', 'file_6']],
 2: [['file_5'], ['file_4', 'file_3'], ['file_1', 'file_8']],
 3: [['file_9']]}

And for example here (this is not a necessary output, it's just to check) the total size of each groups (ie, sum of file sizes for each group) for each cluster:

{1: [85, 83, 82], 2: [67, 65, 66], 3: [51]}

If the problem is NP-complete and/or impossible to solve in polynomial time, I can accept a solution to a reduction of the problem, dropping the first and fourth requirements (no clusters at all, only groups):

Here is the algorithm I could come up with for the full problem, but it's running in about O(n^g) where n is the length of the list of files, and g the number of groups per cluster:

Input: number of groups G per cluster, list of files F with respective sizes
- Order F by descending size
- Until F is empty:
    - Create a cluster X
    - A = Pop first item in F
    - Put A in X[0] (X[0] is thus the first group in cluster X)
    For g in 1..len(G)-1 :
        - B = Pop first item in F
        - Put B in X[g]
        - group_size := size(B)
        If group_size != size(A):
            While group_size < size(A):
                - Find next item C in F which size(C) <= size(A) - group_size
                - Put C in X[g]
                - group_size := group_size + size(C)

How can I do better? Is there a canonical problem? It seems like it's close to scheduling of parallel tasks (with tasks instead of files and time instead of size), but I'm not quite sure? Maybe a divide-and-conquer algorithm exists for this task?


texts: Huffman code optimal substructure property

texts:
I am learning about Greedy Algorithms and we did an example on Huffman codes. To prove the correctness of our algorithm, we had to have the greedy choice property and the optimal substructure property.

Here is what my professor said about the optimal substructure property:

Let C be an alphabet and x and y characters with the lowest frequency.

Let C' = C-{x,y}U{z} where z.frequency = x.frequency + y.frequency

Let T' (a binary tree) be an optimal prefix code for C'
She then drew these pictures

Let T be constructed from T' by replacing z with an internal node with children x and y.
Then T is an optimal prefix code for C

And I don't really understand what/how this proves anything. All I see that she is doing is like..working backwards. First she replaced x and y with z, and now she is replacing z with x and y. What exactly is this showing? I'm really bad with proofs sometimes so I am just completely lost as to how this showed me anything about anything


texts:
Apologies for the newbie question, but I am a bit confused about what exactly counts as a "simple operation" when working out the time complexity of an algorithm. In particular, why do we consider all operations to be equal?

Surely, dividing two very large numbers is more time-consuming than adding one to a number (as in each iteration of a for loop). Multiplication, for example, can consist of any number of small additions. So, instead of just adding them up shouldn't we be applying some kind of weight to each operation depending on the type of operation (addition, multiplication, etc) and the size of the numbers involved?

My problem is that I am being asked to prove that the complexity of my algorithm is $O(f)$ (for some function $f$) and I am not sure how to do this in a mathematically rigorous fashion because of the inherent vagueness in the definition of a "simple operation". So how would I go about this?


texts: Is there any count-preserving cellular automata which tends do "10101010..."?

texts: Suppose that I have a bit string of finite length. Is there any bit rewriting rule rewrire :: (Bit,Bit,Bit) -> (Bit,Bit,Bit), that doesn't change the total count of 1s on the bit string, and that when applied to arbitrary triplets in any order will converge to a bit string that will begin with an arbitrarily long sequence of 10, followed by either all 0s or all 1s.


texts: Reduction from cardinality constrained project selection problem to CLIQUE problem

texts:
Give the polynomial-time $A$ algorithm of the cardinality constrained project selection problem plus the integer k, we are able to compute a maximum-profit set of at most projects to undertake, can we reduce the cardinality CLIQUE $l$ of an undirected graph $G = (V, E)$ (a subset $U$ of $V$ such that $|U|= l$ and each pair of vertices in $U$ is connected by an edge in $E$)?
The biggest challenge for me is that the project selection problem is a directed graph but CLIQUE is an undirected graph. How can I convert the undirected graph to a new graph such that I can use the algorithm of cardinality constrained project selection problem to solve the $l$ CLIQUE?


texts: Applying the Master Theorem on Merge sort

texts:
I found the proof below in a textbook. I would like to know why it is important for the proof that it uses $\lceil \frac{n}{2} \rceil$ instead of just $\frac{n}{2}$? I know that you can't split into calls which aren't natural numbers, but how do I present this argument formally?

The proof:

The recursion splits the problem into two sub problems, each with at most $\lceil \frac{n}{2} \rceil$ elements. Therefore, we can apply the Master Theorem with $a = b = 2$. So, $\log_b{a}$ = 1. The cost of splitting is $0$ comparisons, and that of combining is at most $n−1$ comparisons. Hence the cost of split/combine is $\Theta(n) = \Theta(n\log_b{a})$, so we are in the second case of the Master Theorem, and therefore the total cost is $\Theta(n\log n)$.


texts: Determining Range of Current Node in Segment Tree

texts:
I was attempting, though failing quite miserably, to find some method of of determining the range of some node $n$. By range I mean an interval $[l,r]$ over the base array that is reachable by the sub-tree rooted at $n$.

I'm sorry of using incorrect terminology; I am inexperienced in formality. If, due to this, my explanation above does not make sense, I will instead provide a example:

For the Segmented Tree based off of $A=\{1,2,3,4,5,6,7,8\}$, the root $n_1$ would have a range $[0,l-1] = [0,7]$ for $l$ as the length of the the base array.
The root's left leaf $n_1$, would then have a range $[0,\left\lfloor\frac{l-1}{2}\right\rfloor]=[0,3]$.

The motivation for this is having a recursive update function that requires only the interval to be updated and the current node: $update(l,r,n_i)$


texts:
A random geometric graph (https://en.wikipedia.org/wiki/Random_geometric_graph) is constructed by choosing $n$ points in $\mathbb{R}^d$ at random according to some distribution, and setting $p_i \sim p_j$ if $\|p_i - p_j\|<r$, for some parameter $r$. Geometric graphs are of use in modelling real world networks.

For example, we can model a transportation map using the uniform distribution on $[0,1]^2$.

I am interested in whether there are good graph theoretic algorithms for dealing with these graphs. For example, is there an algorithm for finding the shortest path between two vertices that is better (in expectation) for these graphs than BFS? Obviously such an algorithm would be useful for GPS manufacturers.

Does research like this exist?


texts: projection of arithmetic formulas to determinant

texts:
I am looking for a direct proof (i.e. without going through ABPs) that if $f(\bar{x})$ has an arithmetic formula of size $s$ then it is a projection of an $O(s)\times O(s)$ determinant.

It seems possible using induction on $s$.

The basis, when $s=1,2,3$ is trivial.

Suppose we proved it for size $s$ formulas and let $f$ be a size $s+1$ formula.

If the root gate is a $\times$ gate with children $f_1,\cdots,f_k$, by induction we have that each $f_i$, which is also a formula, is a projection of a determinant of size $O(s_i)\times O(s_i)$, say $f_i=\text{det}(M_i)$.

So, if we construct a new matrix $M$ which is a block matrix with the $M_i$'s as its blocks and zeros elsewhere. Then $\text{det}(M)=\prod_{i=1}^k\text{det}(M_i)$ and the dimension of $M$ is $O(s_1)+\cdots+O(s_k)=O(s)$.

My problem is when the root is a $+$ gate.


texts: Can you say anything interesting about a language knowing only that it is prefix-closed?

texts:
Suppose $L$ is an arbitrary formal language over a finite alphabet $A$, and suppose that $L$ is closed under prefixes (i.e. if $w \in L$, and $u$ is any prefix of $w$, then $u \in L$).
Knowing only this, can you give any positive or negative decidability or complexity results about $L$?
Thanks! :)