texts: Prove the equivalence of regular expressions

texts:
I have a question relating to regular expressions that I'm a bit confused about, If someone can help me out, that would be very much appreciated.

Suppose there exists regular expressions R, S and T.

Then is R* ≡ R* R*?

I know the way to prove this is by showing that L(R*) is a subset of L(R*R*) and vice versa, but I have no idea how to do that.. Just started learning about regular languages so I'm a bit confused. Can I please get any direction on how to do this?


texts:
MAX-2SAT is NP-Complete.
If the solution is stipulated to be unique, is MAX-2SAT still NP-complete?


texts: Is the algorithm implemented by git bisect optimal?

texts:
Let $G$ be a DAG. We know that some nodes in $G$ are "bad", while the others are "good"; a descendant of a bad node is bad while the ancestors of a good node are good. We also know that bad nodes have a unique minimal element in $G$ which we'd like to find querying as few nodes as possible with queries of the type "Are you good or bad?".

This problem is solved in Git, the popular version control system, by the command git-bisect, which helps a programmer find the first commit in which a bug was introduced.

At the start, the algorithm implemented by Git assumes to know a single bad commit and one or more good commits. At each step of its execution, the algorithm finds a commit using the following steps (taken from here):

Keep only the commits that:

a) are an ancestor of the bad commit (including the bad commit itself), and

b) are not an ancestor of a good commit (excluding the good commits).
Starting from the good ends of the resulting graph, associate to each
commit the number of ancestors it has plus one.
Associate to each commit $\min(X, N-X)$, where $X$ is the value associated to the commit in step 2, and $N$ is the total number of commits in the graph (after it was reduced in step 1).
The best bisection point is the commit with the highest associated
number.

This algorithm is essentially finding the commit that achieves the "worst best case": in fact, $\min(X,N-X)$ is the number of nodes in the DAG at the next iteration in the best case, thus $\max\min(X,N-X)$ is the worst best case.

I'm wondering:

Does it make any difference if we select the "best worst case", that is, the node that achieves $\min\max(X,N-X)$?
Is this algorithm worst-case optimal?

EDIT: I've noticed that this problem has a $\Omega(N)$ bound. Consider the DAG formed by a single node $b$ with $N-1$ parents called $g_1,\dots,g_{N-1}$. If we know that $b$ is bad then we have check each of the parents to see if they are the minimal bad node.

EDIT 2: The previous is actually a $\Omega(w)$ bound, where $w$ is the width of the poset. An alternative algorithm for this problem is given in this answer on cstheory.stackexchange that uses $O(w\log{n})$ queries.


texts: Are there current benchmarks for algorithms solving Travelling Salesman?

texts:
I'm researching the travelling salesman problem and looking for data regarding the current state of affairs regarding solutions and performance. So far the only data I've states that the current record for optimality is held by 'Concorde' which found a solution for a graph containing 85,900 cities. I've also found benchmarking data for Concorde, as well as data pertaining to the current best performance for a world map.

Is this data still accurate? It looks like a lot of this hasn't been updated since the early 2000s.


texts: Correctness of a greedy Algorithm on Knockout Tournaments

texts:
You are given a function $\operatorname{rk}:\{1\dots 2^k\}\rightarrow \mathbb{N^+}$ representing the ranks of the players $1\dots2^k$ in a participating in a tournament. The tournament evolves in a random way, so that when player $i$ faces player $j$, he wins with probability $\frac{\operatorname{rk}(i)}{\operatorname{rk}(i)+\operatorname{rk}(j)}$. When a player loses a game, he gets knocked out of the tournament, thus the tournament finishes in $k$ rounds.

You are requested to arrange the players into a knockout tournament starting line-up (i.e. on the leaves of a complete binary tree of height $k$) in the way that maximizes the probability that player $1$ wins the tournament.

The official greedy solution, presented without any trace of proof, is the following:

Sort the players $1, r_2, r_3, \dots r_{2^k}$, where $r_2, \dots r_{2^k}$ are the players $2 \dots 2^k$ sorted in ascending order of their rank.
Arrange players $1, \dots, 2^{k-1}$ in the left-subtree and $2^{k-1} + 1, \dots 2^k$ in the right subtree and recurse.
For each node $v$ of the tree compute (bottom-up using dynamic programming) the probability vector $P_v$ such that $P_v[x]$ is the probability of player $x$ winning the sub-tournament rooted at $v$.

This algorithm runs in $\mathcal{O}(n^2 \log n)$.

How to prove that the algorithm is also correct?

The original problem is from ICPC NWERC 2017 (problem K). Here we posted a simplified version.


texts: PDA recognising all strings with a $1$ in the second half

texts:
My professor gave us an old exam to look over for our final exam and I am having a hard time understanding the push down automata problem he gave. In the problem it says:

  Let $\Sigma = \{0,1\}$ and $B$ is the collection of all strings that contain at least one $1$ in the second half. To state it more precisely: $B=\{uv\mid u \in \Sigma^{\ast}, v \in \Sigma^{\ast} 1 \Sigma^{\ast}, |u|\geq|v|\}$. Give a PDA that recognizes $B$. Give a diagram to describe your PDA.

My question is why do I need a PDA or really a stack for this because all I am looking at is the second half which I can just epsilon to the second half and then when I read a $1$, go to the accept state. For example if $u=1001010101$ and $v=000011$, wouldnt I just loop around for a bit for u and then epsilon over to say I am now looking at $v$. Then when I read the first $1$, I just accept. I wouldnt need to use the stack at all would I?
I'm not sure if I understand it correctly or not and would appreciate any help.


texts: What is the $\mathcal O$ of subtraction-based GCD algorithm?

texts:
Subtraction-based algorithm for finding the greatest common divisor works like this:

For two integers a and b (a > 0, b > 0),
if a > b, then gcd(a, b) = gcd(a-b, b)
else if b > a, then gcd(a, b) = gcd(a, b-a).
else if a = b gcd(a, b) = a

What is the $\mathcal O$ of this algorithm?


texts: Are these two sensible and related or unrelated ways of regarding a logic system as a programming language?

texts:
When I am trying to understand logic programming languages e.g. Prolog, I am immediately confused by the following two ways of relating logic systems and programming languages or type systems.

In Types and Programming Languages by Pierce, Section 9.4
Curry–Howard correspondence on p109  has a table

Does it mean that a logic system is a programming language, where

types are propositions and
values of a type are proofs of the proposition?

On the other hand, a logic system is described in a formal language
that defines what a logic expression is. Can we view a logic system
(e.g. the first order predicate logic system) as a programming
language, where

it has two types: Boolean type and function type, and
Each logic expression without a variable has Boolean type, so can be evaluated to a truth value.  Each logic expression with any
variable has Boolean function type, so its application to truth
values for its variables can be evaluated to a truth value?

Are the above two views of a logic system as a programming language completely unrelated/orthogonal, or are they the same or can they be unified?

Thanks.


texts:
I'm trying to find out how many circuits exist in a graph $G$, given its adjacency matrix.

Yet, the only thing I know is how to find out if there is a circuit in a graph $G(X,U)$ given a list of out-neighbours for each vertex.  To do that, you just delete every vertex with no out-neighbours, and update the adjacency lists for the remaining vertices. If repeating this operation deletes all the vertices, the graph had no circuit; otherwise, it has a circuit.

For example,

\begin{array}{|l|cr|}
x & \Gamma^+(x)\\
\hline
a & b,c,d\\
b & d,e\\
c & d,f \\
e & d,h \\
f & g,i \\
g & h, e \\
h & \emptyset\\
i & g,h \\
\end{array}

Whenever  $\Gamma^+(x)$ is empty, we can delete $x$.

\begin{array}{|l|cr|}
x & \Gamma^+(x)\\
\hline
a & b,c,d\\
b & d,e\\
c & d,f \\
e & d,\not h \\
f & g,i \\
g & \not h, e \\
\not h & \not\emptyset\\
i & g,\not h \\
\end{array}

Therefore, a circuit exists in $G$.

Yet, it only tells me if there is a circuit in my graph. How may I find all circuits?

for instance with:

$$\begin{bmatrix}
   0 & a & b & c & d & e & f & g & h & i \\
   a & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\
   b & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\
   c & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\
   d & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
   e & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\
   f & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\
   g & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 \\
   h & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
   i & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\
\end{bmatrix}
$$

What algorithm should I use to find all the circuits of this graph? Even a hint would be appreciated.


texts: Regular expression for a language which doesn't look regular

texts:
I'm trying to find a regular expression for the following language:

$$L=\{x0y : \text{$x$ contains same number of 0's as $y$ contains 1's}\}. $$


texts: AVL Tree - Print ascending using in-order

texts:
Trying to understand how to write proof of correctness.
Searched over the internet on how to write proof of correctness but can't find a good solution for it.

The following sorting algorithm is proposed using the AVL tree: AVL input of all elements, and printing them in order.

Algorithm  - Sort AVL (A[1..n])

T -> Empty AVL Tree.

for each 1 <= i <= n

insert A[i] to T.

print T elements by using in-order fashion.

Prove the correctness of the algorithm by showing the in-order scan of binary tree is always in ascending order.


texts: Asymptotic lower bound on the number of comparisons needed to find the intersection of unsorted arrays

texts:
A homework problem in my current CS class asks us to produce a comparison-based procedure for taking (essentially—there are some poorly-specified rules about duplicates) the set intersection of $k$ unsorted arrays of at most $n$ elements each. For full credit, we are supposed to do this in $O((k-1)n)$ comparisons. (Specifically, we are given a Java array of arrays of Comparable elements.)
I'm pretty thoroughly convinced that this is impossible, and that the best worst-case comparison bound for such a procedure is $\Theta(N\log n_0)$, where $N$ is the sum of the lengths of the arrays and $n_0$ is the length of the shortest array. I don't, however, know how to prove this is the best.
Since producing such an algorithm is current homework, please adhere to the following restriction in your answers/comments: if I am wrong, and it is possible to do better, do not reveal the algorithm unless it is very difficult (in which case a link to a relevant paper would be appreciated).
What I've tried so far
The shortest array has $2^{n_0}$ subsets. This gives an immediate information-theoretic lower bound of $\Omega(\log_2(2^{n_0}))$. Unfortunately, this is just $\Omega(n_0)$, and $O(n_0)$ obviously can't be obtained.
Edit
I missed a line in the (rather long) assignment. It looks like what he's looking for is actually a lot less interesting than what I thought he wanted. However, I'm still curious about how to prove a lower bound of $\Omega(N \log n_0)$, if that is the lower bound.


texts: I've been recently studying Monte-Carlo and other randomized methods for a lot of applications, and one that popped into my mind was making an (approximate) convex hull by examining random points, and try to get them inside the convex hull. I would like to know if there are algorithms for convex hulls that can improve the $O(n \log n)$ bound of comparison based algorithms, and the $O(n\cdot h)$ bound for Jarvis march and related to $O(n)$, either by building an approximate convex hull in $O(n)$ (with or without some approximation criteria) or by building an exact convex hull in expected linear time.


texts: Why is the running time of heapsort $O(n\log n)$?

texts:
Heapsort(A)
1 BUILD_MAX_HEAP(A)
2 for i=A.length downto 2
3    exchange A[1] with A[i]
4    A.heapsize=A.heapsize-1
5    MAX_HEAPIFY(A,1)

In the book on algorithms by CLRS the running time of this algorithm is given to be $O(n\lg n)$ as the for loop is executed $n-1$ times and each call of MAX_HEAPIFY takes $O(\lg n)$.

But my question is does MAX_HEAPIFY not depend on height of subtree at which it is called? Why then should it still be the same for all $n-1$ calls as $h$ will obviously differ?


texts: Confused about Telescoping/Domain Transformation Question

texts:
I have been working on the following domain transformation problem however, I am stuck on how to continue to receive the solution. I would greatly appreciate it if someone can explain how I can complete this:

T(1) = 0

T(n) = T(n/2) + n^2

The following is what I have so far:


texts: PDA for the language of words $uv$ such that $|u| \geq |v|$ and $v$ contains 1

texts:
Consider the language $\{ uv : \text{$|u| \ge |v|$ and $v$ contains a 1}\}$.
I am unable to understand how to accept this language using a PDA. How to check the length condition as well as check if there's a 1 in the $v$ portion?
The question has previously been posted here but I couldn't figure out much from the answers to that.
PDA recognising all strings with a $1$ in the second half


texts: Linear Search Algorithm - Why allow a user to input a start and end index to LS?

texts:
Here is the linear search algorithm provided in class:

bool LinearSearch(int [] a, int l, int u, int e) {
      for(int i:=l; i ≤ u ; i := i + 1) {
          if (a[i] = e) return true;
      }
      return false;
}

If the intention of this function was to linear search through the function why allow a parameter of l and u? A user could test this function in ways to breach the intention of linear search. For example let l and u be numbers such that it only searches through a subsequence of the list and not the entire list. I asked my professor if the intention of this code was to have the possibility of it being used in ways that do not search the entire list. She didn't quite understand me, because she replied "No, it should be possible to search through the entire list." Well I know it's possible but why have the l and u if you can just write the code better and remove l and u. Now I know in other languages you might need to know the bounds, but this isn't a programming class whatsoever.


texts:
Suppose we have a set of equations like this

p7=f(p1+p6); p6=f(p2+p5); p5=f(p3+p4); p4=f(p3); p3=f(p2); p2=f(p1); p1=f()

It can be represented by computational graph below

If each intermediate value takes 1 unit of memory, you need at least 4 units to compute p7 without any duplicate computation.

Is there an algorithm for estimating memory needed in this setting for a general DAG?

I found a paper called "Adjoint Dataflow Analysis" for estimating this for restricted set of graphs, but it feels like this ought to be a problem that is covered more generally in graph theory.


texts: Deriving recursive definition from function specification

texts:
Given this function specification, where name xs is bound to a list, # denotes its cardinality and . is the list index operator...

$$\left( \sum i: 0 \leq i < \#xs: xs.i * (i + 1) \right)$$

I need to derive a recursive function using induction.

Base case: []

\begin{align}
 \left( \sum i: 0 \leq i < \#[]: xs.i * (i + 1) \right) && \text{(Textual substitution - xs is free)} \\
 \left( \sum i: 0 \leq i < 0: xs.i * (i + 1) \right) && \text{(Def. of #)} \\
 \left( \sum i: False: xs.i * (i + 1) \right) && \text{(Algebra)} \\
 \left( \sum i: 0 \leq i < \#xs: xs.i * (i + 1) \right) && \text{(Empty range)}
\end{align}

Inductive case: (x:xs)

\begin{align}
  \left( \sum i: 0 \leq i < \#(x:xs): (x:xs).i * (i + 1) \right) && \text{(Textual substitution - xs is free)} \\
  \left( \sum i: 0 \leq i < 1 + \#xs: (x:xs).i * (i + 1) \right) && \text{(Def. of #)}
\end{align}

How can I proceed from here ?


texts: Is deciding if there's a solution to a single multivariate quadratic equation NP-hard?

texts:
I know that given a system of multivariate quadratic equations (i.e, of the form $x^T Ax+b^T x=c$), deciding if there's a solution is NP-hard.

Is deciding if there's a solution to a single multivariate quadratic equation NP-hard too?

I am intersted in the NP-hardness of deciding if there's a solution to a single quadratic equation over any field; not only over $\mathbb R$.

I am currently trying to reduce from the problem of deciding whether there's a solution to the equation $x^T Ax=\lambda$ subject to $x\in[0,1]^n$ (which is NP-complete) to our problem using Lagrange multipliers.


texts: How to reduce independent set to longest path

texts: A friend and I have tried for several hours to try and find a reduction from  independent set to longest path, but the results have not been fruitful. We have tried many methods of graphing and complementing but are well and truly lost. Any help would be much appreciated!


texts:
Consider a large graph, minimum 1 000 vertices but it can easily go up to 50 000 vertices depending the case. The graph is the result of social relationships (followers, following, friendship) so it can be oriented but for the ease of the solution let's say it's not, so the matrix is symmetric. Moreover the matrix of adjacency is highly sparse.

I need to calculate the eigenvalues, but the major problem as I see it is that computing eigenvalues for large adjacency matrices cost a lot on time complexity due to matrices operations.  If I can't efficiently compute all the eigenvalues, even a method to find the largest eigenvalue would be nice.

I've searched through the literature in vain, is there an algorithm or other approach to solve this?


texts: How does conversion from fixed-point to floating-point happen?

texts:
I came across to the code that convert 32-bit signed fixed-point number (16.16) to a float and it looks like (pseudocode)

floating = fixed / 65536.0

Could you please explain me what's the essence of dividing by this? Why does this dividing works when fixed-point and floating-point numbers have different internal structures?


texts: Push down automaton for Language of same number of as and bs

texts:
The task

  Find a pushdown automaton $M$, so that $L(M)=\{w \in \{a,b\}^*\ |\ |w|_a=|w|_b\}$, where $|w|_a$ denotes the number of $a$s in a word $w$.

My solution

I'm using the Wikipedia notation.
$$M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, \{q_0\})$$
$$Q=\{q_0\}, \Sigma = \{a,b\}, \Gamma = \{Z_0, A,B\}$$
$$\delta\text{ has the following instructions:}$$
$$(q_0, \varepsilon, Z_0, q_0, \varepsilon),$$
$$(q_0, a, Z_0, q_0, AZ_0),$$
$$(q_0, b, Z_0, q_0, BZ_0),$$
$$(q_0, a, A, q_0, AA),$$
$$(q_0, b, A, q_0, \varepsilon),$$
$$(q_0, b, B, q_0, BB)\text{ and}$$
$$(q_0, a, B, q_0, \varepsilon).$$

Questions

Is this correct? Can it be simplified?
If so, how can I argue (not neccessarily proof) its correctness?


texts: Best algorithm to generate matchmaking pairs

texts:
I am trying to come up with a matchmaking algorithm based on player ratings for my game, and I am pretty sure the algorithm I have is not the best (or maybe doesn't even work), but have no idea how to improve it.

Suppose that I have 5 players, ABCDE, and I want to create a 2v2 match. Each party of 2 have their own ratings precalculated. Suppose that my algorithm is based on minimizing the rating difference between the two parties. DIFFRAT below means the absolute value of the rating difference between the 2 parties:

To start I would generate all possible matchmaking combinations and calculate their DIFFRAT. For 5 players, ABCDE, here are a few of the possible matchmaking combinations:

AB->CD (DIFFRAT = 2)

AB->CE (DIFFRAT = 0)

AB->DE (DIFFRAT = 1)

AC->BD (DIFFRAT = 4)

AC->BE (DIFFRAT = 5)

AC->DE (DIFFRAT = 2)

AD->BC (DIFFRAT = 0)

Currently, the match making algorithm I have would recursively pick the lowest DIFFRAT match first. Then remove the matches where the players already match made.

However, this is problematic when there are n players, and n/4 matches are to be created. This approach would always greedily pick the lowest DIFFRAT first, thus removing players from the better matchmaking options. In fact, this approach would probably prevent some players from finding a match as well.

What is a better way of implementing matchmaking than the one I have so far?


texts: Value Maximisation Algorithm with multiple costs

texts:
So in front of me lies different items. To buy each item you will need a certain amount of multiple things. For example, to buy a lamp, you will need to pay 3 apples, 4 oranges and 17 bananas. Each item has it's monetary value, and some items can only be unlocked after another item is bought.
To rephrase:
There are n items each with a value of kv.
For each item k, it will cost you a different amount of w, x, y, z.
For some item ki, another item kj needs to be bought for ki to be buyable.
Given a certain amount of w, x, y and z, maximise the total value bought, identifying which items to buy.

I'm figuring out what algorithm I can probably look into.
If you take away the item unlocking part then it looks like a knapsack with multiple weights on each item. What is my best bet on this?


texts:
I came across a new list data structure called GlueList that claims faster than classic list implementations.

How does it work ?

How can it be faster than ArrayList and LinkedList ?


texts: Determining if (infinite) binary language DFAs contain at least 1 prime?

texts:
This problem has been given by Shallit as an open DFA/ complexity theory problem and is currently not even known to be decidable. It seems to be circulating on the internet in a few places (e.g. [1][2]) but not in any papers. Almost nothing seems to be known or published. I am looking for any nontrivial analysis or references.

  Given: binary DFA D. Does L(D) contain at least 1 prime?

(Binary means Σ = {0, 1}.) As an example of something nontrivial about it (a subproblem), what can be said of the base-2 DFA language representations, what is their general form? Or, given any d, does there exist a DFA (language) that contains only multiples of d in binary? Are there arithmetic progressions embedded in DFA binary languages? Note there are many number theoretic investigations into primes in arithmetic sequences/ progressions and recent findings/ research, could any be demonstrated to be applicable?

[1] a simple problem whose decidability is not known / cstheory.SE

[2] are there any open problems left about DFAs? / cstheory.SE


texts:
From Wikipedia: Off-side_rule#Implementation, there is a statement:

  ...This requires that the lexer hold state, namely the current
  indentation level, and thus can detect changes in indentation when
  this changes, and thus the lexical grammar is not context-free –
  INDENT/DEDENT depend on the contextual information of previous
  indentation level.

I'm a bit confused. Some lexical grammars of Python is not context-free but INDENT/DEDENT themselves can be expressed in CFG. So lastly, Python is a context-free language or not?


texts: Calculating the end-to-end delay of a message sent over a network

texts:
This is a problem from a MOOC on computer networking:

  We wish to send a message of size $150,000$ bytes over the network. There are four hops, each of length $20$ km and running at $100$ Mb/s. However, before sending we split the message into $1500$ byte packets. What is the end-to-end delay of the message? Use speed of light in copper $c = 2 * 10^8$ m/s, and round your answer to the nearest integer millisecond.
  HINT: Break the problem into two parts: the end-to-end delay of one packet and the delay of the rest of the message across the slowest link.

After struggling for a bit, I obtained the answer by following the hint as follows:

$$
4\left(\frac{1500 \ B * 8 \ (b/B)}{100 \ Mb/s} + \frac{20 \ km}{2 * 10^8 \ m/s}\right) +
\left(\frac{150000}{1500} - 1\right)\left(\frac{1500 \ B * 8 \ (b/B)}{100 \ Mb/s}\right) = 12.76 \ ms
$$
The answer is correct but I don't understand why the packetization delay only was considered for the rest of the message. Why wasn't the propagation delay also considered for the remaining packets?


texts: Data structure for maintaining large space-efficient filtered array

texts:
How does one implement a space efficient data structure that satisfies the requirements below?

You have a large array
You have a filter which tells you which elements in that large array are to be deleted
Lookup of i'th element in the array should be constant time
The space formerly occupied by deleted elements in the array should be available for further use.

I've explored approaches ranging from bloom filters to trees, but they violate one requirement or the other.

EDIT: Further clarification.

Space-efficient: Any space not used by elements of the array that have not been deleted by the filter, which we can term extra space or space for book-keeping, should be $O(1)$. We can probably relax this to allow any solution that gets close to $O(1)$ extra space. $O(n)$ extra space is undesirable.

Array in the context of this problem is an array-like collection where you can get the $i$th element in constant time. You lookup by index here.

I suspect amortized performance bounds should be fine.

The filter takes each element of collection and returns 0/1 corresponding to delete/no delete.


texts: What is the Time Complexity of $T(N)=2T(N/2)+\log n!$ and the answer does not have $\log n!$ in it?

texts:
None of the 4 possible answers have $\log n!$ in them

e.g. one of them is $O(n\log n)$

I tried solving, but I can't get why there is no $\log n!$ in non of the answers?!


texts: Approximation Algorithms via Unit Disk Graph Embeddings

texts:
A unit disk graph is defined by a collection of $n$ vertices corresponding to $n$ points on the plane, with an edge between any two vertices whose distance is at most $r$.
Some $NP$-hard problems become solvable in polynomial time for unit disk graphs. I am interested in designing approximation algorithms by adapting such algorithms to general graphs as follows:
Let $A$ be an algorithm that solves an $NP$-hard problem in polynomial time in the special case of unit disk graphs.

Given a graph $G$, first embed it into the plane in such a way that vertex pairs connected by an edge tend to be close together, whereas vertex pairs that aren't connected tend to be farther apart.

Of course, the resulting graph is probably not going to be a unit disk graph, but hopefully it is close to such a graph in some sense.

Use the algorithm $A$ to find a solution for the graph.

Hopefully, if the embedding of $G$ is close to a unit disk graph, $A$ will return a good approximation to the $NP$-hard problem.
Has this type of thing been studied? In particular, I haven't been able to find an appropriate algorithm for the first item.
"Low distortion Embeddings" is something related but different: There, the goal is that all edges should have similar lengths, whereas in my case I don't care about eliminating short edges. I just don't want any long edges.
I have an idea but it's rather silly: I thought of running a physical simulation in which we place an attractive force on edges between vertices that are far apart, and a repelling force on non-edges between vertices that are close together. We would wait for the system to reach an equilibrium, which hopefully would minimize some potential function that measures the distance between our embedding and a unit disk graph.


texts: Is the language below not decidable , if yes , it is then R.E ?

texts:
I am given a Turing machine M as input  and i have to find  out  if this language  below  decidable  and  if not  is it then in this case  recursively enumerable .

$$L=\\\{<M>  \mid \text{ is there $w_1,w_2$ for M so that M for both halts but  with  different results }\}$$

Somehow i ended up finding that the language is not decidable nor R.E .

if you have an other point of view ,  can you  then please give me some  hints.


texts: Best a-little-advanced examples of dynamic programming

texts:
I was offered by a professor to give some tutoring in his course of Algorithm Design, based on Kleinberg and Tardos' book. He suggested me to prepare two exercise on dynamic programming, one exercise for polynomial reduction, and another one for approximation algorithms.The exercise should be not too advanced, but not just routine (they should fill two hour of tutoring).

Then my question is: what are fascinating problems one can propose in dynamic programming?


texts:
This is my first time posting here, so I hope I'm on topic. I have a table of natural-language data of the form
[Underlying] -> [Observed]
ABC -> abcd
EFGH -> eghf
IJK -> ik
LMNOP -> lnop
LNOP -> lnop

and so on. There are around 5000 more of these, but this is a sort of representative sample of things that go on. For the most part, it is fairly
obvious which underlying states correspond to which observed state, but sometimes things get deleted, sometimes adjacent states swap spots, sometimes things get added, and sometimes two underlying sequences have the same observed sequence of characters. In the list of productions, assume that I have tagged each uppercase (underlying) state with its corresponding lowercase (observed) state. So in EFGH -> eghf, my program knows that f and g have switched spots in the output.
Now when the program is given a new string, it is completely untagged. So given eghf, it would have to somehow deduce that EFGH was the underlying sequence of states.
I would like to be able to output all productions that could have occurred, given a string with a substring that is an observed string. For example, if
my program is given the string
xxxxlnopxx
it should output xxxx[LMNOP]xx as well as xxxx[LNOP]xx. We know there is only one observed substring (so we don't have to worry about, say, abcd hiding in the xxxx part of the string).
There is no distributional data at all on how often each production happens,
so I would simply output every possible parse if more than one exists. Is this a special case of some kind of parsing algorithm? I guess the finiteness of the data means I could simply make a dictionary of all 5000 observed -> {set of underlying}, and then search for substrings, but one of the motivations of my exercise is to see "how" context-free/regular/context-sensitive my list of productions is. For example, perhaps the grammar reduces to something context-free, minus a couple of exceptions that can be hard-coded in. This is something I'd like to detect if possible.
Thanks in advance for the help! I would equally appreciate a link to a paper or outside resource that has solved a similar problem.


texts: Minimum spanning tree and Hamiltonian path

texts:
For a graph $G(V,E)$, under what conditions is a minimum spanning tree  of $G$ equal to a hamiltonian path on $G$?
IS there any body of literature connecting these two?


texts: Does minimum cost flow problem work for real valued edge weights/costs?

texts:
I'm a bit confused about the definition of the Minimum Cost Flow problem, in terms of the edge cost (or weight) values.

I don't remember a integral requirement on the cost/weight values for the edges when first learning the problem. But when I start to look for implementations, most algorithmic code I found require the edge weights to be integers. (I haven't delved into Simplex or LP related code though). For example, in here, and here, weight values are defined as int cost; and typedef long long int price_t; ... price_t _cost; // cost of arc;, resp.

Boost Graph Library (BGL) seems to allow different weight types through C++ templates, but the examples in documentation are using integer weight values. The only use of floating weight values I can find is a SO question about the errors associated with using the floating points (https://stackoverflow.com/questions/35746487/). Google optimization tool also has a bug/feature request for floating point weight values, which is closed immediately stating it only supports int64, currently.

Is there a fundamental reason behind this lack of real valued weights in mincost flow implementations (such as complexity)? That is, is the real valued Min Cost Flow more difficult or impossible to solve, or is this just a coincidence?


texts:
Given some strings, is there some algorithm (and program that implement such an algorithm) that can create a regex which matches some of the given strings and not the other given strings?

Note that the given strings are not all the strings that will be met by the regex.
I hope the regex can generalize well on other strings not given (just like machine learning algorithms), but not necessarily achieve 100% accuracy.

Also it will be great if such an algorithm can take into account the efficiency of implementing  regex matching

Thanks.


texts: Can a $k$-ary relation have polymorphisms of arity greater than $k$?

texts:
To quote Hubie Chen's A Rendezvous of Logic, Complexity, and Algebra (2009) on constraint satisfaction and complexity,

  An operation $f : D^m \to D$ is a polymorphism of a relation $R \subseteq D^k$
  if, for any choice of $m$ tuples $(t_{11}, ... , t_{1k}), ... , (t_{m1}, ... , t_{mk})$ from $R$, it holds that the tuple obtained from these $m$ tuples by applying $f$ coordinate-wise, $( f (t_{11}, ... , t_{m1}), ... , f (t_{1k}, ... , t_{mk}))$, is in $R$.

Two examples follow, but neither answers this question.  Let's say that there's a relation $R$ and function $f$ such that $m > k$.  Is $f$ a polymorphism of $R$?

Concrete example: Assuming an $\wedge$ relation $\{ (1,1) \}$ (i.e. arity is 2), is the majority function $f(a,b,c) = (a \wedge b) \vee (a \wedge c) \vee (b \wedge c)$ a polymorphism of this relation?


texts: Compute square root using (bit) additions and shifts as primitives

texts:
Question: Given an $n$-bit natural number $N$, how to compute $\lceil \sqrt{N} \rceil$ using only $O(n)$ (bit) additions and shifts?

The tip is to use binary search. However, I could not achieve the required complexity (I got $O(n^2)$).

What does it mean by using only $O(n)$ (bit) additions and shifts:

This is an exercise in an algorithm book.
In my opinion, it means that adding two, say $n$-bit, natural numbers costs $O(1)$ and shifting a, say $n$-bit, natural number also costs $O(1)$. Then we are only allowed to use such $O(1)$ operations $O(n)$ times.
It does not mention the cost of comparison. I guess we can ignore it or assume that comparing two, say $n$-bit, natural numbers costs $O(1)$ as well.

My $O(n^2)$ algorithm:

Determine the range of the number of bits $t$ of $\lceil \sqrt{N} \rceil$:
      $$2^{\frac{n-1}{2}} \le \sqrt{N} \le 2^{\frac{n}{2}} \Rightarrow 2^{\lfloor \frac{n-1}{2} \rfloor} \le \lceil \sqrt{N} \rceil \le 2^{\lceil \frac{n}{2} \rceil}$$
Therefore,
$$t_1 \triangleq \lfloor \frac{n-1}{2} \rfloor + 1 \le t \le \lceil \frac{n}{2} \rceil + 1 \triangleq t_2.$$
Binary search:
Find $\lceil \sqrt{N} \rceil$ between $2^{t_1}$ and $2^{t_2}$ using binary search. For each number $x$, to compute $x^2$ using additions and shifts as primitives and compare it with $N$.

The complexity is thus $O(n \times n) = O(n^2)$ for $O(n)$ times of binary search and computing $x^2$, each of which in turn takes $O(n)$ additions and shifts.


texts: Is “Find the shortest tour from a to z passing each node once in a directed graph” NP-complete?

texts:
Given a directed graph with the following attributes: - a chain from node $a$ to node $z$ passing nodes $b$ to $y$ exists and is unidirectional. - additionally a set of nodes having bidirectional vertices to at least two of the nodes $a \ldots z$ exists. These nodes are connected in a second unidirectional chain.

(the red route is the requested result, the squares are the first chain (unidirectional) and the circles are the second chain (unidirectional). $1$ is the start node and $5$ is the destination node.)

Is it possible to find the shortest path from $a$ to $z$ that includes nodes $b$ to $y$ and the additional nodes once without probing all possibilities?

I think the problem is roughly the same as the minimal traveling salesman problem since adding a vertex from $z$ to $a$ will result in the min-TSP - but this problem is slightly easier since a path from $a$ to $z$ is already known.


texts: Showing NP-hardness by reducing from a search problem

texts:
I'm comfortable with showing NP-completeness of a decision problem: just take some problem that is known to be hard and reduce it to your new problem. This establishes NP-hardness of the new problem.

But we can also have NP-hard search problems. For example, it is claimed in the introduction of this paper, that finding a $k$-coloring of a $k$-colorable graph is NP-hard for $k \geq 3$. Let me call 3-COL-SEARCH the problem in which we are given a 3-colorable graph $G$, and have to output a valid 3-coloring for $G$.

For concreteness, suppose $X(G)$ is asking for the minimum number of operations to achieve something fancy for a graph $G=(V,E)$. We wish to show computing $X(G)$ is NP-hard. Technically, I should be able to do this by a reduction from 3-COL-SEARCH.

But what would we show in the reduction now? If this was a decision problem (3-COL) we are reducing from, perhaps we'd be showing "the graph $G$ is 3-colorable if and only if $X(H) \leq |V|$, where $H$ is some new graph we construct". But now I'm confused: would we show "we can find a 3-coloring for the 3-colorable graph $G$ if and only if $X(H) \leq |V|$"?

Is there perhaps some paper or resource that gives an example of such a reduction as well? I'd guess this is not so exotic.


texts: Proving a language (ir)regular (standard methods have failed)

texts:
I'm currently trying to prove a language regular (for personal amusement). The language is:

The language containing all numbers in ternary that have even bit-parity when encoded in binary.

Now, I've currently tried a few different approaches that have not led me to any success. I've tried using the pumping lemma (couldn't find anything to pump on), Myhill-Nerode (similar) and even counted the number of strings of each length for which the statement is true (my intuition is that it checks out with a probabilistic argument).

Are their any other approaches that might help here, or are there any intuitions that might be helpful? At this point, my best guess is that the language is not regular, but I don't seem to be able to come up with an explanation.


texts: cheap multi agent path planning algorithms

texts:
I am trying to make a tower defence game where some critters are trying to make their ways through a 2D grid-like obstacle course. The idea is these critters cannot walk into the obstacles or into each other during their path, and they would like to get to the other side as soon as possible.

I just need a cheap, not-optimal solution that can path all the agents from one side of the map to another, moving in the grid (up-down-left-right) directions while not walking into each other nor into the obstacles.

I am not wanting an optimal solution, just one that looks reasonably greedily optimal would be nice (i.e. not like not moving the 2nd agent without completing the path on the first agent, etc).

I'm thinking about something with potential fields with a little bit of A* is as much as I am willing to compute. If there's anything simple to implement I'd be happy to know ! !


texts: How to reach data segment from global pointer in MIPS?

texts:
The global pointer is initialized to 01x10008000. The data segment starts at 0x1000000.

I want to load the first word found in the data segment. So I place 0x8000 in the address field of lw.

lw $a0, 8000hex(\$gp)

Apparently 0x8000 in binary is 1000 0000 0000 0000 which is a negative number because the sign bit is 1.

This is the logic my professor provides so that we reach the start of the data segment by subtracting.

But if you convert all the other numbers to binary they also have 1 as the sign bit. So are they all negative?


texts:
Prove that 9 is the minimum number of calls to make-set, union-set, find-set such that a disjoint set union using weight (number of nodes) by path compression and disjoint set union using rank (upper bound on height) such that the trees produced by this sequence of calls is different.
So far I've found a tree example for which this holds. But now I must prove that this is the minimum. My first idea is contradiction but I'm not sure how to use it well, or maybe some other argument works better. Any help would be appreciated!
The proof idea I have takes a tree from height 0 and then keeps growing until I realize it needs to have 9 operations. But I don't think this is enough.


texts: Can the effective branching factor be negative?

texts:
I've implemented A* algorithm in Python, after that I calculated the effective branching factor $ B^* $

$$ T+1=1+B^*+(B^*)^2+\dots +(B^*)^L$$

where $T$ is the number of expanded nodes.

My question is: is it possible in theory that the effective branching factor calculated is negative? And if not possible, is the solution to take only positive root?


texts: Doubt regarding Maximum Bipartite Matching

texts:
I was given this question by a friend:

"You are given 3 sets of size n, X,Y and Z. Devise an algorithm to find maximum number of different pairings (u,v,w,x) such that u,v,w,x belong to X,Y,Z and X respectively (u is not equal to x) and gcd(u,v,w,x)>1."

My approach is to create new sets S and T, such that S contains pair (u,v) (create a node A) with gcd(u,v)>1 and T contains (w,x) with gcd(w,x)>1 (node B). If gcd(u,v,w,x)>1 add an edge between A and B. Now find maximum matching in this bipartite graph.

But he isn't satisfied and says I didn't use the gcd property and the problem can be reduced significantly. Can this algorithm be improved?


texts: Constant in Substitution method for recurrence

texts:
The solution for solving the following recurrence with the substitution method involves adding the a constant inside the recurrence, which is confusing to me. This is question 4.3-2 in the CLRS textbook.
Show that $T(n)=T(n/2) + 1$ is $O(lgn)$
The solution states that the guess should be $T(n) \leq clg(n-2)$. I understand the need to add the n-2 for the proof. What I don't understand is the first step in the algebra.
Breakdown:
$(Tn) \leq clg(n/2 + 1 - 2) + 1$ ( Don't understand why 1 is added inside the parenthesis.)
$ \leq clg((n-2)/2) + 1$
$ = clg(n-2) - clg2 + 1 $
$ \leq clg(n - 2) $
What I don't understand is step 1 of the breakdown. Why is there a 1 added to n/2? It might be something minor in the math that I'm missing but I can't seem to understand it. My only guess is that it is added in the recurrence to match the + 1 at the end of the equation.


texts: Whats the best way to sort a dataset into groups by using a facial recognition algorithm that compares only 2 images at a time?

texts:
I have a facial recognition algorithm that compares two images A and B and returns the likelihood that they match.

I also have 50,000 images, and I would like to sort these images into groups.

Here's the immediate way I thought of to do this:

Start with image 0, compare it to all 49,999 images. Store the similarities in an array
Move on to image 1, compare it to 49,998 images (skip img_0). Store the similarities in an array

At the end of it all I'm left with a verified_listof images that matched, and I can basically feed them into a network to combine them, ie if I have a verified_list like so:

[[1,2,3],[2,5,6],[8,9]] (verified_list is the same length as the number of images, so verified_list[1] contains references all the images that image_1 matches with)

then the network graph combines them into:

[[1,2,3,5,6], [8,9]

Indicating I have two groups.

Obviously this is a huge amount of processing, I think it equates to: nCr(50000,2), some huge number!

Is there a faster way to sort my dataset into groups?


texts: How to prove stability of sorting algorithms?

texts: I know to prove instability, we can simply provide a counter-example. But is there a general way to prove that a sorting algorithm is stable? Could you please tell a general method and then show an example perhaps on insertion or merge sort.


texts: How are lamport clocks implemented in real world distributed systems?

texts:
Can anyone explain, how lamport clocks implementations are used in modern distributed systems?
Can you name an open source package which implements this algorithm?


texts:
I know from a general point of view what big O notation is. I have taken an algorithms class before that was all implementations and did well. I am now in an algorithms class that is mostly theory and I cannot answer a basic question...

Assume that the cost of multiplying two numbers is $M(n) = O(n^2)$, analyze the asymptotic bit cost of the equation...

$$
\frac{(.1 + \sqrt{4})^k}{.2}
$$

I came up with $O(kn^2 + 1024)$ since they are 32 bit floats and I have to do $k$ multiplications plus 1 more for the division. This answer seems dumb though and I am pretty sure it is wrong. How would you answer it?


texts: Grammar for language L on {a, b} where L = {w|na(w)mod 3 = 0}

texts:
I am able to form the regular expression but I am not confident with the grammar.
I have tried the following:

S-->aaaS|bS|b|lambda

Regular expression is given by:

b* +(ab*ab*ab*)*

Somebody please guide me.

Zulfi.


texts: Which areas in CS will be (or have been) most affected by fully homomorphic cryptography?

texts:
I'm in the middle of planning a 5000ish word essay on fully homomorphic cryptography, the current practical implementations and their limitations.

Which areas of CS as a subject have been (or will be) most affected or will utilise fully homomorphic cryptography the most in the coming years and developments?

PS. I did several searches and couldn't find a repeated iteration of this question, hope the fact this isn't a specific theory questions gets me in hot water!


texts:
I'm trying to prove that P$^{NP}_{||} =$ P$^{NP}_{O(\log n)}$ where $n$ is the length of the input.

So, to see that polynomially many non-adaptive queries to a problem in NP can do as much as logarithmically many adaptive ones.

I know I need to see both inclusions, and have worked out the "easy" one: P$^{NP}_{||} \supseteq$ P$^{NP}_{O(\log n)}$ by arranging all the logarithmically many possibilities in a long deterministic one, and then use the fact that it's still polynomial (from known time complexity properties).

Now, I bang my head on a wall when I try to do the other one. I'm not even sure of where to start. I would very much appreciate your input on this problem, and besides the problem advice on where I could read examples on similar problems to get a better hang on them.


texts: How to state that a complexity bound does not depend on a given parameter size?

texts:
I am often ill at ease with Landau (Big O) notation, because it seems
often to be abusing mathematical notation. The best example is the use
of the equal sign to express a set membership. And this can be
misleading.

I have an algorithm that is dependent on two parameters $n$ and $m$,
which are the respective sizes of the two pieces of data it works on,
like (for example) in the case of a substring search, where you have
the size $n$ of the string being searched and the size $m$ of the
pattern to be found.

I want to express that the algorithm is $O(n)$, but with a constant
that is independent of the value of $m$.

A simple example is the recognition of a regular set, which is linear
in the size of the input string, independently of the size of the
regular expression defining the regular set, provided it has been
compiled into a DFA (which is supposed to be amortized on many
recognitions). This is usually implicit, but can I make it explicit when it is less obvious, or less well known.

The problem seems to be that people will often write $f(n)\in O(g(n))$
to mean that ultimately $|f(n)|\leq k\cdot |g(n)|$ even when $k$
actually depends on $m$. I realize that this depends on how you look
at the problem, and whether you consider that the parameter of size
$m$ is part of the data.

But then, how can one state unambiguously and clearly, but without
being too verbose, that, though the size $m$ parameter is part of the
data, the algorithm is $O(g(n))$ independently of $m$, i.e. the same
constant $k$ can be used even though $m$ may grow arbitrarily? Is there a notation or terminology for it?

Is there a better way recommended by HABON (the High Authority on Big
O Notation)?


texts: How do deal with the following situations using Prim's algorithm?

texts:
Consider the following Graph

We want to generate the MST using Prim's algorithm.

Starting from node A, suppose we pick B as our next node, we see a self-loop that has less weight than the two other alternatives.

Do we ever take the self loop? Why not?

Suppose we just moved from C to D

D only has one edge connecting to E, under Prim's algorithm we will take that edge right?

Now we have travelled from C to D to E, now I am making a choice at E. By picking the edge with the lowest weight we are back at C and the loop from C, D, E continues on forever

What should we do if we enters an in-terminating loop?


texts: Time Complexity of Rabin-Karp matching algorithm

texts:
I asked a question on Rabin-Karp Searching algorithm here, which I am reading from the book "Introduction to Algorithms" 3rd edition Cormen et al..
After reading few para of the section on Rabin-Karp, I got some more confusions:
In the third paragraph the authors say that the if we could find p  (decimal value of pattern P[1....m] )  in  time O(m) and all the ts values (i.e decimal value of length-m sub-string T[s+1....s+m], s=0,1,2,,,,n-m) in time O(n-m+1),  then we could determine all valid shifts s in time O(m) + O(n-m+1) by comparing p with each of the ts values.
How is this possible? O(m) is for finding p, O(n-m+1) is for finding all ts, so total pre-processing time so far is O(m) + O(n-m+1). This is the total pre-processing time; the comparison has yet to start, I have to spend some extra $ for doing comparison of a decimal p with each of the (n-m+1)-ts values.
1-Then why the authors say in the first para that the pre-processing time is O(m)? Why it is not O(m) + O(n-m+1) which include processing time of p and all ts values?
2- Now if we talk about worst case matching time, what should be that? So in the worst my decimal number p (already calculated ) will be compared with each of the another (m-n+1) decimal numbers, which are the values of ts (already calculated, no extra cash needed for doing this job now ). The worst case is when I am most unlucky and I have to compare every value of ts with p. Right?
Based on my understanding,(if I am right) the worst case matching time should be O(m-n+1) and not O((m-n+1)m) as claimed by the authors in the first para. For example let us say my Pattern is P[1...m]=226 and Text is T[1....n]=224225226. so  my p is decimal 226, and ts is decimal value of T[s+1, s+2, s+3], for s=0,1,2...6 as n=9, and m=3. The ts values will be as follows:

s=0 => T[224]=> ts=224
s=1 => T[242]=> ts=242
s=2 => T[422]=> ts=422
s=3 => T[225]=> ts=225
s=4 => T[252]=> ts=252
s=5 => T[522]=> ts=522
s=6 => T[226]=> ts=226

Now you will be comparing p=226 with all these values. So are you not making n-m+1=7 comparisons to achieve search for 226 in T, and not (n-m+1)m =7 x3=21? So the worst case time should be O(n-m+1) and not O((n-m+1)m).
In short I understand that:

Total pre-processing time = O(m) + O(n-m+1) (including for both p and
all the ts values)
Total matching time in worst case = O(n-m+1)

Where I am making mistake?


texts: How to prove formally that grammar isn't LR(1)

texts:
I want to prove that grammar
$$
\begin{cases}
S'\rightarrow S\\
S\rightarrow aSb ~|~ A\\
A\rightarrow bA~|~b
\end{cases}
$$
isn't $LR(1)$. I've constructed parser table and got Shift-Reduce conflict.

I want to prove that without parser table, using another $LR(1)$ definition.

Here's definition:
Grammar is $LR(1)$, if from

$S' \Rightarrow^*_r uAw \Rightarrow_r uvw$
$S' \Rightarrow^*_r zBx \Rightarrow_r uvy$
$FIRST(w) = FIRST(y)$

$\Rightarrow uAy=zBx.$

So how can prove that?


texts: Why closedness of complement of randomized classes imply containment of complement of contained classes?

texts: Suppose if class $\mathcal C$ is in $PP$ or $BPP$ does it mean complement also belongs to $PP$ or $BPP$ respectively? Does it immediately follow from $PP=coPP$?


texts:
I have a directed, unweighted graph that obeys the following rules:

The number of nodes and edges is finite
Each node can eventually be reached from any other node by some path
Each node has an equal number of incoming and outgoing edges

Like this:

I am trying to develop and algorithm that starts in any node and travels each edge of the map once and only once but I'm struggling to come up with anything.

I've thought about finding an algorithm to hit each node and then following it out and back but this can easily be done without traveling every path. (In the graph above you could go a->d->g->e->b->c->f->c->b->e->g->d->a but never hit the paths connecting d to e or the paths connecting e to f)

I've also tried to come up with something like the corn maze solution where you always take the left most available path, but this too has the potential to leave out large chunks of the graph. (you could go a->d->a and think you were done)

I think in order to do this I probably need to be keeping track of which nodes I've already visited and how many remaining untraveled edges it had and always choose to travel to the node with the max remaining untraveled edges. But I feel like this has errors too where I could trap myself into part of the graph  though I haven't found a good example where it does so. Any way to prove the correctness of this or find a counterexample (and in that case maybe thoughts on a new possibility) would be greatly appreciated! I've found a counter example:

Consider the following graph with moves marked in red and remaining count at each node marked in blue, at this point, you are in node b, and can move to either a or c because they are equally weighted, if you move to a, you have effectively cut yourself off from ever traveling the b->c paths.

So now I'm at even more of a loss :/


texts: Is it possible to design a programming task that is unsolvable?

texts:
Can a problem (described by a set of inputs and accepted answers) be designed such that for all programs which produce an answer in finite time for a (countably) infinite number of inputs, at least one of those outputs is incorrect.

That is, the program need not terminate for all outputs, but the outputs it does generate must all be correct, and there must be an infinite number of inputs for which it will terminate.

Not too sure about this, but my intuition says that the question may be related to the Halting problem/Turing machines.

As an example, the halting problem, (as far as I understand) does not meet this requirement, as one could run the input program, and output "terminated" if it terminates. If the input program never terminates, nor does the solution, so it never generates an incorrect output.


texts: What is the time complexity for division by repeated subtraction?

texts:
Given the following algorithm :

    input : a (integer), b (integer != 0)

    result = 0;
    while(a >= b)
    {
       a = a - b;
       result = result + 1;
    }

    return result;

How to find the number of instructions and the time complexity of this kind of algorithm since we don't know neither a nor b nor the number of iteration in advance ?


texts: Efficient algorithm to compute the Heesch number of a shape

texts:
The Heesch number of a shape is the maximum number of layers of copies of the same shape that can surround it. For example the following shape (in the center) has a Heesch number of 4, because we can get at most 4 layers to surround it:

Given a shape, is there an efficient algorithm to compute its Heesch number? The only thing I can think of is to do a brute-force BFS search, surrounding it layer by layer. But this seems awfully inefficient.


texts:
Show that any language accepted by a RAM can be accepted by a RAM without indirect addressing.

Could you give me some hints what I could do??


texts: Deterministic CSL = semi Deterministic CSL

texts:
How can it be proven that a
deterministic CSL = semi-deterministic CSL?
Does that imply that a CSL = semi CSL?
Would I need to build a Turing machine, since a language accepted by a Turing machine is considered semi CSL?


texts: Fair cake-cutting when players join late

texts:
The usual statement of the fair cake-cutting problem assumes that all $n$ players get their share at the same time. However, in many cases the players arrive incrementally. For example, we may divide a cake over $n$ players, but then a new player arrives and wants a share.

Usually, fair cake division requires a lot of effort (for example, requires the players to answer many queries), especially when the number of players is large.

Is it possible to use the existing division of the cake over $n$ players, in order to create a new division of the cake to $n+1$ players, with minimal additional effort (i.e. substantially less effort than re-distributing the cake from scratch)?


texts: Finding maximum and minimum of consecutive XOR values

texts:
Given an integer array (maximum size 50000), I have to find the minimum and maximum $X$ such that $X = a_p \oplus a_{p+1} \oplus \dots \oplus a_q$ for some $p$, $q$ with $p \leq q$.

I have tried this process: $\text{sum}_i = a_0 \oplus a_1 \oplus  \dots \oplus a_i$ for all $i$. I pre-calculated it in $O(n)$ and then the value of $X$ for some $p$, $q$ such that $(p\leq q)$ is: $X = \text{sum}_q \oplus \text{sum}_{p-1}$. Thus:

$$
\mathrm{MinAns} = \min_{(p,q) \text{ s.t. } p\le q}{\text{sum}_q \oplus \text{sum}_{p-1}} \\
\mathrm{MaxAns} = \max_{(p,q) \text{ s.t. } p\le q}{\text{sum}_q \oplus \text{sum}_{p-1}} \\
$$

But this process is of $O(n^2)$. How can I do that more efficiently?


texts:
I want to show, that for an CFG G the question wether $L(G)=L(G)^R$ is undecidable.

My first try was to reduce from the CFG-Equivalent Problem) $CFG_{EQUIV}\leq CFG_{SYM}$.

My first attempt was to say, that if there are $G_1\#G_2 \in CFG_{EQUIV}$, you can turn $G_2$ into Chomsky Normalform and change all rules $P\longrightarrow AB$ into $P\longrightarrow BA$, so that we get a Grammar $G^+$, so that $L(G^+)=(L(G'))=(L(G_2))^R=(L(G_1))^R$

The problem i have is that i wanted to create a grammar $G_3$ for which $L(G_3)=L(G_1)\circ L(G_2)$, but i realized, that $L(G_3)\neq (L(G_3))^R$ ... so my reduction wont work

Is there any better way to for the reduction?

Thanks in advance!


texts: What use are the minimum values on minimax trees?

texts:
Consider a minimax tree for an adversarial search problem. For example, in this picture (alpha-beta pruning):

When marking the the tree with $[\min,\max]$ values bottom-up, we first traverse node $3$ and assign $B.\max = 3$. Then we traverse $12$ and $8$ in this order, it will make sure $B.max = 3$.

But why is $B.\min = 3$? What is the use of that value?


texts: Why are these (lossless) compression methods of many similar png images ineffective?

texts:
I just came across the following thing: I put multiple identical copies of a png image into a folder and then tried to compress that folder with the following methods:

tar czf folder.tar.gz folder/
tar cf folder.tar folder/ && xz --stdout folder.tar > folder.tar.xz (this one works well for identical images, however for similar images the gain is zero)
zip -r folder.zip folder/

When I checked the size of the .tar.gz, .tar.xz, .zip I realized that it is almost the same as the one of folder/.
I understand that a png image itself may have a high level of compression and therefore cannot be compressed further. However when merging many similar (in this case even identical) png images to an archive and then compressing the archive I would expect the required size to decrease markedly. In the case of identical images I would expect a size of roughly the size of a single image.


texts: Intro to Algorithms: asymptotic function analysis

texts: I'm reading "Introduction to Algorithms" 3rd edition by Cormen, Leiserson, Rivest, Stein Page 46.  The authors place formal upper and lower bounds on a function which is quadratic.   Can anyone explain where the values for $c_1$, $c_2$ and $n_0$ are taken?  I'm also confused why the $max$ function is used and it's parameters.


texts:
This was a question at SO, and I think it's very interesting, I thought about it, but I could not provide any efficient algorithm neither showing the NP-Hardness:

  Find the length of the longest non-decreasing sequence through
  adjacent, non-repeating cells (including diagonals). For example, in the
  following grid, one legal path (though not the longest) that could be
  traced is 0->3->7->9 and its length would be 4.

  8 2 4

  0 7 1

  3 7 9

  The path can only connect adjacent locations (you could not connect 8 ->
  9). The longest possible sequence for this example would be of length
  6 by tracing the path 0->2->4->7->7->9 or 1->2->4->7->7->8.

For first attempts and possible misinterpretations is not bad to see this answer at SO.

My question: above problem is in $P$?


texts: Is there a difference in the convergence analysis/proof of the chaotic learning automaton compared to the standard LA?

texts:
We have recently presented an article entitled Improving learning ability of learning automata using chaos theory.
In this article, a new type of learning automaton called chaotic Learning Automaton (cLA) is presented. In cLA, the chaotic numbers are used instead of the random numbers when choosing the action. Experimental results indicate that the cLA has a higher convergence rate with low convergence time than standard LA. Furthermore, the cLA has more scalability than the standard LA, and its performance will not decrease significantly by increasing the problem size (number of actions).
Is there a difference in the convergence analysis/proof of the cLA compared to the standard LA?


texts: Regex: Any pair of zeros is before any pair of ones

texts:
Write a regular expression for all the strings in which every pair of adjacent zeros appears before any pair of adjacent ones. The answer given in the book is:
$$(0+10)^*(00)(1+01)^*(11)(0+10)^*(1+01)^*$$
Is that correct? I fail to see how could you get a string like 10011, but it fits description. I mean even a string like 1 fits a description. So, if this answer is incorrect, then what is a correct answer?
My simple guess is:
$$(\epsilon+1)(0+10)^*(1+01)^*(\epsilon+0)$$

P.S.
Does $(0^*1^*)^*$ generate every possible binary number? If not, what does it generate?


texts: context-free language : if yx belongs to cfl then xy is also cfl

texts:
I faced a problem.
What is the proof to say that if yx is in a Context-Free Language we can say that xy is also in a context-free language.

C is a Context-Free Language.

I think we can use the PDA defining C and edit final states.

Any ideas?
thank you.


texts: The origin and the meaning of "Abstract Syntax Tree"

texts:
This question is closely related to Does an abstract syntax tree have to be a tree? and is partially answered there, but I would like to be more precise and to have more concise answers.

What is the origin of the term?
Are there any formal definitions of AST?
If I understand correctly the spirit of the use of "AST" term, it is a misnomer: an AST is any combinatorial object or datum that one tries to represent by strings of characters using more or less simple syntax that should ideally reflect the internal structure of the object/datum.  For example, in first-order logic and in lambda calculus, expressions like
$(\forall x)(x = x)$ or $(\lambda x.x)$
do not really represent trees because bound variables introduce loops.
Do I understand correctly?

Basically, I broke up here in simpler pieces a single question: What is AST?
Without answering parts (1) and (2) the answer will probably be incomplete or hard to verify, and if (1) and (2) are answered, an answer to (3) probably should follow.

Update

I have realized that it is not the "syntax tree" that is abstract, but the syntax.  This clarifies the terminology to me and makes this question less relevant.  Basically, I parsed "abstract syntax tree" incorrectly.

I also provided an answer to the related question.


texts: Is the discrepancy in Turing's representation of complete configurations intentional?

texts:
On page 235 of Turing's 1936 paper, in the figure marked (C), the illustration appears not to match the description. The description states that

space has been made on the left of the scanned symbol, and the m-configuration written in its place

but the illustration (repeated on p. 242 using SD encoding) shows no scanned symbol for the first complete configuration:
b:əəo0 0:əəq0 0: ...

It's hard to tell if this is meant to me something special about the starting state, or a general part of the representation so that one would have
b:əəo0 0:əəq0 0:əə0 q0:əə0 0 q:əə0 0p 1:əə0p 0 1:əpə0 0 1:...

rather than the representation corresponding to the description:
b :əəo0 0:əəq0 0:əə0 q0:əə0 0 q :əə0 0p 1:əə0p 0 1:əpə0 0 1:...

Is there significance to this discrepancy? Is it intentional?


texts: Shortest Path in Layerwise Complete Graph

texts:
Consider a directed $k$ partite graph $G$ with a source node $s$ and a sink node $t$. Each vertex in the graph is labeled with a positive integer value. Both the source and sink are labeled with $0$. There are directed edges from the $s$ to all vertices in partition $0$. There are directed edges from all vertices in partition $k$,, ie, the last partition to $t$. $G$ is layerwise complete that is, in addition to the above, there is a directed edge from all vertices in partition $i$ to all vertices in partition $i+1$, ie, adjacent partitions form complete bipartite graphs. An edge between any two nodes is labeled with a negative integer value or with $0$.

There could also be directed edges between nodes in partitions $m$ and $n$ where $1 \leq m, n \leq k, m \lt n,  n \neq (m+1)$, and  labeled with a negative value. This is depicted in the following figure where there are two edges between partition $1$ and partition $3$ indicated with dashed lines. Non adjacent partitions do not form complete bipartite graphs. They only comprise edges as indicated. In the figure, the edge labels are shown with negative values, wherever edges are not labeled with values, they are labeled with $0$ by default.

Consider all paths from $s$ to $t$. The length of this path would be calculated as the addition of all the integer labels of the nodes on this path and the addition of the edge labels if there is an edge between any pair of vertices in this path. For example, the length of the path taking the first vertex from each partition would thus be $0 + 50 + 30 + 50 + 0 -8$, where the negative value of $-8$ corresponds to the edge between nodes labeled with $50$ and $50$. Similarly, if we took the first vertex from partition $1$, the last vertex from partition $2$ and the first vertex from partition $3$, the length of this path would be $0 + 50 + 40 + 50 + 0 - 6$, where the $-6$ value corresponds to the edge between the first vertex in partition $1$ and partition $2$. The $0$ values correspond to the source and sink vertices.

Find the shortest path from $s$ to $t$ taking exactly one vertex from each $k$-partition where the length would be calculated as described.

Attempt : I converted the node weights for a pair $(a, b)$ into edge weights where each edge weight would be the sum of the node value of $b$ deducting the edge cost between $a$ and $b$. This works for edges between successive partitions and produces the correct shortest path in cases where the edges are only between such. However, if I use the same approach for edges between different non successive layers it doesn't work. What would be an algorithm to find the shortest path and the transformation?


texts: Applications of the LU factorization in computer science

texts:
I have been searching for the applications of the LU factorization/decomposition in computer science. From Wikipedia, I have found some of the applications, but these don't seem to be relevant to computer science.

Applications I found are

Solving linear equations
Inverting a matrix
Computing the determinant

Is there any application of LU factorization/decomposition in computer science?


texts: I have been reading about model counting, a.k.a. the #SAT problem. What are the practical applications, if any, of this problem, and how exactly do they reduce to it? I have been unable to find any, though that's simply due to my own ignorance of the subject.


texts: Argument in proving that function is not polynomial time in bit length of input seems faulty

texts:
I am currently solving a question that asks which of the following functions can be calculated in polynomial time:

$$n!, \binom{n}{5}, \binom{2n}{n}, n^{\lfloor \lg n \rfloor},  \lfloor \sqrt{n} \rfloor, \text{the smallest prime factor of } n, \text{the number of prime factors less than }n.$$

In proving the first one, I thought $n! \geq n$ and the input size is $\log_2 n$ so the output cannot even be written in polynomial time. So then clearly the calculation cannot be done in polynomial time.

But then I thought I must have some misunderstanding, since by that logic even just calculating $n$ from the input (that is, the identity function) should not be polynomial time. But that's clearly not possible.

What is the problem in my thinking, and instead how should I be thinking about these?


texts: On the limitation of the "adversary" in randomization for online learning

texts:
While reading on randomization for online learning from the text "Online Learning and Online Convex Optimization" by Shai Shalev-Shwartz, I found the following statement (Pg 115)-
"The adversary can still know the learner’s forecasting strategy and even the random bits of previous rounds, but it doesn’t know the actual value of the random bits used by the learner on round t."

Assume the learner is using a coin with bias "p" for the random experiment.  Does the statement mean that it precludes the adversary from knowing the bias "p" of the coin as well?

My guess is it does not, I assumed that the adversary just does not know the outcome of the coin flip but can know the bias. Can someone clarify.


texts:
Please excuse my language, I am new to the topic.

I am trying to classify/find a class of game that describes games such as chess, tic-tac-toe as a finite state machine.

For those games, final states are easy to determine and can be efficiently checked.

My question is:

is there a name for such class of games/programs?
is there a game/program such that there is no way to determine the final state?

Thanks


texts: Constructing a PDA to accept the language {a^i b^j c^k where i,j,k>0 and i<=j<=2k}

texts: Can anybody help me out with this? If I try to compare $a$'s with $b$'s to check if $j\ge i$ then I won't be able to compare the same number of $b$'s with the number of $c$'s that is to check if $j\le 2k$.


texts:
I have

$4$ variables $n_1, n_2, n_3, n_4 \in \mathbb N$ that sum to $N$.
$4$ positive real constants $c_1 < c_2 < c_3 < c_4$.

Given a particular tuple $(k_1,k_2,k_3,k_4)$, how do I find the partial sum of the ordered (w.r.t. the sum $c_1 n_1 + c_2 n_2 + c_3 n_3 + c_4 n_4$ in an increasing manner) sequence

$$\sum_{n}^{(k_1,k_2,k_3,k_4)} (c_1 n_1 + c_2 n_2 + c_3 n_3 + c_4 n_4)$$

from the minimum to the given $(k_1,k_2,k_3,k_4)$?

I think this problem involves some sorting algorithm. This should already be studied in some linear programming problem but I am just not aware of how to do this efficiently (e.g. using Python).


texts: Relative primality is primitive recursive

texts: How do I prove that the predicate $P(x , y)$ is primitive recursive, where $P(x,y)$ holds if $x,y$ are relatively prime?


texts: Does this loop invariant guarantee that the variable never changes?

texts:
Suppose you have some loop and and integer k:

int k = 5;
for (int i = 0 ; i < N; i++)
{
  //(*)
  //do something
}

The loop invariant at (*) is:
$\{ K=k\}$

Does that guarantee that $k$ doesn't change in between iterations? if not, is there any otherway to guarantee that?


texts: Does the running-time of this push-relabel algorithm become zero if there are many edges?

texts:
According to the Wikipedia page on the Push-relabel maximum flow algorithm:

  Subcubic $O(|V||E| \log\frac{|V|^2}{|E|})$ time complexity can be achieved using dynamic trees, although in practice it is less efficient.

What if $|E| = |V|^2$? Don't we then have this?

$$O(|V||E| \log\frac{|V|^2}{|V|^2})$$
$$O(|V||E| \log 1)$$
$$O(|V||E| 0)$$
$$O(0)$$

There's no way this can be right, so what am I misunderstanding?


texts: How do you protect an AI from a human doing "illogical" moves?

texts:
Using a monte carlo approach and evalutation function. Some moves will deemed to be more advantageous than others.

As a computer plays itself, it will generally go for the best moves possible. And hence train itself to deal with these moves.

But what if a human does a few seemingly detrimental moves to throw the AI off track. And then using the human's expertise, go on to win the game?

How can one train an AI to account for this?

Or must we assume that it can generalise board positions from "perfect" games to board positions of imperfect games?

(Presumably AlphaZero has no problem with this? Has anyone ever tried to trick AlphaZero by doing a few silly moves?)


texts:
In a different post it came up that
(using the Turing machine model of computation),
it is not even safe to say that $N$ numbers can be read in $O(N)$ time.
To me this is boggling since
it's something I take for granted in the RAM model of computation,
and I admittedly only have a cursory understanding of Turing machines.

However, the more boggling part is that
the same person claimed that in the Turing machine model
we cannot read $N$ numbers even in exponential time,
BUT that we can read the input for Knapsack and fill a table of size $N$ by $w$ in exponential time.

How can filling a two-dimensional $N$ by $w$ array take less time than
an $N$ by $1$ array?


texts:
I know how to find a regular expression when given a FA. But how do I find a regular expression given just a language and its rules?

For example, for the language $L \subset \{ a,b\}^* $ which accepts all words that contain exactly one $aa$. How do I find a regular expression in this case?

I know that I would be able to FA and convert it into a regular expression, but this can be time-consuming. Is there a faster/easier way that I could use in an exam to save time?


texts: What is the relationship between NP/NP-Complete/NP-Hard to time complexity?

texts: I'm familiar with a few problems of each class and even though the definitions are based on sets and polynomial reducibility, I see a pattern with time complexity. NP problems appear to be $O(2^n)$ (minus the P problems of course), and NP-hard problems seem to be worse: $n^n$ or $n!$ (Chess, TSP). Is this a misleading interpretation?


texts: How can alpha-beta pruning be made safe for a chess program? Pruning away a certain set of nodes is safe when the tree is complete and it is known that no other new nodes can be found deeper in the tree, but obviously this is not the case in chess. If my program prunes away a move that looks bad because it sacrifices valuable material that may just be the sacrificial move that would have checkmated the opponent in another few additional ply (or just gain a material and/or tactical advantage)?


texts:
I'm learning graphs these days and need to clear few doubts-

Can I determine weather 5 points in two dimensions whose X and Y coordinates are given lie on the same straight line in O(1).
What is the efficient way to find out the degree of the specified vertex in an undirected graph (V,E)? I'm thinking of O(|E|)?
What is the efficient way to find degrees of all vertices in an undirected graph (V,E)? I'm think of O(|V||E|)
if |E| ≥ |V| can I say grapgh will be have guaranteed Euler circuit?
Is it possible to find slope of a straight line in O(1)time given the X and Y coordinates of n points on the line?


texts: Vertex cover of a graph by removing leaf-vertices from a DFS tree

texts:
Question taken from "The Algorithm Design Manual" by Steven S. Skiena, 1997.

A vertex cover of a graph $G=(V,E)$ is a subset of vertices $V'\subseteq V$ such that every edge $e\in E$ contains at least one vertex from $V′$.

Delete all the leaves from any depth-first search tree of $G$. Must the remaining vertices form a vertex cover of $G$? Give a proof or a counterexample.

Answer given :

If the tree has more than one vertex, then yes. The remaining vertices are still the vertex
cover because for every edge e∈E incident on the leaves, their other end-point is still in the
remaining tree.

My question:

The answer is right for undirected graphs. But I think there exist counterexamples to this question using directed graphs.

For example:

If we are using DFS starting from vertex $a$ and we are traversing in alphabetical order, i.e. explore b first, then we end up with two tree edges, which are $(a,b)$ and $(a,c)$. Therefore, $b$ and $c$ are leaf-vertices.

But here if are going to delete vertices $b$ and $c$ the edge $(c,b)$ has no incident vertices which are contained in our vertex cover.

Am I right? I am confused actually.


texts: Why is pure literal elimination absent in DPLL-based algorithms like Chaff?

texts:
I'm looking into various SAT-solvers and trying to understand how they work and why they are designed in certain ways. (But I'm not in a university at the moment and I do not know anyone who is a professor. So I'm posting here hoping that someone can help me out. I'd really appreciate.)

In Chaff, BCP (Boolean Constraint Propagation) is implemented differently from the original DPLL: it does it by watching two literals at a time (a technique slightly different from one initially suggested in SATO: An Efficient Propositional Prover) according to the 2001 paper, Chaff: Engineering an Efficient SAT Solver. There is, however, no mention of pure literal elimination in this paper.

In The Complexity of Pure Literal Elimination, Jan Johannsen wrote

  The current best implementations of DLL-type SAT solvers, like Chaff
  or BerkMin sacrifice this heuristic in order to gain efficiency in unit
  propagation.

where "this heuristic" is referring to pure literal elimination. My understanding of what pure literal elimination does is that it

searches for all single-polar (or pure) literals
assigns a boolean value to them such that each yields True
in which case we can now delete all the clauses containing them

Here is my question:

How is the sacrifice necessary? Is there a good reason why pure literal elimination is absent in DPLL-based algorithms like Chaff? Can't we just do pure literal elimination in each decision level (or at least do it at the start before branching)?


texts: calculate the effective (average) access time (E AT) of this system

texts:
A computer with a single cache (access time 40ns) and main memory (access time 200ns) also
uses the hard disk (average access time 0.02 ms) for virtual memory pages. If it is found that the cache hit rate is 90% and the page fault rate is 1%

I have to work out the EAT time for this and the speedup due to use of cache.
I'm really confused about how to do this because I have seen two different ways of doing this and I'm not sure which is correct

solution 1: 0.90*40 + 0.10[0.01*20,000 + 0.99*200]=75.8 ns

solution 2: 0.90*40 + 0.10[0.01*(20,000+200) + 0.99*(2*200)]= 95.8 ns

In the second one, it accesses main memory twice when there is a page hit and accesses disk and main memory when there is a page fault. Which one is correct?

And for the speedup, which equation do I use?:
Memory access time/(Memory + Cache access EAT)
OR
EAT without cache/EAT


texts: Find all values repeating more than $\lfloor n/k \rfloor$ times in $O(n \log k)$ time

texts:
Given a parameter $k$ and an array (not sorted) of length $n$ return all values which repeat more than $\lfloor n/k \rfloor$ times in $O(n \log k)$ time.

I've managed this in $O(nk)$ time, but can't figure out how to do it in the required performance.


texts: A fuzzy string matching algorithm for finding all occurrences from a set of strings in a large string

texts:
I have thousands of documents, and a term list with thousands of entries. The entries in the term list range in length from an acronym of two characters to a 14-word phrase with 96 characters. I would like to find every occurrence of any term in the term list in each document in the order that they appear.

I have created two test implementations so far: one using the Aho-Corasick algorithm and the other using n-gram matching. I tested them both on a medium-sized document (8 MB). The Aho-Corasick algorithm came up with over 8700 matches in 24 seconds. This would be great, except that I would like to use a fuzzy matching algorithm, and Aho-Corasick only finds exact matches. N-gram matching found 9600 matches, since some of them are approximate, but it took 885 seconds!

As such, I would like suggestions on an efficient fuzzy matching algorithm for finding matches from a set of strings. Is there any way to modify the current code I have for the Aho-Corasick algorithm so that it can take into account Levenshtein distance? I have found some other questions on this site that are related, but I didn't feel like they solved my problem. Thanks.


texts: Is there a name for a compiler that runs once at runtime right before a program is executed?

texts:
I wrote a tiny compiler that is used to execute user-defined plugin code. The compiler is shipped as part of the application. When the user loads a plugin, the compiler runs first (once) and then the emitted code is executed.
I'm trying to describe this project in a blog post, and I'm unsure if calling this a "Just in Time" compiler (JIT) is accurate or not. The Wikipedia article indicates that a JIT typically uses runtime information to inform how/when the program gets compiled, and my project does not do anything that fancy.
Is there a common name for a compiler that executes at runtime but does not analyze the execution of the program?


texts: Computing (near) optimal displacement tables

texts:
Suppose we have a two-dimensional table $T$ with $r$ rows and $c$ columns that is sparse. Let $T[i][j]$ be the element at the $i$th row and $j$th column of $T$, with zero-based indexing.

We can compress $T[i][j]$ by putting all elements in a single 1D array $A$, and letting $A[D[i] + j] = T[i][j]$. Now with $D[i] = ci$ we have simply flattened the table.

But if the table is (very) sparse, we can do better than $D[i] = ri$. We can overlap rows where they're sparse! As an example we could have the table:

\begin{bmatrix}
0 &1 & 0 & 0 & 0\\
2 & 6 &0 & 0 &0\\
0 & 0 & 0 & 3 & 0\\
0 & 0 & 4 & 0 & 9\\
0 & 0 & 0 & 0 & 5\\
\end{bmatrix}

Which we could compress like such:

$$A = [2, 6, 4, 3, 9, 1, 5]$$
$$D = [4,0,0,0,1]$$

Finally, to detect non-existing entries we also need a table of the same size as $A$ that tracks the source row of each entry:

$$C = [1, 1, 3, 2, 3, 0, 4]$$

Only when $C[D[i] + j] = i$ we consider $A[D[i] + j] = T[i][j]$, otherwise we deduce $T[i][j] = 0$. We also assume that when $D[i] + j \geq |A|$ that the element is zero.

Now the question is, what  is a (near) optimal choice of $D$? We need to shift each row of $T$ so that each column only contains at most one non-zero element. A fast greedy method would be to handle each row in descending order of number of elements, and assign $D$ for that row in the first spot that doesn't cause a conflict.

But that isn't optimal. Is there another reasonably fast algorithm that provides better or optimal results?


texts: Mapping a Decision Tree using points in euclidean space

texts:
INTRO: I have 15 points forming a graph G in R^3. Call permutations of the form  {-4,-3,...3,4}^3 \ V{G} (vertex set of G):= "Candidate set". Each point in the candidate set is added to the Graph and a metric is checked, if the metric spits out a 'True', then I add it to a list of "Successes". Of the candidate points, something like 5% give 'True', and are added. I now have 0.05 * |candidate_points|  # of points to check. A decision tree is made in this way, Since I start with 15, I have ~100 'True' options for growing it to 16. But, there are 'dead ends', wherein if I choose a certain point that gave 'True', it will not grow to anything greater than 17. But, there are certain longer paths that are found when I randomize things, and can get to 22 even 23. But i'm confident there are even longer paths down the tree.

PROBLEM: I eventually step up to permutations in R^6, R^7. And things blow up quickly. Is there a neater way for me to sample the candidate points other than bruting it or just doing random.shuffle on the set? Is there a faster algorithm for this?


texts: Is the runtime complexity of sorting $O(n\log n)$ or $O(n\log^2 n)$?

texts:
Suppose we want to sort an array that contains $n$ different integers in the range $[1,2n]$. It is known that this requires $\Theta(n\log n)$ comparisons. But comparing integers which might be as large as $n$ might requires time $\Theta(\log n)$ since we have to compare them bitwise. So, apparently the runtime complexity of sorting is $\Theta(n\log^2 n)$. Is this correct? If so, why is it taught that the complexity of sorting is $\Theta(n\log n)$? Is there a better algorithm for sorting which runs in time $\Theta(n\log n)$?

EDIT: I understand that the question depends on the computational model. In fact, I just found an interesting unanswered question that specifically asks about the runtime complexity of sorting on a Turing machine. Originally, I had in mind a realistic computer, only with unlimited memory. In such a computer, we can represent arbitrarily large integers (as sequences of bytes). We are given an array that contains $n$ different integers, each of which is between $1$ and $2n$. We measure the clock-time it takes to sort this array, as a function of $n$. What function will we see?


texts: Understanding the "ordering of the four types of edges" in DFS

texts:
The following is Exercise 22.3-6 from CLRS (Introduction to Algorithms, the 3rd edition; Page 611).

  Show that in an undirected graph, classifying an edge $(u,v)$ as a tree edge or a back edge according to whether $(u,v)$ or $(v,u)$ is encountered first during the depth-first search is equivalent to classifying it according to the ordering of the four types in the classification scheme.

Problem: What does it mean by "the ordering of the four types in the classification scheme"? In particular, what does the "ordering" refer to? What is supposed to prove?

The classification scheme is defined on page 609:

  We can define four edge types in terms of the depth-first forest $G_{\pi}$ produced by a depth-first search on $G$:

  Tree edges are edges in the depth-first forest $G_{\pi}$. Edge $(u,v)$ is a tree edge if $v$ was first discovered by exploring edge $(u,v)$.
  Back edges are those edges $(u,v)$ connecting a vertex $u$ to an ancestor $v$ in a depth-first tree.
  Forward edges are those nontree edges $(u,v)$ connecting a vertex $u$ to a descendant $v$ in a depth-first tree.
  Cross edges are all other edges. They can go between vertices in the same depth-first tree, as long as one vertex is not an ancestor of the other, or they can go between vertices in different depth-first trees.

Added Example:

Consider the figure below.

Suppose that a DFS starts from node $u$ and travels along $(u,x)$ first and then $(x,v)$. Both $(u,x)$ and $(x,v)$ are tree edges.

What about the edge $(v, u)$? It should be a back edge according to the classification scheme in the textbook.
How is $(v,u)$ classified as back edge according to the classification in the exercise?

Is $(v,u)$ a tree edge while $(u,v)$ a back edge according to the definition in the exercise? This is strange, because in an undirected graph, $(u,v)$ and $(v,u)$ refer to the same edge.


texts: Have people looked at "Hypergraphical" models?

texts:
Graphical models are a very useful tool with many applications, whereby a joint distribution of a set of random variables is modeled using only pairwise dependencies between the variables, and two variables with a direct causal relationship are connected by an edge, which is associated with their joint distribution.

It makes sense to extend this by looking at "hypergraph models", where we allow direct causal relationships involving (say) up to $d$ variables, and the hyperedges connecting them are associated with a $d$-way joint distribution.

I am interested in whether people have looked at such things, and analyzed the behavior of belief propagation type algorithms for them.


texts: While using K-means, how do I represent IP addresses and languages on the coordinate axis?

texts: I'm using K-means for unsupervised learning, using data vectors with an IP address and a language. I need to represent them in an abstract way, so that I can use this algorithm.


texts:
Would a sparse NP-Complete language imply L = NP?

Update: Thanks to Noah Schweber for clear and comprehensive answer. Having thought about it more, one would need a logspace reduction from NP-complete to L-complete for NP=L. [4] below does not directly address this.

Here is my proof attempt:

[1] Assume there exists a (sparse NP-Complete language).

  Mahaney's theorem is a theorem in computational complexity theory proven by Stephen Mahaney that states that if any sparse language is NP-Complete, then P=NP.

https://en.wikipedia.org/wiki/Mahaney%27s_theorem

[2] In other words, (sparse NP-Complete language) implies (P = NP).

[3] From [1] and [2] (P = NP).

[4] (P = NP) implies (P-complete = NP-complete).

[5] From [3] and [4] (P-complete = NP-complete).

[6] From [1] and [5] there exists a (sparse P-Complete language)

  In 1999, Jin-Yi Cai and D. Sivakumar, building on work by Ogihara, showed that if there exists a sparse P-complete problem, then L = P."

https://en.wikipedia.org/wiki/Sparse_language

[7] In other words, (sparse P-complete problem) implies (L = P).

[8] From [6] and [7] (L = P).

[9] From [3] and [8] (L = NP).


texts: Spanning tree with chosen leaves NP-Complete proof

texts:
I want to prove that the problem described here

Spanning tree with chosen leaves

is NP-Complete.

Of course it is in NP, but what problem would be appropriate to reduce to prove NP-Hardness? And how would that work?


texts:
BPP is defined as the class of polynomial-time random algorithms which have an error probability of at most 1/3.

But why was 1/3 chosen? If we have an algorithm with some error probability less than 1/2, then we can run it several times, taking the most common result, to obtain an error probability of less than 1/3 while still staying in the same complexity class.

So why isn't BPP instead defined as the algorithms which have an error probability of less than 1/2? Is there something special about 1/3?


texts: DP - Removing contiguous subsequences from a sequence optimally

texts:
I was asked this question a while ago and I'm very stuck:

  You have a sequence of 0's and 1's, and you can perform one operation it: removing at least $K$ consecutive 0's or $K$ consecutive 1's from the sequence. After performing one of these operations, the ends of the sequence that are on the sides of the removed portion come together and close the gap created by the removal.

  Can you make operations such that the sequence becomes empty? If so, what is the least number of operations that you can make? I'm hazy on the restraints on the problem, but assume both $N$ and $K$ have at most two digits, and that $K$ is a lot smaller than $N$.

  For example, say you have the sequence 1111000001, and $K = 5$. The solution is to remove the middle line of 0's. You cannot remove any 1's on the first step, because the longest consecutive substring of 1's is only four long. Afterwards, however, the gap closes, and the sequence 11111 is created, which can also be removed, creating the desired empty sequence. Only two operations are needed to make the sequence empty.

I believe that this is a DP problem, but I'm having trouble on what to represent as a state and how to construct a state from previous ones. Could anyone give me a hint?


texts:
As per the Sanjeev Arora book, for a certificate based definition of $NL$, the machine is allowed a "read-once" certificate tape to store the certificate along with $O(log n)$ read/write work tape for a deterministic verifier machine.

My doubt is that for a $3-SAT$ problem, if instead of storing an assignment to the $n$ variables, I store the $3k$ assignments to the $3k$ literals in a $k$ clause 3-SAT formula in the certificate tape. This way I don't have to re-read a previous symbol and I can go from left to right in the certificate tape at each step of the machine.

And in work tape I can calculate OR of 3 literals. If it is $0$, then I reject, if it is $1$, I erase the contents of the work tape and store the values of 3 literals of the next clause, and repeat. If all clauses were satisfying, I accept.

The certificate is also polynomial in the length of input. Kindly point out the flaw in this argument, otherwise $3-SAT$ would $\in NL$, which is not believed to be true.


texts: Can Euclidean TSP be exactly solved in time better than (sym)metric TSP?

texts:
Symmetric/Metric TSP can be solved via the Held-Karp algorithm in $\mathcal O(n^2 2^n)$.

See A dynamic programming approach to sequencing problems by Michael Held and Richard M. Karp, 1962.

In Exact Algorithms for NP-Hard Problems: A Survey (PDF) Woeginger writes:

  This result was published in 1962, and from nowadays point of view almost looks trivial. Still, it yields the best time complexity that is known today.

Thus, this is the best known upper-bound.

Question:

  Are there any better results for Euclidean TSP? Or does that best-known bound apply to Euclidean TSP as well.

How is Euclidean TSP different? Well,

Euclidean TSP can be encoded into $\mathcal O(n \log m)$ space, where $n$ is the number of cities, and $m$ is the bound on the integer coordinates of the city locations. As opposed to (sym)metric TSP variants, which essentially require a distance matrix of size $\mathcal O(n^2 \log m)$. Thus, it might be easier to solve; for example, perhaps Euclidean TSP can be more easily encoded into k-SAT, because the distance function is implicit.
Contrary to popular notion, Euclidean TSP's reduction from k-SAT is quite different from (sym)metric TSP. UHC (undirected Hamiltonian cycle), symmetric TSP, and metric TSP are pretty directly related to each-other. But formulations of reductions from (sym)metric TSP to Euclidean TSP are not easy to come by. Paragraph, from interesting article, The Travelling Salesman’s Power by K. W. Regan (bold mine):

  Now the reductions from 3SAT to TSP, especially Euclidean TSP, are less familiar, and we ascribe this to their being far more “expansive.” Texts usually reduce 3SAT to Hamiltonian Cycle, then present the latter as a special case of TSP, but this does not apply to Euclidean TSP. The ${\mathsf{NP}}$-completeness of Euclidean TSP took a few years until being shown by Christos Papadimitriou, and a 1981 paper by him with Alon Itai and Jayme Luiz Szwarcfiter advertised a “new, relatively simple, proof.” This proof uses vertex-induced subgraphs of the grid graph in the plane, for which the shortest possible TSP tour and any Hamiltonian cycle have the same length. Despite this simplification, the gadgets involved are large—a diagram of one occupies most of one journal page.

Hunting down k-SAT $\rightarrow$ Euclidean TSP reductions is quite an adventure; so far I've found two of them. One $\rm k\text{-}SAT \rightarrow CircuitSAT \rightarrow PlanarCircuitSAT \rightarrow EuclideanTSP$, and another, even tougher one to find, $\rm k\text{-}SAT \rightarrow DHC \rightarrow UHC \rightarrow PlanarUHC \rightarrow EuclideanTSP$. The latter reduction can perhaps be seen to make Euclidean TSP parallel (sym)metric TSP.


texts: Wait-Free implementation of an incremental counter

texts:
I know the theoretical difference between lock-free and wait-free algorithms, but it's a little hard to me to figure out how do they differ in implementation (code). In particular, i would like to know how would the implementation (code) of a counter be.
Thanks


texts: When is a root node an articulation point in a graph?

texts:
I am trying to find the articulation points in a connected undirected graph and I'm finding it difficult to figure out if the root node of the DFS is an articulation point.
Based on the literature I've read the root node is considered an articulation point if it has more than one child link1

My question is around the graph
(0 - 1)
(0 - 2)
(1 - 2)
(1 - 3)
(2 - 4)
(2 - 5)

When we the DFS rooted at 0 should 0 be considered an articulation point? it does have more than one child, however, the children are connected so removing 0 does not increase the number of connected component (doesn't cut the graph)

I would appreciate if someone can shed some light on this for me.


texts:
Imagine villages (or Internet Routers) scattered all over the world (or World Wide Web) connected by roads or shipping lanes (or Cables). All villages (nodes) has the same amount of villagers which visit some other villages (their intentions are undefined, so it's basically random) through shortest paths over the roads (edges). What is the way to sort villages by amount of travelers passed through it? Without forcing people to actually travel since we need to build hotels to make their journeys comfortable.

I think the technical specification of the problem can be like this:
Cyclic connected undirected graph. Every node in a graph has T value initially zero. Suppose there is a traversal via shortest path between every two nodes which increases every node's T value it passes through by 1 / N where N is amount of shortest paths between these nodes.

What is an algorithm to sort nodes by T without an actual traversing (faster than that)?

P.S. If there are two shortest paths, so it's like villager chooses to pass through random one (as defined as 1/N since we need to prepare hotels for approximate amount of visitors).