texts: Finding any path between nodes of implicit, finite, regular, undirected graph

texts:
Consider a 4-regular, finite, non-directed, integer-weighed graph $G$. Let each node carry an integer value indicating its distance from zero on a hypothetical axis $X$. Take a given node $N$ for which we know its distance from zero (either negative or positive) and the weights on the edges incident to it. Note, that for each node, two of the edge weights are positive and two are negative. All four are integers.  Let $N_0$ denote the node with distance zero on the $X$-axis. In the graph there is at least one $N_0$.

To better illustrate it see an outline diagram (apologies to readers with impaired eyesight for not including high contrast image).

Central blue node in the example has some negative distance from zero (black axis). Now, this node (like each node in this graph) has four edges with weights: w1 and w2 are positive-valued (so that if you choose to move along w1 and w2 this will bring you closer to zero on the axis), while w3 and w4 are negative. In the picture the blue node is connected with the target node with distance zero, but this is of course just for illustration.

Although the graph is finite, it is very large ($>10^{500}$ nodes or so), so one cannot represent the entire graph at once in RAM.

Take any initial node $N$ with weights $w_1,w_2,w_3,w_4$ and distance $d$. If one traverse along either of the four edges towards neighbour node, then all remaining weights in this neighbour can be easily calculated based on the weighs of the initial node (they form some arithmetic sequences, formulae of which are given).

Problem: Find any path (not necessarily the shortest) from $N$ to $N_0$ for the graph described above. The algorithm should basically provide values of subsequent edges (with their weighs) constituting the relevant path to $N_0$. What is the expected computational time complexity?

Additional - strictly related to the problem: Does one need to map the entire graph into memory in order to launch any suitable search algorithm?


texts: is there a (FLAC like) loseless compression coding format for EEG data?

texts:
EEG and Audio data are very similar, both

are numerical samples in continuous sequence

have a sample rate

need and can have multiple channels

channels for multi-channel audio
channels for each electrode

have predictable characteristics that are exploitable for compression.

FLAC is specifically designed for efficient packing of audio data, unlike general-purpose lossless algorithms such as DEFLATE, which is used in ZIP and gzip. While ZIP may reduce the size of a CD-quality audio file by 10–20%, FLAC is able to reduce the size of audio data by 40–50% by taking advantage of the characteristics of audio.

is there a standard loseless compression coding format for EEG data, that takes advantage of the characteristics of EEG, like FLAC takes advantage of the characteristics of audio?


texts: Solving a Knapsack problem with a special structure

texts:
I have a set of $N$ items to fill a knapsack with maximum capacity
$W$ and the maximum number of items that the knapsack can carry is $N_{m}$ items. The problem can be formulated as following:

max $\sum_{i=1}^{N} w_{i}x_{i}$

subject to

C1: $\sum_{i=1}^{N}w_{i}x_{i}\le W$.

C2: $\sum_{i=1}^{N}x_{i}\le N_{m}$.

C3: $x_{i}\in {0,1}$

Note that the profits are the same as the weights. The size of the problem maybe large, for example, $N=500$ and the weights are floating point (non integers).

As far as I know, dynamic programming can not be used as the weights are not integers. Therefore, I am thinking of using branch and bound (B&B). As this problem has a special structure where the profits and the weights are equal, I wonder if this simplifies the problem.


texts: What is the time complexity of the original Otsu's method?

texts:
I'm trying to give a general comparison of the time complexities of various thresholding algorithms. I have not taken an algorithms course yet, so please forgive any misunderstandings.
Otsu's method is performed on $N$ pixels with $L$ number of pixel intensities (e.g. an 8 bit greyscale image would have $L=256$). The algorithm will choose an intensity $k$, and calculate the variance for pixels with intensity less than $k$, and for pixels with intensities greater than $k$.
Calculating the variance involves finding the mean intensity (summing a total of  $N$ pixels), then sum the square of the difference between each pixel intensity and the mean mean intensity (again summing a total of $N$ pixels). This is performed for all intensities.
Therefore, would I be correct to say that the average time complexity of the algorithm is $O(LN)$?


texts: For a graph $G$ find the minimal $t$ such $G(t)=(V,E(t))$ is connected

texts:
Given a connected and directed graph $G=(V,E)$ with positive weights on the edges. for every $t>0$ we define $E(t)$ to be the group of edges with weight lower or equal than $t$. I need to find an efficient algorithm which computes the minimal $t$ such that $G(t)=(V,E(t))$ is connected.

I can sort all the edges with $|E|\log|E|$ complexity and try to take edges out of the graph from the heaviest to the easiet one, and to check with DFS if it is still connected, but its not effiecnt enough,

Any suggestions?


texts:
Theorem states that every problem in $\mathsf{NP}$ can be reduced to another $\mathsf{NP}$-complete problem in polynomial time. Also you can only make a problem polynomially longer using polynomial time.

Thus SAT of length $n$ can be reduced to knapsack with length $n^k$ for some fixed $k\in\mathbb{R}^+$. We don't need to show that reduction, we only need to know that it exists.

Knapsack has quasipolynomial algorithm, in other words running time is $O(\alpha^{\log^p q})$ where $\{p,\alpha\}\in\mathbb{R}^+$ are some fixed numbers and $q$ is length of knapsack problem.

Now assuming we have converted SAT to knapsack we get runtime $O(\alpha^{\log^p n^k})=O(\alpha^{k^p\log^p n})=O(\beta^{\log^p n})$ where $\beta\in\mathbb{R}^+$ is some fixed number. So, the runtime is quasipolynomial.

Why doesn't this simply negate ETH?


texts: Why are four context sensitive grammar (CSG) rules needed to represent AB -> CD?

texts:
In Wikipedia of Kuroda normal form, it says

  A straightforward technique attributed to György Révész transforms a grammar in Kuroda's form to Chomsky's CSG: AB → CD is replaced by four context-sensitive rules AB → AZ, AZ → WZ, WZ → WD and WD → CD.

Why are four rules needed here? Aren't three rules: AB → AZ, AZ → CZ, CZ → CD enough?


texts: Check if given safety properties are regular, and if so construct NFAs

texts:
Let $\mathit{AP} = \{a, b, c\}$. Consider the following LT properties:

Between two neighboring occurrences of $a$, $b$ always holds.
Between two neighboring occurrences of $a$, $b$ occurs more often than $c$.

For each of these properties $P_i$ (where $1 \leq i \leq 2$), decide if it is a regular safety property (justify your answers) and if so, define the NFA $A_i$ with $L(A_i) = \mathrm{BadPref}(P_i)$.


texts: Playing the game of life on an infinite grid

texts:
I would like to implement Conway's game of life on a grid that is infinite in all directions. It should be initialized with an initial pattern and then run, e.g, like this:

set(-500,200)
set(-501,201)
set(-502,202)
start()

What data structure should I use?

Matrices usually start with (0,0). One solution is to keep track of the smallest and largest index of a living cell, and move the matrix accordingly (so in the above example, we will need a 3-by-3 matrix). However, this might require to copy the entire matrix whenever a new cell is born.

Another solution is to use a hashtable indexed by pairs of indices. However, in this case the calculation of the next step will be more expensive since cells will not be next to their neighbors.

Is there a better data structure for such infinite grid?


texts: Calculating eigenvalue gap of a torus graph

texts: Consider a two-dimensional grid with wrap-around edges (a doughnut-shaped graph). I need to calculate the second-largest eigenvalue of the adjacency matrix. Is there a faster way of computing it for such a special graph than a general method such as the "eigs" function in MATLAB?


texts: DFA to accept a String containing even number of both A and B, but rejects empty String

texts:
I want to draw a DFA to accept a String containing even number of both A and B, but rejects the empty String(ε)
I have already drawn the DFA which accepts the above language, without rejecting the empty string.


texts: How to prevent deletion in an array in the B method

texts:
I have created a very basic model of an array list in the B method as shown below

MACHINE Array(TYPE)

VARIABLES block

INVARIANT block : seq(TYPE)

INITIALISATION block := []

OPERATIONS

add(e) =
   PRE e : TYPE
   THEN block := block <- e
   END;

remove =
   PRE block /= []
   THEN block := tail(block)
   END;

res <-- showArray =
    res := block;

res <-- getfront =
   PRE block /= []
   THEN res := first(block)
   END

END

However what I am trying to achieve is to create a model that prevents deletion from the list, so when an element is added, it cannot be deleted.

What should I add in the invariant to achieve this?


texts: Can we say DFA is more efficient than NFA?

texts:
I just started reading about theory of computation. If we compare which is more powerful (in accepting strings), both are same. But what about efficiency ? DFA will be fast compared to NFA, since it has only one outgoing edge & there will be no ambiguity. But in case of NFA we have to check all possible cases & that surely takes time. So can we say DFA is more efficient than NFA ?

But, my other part of brain is also thinking that NFA exists only in theory, so we cannot compare it's efficiency with DFA.


texts: Median-of-Medians proof for time complexity

texts:
Wikipedia mentions, that from the formula
$$
T(n) \leq T(n/5) + T(n\cdot7/10) + c \cdot n
$$

one can "easily" show using induction that

$$
T(n) \leq 10 \cdot c \cdot n
$$

I am, as it seems, not so smart. So, can anyone tell me how to show this using induction?


texts: What do `i` and `Number` represent in the Bakery Algorithm?

texts:
I am studying the bakery algorithm, and I am unsure of what the variable i represents in it. I understand that Entering represents a bool value to protect Nummber while it is updating, but I'm having a hard time finding clear explanations as to what variable is doing what.

Is Number an array of threads? Is i a particular thread? Or the value being updated?

What do i and Number actually represent?
What is passed in via Thread(integer i)? The value we are locking? Or a thread ID number?
Is there a value that represents a value being locked?

For reference, here is the Bakery Algorithm I am referencing, from Wikipedia:

   // declaration and initial values of global variables
   Entering: array [1..NUM_THREADS] of bool = {false};
   Number: array [1..NUM_THREADS] of integer = {0};

   lock(integer i) {
       Entering[i] = true;
       Number[i] = 1 + max(Number[1], ..., Number[NUM_THREADS]);
       Entering[i] = false;
       for (integer j = 1; j <= NUM_THREADS; j++) {
           // Wait until thread j receives its number:
           while (Entering[j]) { /* nothing */ }
           // Wait until all threads with smaller numbers or with the same
           // number, but with higher priority, finish their work:
           while ((Number[j] != 0) && ((Number[j], j) < (Number[i], i))) { /* nothing */ }
       }
   }

   unlock(integer i) {
       Number[i] = 0;
   }

   Thread(integer i) {
       while (true) {
           lock(i);
           // The critical section goes here...
           unlock(i);
           // non-critical section...
       }
   }


texts:
I haven't found anything in the literature that suggests what would happen if that is the case.
Thank you,
Akash


texts: What is the optimal way to perform GCD chain operation?

texts:
Matrix chain multiplication problem:- Given a sequence of matrices, the goal is to find the most efficient way to multiply these matrices.
This problem is solved using dynamic programming.

Similarly

GCD chain operation is defined as:- Given a set of $n$ integers, what is the most efficient way to find the gcd of all the elements?

The cost is the number of GCD(x,y) invocations done by a binary GCD algorithm.

Basic attempt at solving the problem is:-
GCD$(a_1,a_2,a_3,a_4,\ldots a_n)$

{

$k=GCD(a_1,a_2)$.

if ($k=1$)

return 1;

else

return $GCD(k,a_3,a_4\ldots a_n)$;

}

In simple terms, it keeps finding the gcd of the smallest two among all the $n$ elements and then recurse, by replacing the two elements with their gcd which is at most the smallest element in the input.

Make suitable assumptions if necessary. For example you can assume that the integers are given in sorted order.

Assume GCD is computed using a binary GCD algorithm (other GCD algorithm is also fine)
aka

$GCD(a,b)= GCD(a-b,b)$

$GCD(2a,2b)=2GCD(a,b)$

and $GCD(a,2b)=GCD(a,b)$ (if $a$ is odd)

GCD(75,25)=GCD(50,25)=GCD(25,25)=25

Number of steps is 3

GCD(125,25)=GCD(100,25)=GCD(50,25)=GCD(25,25)=25

Number of steps is 4

GCD(179,25)= GCD(154,25)=GCD(77,25)=GCD(52,25)=GCD(26,25)=GCD(1,25)=1

Number of steps is 6

A heuristic strategy mentioned in the basic attempt above is not optimal for the following example

GCD(25,75,125,179,181,225)

= GCD(GCD(25,75),125,179,181,225) (3 steps)

=GCD(GCD(25,125),179,181,225) (4 steps)

=GCD(GCD(25,179),181,225) (6 steps)

=1

This required 13 invocations of GCD(x,y) function.

But the optimal strategy would be to see that 179 and 181 have gcd 1 and therefore the solution is 1, which requires computing only 1 bivariate gcd.

GCD(179,181)=GCD(179,2)=GCD(179,1)=1

which takes 3 invocations of GCD(x,y) only

I am not sure if there exists an optimal way to do it, or maybe it is NP hard to find a solution which makes the least number of GCD(x,y) calls.


texts: Can I use the set of "used arguments values" as a memoization key for a deterministic function?

texts:
I have a deterministic function $f(x_1, x_2, ..., x_n)$ that takes $n$ arguments.

Given a set of arguments $X = (x_i)$, I can compute $U_X = \{ i \in [1, n] : x_i \text{ was read during the evaluation of } f(X) \}$

Would it be valid to use the set $K_X = \{(i, x_i): i \in U_X\}$ as a memoization key for $f(X)$?

In particular, I am worried that there may exist $X=(x_i)$ and $Y=(y_i)$ such that:

$$
\tag1 U_X \subset U_Y
$$
$$
\tag2 \forall i \in U_X, x_i = y_i
$$
$$
\tag3 f(X) \neq f(Y)
$$

In my case, the consequence of the existence of such $X$ and $Y$ would be that $K_X$ would be used as a memoization key for $f(Y)$, and would thus return the wrong result.

My intuition says that, with $f$ being a deterministic function of its arguments, there should not even exist $X$ and $Y$ (with $U_X$ a strict subset of $U_Y$) such that both $(1)$ and $(2)$ hold (much less all three!), but I would like a demonstration of it (and, if it turns out to be trivial, at least pointers to the formalism that makes it trivial).


texts: Find the Simple Cycles in a Directed Graph

texts:
This problem, for me, looks very interesting. It was about to find a simple cycle (i.e. cycle where are not repeat nodes) in a directed graph.

My solution is going like this, i.e, this graph is a case problem:

I know that there is a cycle in a graph, when you can find "back edges" in a depth-first-search (dashed in my picture in DFSTree), and for a moment I can sure for a few cycles, but not for all, simple cycles. Because, the directed egdes so important to from a cycle, i.e (0123) != (0321)

I'm thinking in make a dfs for each node with back-edges, but I'm not sure, and it's not clear. So, I ask you, if you guide me. Thanks!.

Here is my count of simple loops for my case problem.


texts: A data structure to do a specific lookup fast

texts:
I have 30,000 items; each item has 30 parameters that take values from 0 to 5. These parameters are named $p_0$ to $p_{29}$ and their value is an integer between 0 and 5. I want to store these items in a data structure where I can do this lookup quickly: find the parameter with a given value for $(p_0, \ldots, p_{29})$.

All items that have $p_i$ less than or equal $x_i$.

So having 50 values $x_0$ to $x_{29}$ I run the above lookup and it returns all items that satisfy it. I used PostgreSQL and created indices for each of these parameters. Querying in PostgreSQL happens in ~20ms. I stored them in a Python list and did a simple [i for i in items if all(i['p' + str(j)] < n[j] for j in range(30))] and it takes ~250ms. By using 30 dicts each containing 6 sets for different values of each parameter and doing the lookup in dicts and intersecting sets I was able to each ~10ms (a bit memory consuming but not that much). Does anyone know about a better data structure to do this query faster? Memory is not an issue as long as it's below 2GB.

In formal language I'd describe it this way:
I have 30,000 records; each record contains 30 values, each in range 0..5:

type Record: array[1..30] of 0..5
var Store: array[1..30000] of Record

I need to find all records in the store, where each element is smaller than in the target one:

procedure Find(target: Record):
  for item in Store:
    if item[0]<=target[0] and item[1]<=target[1] and ... and item[30]<=target[30]:
      print item

I need to perform Find quick, and can preprocess the Store to make the lookups faster. What data structure and algorithm can I use?


texts: If $P = NP$ would this imply that polynomial time reduction from an $NP$- to a $P$-problem would be possible? And if $P\neq NP$ does it imply that a polynomial time reduction from an $NP$- to a $P$-problem would be impossible?


texts: Logarithmic Randomness is Necessary for PCP Theorem

texts:
I am trying to proof the following statement:

If $ {\rm SAT} \in {\rm PCP}[r(n),O(1)]$, where $ r(n)=o(\log n)$, then ${\sf P}={\sf NP}$.

Here are my ideas for the proof:
It can be easily worked from here that there exists an nondeterministic Turing machine $N$ solving any SAT instance in time $o(n^{q})$ for any $q \in R^{+}$. I believe it should lead to a contradiction somewhere  (maybe alteration theorems). I had another approach to guess the certificate, but that takes time $2^{2^{o(\log n)}}$ which is not always polynomially bounded.

Source: PCP Course By Prahladh Harsha. This was one of the excercise questions. I am self studying this, so this does not violate any ethical arguments.


texts: Free description of the Kameda-Weiner algorithm?

texts: I found the paper "On the State Minimization of Nondeterministic Finite Automata" which, I assume, contains the Kameda-Weiner algorithm that I've been searching for. It's behind a paywall though. I'm just a hobbyist. Can someone explain it, or point me to another source?


texts: SAT solver optimizations of DPLL for unsatisfiable formulas

texts:
I am implementing a SAT solver based on DPLL algorithm, and it works fine on small formulas and larger satisfiable problems. My case split is based on a tree like structure, where every branch is tried one by one until solution for the problem is found or until every branch is tried.

So my problem now is that the above described approach does not terminate when trying to find a solution on large UN-SAT problems (so there shouldn't be a solution), therefore my program tries every possibility $2^n$, giving it a run time of years to solve UN-SAT problem with $50$+ variables (it would eventually terminate in years as I am not having any memory issues etc.).

My question is: what topics/implementations would I want to look at to speed up the tree processing or this case split process on unsatisfiable problems. Thanks.


texts: Algorithm to find maximum number of floors you can check with N eggs and D maximum drops

texts:
Question:  You are given access to a multistory building.  You have N eggs and are allowed D maximum drops from their window.

Rules:  If a egg is dropped from window of floor F and it breaks, it will break for all floors > F.

If an egg is dropped from window of floor F and survives, it will survive for all floors < F.

What is the maximum number of floors you can check in the worst-case?

E.g:  With 1 egg and 5 drops, you can check at most 5 floors (1, 2, 3, 4, 5)

With 2 eggs and 5 drops, you can check at most 9 floors (2, 4, 6 ,8, 9)

EDIT: By "maximum floors you can check", I mean the highest floor for which you can guarantee that you know the outcome for all floors <= to it. For. e.g in N = 1, D = 5 case, there is no algorithm that guarantees you will know the outcome at every floor <= 6 in the worst case. This is because in the worst-case: drops from 6, 5, 4, 3, 2 break and you don't know what will happen at floor 1 since you have no more drops left.

My solution is as follows

findMaxFloors(N,D)
{
 nextFloor = 0

 while (D > 0)
 {
    nextFloor += MIN(N, D);
    D = D-1;
 }

 return nextFloor;
}

But the solution given on the forum is more complicated (using recursion)
maxFloors(N+1,D) = maxFloors(N, D-1) + 1 + maxFloors(N+1, D-1)

I would appreciate any suggestions on the conditions under which my solution won't work.


texts: Using Subset Sum algorithm $O(n)$ times to find the subset

texts:
Subset Sum is a well-known dynamic programming problem, which states that given a succession of numbers and a number, the algorithm determines if exists a subset that its sum is equal to the given number. I was asked to use this algorithm (however it is implemented) at most $O(n)$ times to build a subset which satisfies the sum. My solution is given below:

    findSubset(A[1,...,n], sum){
      if(blackBox(A,sum)){
        for i = 1 to n do
          if(blackBox(A - A[i], sum))
               return findSubset(A - A[i],sum);
          endif
      return A;
      }else
        return [];
      endif
    }

The problem with this solution is that it uses the subSetSum algorithm $O(n^2)$ times. As a hint to optimize the problem to $O(n)$ is that I should not use the loop and appeal only to recursion. Can anyone give a hint for an optimal solution to this problem?


texts: Can the edges of a graph be assigned directions such that all nodes in a given subset have in- or outdegree 0, and every other node indegree > 0?

texts:
In a directed graph, the indegree of a node is the number of incoming edges and
the outdegree is the number of outgoing edges. Show that the following problem
is NP-complete. Given an undirected graph G and a designated subset C of G’s
nodes, is it possible to convert G to a directed graph by assigning directions to each
of its edges so that every node in C has indegree 0 or outdegree 0, and every other
node in G has indegree at least 1?

I need an idea how to prove it


texts: Treating undirected graphs as a subcategory of directed graphs

texts:
Roughly, an undirected graph is very similar to a directed graph where for each edge (v, w), there is always an edge (w, v). That suggests that it might be acceptable to view undirected graphs as a subset of directed graphs (perhaps with an additional restriction that adding/deleting edges can only be done in matching pairs).

However, textbooks usually don't follow this treatment, and prefer to define undirected graphs as a separate concept, rather than a subcategory of directed graphs. Is there any reason for that?


texts:
if A is in P and B is NP, then is A polynomial time reducible to B?

Could anyone prove a prove or disprove for it?


texts: Difference between virtual memory and job pool

texts:
Both virtual memory and job pools store the processes temporarily on disk and bring them to memory at some later stage, so what is the actual difference in between them?

What I guess is that when a process is just created, it first goes to the job pool and then it is sent to the ready queue. Virtual memory is only used when available memory becomes smaller than the required memory for any process (please correct me if I am wrong).

If this is the case then doesn't it decrease performance? What is the need to store processes in job pool first? Why don't we send processes directly to memory?

Also somewhere it was written as “job contains the list of all the jobs in the system and jobs in the memory are a subset of the jobs in the job pool”. So what is meant by “all jobs in the system” here? Does it mean “all NEW jobs”?


texts:
I am trying to solve this problem, and i have tried multiple methods, but i must be missing something, here is the problem:
Given a matrix MxN. Find the shortest path from (1,1) to (M,N), where each number in the matrix represents the costs and one can only move horizontal and vertical:

e.g.

M =

1, 50,50,50,50;
1, 50,1, 1, 1 ;
1, 1, 1, 50,1 ;
50,50,50,50,1 ;
50,50,50,50,1 ;

where the shortest path is: (1,1) , (2,1) , (3,1) , (3,2) , (3,3) , (2,3) , (2,4) , (2,5) , (3,5) , (4,5) , (5,5)

Initially i tried to solve this recursion using Dynamic Programming:

SP(i,j) = {
    M[i][j], if i=M and j=N
    min(SP(i+1,j), SP(i-1,j), SP(i,j+1), SP(i,j-1)) + M[i][j], otherwise
}

It however loops infinitely since it calls in every direction e.g. going right is dependent on going left and so on..

Can anyone help me solve this problem?


texts: Can every self-modifying algorithm be modelled by a non-selfmodifying algorithm?

texts:
If we have any arbitrary computer program that can modify its instructions, is it possible to simulate that program with a program that cannot modify its instructions?

Edit:

I am new to stackexchange so not sure if I'm allowed to ask a NEW question here, but here goes:
Ok so the proof that it is possible is actually really simple as you guys have shown.
Now, I am wondering: Are there problems for which it is more efficient (and to what extent) to use the most efficient self-modifying algorithm to solve the problem, versus the input-output-equivalent most efficient non-selfmodifying algorithm?


texts:
I am a physicist learning a bit of information theory.

I have encountered a term ("symbol codes") on Wikipedia, and cannot find what it means:

  Source coding theorem for symbol codes

  Let $\Sigma_1,\Sigma_2$ denote two finite alphabets and let $\Sigma_1^*$ and $\Sigma_2^*$ denote the set of all finite words over those alphabets (respectively).

  Suppose that $X$ is a random variable taking values in $\Sigma_1$, and let $f$ be a uniquely decodable code from $\Sigma_1^*$ to $\Sigma_2^*$, where $|\Sigma_2| = a$. Let $S$ denote the random variable given by the length of the codeword $f(X)$.

  If $f$ is optimal in the sense that it has the minimal expected word length for $X$, then (Shannon 1948): $$ \frac{H(X)}{\log_2 a} \leq \mathbb{E}[S] < \frac{H(X)}{\log_2 a} + 1, $$ where $\mathbb{E}$ denotes the expected value operator.

Please let me know what does symbol code mean.


texts: Can all types of computational problems be modeled as decision problems?

texts:
Can all types of computational problems (search, counting, optimization...) be modeled as (sets of) decision problems? Rephrased: For every type of computational problem is there a set of decision problems that if you solve those problems you get the result of the original problem?

colloquially: can all types of questions you can ask a string be answered by (a series of) results from YES NO questions? So the game is: you are given a question about a string, you are allowed to ask the string only YES NO questions. The string responds with answers to your YES NO questions that are computable. Can you compose all the answers you receive to narrow in on THE SINGLE answer to the original question (not a spread of answers / not some result but with a probability attached)?

Decision problems can be modeled as word to language membership. On the surface, this only models the functions that go from f:{0,1} * -->1 not all the other types of functions. Some g: {0,1} * -->{0,1} * for example. But I have a feeling the answer could be yes...


texts: Is the time complexity of the Fibonacci sequence O(fib(n))?

texts:
I started watching SICP lectures and am totally new to computer science.
SICP. LEC 1B: Procedures and Processes; Substitution Model
I don't know why the time complexity of the Fibonacci sequence is O(Fib(n)).
So, I googled about it,
he says

There's a thing that grows exactly at Fibonacci numbers. It's a horrible thing. You wouldn't want to do it. The reason why the time has to grow that way is because we're presuming in the model-- the substitution model that I gave you, which I'm not doing formally here, I sort of now spit it out in a simple way-- but presuming that everything is done sequentially. That every one of these nodes in this tree has to be examined. And so since the number of nodes in this tree grows exponentially because I add a proportion of the existing nodes to the nodes I already have to add one, then I know I've got an exponential explosion here.

Can anybody please explain what he's saying?


texts: Number of nodes at given depth in binary tree

texts:
Show that there is no comparison sort whose running time is linear for at least half of the $n!$ inputs of length $n$. What about a fraction of $1/n$ of the inputs of length $n$? What about a fraction of $1/2^n$?

The running time of a specific input is linear if the corresponding leaf node is within a linear distance from the root. Considering a binary tree, the maximum number of nodes within a linear distance from the root is $2^{kn+1}-1$.

How $2^{kn+1}-1$ was reached? just I need an intuitive idea not a proof. this is my notes not an homework or exercises. $k$ and $n$ not defined on it context.


texts: How can the local feature size become arbitrarily small?

texts:
I am stuck at the following exericse:

Let $\rho$ denote the local feature size. Draw an example where the curve C contains the line segment from $(-1, 0)$ to $(1, 0)$, but where $\rho( (0,0) )$ is arbitrarily small.

Here are the definitions that I heard in class:

Let $C$ be a smooth closed curve in the plane, and let $x$ be a
point of $C$. The local feature size $\rho(x)$ of x is the shortest distance from $x$ to the medial axis of C. (The medial axis $M(C)$ of a closed smooth curve $C$ is the locus of the centers of disks that touch $C$ at two or more distinct points.)

I do not understand how it should be possible for the local feature size to become arbitrarily small, since we are looking at smooth plane curves. I have tried to draw some examples, but the ones I found were always non-smooth, like the one below. (The image comes from Wikipedia's article on cusps.)


texts: When shopping for a set of items, find the lowest price set of bundled items

texts:
Suppose a store sells items a, b, ..., z.

Rather than sell the items à la carte, the store bundles them at seemingly arbitrary prices, e.g.:

+-----------+---------------+-------+
| bundle    |     items     | price |
+-----------+---------------+-------+
|         1 | 1 a           |    10 |
|         2 | 1 b           |    10 |
|         3 | 1 a, 1 b      |    15 |
|         4 | 1 a, 1 b, 2 c |     5 |
|         5 | 1 a, 2 c      |    20 |
+-----------+---------------+-------+

Given the bundles and a shopping list of items, e.g., 1 a, 2 b, 6 c, etc., find the lowest price set of bundles that includes all the shopping list items. It's ok to leave with unwanted items because you can sell them on ebay.


texts: Is there a concept of information that distinguishes between "computed" and "non-computed" information?

texts:
I always tend to think of information as follows: If we have an information set $I$, and it is possible to derive from $I$ another information set $X$, then $I$ really contained $X$ all along, and we haven't actually discovered "new information". We've merely found out something new about the information we already had.

But sometimes, deriving $X$ from $I$ is computationally very complex, so that it may take 1000 years to do it. In this case, any reasonable person in every day life, would say that we don't have the information $X$, even though we have $I$ and $X$ can theoretically be computed from $I$.

My question is, is there a concept that captures this notion of not having a piece of information merely because it is hard to compute? i.e. it could be something like: $I_{405}^*$ is the information set containing all information that can be generated by at most 405 computational steps from $I$. This is a somewhat vague definition, but I'm wondering if there is something more formal


texts: Understanding memory mapping conceptually

texts:
I've already read several blogs and questions on stack exchange, but I'm unable to grasp what the real drawbacks of memory mapped files are. I see the following are frequently listed:

You can't memory map large files (>4GB) with a 32-bit address space.

QUESTION #1:
Why? Isn't that the whole point of virtual memory? If a file is greater than 4GB, it may cause trashing by swapping out some memory mapped pages, but why is there a limitation?

If the application is trying to read from a part of the file that is not loaded in the page cache, it (the application) will incur a penalty in the form of a page-fault, which in turn means increased I/O latency for the operation.

QUESTION #2:
Isn't this the case for a standard file I/O operation as well? If an application tries to read from a part of a file that is not yet cached, it will result in a syscall that will cause the kernel to load the relevant page/block from the device. And on top of that, the page needs to be copied back to the user-space buffer.

Is the concern here that page-faults are somehow more expensive than syscalls in general - my interpretation of what Linus Torvalds says here? Is it because page-faults are blocking => the thread is not scheduled off the CPU => we are wasting precious time? Or is there something I'm missing here?

Overhead of kernel mappings and data structures - according to Linus Torvalds. I won't even attempt to question this premise, because I don't know much about the internals of Linux kernel. :)
No support for async I/O for memory mapped files.

QUESTION #3:
Is there an architectural limitation with supporting async I/O for memory mapped files, or is it just that it no one got around to doing it?

One drawback that I thought of was that if too many files are memory mapped, this can cause lower available system resources (memory) => can cause pages to be evicted => potentially more page faults. So some prudence is required in deciding what files to memory map and their access patterns.

QUESTION #4:
Vaguely related, but my interpretation of this article is that the kernel can read-ahead for standard I/O (even without fadvise()) but does not read-ahead for memory mapped files (unless issued an advisory with madvice()). Is this accurate? If this statement is in-fact true, is that why syscalls for standard I/O maybe faster, as opposed to a memory mapped file which will almost always cause a page-fault?


texts: What's the algorithm for floating points equality test?

texts:
I've found that 0.1 + 0.2 == 0.3 is not true in Java (see this demo).

So, I'm interested in how equality testing can be implemented for floats. Is there a standardized algorithm?


texts: Running time analysis of a linear algorithm seems to me quadratic

texts:
I have been analyzing an algorithm for several hours in order to find out why it is expressed as $O(n)$ (I saw this solution in a PowerPoint presentation which refers to it as a linear algorithm). I see a while  loop inside a for loop.

The for loop executes $n$ times.

The while loop executes "at most" $n$ times $(0, 1, 2, ..., n - 1)$ which can be represented as $n*(n+1)/2$

So, the running time formula can be $(n)*[n*(n+1)/2]$ which yields to a quadratic expression. (I have not taken into account individual statements inside the loops for simplicity).

What is wrong with my reasoning?

Algorithm spans2(X, n)
    S = new array of n integers
    A = new empty stack
    for i = 0 to n - 1 do
        while (!A.isEmpty() && X[A.top()] <= X[i] ) do
            A.pop()
        if A.isEmpty() then
            S[i] = i + 1
        else
            S[i] = i - A.top()
        A.push(i)
    return S


texts: Time complexity of a recursive enumeration in the problem of finding n-tuples of naturals greater than 1 with bounded product

texts:
I have to determine the time complexity of a recursive enumeration in the problem of finding n-tuples $(k_i, ..., k_n)$ of naturals greater than 1 with product less or equal to $K$. Problem can be formally expressed as: $$\begin{align}0<\prod_{i=1}^nk_i\leqslant K\in\Bbb N,\ k_i \in \Bbb N^{+}\setminus\{1\}&\  \forall i\in\{1,\ldots,n\},\end{align}$$

The number of steps required to enumerate all n-tuples of naturals greater than 1 is:
\begin{equation}
f(K, n) = \sum_{k=2}^{\lfloor \frac{K}{2^{n-1}}\rfloor} \bigg(1 + f(\lfloor \frac{K}{k} \rfloor, n - 1)\bigg)
\end{equation}
\begin{equation}
f(K, 0) = 0
\end{equation}

I can provide trivial time complexity analysis. As every $k_i \leq \frac{K}{2^{n-1}}$ and there $n$ factors which can be in interval $[2,  \frac{K}{2^{n-1}}]$, we have that the maximum number of steps is $(\frac{K}{2^{n-1}} - 1)^n$. Therefore,  complexity in big-O notation should be $O\bigg(\frac{K^n}{2^{n^2-n}}\bigg)$. I do not know if this observation is of any relevance to the time-complexity analysis.


texts: Knuth's Algorithm X - why do we backtrack rows but not columns?

texts:
Knuth's Algorithm X (described here in more details) prescribes that we select a column deterministically (but arbitrary), when we backtrack rows we do not backtrack columns, so we do not have an opportunity, to "rewind", select a different column and try again, during the course of the algorithm.

How can we be sure, that we find all solutions if we do this, and don't miss a few? Or did I get this wrong, and the algorithm cannot actually find every solution? Reading the research paper linked above I got an impression, that it is able to find / enumerate all the solution. So what makes sure we do not miss some of these?


texts:
Suppose I have two sets $A$ and $B$ containing integers. Let $B'$ be the power set of $B$. Then suppose I have an algorithm that enumerates all possible pairings of elements in $A$ and $B'$ to apply a function $f$ to them and check something.
I understand that generating a power set is $O(2^n)$, but what complexity class does this belong to, and how do I prove it?


texts: Are all Recursively Enumerable languages which are not Recursive also Undecidable?

texts:
Knowing that all Recursive languanges are Decidable and All Not R.E. Languages are Undecidable (correct me if I am wrong), Are all languages which are R.E. but not Recursive also Undecidable?
R.E. ==> Recursively Enumerable


texts: Tuning the parameters of Particle swarm optimization (PSO)

texts:
To tune the parameters of Particle swarm optimization (PSO), there are two methods offline and online. In offline manner, the meta-optimization is used to tune the parameters of PSO by using another overlying optimizer. In the online manner, there are two techniques, Self-Adaptation, "consisting of adding some or all of the optimizers behavioural parameters to the search-space, thus making them subject to optimization along with the problem at hand". Another technique is Meta-Adaptation ," in which an overlaying optimizer is trying to tune the parameters of another optimizer in an online manner during the optimization of a problem."

"The concept of meta-optimization. A black-box optimizer is used in an offline manner as an overlaying meta-optimizer for finding good behavioural parameters of another optimization method, which in turn is used to optimize one or more actual problems."

In standard PSO the particles are initialized by using uniform random numbers and these particles are updated using update equations. the best solution is selected based on the best value of objective function.

In my work. I have two data sets, training and theoretical dataset and I need to initialize the particles by using training data instead of random numbers.

In this case, how can I tune the parameters of PSO using training and theoretical data set.

Also, I have a problem which is, I got the best cost in the initial step of PSO and in the initial step there are no parameters or update equations.

Is it possible to tune the parameters using Machine Learning method? How can I do this?


texts: An encoding algorithm with an expensive encoder and a cheap decoder

texts:
I am looking for an encoding algorithm that would have an encoding function with highly expensive computational costs (ideally like scrypt). At the same time its decoding function must be a lot easier to calculate.

Computational costs should not depend on the size of the encoded data. The size of the encoded data can be up to 10 KB. The encoding part of the algorithm should also be small in the sense of not containing a huge constant data set used for calculations. The decoder can be large but not ridiculously (< 10 MB). Some sorts of encryption are not forbidden.

Under computational costs I understand both calculation and memory costs, however one of them would also suffice

Pseudocode:

var encoded = encode("Hello world"); // Takes 10 seconds
var decoded = decode(encoded); // Takes 0.01 second

Encoding by brute-forcing the decode operation should be slower than encoding operation itself unless decode operation can be kept secret.

I was looking at asymmetric cryptography, I may be wrong, but those algorithms usually have equally expensive encryption and decryption functions. And their keys have length of the same order.

Maybe some of NP-complete problems could be a solution, but I don't know how to reuse them.

Thanks!


texts: Multi-Paxos Full Disclosure: How does the acceptor know about the chosen value after it marks an entry as chosen?

texts:
I am learning multi paxos from the slides of this made by John Ousterhout and Diego Ongaro.

In this section talking about Full Disclosure, it says the acceptor mark entry 6 as chosen, since the proposer tells it, with the same proposal 3.4 and firstUnchosenIndex 7.

My Question is: As you can see, proposal 3.4 is for entry 8 now, how can the acceptor simply mark entry 6 as chosen without knowing the chosen value?


texts: Why is abstraction in lambda calculus called abstraction?

texts:
The term abstraction as I understand it, is used in many different contexts, but has one essential meaning, namely that it refers to the “general properties of some class of objects that doesn’t rely on their details”. For example, abstraction in programming is e.g. interfaces that allow you to constrain a set of objects without specifying certain implementation details.

But in lambda calculus, I don’t see what “function abstraction” has to do with something like “independence of details”. It seems to me like “function application” or “argument substitution” makes more sense.

Am I missing something?

Ps. Note that I have only read an introductory chapter of a book on lambda calculus.


texts: Getting maximum number of pairs in a set

texts:
I'm sorry if the title is unclear, I didn't know how to name this question.

I have a problem where I have an array of numbers with positive integer values. For a pair of these integers to be considered valid, they should follow the format a^2 + b^2 = x^2, where a and b are the integers, and x is any whole number.

What I need to do is to find the maximum number of pairs that can be used concurrently (for example, if I have numbers {3, 4, 4}, the answer would be 1, even though there are two valid pairs (3 and the first 4, as well as 3 and the second 4), because we can not use both of these pairs at the same time.

Can anyone point me in the right direction toward solving this problem without brute-forcing all the combinations?


texts: Huffman coding for non-dyadic distribution

texts: I have a question regarding the methodology of Huffman coding. So, is there a Huffman coding methodology that approximates the minimum average number of bits per decimal character when the odds of information symbols are not powers of 2? I can't understand or find anything relevant


texts: Nominal unification: How this lemma is proved?

texts:
I was reading nominal unification paper. I could not understand the proof of a lemma. The paper is here  nominal unification. The lemma is following.
$\sigma$ is a substitution, $\pi$ is a permutation (swapping of atoms).

Lemma 3.3. if  $\Delta \vdash \sigma(\pi .X) \approx \sigma(t)$, then $\sigma.[X:=\pi^{-1}.t] = \sigma $.

The paper said, to prove the lemma, need to show that  $\Delta \vdash \sigma(\pi^{-1}.t) \approx \sigma(X)$.
It first showed $\Delta \vdash \sigma(t) \approx \pi.\sigma(X)$, from which,
then the paper finished the proof by saying the following.

  The case the follows from the assumptions by symmetry and commuting
   the  permutation inside the substitution.

I could not imagine  how $\sigma.[X:=\pi^{-1}.t] = \sigma $ is obtained from $\Delta \vdash \sigma(\pi^{-1}.t) \approx \sigma(X)$.
what does that "assumptions by symmetry" mean?

Could anyone point out what proof technique is used here?

Thanks.


texts:
I've been learning about Theory of Computation lately, and i'm trying to link general programming with the Theory of Computation.  I thought of considering any arbitrary program that halts, as an algorithm for solving some specific computational problem in the sense of Theory of Computation.

For some programs (like a calculator program, etc.), it is really easy to see them as an algorithm for solving some computational problems.

It seems to me, however, that some other programs are really not solving any computational problem.

Computational problems have instances, which can be see as the possible inputs to the algorithm that solves the problem (if the problem is computable), and for each instance there is an answer, which can be seen as the outputs to the algorithm.

But now, how could a Hello World program (prints the string "Hello World") be considered as the algorithm for solving some computational problem?  What would be the computational problem, and its possible instances?

Other examples would be a program that solely does the job of establishing a connection to another computer over a network, and then proceeds to send messages to it, closing the connection in the end.

Is it really an algorithm to solve some computational problem?

So I'm thinking that programs (even considered the subset of those that halt)  don't ALWAYS relate to Theory of Computation.  In another words, there are some programs (mostly the ones that seems fixed procedures with no inputs) that don't represent the algorithm/solution for a problem, and hence can't be represented in a true Model of Computation like a Turing Machine.

Any opinions on the relation between programs that halt in general and Computation Theory?


texts: Which language is used to construct a type system?

texts:
Typically, OCaml and Scala seem to be used for designing any programming languages tool. But what features offer them an edge over other languages.
A related question, is a type system for a language always written in the native language itself?


texts:
I have a question about undecidability. And I hope you could point out where I am wrong.

The question is: to decide the following question as (A) recursive, (B) RE but not recursive, (C) not RE.

$L = \{\langle M\rangle|M \text{ is a TM and } |L(M)| \geq 3\}$

If we use $HP$ as halting problem and $\overline{HP}$ as the complement of halting problem. Then the solution could be (B) RE but not recursive (Taken from the Internet):

I understand this proof. But I have another proof as follows, and I can't figure it out why it is wrong.

We prove this by a reduction from $\overline{HP}$. Simulate $M'$ on input $w$ works as follows: it runs $M$ on $x$ and rejects if $M$ halts on $x$.

(1) $\langle M, x\rangle \in \overline{HP}$ $\rightarrow$ $M$ doesn't halt on $x$ $\rightarrow$ $M'$ accepts all inputs $\rightarrow$ $|L(M')| \geq 3 $ $\rightarrow$ $M' \in L$

(2) $\langle M, x\rangle \notin \overline{HP}$ $\rightarrow$ $M$ halts on $x$ $\rightarrow$ $M'$ doesn't accept any input $\rightarrow$ $|L(M')| < 3$$\rightarrow$ $M' \notin L$

Thus $\overline{HP} \leq_m L$. As $\overline{HP}$ is not RE, $L$ is not RE, which is wrong.

So where is wrong?

Thanks!


texts: What can be said about complexity class of a problem if there exist a pseudo-polynomial verification algorithm?

texts: Let X be a problem for which pseudo-polynomial algorithm time for verification of solution exists. What can be said about complexity of problem X? Can X belong to NP-hard class?


texts: Does NP-hard problems have to be decision problems?

texts: According to the selected answer on this question NP-hard problems do NOT have to be decision problem. But by definition all NP-hard problems can be karp-reduced from any NP-problem in polynomial time; thus, implying that the answer from the reduction must be the same as the NP-problem which is yes/no => decision problem. So isn't NP-hard problems in fact always decision problems?


texts: Number of submatrices with a particular sum- Answer Explantion

texts:
I read Evgeny Kluev answer on this and was not able to understand the mechanism. Now let us understand using an example. let us say we have this matrix.

[1  2  3  2   5,
 2  4  6  4  10,
 3  6  9  6  15,
 2  4  6  4  10,
 5  10 15 10 25]

Now applying step 1 we get .

[ 1  2  3  2  5 ,
  3  6  9  6  15,
  6  12 18 12 30,
  8  16 24 16 40,
  13 26 39 26 65]

Now applying step 2 we get all the possible pair of row indices i.e.

(1,2) (1,3) (1,4) (1,5) (2,3) (2,4) (2,5) (3,4) (3,5) (4,5)

Now comes the last part of applying two pointer algorithm. Which i am failing to understand.For ex.
Lets take (1,2)

B[2][1] - B[1][1]= 3-1 = 2
B[2][2] - B[1][2]= 6-2 = 4
B[2][3] - B[1][3]= 9-3 = 6
B[2][4] - B[1][4]= 6-2 = 4
B[2][5] - B[1][5]= 15-5 =10

Now how is that helping? I mean on these values if we apply two pointer algorithm what will we achieve? For example i am looking for all occurrences of 36. How do i get close to it. ?

Can anybody carry this forward and explain the solution?


texts: Covering grid with constrained rectangles

texts:
I need to place N rects on a 2-dimensional grid with constraints.

For the each rect height/width and placing limitations($x_{min}$-$x_{max}$) are known.

The problem is to place all rects on a grid with no intersections that every rect's bottom left $x$ is in rect's $x_{min}$-$x_{max}$.

I've implemented the naive solution where I just iterating over rects and incrementing $x$ by some fixed step while checking for intersections. If no place found then I increment $y$ and iterate again.

The question: I'm sure that there are algorithms/data structures that will help me to solve this task faster, but I do not know where to start.


texts: Large number of layers in a neural network?

texts:
How large can the number of layers in a neural network be? Can there be maybe 1000 layers with, say, 1000 neurons in each layer?

I imagine the brain has hundreds of thousands of layers.


texts: Order the vertices to maximize the weights of edges in the induced subgraph

texts:
I have a complete directed graph $G:=(V,E)$ with directed edge weights $c_{ij}$ for every distinct nodes $i$ and $j$.

Goal: Find the topological order such that the smallest edge weight of the complete DAG that corresponds to the topological order is maximized.

Example: Imagine we have 3 nodes and the topological order $\pi:=(1,2,3)$; then the complete DAG is the subgraph of $G$ with vertices 1,2 and 3 and edge weights $c_{12}$, $c_{13}$ and $c_{23}$. If $\pi_2:=(1,3,2)$, then the complete DAG is the subgraph of $G$ with vertices 1,2 and 3 and edge weights $c_{13}$, $c_{12}$ and $c_{32}$.  I am looking for the topological order of vertices such that the minimum value of the corresponding DAG is maximized.  So in our example for $\pi:=(1,2,3)$ we get the value $\min(c_{12},c_{13},c_{23})$, for $\pi_2:=(1,3,2)$ we get the value $\min(c_{13},c_{12},c_{32})$.

We are looking for a topological order such that the value is maximized.  There may be more than one valid solution.

Is there an efficient algorithm for this problem?

More precisely, we can formulate the optimization problem as follows. Let $\Pi$ denote all possible topological orders of the nodes $\{1, \ldots, d\}$. Then what I want is

$$\text{arg}\max_{\pi \in \Pi}\min\limits_{(i,j) \in E: \\ \pi(i)<\pi(j)}c_{ij},$$

where $\pi(i)$ denotes the position of node $i$ in the topological order.


texts: When to use Djikstra or Bellman-Kallaba algorithm?

texts:
This the answer that was accepted for the arrangement problem of a library:

  we have books with heights $H_n,$ $1 \le n \le N$ and widths $W_n,$ with heights in ascending order for each book, and we want to group them into shelves.

  Reuse these numbers for solution nodes $n,$ where that node represents a solution state "all books $i \le n$ have been shelved." We will therefore start at node $0$ and seek to get to node $N$ by the shortest path with Dijkstra's algorithm. These nodes are the vertices of our graph.

  We then draw from node $i$ to any node $j \gt i$ a directed edge which assumes that all of those intermediary books will be shelved with one shelf, i.e. the length of this edge is $$L_{ij} = F_j + C_j~\sum_{n=i+1}^j W_n,$$where I have assumed that when you were saying the cost of the sum was $F_i + C_i x_i$ the subscript $i$ on the $x_i$ was totally meaningless.

  Dijkstra's algorithm will then give us a shortest-length path to node $N.$

With such an array, showing how many books do we have of length $H_i$ with $L_i$ meters of documents of $type \ i$, and the cost of storing such documents: $F_i$ a fixed command cost and $C_i$ the varying cost accorfing to $x_i$ the length of documents we would store within it,

\begin{array}{|c|rr}
i & 1 & 2 & 3 & 4\\
\hline
H_i & 12\,\mathrm{cm} & 15\,\mathrm{cm} & 18\,\mathrm{cm} & 23\,\mathrm{cm}\\
L_i & 100\,\mathrm{cm} & 300\,\mathrm{cm} & 200\,\mathrm{cm} & 300\,\mathrm{cm} \\
\hline
F_i & 1000€ & 1200€ & 1100€ & 1600€ \\
C_i & 5€/\mathrm{cm} & 6€/\mathrm{cm} & 7€/\mathrm{cm} & 9€/\mathrm{cm}\\
\end{array}

The graph is:

My question is: why should we use a Djikstra algorithm? We don't have any circuits and we can't go backward. Therefore, shouldn't we use Bellman-Kalaba algorithm?


texts: I need a better data structure than a graph with condition nodes

texts:
Suppose i have a cyclic weighted ($\mathbb{Z}$) directed graph where nodes are either simple or complex. a simple node is just a usual node whilst a complex node is a node that contains a set of integers which act as conditions. Consider the graph $G=(V,E)$ where
$V= \{v_1,v_2,c\}$ and $E=\{(v_1,v_1,2),(v_1,v_1,-1),(v_1,c,0),(c,v_2,0)\}$ and $c:=\{1,4,5\}$. The conditions are defined as follows. Suppose i start a walk in the graph from node $v_1$ and i arrive at node $c$ with a current weight of $m$. The condition node states that the walk may pass through node $c$ only if there are three separate walks from the start node $v_1$ to $c$ (without going through $c$) of weights $m+1,m+4,m+5$ (i.e the conditions of $c$). All condition nodes in the graph will always only have one incoming edge and one outgoing edge.

Example: Suppose i want to ask the graph if there is a walk from $v_1$ to $v_2$ of weight 0. There is a walk of length 0: $v_1 \rightarrow_0 c \rightarrow_0 v_2$ but this walk is only valid if i can get from $v_1$ to $c$ with weights 0+1,0+4 and 0+5
which i can with the following paths:

1: $v_1 \rightarrow_2 v_1 \rightarrow_{-1} v_1 \rightarrow_0 c$
4: $v_1 \rightarrow_2 v_1 \rightarrow_{2} v_1 \rightarrow_0 c$
5: $v_1 \rightarrow_2 v_1 \rightarrow_{2}v_1 \rightarrow_{2} v_1 \rightarrow_{-1} v_1 \rightarrow_0 c$

Although i can represent this in a graph well (as above) its hard to utilise any existing graph algorithms that can decide this for any walk as the nature of the condition node is unusual for a standard graph. Ideally, it would be good if i could remove all condition nodes from a graph, but it is not obvious how to do this. I did think about using petri nets, but it is difficult to take an unbounded number of tokens (the weights) into account and start a new walk whilst "remembering" the conditions that need to be satisfied.

Is there a better data structure that would be more suitable to represent this problem that existing algorithms could act upon in order to answer the decision question?

Is there a known graph algorithm we can utilise to decide if there exists walks of an exact weight $k$ between 2 simple nodes? I asked a similar question here but this was with a graph of only simple nodes.


texts: Sequential subsequence removal with arbitrary predicate

texts:
I want to extract sub-sequences from a sequence of float values.
The "scale" and range of these values is arbitrary (as I can manipulate it at will) but the "shape" is consistent.

For a visual example:

I want to extract the above five stacks as five "chunks". I want them in the order they occur (left-to-right). Do not be too distracted with the visual, though, as there can be an arbitrary number of points within the interval, but guaranteed $N_{points} < 2000$.

I have tried framing this problem as a dynamic partitioning problem, as an iterative subsequence extract problem, and something like $argmax$ but applied multiple times on a shrinking sequence.

Please pardon the ambiguity; I am struggling to even articulate the problem in a useful fashion. Critique and guidance would be much appreciated


texts: Creating all possible subsets and complexity calculation

texts:
I am a novice programmer and very weak in complexity calculation. I have learnt to write a program for creating all possible subsets from a set of elements, i.e. knapsack algorithm.  Now I would like to know how to calculate the complexity of the algorithm. Can anyone help me with better clarification.
Here is my code:

#include<iostream>
#include<cstdio>
#include<map>
#include<vector>
using namespace std;
int N,M,a[15];
map<int,vector<int> >multiple;
void creating_subset(int i,int m,int l)
{
  if(i>=M)
  {
    multiple[l].push_back(m);
    return;
  }
  creating_subset(i+1,m*a[i],l+1);
  creating_subset(i+1,m,l);
}
int main()
{
  cin>>M;
  for(int i=0;i<M;i++)
  cin>>a[i];
  creating_subset(0,1,0);
  for(int i=0;i<multiple[3].size();i++)
  printf("%d ",multiple[3][i]);
  cout<<endl;
  return 0;
}


texts:
I'm reading The Algorithm Design Manual and this is one of the excersizes:

Prove or disprove the following statement:
$\Theta(n^2 ) = \Theta(n^2 + 1)$

I think this is untrue because the right side of the equation claims to have a multiple $c$ such that it is smaller than all the multiples of $n^2$, which is untrue.
But since the book doesn't have answers and I'm not really sure about this question I had to ask.
Thanks a lot :)


texts: relationship between binary numbers and binomial heaps

texts:
I understand that a binomial heap can be represented as binary numbers according to the degree of each tree but what exactly is the relationship between inserting a new node into the binomial heap and incrementing the binomial number.

In addition to that, I assume that there is a relationship between performing union on two binomial heaps and adding the two binary numbers of the binomial heaps but what exactly is the relationship.

I'm looking for something like a formal / textbook definition or of the relationship (if possible)


texts: How to find the vertices on simple path between two given vertices in a directed graph

texts:
Given a directed graph and two distinct vertices S and T, is there a polynomial-time algorithm which finds every vertex which is on at least one simple path from S to T?

It is not difficult to find all vertices that are both successors of S and predecessors of T but this is only a superset of the set above. For example, consider the following graph:
S -> a; a -> b; b -> c; b-> T; c -> a

While a, b and c are all successors of S and predecessors of T, there is no simple path from S to T going through c (because every path from S to T going through c contains twice a and b).

A closely related problem is the following:
Given a directed graph and three distinct vertices S and T and I, is there a polynomial-time algorithm to decide if there exist a simple path from S to T going through I.

A polynomial-time algorithm to this latter problem can be use to build a polynomial algorithm to the former since we can apply it succesively by replacing I by every node in the graph (or more efficiently to every node that is both a succesor of S and a predecessor of T).


texts:
Is there any algorithm which takes regular expression as input and finds if the regular language which expression describes is infinite?Does it have to do with pumping lemma?

Additionally,is there an algorithm which finds if a regular language of a regular expression is the empty set?

Thank you


texts: Select at least one from each category to minimize union, NP-hard problem?

texts:
I have this problem that is very similar to the minimum k-union problem:

Given a collection $C$ of subsets of a finite set $S$ and each set $c\in C$ has a label that is its category. The problem is to select at least one $c$ from each category such that the size of their union is minimized.

Is this problem NP-hard?


texts: CFG for palindromes containing atleast 3 c's

texts:
Input alphabet = {a,b,c}

I tried with the following grammar :-

S -> aSa / bSb / T
T -> cTc / cSc / cBc
B -> c  / cXc
X -> a / b / aXa / bXb / epsilon

This grammar is not able to generate 'cacac' .Is there any way to write this grammar with less number of productions or are any productions redundant here ?

Thanks.


texts: length of longest representative "uu" in suffix automaton

texts:
Trying to find the length of the longest representative of an equivalence class in suffix automaton, such that it has the form:
$\{v\in{}\Sigma|v$ is the longest representative $\wedge$ $(\exists{}u\in\Sigma*)(v=uu)\}$|. In other words how can we find the length of the longest node $v$, such that $\overset{\overset{w}\longleftarrow{}}{v}=v$, where $\overset{\overset{w}\longleftarrow{}}{v}$ is just the notation for the longest infix $u$ of $w$, i.e. $\big($ i.e. $u\in{}Inf(w)\big)$ , such that $u_{\equiv{Suff(w)}}v$ ($u$ is in one class of equivalence with $v$: $end\_pos(u)=end\_pos(v)\big)$.
I know that the charactarization of a representative, i.e. a state in the suffix automata for $w$ can be $v$, either $v$ is a prefix of the word $w$, OR there exists $a,b\in\Sigma,a\ne{}b$ such that $av,bv\in{}Inf(w)$.
Knowing that fact, I tried to prove that if there is a state with represents $Inf(w)$ of the form $uu$, it must be either created only from one letter, or it must be the whole word $w$, but I failed, because that assumption was wrong: the suffix automaton for word $ababc$ has a representative "abab". Does anyone have any ideas how to find that longest length? (Consider we have build or that we can build a suffix automaton for the word $w$ and we have the suffix states, suffix transitions and etc... but that may be a wrong direction, I don't know, because maybe we can find the answer for the task while building the SA). Help?


texts: Need help to come up with definitive proofs with regard to Planar Graphs

texts:
I was working through a few problem sets and came across this question

Suppose there is a connected planar simple graph $G$ with $v$ vertices such that all its regions are triangles (a cycle consisting of three edges).
Question 1: Into how many regions does a representation of the Planar Graph $G$ Split the plane?

Incase of this question, since all the degrees of regions are said to be 3, we can say $2e=3r$. I substituted this value into the Euler equation, $v-e+r=2$  and got my final answeras $2(v+2)$.

Question 2: Suppose the vertices of the planar graph G are colored in three colors. A region is called to be tricolored (or bicolored) if its vertices are colored in exactly three (or two) different colors. Similarly, a monocolored region is the one with all its vertices colored in exactly one color. Prove that the number of tricolored regions is always even no matter how the vertices are colored.
(Hint: If you place a new vertex inside a region (triangle) of G and connect it with all vertices of that region, then all regions are still triangles and the parity of the total number of regions stays the same.)

This question seemed very straight-forward to me on account of my previous answer. Since I derived the value $r = 2(v+2)$ which would always remaining even while incrementing $v$. I don't really understand the point of the Hint or maybe what exactly we have to prove here.
Any help with regard to the same would be appreciated. Thanks!


texts: Discrete solution space in NP-complete problems

texts: While there are many known NP-complete problems, they all seem to be discrete in the solution space. What is the underlying principle for this?


texts: How can I estimate Bhattacharyya parameter for BSC channel, used for Polar codes

texts:
In polar codes, the frozen bits in each message are determined through the worst channel, where the relevant parameter is the Bhattacharyya .

How can I estimate Bhattacharyya parameter for BSC channel?


texts: Offline bin-packaging problem: probability of a non-optimal solution for the first-fit-decreasing algorithm

texts:
For the offline bin packaging problem (non-bounded number of bins, where each bin has a fixed size, and a input with known size that can be sorted beforehand), the first-fit-decreasing algorithm (FFD) gives a solution whose number of bins is, at most, $\frac{11}{9}\times S_{opt} + \frac{6}{9}$, or, for the sake of simplification, around $23\%$ bigger than the optimal number of bins ($S_{opt}$).
Has the probability of getting a non-optimal solution using FFD been ever calculated? Or, in other words, what is the probability of getting a solution whose exact size is $S_{opt}$? Or do we have no other choice than assuming that the solution size is evenly distributed in the interval $[S_{opt}, \frac{11}{9}\times S_{opt} + \frac{6}{9}]$? Or, as another alternative I can think of right now, is the solution size so dependant on the input that making this question has no sense at all?
And, as a related question, is there any research about what is the NP-hard or NP-complete problem that has an approximation algorithm (of polynomial asymptotic order) with the highest probability of providing an optimal solution?


texts: Introduction to Linear Optimization: Driving the artificial variables out of the basis (case: no entries in the $j$-row are nonzero)

texts:
Reading the book Introduction to Linear Optimization by Bertsimas and Tsiklisis, I've come across the following subject: Driving the artificial variables out of the basis.

The description is as follows: suppose an artificial variable $x_{B(j)}$ is in the basis, then examining the $j$-row of the simplex tableau there are two cases:

Either the $j$-row of $B^{-1}A$ contains a nonzero element (I understand this case !), otherwise all elements in the row are equal to $0$, which imply that the rows of $A$ are linearly independent and it is shown that the constraint $a_j x = b_j$ is redundant.

The book then suggest we delete the $j$-row of the simplex tableau and continue from there. Why is this possible ? By deleting the $j$-row of the tableau, we remove the $j$-basic variable from the basis. Also, deleting the $j$-row of the simplex tableau corresponds to deleting the $j$-row of $A$, form the basis of the basic variables, not including the $j$'th basic variable (now one dimension smaller), and then forming the simplex tableau corresponding to these ?

Now, how can we be sure the vectors corresponding to the basic variables excluding the $j$'th are linearly independent and form a basis ($j$-element is removed from these vectors) ? How do I know the simplex tableau with the $j$-row removed is actually a real simplex tableau and what vectors and basis matrix does it correspond to ?

Please give me advice and tell me whether I'm wrong and what to do, I've been really thinking over this, but haven't come to a conclusion.


texts: Power of nondeterministic type-1 min-heap automaton with both a heap and a stack

texts:
I have asked a series of questions concerning capabilities of a certain class of exotic automata which I have called min-heap automata; the original question, and links to others, can be found here.

Two of my last questions seem to have been quickly dispatched; one completely, and the other mostly (I have edited it to make it more viable). In either event, I actually had one other question I meant to ask, and would be interested to lay this subject to rest for good and all. So here it is:

  A two-stack PDA can simulate a Turing machine. A $k$-heap nondeterministic type-1 min-heap automaton cannot (it seems; see the linked question). What about a $k$-tape nondeterministic type-1 min-heap automaton augmented with a stack (similar to that of a PDA)? Can it simulate a Turing machine? If not, does an augmented $(k+1)$-heap nondeterministic type-1 min-heap automaton accept a class of languages which is a proper superset of languages accepted by augmented automata with only $k$ heaps?

Thanks, and I promise this is the last of these questions.


texts:
I am learning Automated Theorem Proving / SMT solvers / Proof Assistants by myself and post a series of questions about the process, starting here.

Which are the relevant automated theorem provers? I found A Review of Theorem Provers

Is this still current?

Which ones are still very active, i.e. which are currently used beyond the group that created it?

Find the series' next question here.


texts: Applied $\pi$-calculus: Name binding and if clauses

texts:
Assume in the applied pi-calculus we have the following process:
$$(\nu n)\overline{c} \langle n \rangle.0 | (\nu n) (c(y).(\text{if n=y then P else Q}))$$
where $P$ and $Q$ are further processes.
I know that the following reduction semantic holds for the applied $\pi$-calculus (from wikipedia):
$$\overline{x}\langle z \rangle.P | x(y).Q \rightarrow P | Q[z/y]$$
where $Q[z/y]$ denotes the process $Q$ in which the free name $z$ has been ''substituted'' for the free occurrences of $y$. If a free occurrence of $y$ occurs in a location where $z$ would not be free, alpha-conversion may be required.
Do I understand correctly, that in the above example, because $n$ is already used and thus not free, we would need to rename and thus the reduction would be like so:
$$(\nu n') (\nu n) (c(y).(\text{if n=n' then P else Q}))$$
While on the other hand, in the following process:
$$(\nu n)\overline{c} \langle n \rangle.0 | c(y).(\text{if n = y then P else Q}))$$
because $n$ is not bound, we can simply perform the transaction like so:
$$(\nu n) (\text{if n = n then P else Q})$$
(and thus those two processes are also semantically different)?


texts: Subgraph of paths of a graph has cycles?

texts:
Suppose that we have multiple minimum paths from $u$ to $v$ of a graph $G=(V,E)$. Now, we take this paths and create a subgraph $G'=(V',E')$ where for each $v \in V$ and $e \in E$ we have that $v \in V'$ and $e \in E'$ if and only if $v$ and $e$ exists in one of the minimum paths.

Now, my question is:

It is possible that $G'$ has cycles?
There is a way to prove this?

Edit 1: I forgot to put here that $G$ is an weighted directed graph. Yuval made clear that for undirected graphs we can have cycles, as we can just take an graph like $C_{4}$. But I am more interested in undirected graphs. We can consider that these minimum paths are the $k$ shortest paths in $G$, with $k>0$.

Edit 2: For each $e \in E$ we have a weight function $f(e) = w$, where $w$ is the weight of the edge. This weight is non-negative and can not be zero.


texts: Number of binary matrices with all 1's connected

texts:
What's the best/optimal known method/algorithm known that can be used
  to calculate the number of binary $M_{m,n}$ matrices for given $n,m$, whose $1$'s are all connected?

  Or equivalently, to calculate the number of connected induced subgraphs of a grid graph.

I'm aware of the computed values so far listed on $(n,m)$ OEIS table, and also that formulas are known for the $(1,n)$,$(2,n)$,$(3,n)$ cases, and supposedly an empirical generating function for $(4,n)$.

I assume those were derived from the computed data.

I'm interested to know what algorithm was used (or what's the best known option that could've been used) to compute the larger terms in the linked table, and how effective/complex it was?


texts:
Im pretty new here.

My question showing me an algorithm:

TRUE_SEQ(A[1...n])

for i <- 1 to n do
 A[i] <- FALSE
for i <- 1 to n do
 k <- i
 while(k <= n) do
  FLIP(A[k])
  k <- k + i

FLIP(x)

if x = TRUE then
 x <- FALSE
else
 x <- TRUE

Now i need to prove that after we finish TRUE_SEQ, the value of $A[i]$ is TRUE if and only if $i \in N$ is a power of a some natural number.

We learned about loop recorded sequence (Im not sure if i say it correctly in english)

Any way i would like a hint (and prefer a hint than a solution - as those are my homeworks)

Thank you for the help.


texts: Proving $L = \{0^i1^j0^i1^j\ |\ i+j > 0\}$ is not a context-free language

texts: I have the language $L = \{0^i1^j0^i1^j\ |\ i+j > 0\}$ I and want to prove that it is not context-free by using the Pumping lemma for context-free languages. I am new to this field and I am having some problems with the constant $n$ given by the Pumping Lemma. I do not know how to express $i$ and $j$ in terms of $n$. I have come up with a few example of expressing $i$ and $j$ as $n$ but some cases are always left out.


texts: Online algorithm for compressing multiple SETS?

texts:
Algorithms like LZW and others compress data sequences.
What I'm looking is an algorithm that compress multiple Sets. if possible online algorithm.
For example :
 1,2,3,4,5
 2,8,7,5,4
 3,1,8,9,7
 2,4,5,8,7

becomes :
 Rule1 : 2,4,5
 Rule2: 8,7
 Rule3 : 3,1
 Rule4 : R1,R2

 R1,R3
 R1,R2
 R2,R3,9
 R4

.. Rules are hierarchical .. which will be better compression...
this is one example of compression .. i'm looking for online algorithm.
The hard thing is to do compression on the fly ... and be optimal i.e. maximize compression.


texts: What is the point of the "respect" requirement in cut property of minimum spanning tree?

texts:
The cut property stated in terms of Theorem 23.1 in Section 23.1 of CLRS (2nd edition) is as follows.

  Theorem 23.1 Let $G = (V, E)$ be a connected, undirected graph with a real-valued weight function $w$ defined on $E$. Let $A$ be a subset of $E$ that is included in some minimum spanning tree for $G$, let $(S, V-S)$ be any cut of $G$ that respect $A$ (emphasis added), and let $(u,v)$ be a light edge crossing $(S,V-S)$. Then, edge $(u,v)$ is safe for $A$.

Why does this theorem require that the cut $(S,V-S)$ respect $A$? How is this requirement used in the correctness proof? I do not see what would fail if the requirement was removed.

Some Definitions:

Cut: A cut $(S, V-S)$ of an undirected graph $G=(V,E)$ is a partition of $V$.
Cross: An edge $(u,v) \in E$ crosses the cut $(S,V-S)$ if one of its endpoints is in $S$ and the other is in $V-S$.
Respect: A cut respects a set $A$ of edges if no edge in $A$ crosses the cut.
Light edge: An edge is a light edge crossing a cut if its weight is the minimum of any edge crossing the cut.


texts: Search for range in continuous function satisfying some condition

texts:
I am attempting to define an optimization for the following problem: given a graph find the largest interval(s) where S > S_th (the narrower the interval the smaller S will be) and P < P_th (the wider the interval the higher P will be).

I am not 100% certain the claims in parenthesis are always correct as, I think, it is affected by the distance between the Red and Green graphs.

The graphsR and G are KDEs generated with Gaussian functions, therefore continuous.
I already know that the conditions can be true only where the Red graph is above the Green one. I therefore find the intersections between the graphs (e.g. with brentq) and find relevant intervals by calculation a single point in them.
Below are a few examples of graphs I want to analyze. The blue vertical lines mark graph intersections; blue horizontal lines with the condition results on top are shown only when the conditions were met for the whole interval.
The vertical and horizontal lines in black are generated from a ML algorithm which I want to replace with a numerical calculation. As it can be seen it,  usually, finds intervals that are smaller then the whole area where red is on top.
Example 1: ML algo found better solution on the right section, neither found the left one interesting.

Example 2: on the right you can see the ML algo suggesting a range not quite between the blue lines. I am OK with the new algo clipping the portion on the left.

Example 3: showing that there may be more than one interesting range per marked section.

Example 4: ML algo missed the leftmost range


texts:
I understand the difference between DFA (has finite set of accept states, and doesn't have output function, nor output alphabet) and Moore Machine (doesn't have accept states, but has output for every state). But when implementing DFA in programming language, it always generates output. That is, if it last state was accept then it returns TRUE, to indicate that string was in the language. And if the last state was not accept then it returns FALSE. Thus DFA has output function $G\colon Q \to A$, where $Q$ are finite set of states, and $A = \{TRUE, FALSE\}$

So my question is: doesn't that make DFA a Moore Machine?


texts:
I am trying to solve the following:

Given a set $S_0$, find min $|S|$ where $S_0 \subseteq S$ subject to:

$\forall s \in S$ $\exists$ $s_a, s_b \in S $ $|$ $ ( s_a \neq s, s_b\neq s ) \land ( s = s_a + s_b \lor s = 1 \lor s=2 ) $

Or in english, forall s in S there exists sa, sb in S such that sa != s, sb != s AND ( s = sa + sb OR s = 1 OR s = 2 )

For example if $S_0 = \{ 7, 9, 13, 22 \}$
then the solution is $S = \{ 1, 2, 3, 4, 7, 9, 13, 22 \}$ as

1 -> is 1 so allowed
2 -> is 2 so allowed
3 = 1 + 2
4 = 1 + 3
7 = 3 + 4
9 = 7 + 2
13 = 9 + 4
22 = 9 + 13
|S| = 8

$|S_0|$ is not particularly large but the numbers in $S_0$ can be very very large such that expressing all numbers possible is infeasible.

I have tried an ILP and ran out of memory expressing the binary variables for each number in the set.

My current approach ( which gives a pretty bad solution ) is pick the lowest number that is violated, heuristically pick two numbers and put them in the set. Repeat until all numbers meet constraints.

An approximate solution is fine. Anyone have any ideas?


texts: NP-completeness for integer linear program

texts:
This is a homework problem, so I don't want the solution. I need a hint which problem to reduce to the following and/or how to start on it. We were thinking of TSP or independent set but couldn't come up with a solution.

We have $i\ldots j$ stores and $i\ldots n$ possible places to build a new warehouse. Costs to build a new warehouse are $c_j$. Between each store and warehouse is a path of cost $d_{i,j}$. Every store needs to be connected to at least one warehouse.

The decision problem is: is there a set of warehouses and paths so that the sum is smaller than a given number $k$.


texts: Finding minimal and complete test sets for circuits

texts:
I have been playing around with analysis of circuits and am trying to generate test vectors. In order to exercise the circuit in the manner I require, I need a vector that includes every change in the circuit's inputs where only 1 input toggles, but in order to be efficient, it must include each change only once and must not include any changes where more than one input toggles. Inputs can be only logic high (1) or low (0). If these sequences don't already have a name I would like to call them Majella tuples.

I believe the length of these Majella tuples to be    ((2^n) * n) + 1    where n is the width of the input in bits.

for example (with all 0 starting patterns):

n = 1:

0
1
0

n = 2:

00
10
11
01
11
10
00
01
00

n = 3:

000
100
110
010
110
111
011
001
101
001
011
111
101
111
110
100
101
100
000
010
011
010
000
001
000

I have written a bit of code to brute force generate these codes. However, it starts to struggle at n = 5 (actual code in a prev. revision of this question).

FUNCTION gen
  IF height of stack == ((2^bit_width) * bit_width)
    PRINT ZERO_PATTERN
    RETURN TRUE
  IF the change between the value at the top of stack and value does occur between other values on the stack
    RETURN FALSE

  PUSH value to stack
  WHILE shift < bit_width
    IF RECURSE with value as (value XOR (1 << shift)) returns TRUE
      PRINT value
      RETURN TRUE
    shift = shift + 1
  RETURN FALSE

SET stack to an empty list
SET bit_width to n

CALL gen with value as 0

some properties:

I would guess that there are solutions for all every possible n (positive integers). If there is a solution for n, there must be at least n! solutions as swapping the order of the inputs does not invalidate the solution. Reversing the order of a solution also does not invalidate it.

In each solution each input pattern should be present n times (except the starting pattern, that is present n + 1 times). The start and end patterns will always be the same.

Unfortunately this is where my knowledge runs out.

Is there a more efficient way of producing a valid solution given n as an input?

Can it be (easily) proven that there are solutions for all values of n?

edit:

I think it can be viewed as a graph:

   n = 2                   n = 3

                             000
    00                      / | \
   /  \                    /  |  \
  01  10                100  010  001
   \  /                  | \/   \/ |
    11                   | /\   /\ |
                        110  101  011
                           \  |  /
                            \ | /
                             111

The sequence is required to traverse each edge in both directions, but in neither direction more than once.


texts:
Show that $O(\text{max}\{f(n),g(n)\})=O(f(n)+g(n))$

Can I keep the same constant $c$ in each of the cases?

Consider two cases:
$$1)f(n)>g(n);O(\text{max}\{f(n),g(n)\})⇒O(f(n))\Rightarrow d(n) ≤c⋅f(n);c>0$$
$$2)f(n)≤g(n);O(\text{max}\{f(n),g(n)\})⇒O(g(n))\Rightarrow e(n)≤c⋅g(n);c>0$$
Combining the 2 cases yields:
$$d(n)+e(n)≤c⋅f(n)+c⋅g(n)$$
$$d(n)+e(n)≤c⋅(f(n)+g(n))$$
Which is definition of $O(f(n)+g(n))$


texts: 3-Col using each colour exactly $|V|/3$ times

texts:
Is the following problem in P?

Does a graph $G$ have $3$-colouring, where each colour is used exactly $|V|/3$ times?

I believe it is as we are trying to sample three sets (one for each colour) of vertices without replacement, giving a running time of $O(|V|^5)$. The first set is for three colours, the second for two and third for one col.


texts: proving existence of TM that accepts the next language

texts:
I have an idea of how to approach the problem, but I'm not sure about it.
Given a Turing Machine, I can check how many states the machine has, and somehow by the number of states to know if the run uses endless cells of the tape.
However, I am not sure how I can use the number of states and what I should check.
What confuses me is that entering an endless loop does not necessarily require the use of endless cells of the film.
$L_k=\{<M>| \,M\,\,\,is\,\,a\,\,TM\,\,that\,\,uses\,\,at\,\,most\,\,k\,\,tape\,\,cells\,\,\,when\,\,\,running\,\,\,on\,\,\,\epsilon\}$
prove that:
$L^*=\bigcup\limits_{k\,\in\,\mathbb{N}} L_k\,\in\,\,\,RE\setminus R$


texts: Master theorem: When a $f(n)$ is smaller or larger than $n^{\log_b a}$by less than a polynomial factor

texts:
I was trying to solve the following question while reviewing master theorem.

Which of the following asymptotically grows faster.

(a) $ T(n) = 4T(n/2) + 10n $

(b) $ T(n) = 8T(n/3) + 24n^2 $

(c) $ T(n) = 16T(n/4) + 10n^2 $

(d) $ T(n) = 25T(n/5) + 20(n\log n)^{1.99} $

(e) They are all asymptotically the same

My calculation says, (a) is $\theta(n^2)$ (b) is $\theta(n^2)$ (c) is $\theta(n^2\log n)$. Now how can I evaluate (d)?

If $f(n)$ is smaller or larger than $n^{\log_b a}$by less than a polynomial factor, how can I solve $T(n)$?


texts: Best complexity to find solutions to $x^2+y^2=z^2$

texts:
What is the algorithm with the best complexity that finds solutions in a given range to the equation $x^2+y^2=z^2$ ?

The best i could do is to iterate through all $x$ and all $y$ and store $x^2+y^2$ in a hash and then iterate through all possible $z$ and check if $z^2$ is in the hash.


texts: Complexity class of Towers of Hanoi problem

texts:
Given a problem

  List all steps to move n disks from rode 1 to rode 2.

I guess you are familiar with Towers of Hanoi rules.
I couldn't find a proper answer for the complexity class of this problem. My first guess would be NP or even NP-hard yet the output is exponential and no matter how hard we try there's no chance to check the answer in polynomial time even on non-deterministic Turing machine. So what's the complexity class?


texts:
I was not able to find or come up with two formulae which are equivalent but have different CNF. All my ideas reduce to the same formula after applying transformations. The requirements are the following:

Give an example which shows that proving equivalence of two formulas by bringing them into conjunctive normal form is incomplete. By incompleteness, we mean that there are examples of formulas which are equivalent but their conjunctive normal form is not the same.


texts: Without using the Space Hierarchy Theorm is there any other way to prove that NL is not equal to PSPACE

texts:
From what I know there is no alternate way  that NL is not equal to PSPACE. If possible can you link a paper or some book recommendations to show that this is the case.
Thank You
Akash


texts: Sum of 2^Pi mod 1000000007 for all i where Pi is sum of numbers in ith subset of a set X

texts:
I am stuck on a problem in which I have to print sum of 2Pi mod 1000000007 for all i where Pi  is sum of numbers in ith subset of a set X.

Length of set can be upto 100000.

Value of element in the range [0,1012].

Here's the link of the Problem.
Problem Statement

I could not find any approach other than Brute-Force which gives verdict TLE.

@Moderators,admins etc.
Before putting this question on hold or marking off-Topic or closed....
Please comment the reason so that I can know the reason and if possible reword it or ask on any other StackExchange Site.
I first posted it on codegolf.stackexchange.com and people(moderators) there have suggested me to post it here as it comes under algorithm category.

You can read about it here.

Programming Puzzles and Code golf

Thank You


texts:
I'm learning about asymptotics and time complexity.
The algorithm I'm analyzing has a for loop that starts at $i = 1$ and ends at $\left \lfloor \sqrt n \right \rfloor$. The body is said to run in $n-i$ steps. I'm trying to do a summation from $i=1$ to $\left \lfloor \sqrt n \right \rfloor$ to come up with a Big Theta, but I am not sure how to deal with the upper bound of the summation. Thank you in advance.


texts: Efficiently selecting the median and elements to its left and right

texts:
Suppose we have a set $S = \{ a_1,a_2,a_3,\ldots , a_N \}$ of $N$ coders.

Each Coders has rating $R_i$ and the number of gold medals $E_i$, they had won so far.

A Software Company wants to hire exactly three  coders to develop an application.

For hiring three coders, they developed the following strategy:

They first arrange the coders in ascending order of ratings and descending order of gold medals.
From this arranged list, they select the three of the middle coders.
E.g., if the arranged list is $(a_5,a_2,a_3,a_1,a_4)$ they select $(a_2,a_3,a_1)$ coders.

Now we have to help company by writing a program  for this task.

Input:

The first line contains $N$, i.e. the number of coders.

Then the second line contains the ratings $R_i$ of $i$th coder.

The third line contains the number of gold medals bagged by the $i$th coder.

Output:

Display only one line that contains the sum of gold medals earned by the three coders the company will select.


texts: Why is $\Omega(\log\log n)$ a lower bound for the depth of polynomial-width circuits computing parity?

texts:
I'm working on an exercise from The Nature of Computation concerning polynomial-width circuits computing parity. In particular the exercise asks to sketch a proof that the depth of such a circuit has the lower bound $\Omega(\log\log n)$ where $n$ is the number of input variables.

There is quite a large amount of literature on the subject flying around the web and I have seen claims for lower bounds of $\Omega(\log^* n)$ as well as $Ω(\log n/\log\log n)$. However the proofs of these statements completely defeat me.

Does anybody see a simpler way to arrive at the desired result?


texts: How is a grammatical rule applied if the variable is not part of the source word

texts:
I'm currently working with this grammar:

$S \to aSBC$
$S \to aBC$
$CB \to BC$
$aB \to ab$
$bB \to bb$
$bC \to bc$
$cC \to cc$

It is supposed to define the language $$ L = \{a^nb^nc^n : n \geq 1\}. $$

I need to know how to get through the grammar rules to end up with $L$. So I started with the first two rules which end up to be $a^n(BC)^n$.

$$ S \Rightarrow^* a^{n-1}S(BC)^{n-1} \Rightarrow a^{n-1} aBC (BC)^{n-1} = a^n (BC)^n.$$

It's quite obvious until there. My lecture than adds the third rule to $a^n(BC)^n$:

$$ a^n(BC)^n \Rightarrow^* a^nB^nC^n. $$

And that's where I'm completely lost. How is the third rule applied if its left-hand side ($CB$) isn't even part of the initial word ($a^n(BC)^n$)?


texts: Name for tree where each node has the aggregate of its children

texts:
Is there a general name for a tree in which the leaves have some arbitrary values and the value of every other node is some "aggregate" function of its children?

An example where the aggregate function is the sum:

  14
 /  \
4   10
   / | \
  7  1  2

The function could also be the min, max, or any other function of the form $f:S^n\to S$.


texts: What is the relationship between minimum sized vertex covers and complete graphs?

texts: What is the relationship between the sizes of minimum sized vertex covers and complete graphs?


texts: Why do these functions satisfy that f(n) is not O(g(n)) and g(n) is not O(f(n))?

texts:
I don't understand what these function are like and why they satisfy that f(n) is not O(g(n)) and g(n) is not O(f(n)).
Where is x?
\begin{eqnarray}
f(x)=
\begin{cases}
    k^{2k}, &x\in(2,2+1)& \\
    k^{2k+1}, &x\in(2+1,2+2)&
\end{cases}
\end{eqnarray}
\begin{eqnarray}
g(x)=
\begin{cases}
    k^{2k-2}, &x\in(2,2+1)& \\
    k^{2k+2}, &x\in(2+1,2+2)&
\end{cases}
\end{eqnarray}
Also, could you teach me how to write these functions in Grapher on MacOS? Cuz I want to know what they are like.


texts: Complexity of checking whether linear equations have a positive solution

texts:
Consider a system of linear equations $Ax=0$, where $A$ is a $n\times n$ matrix with rational entries. Assume that the rank of $A$ is $<n$. What is the complexiy to check
whether it has a solution $x$ such that all entries of $x$ are stricly greater than 0 (namely, $x$ is a positive vector)? Of course, one can use Gauss elimination, but this seems not to be optimal.


texts:
Given this language:
$$L_{s_1,s_2} = \{ \langle M_1 \rangle \langle M_2 \rangle | L(M_1) \in S_1 \text{ and } L(M_2) \in S_2 \}$$
I want to prove that for $S_1=RE$ and  $S_2=RE$, then $L_{S_1,S_2} \in R$.

The way I started was by trying to build a Turing Machine that decides $L_{S_1,S_2}$:

Let $M_{12}$ be that Turing machine.

For each input word $w$:
If $w$ cannot be decoded as $\langle M_1 \rangle \langle M_2 \rangle$ then halt and reject.
Run $w$ on both $M_1$ and $M_2$.
If one of the two machines above halted, then $M_{12}$ halts and accepts $w$.

And here I got stuck:

What if the two machines didn't stop over $w$? how should I halt and reject $w$ in $M_{12}$?


texts: Is $T=\{\langle M\rangle \mid |L(M)| =1 \text{ or } |L(M)| >2\}$ recognizable?

texts:
$$T=\{\langle M\rangle \mid |L(M)| =1 \text{ or } |L(M)| >2\}$$

I started with Rice's theorem (come up with an example where $|L(M)| = 2$) to see that $T$ was undecidable. Then I figured out $\bar{T}$ was unrecognizable, because $H =\{\langle M \rangle \mid M\text{ halts on the empty string} \}$ has a mapping-reduction to $T$, and $H$ is not co-recognizable, so $T$ is not co-recognizable.

Now I'm stuck. I tried mapping-reductions from $H$, $E = \{\langle M \rangle \mid M \text{ doesn't accept anything} \}$ and $F = \{ \langle M \rangle \mid L(M) \text{ is finite} \}$.

What's a good set to try and reduce from (or reduce to)? Am I right that $T$ is unrecognizable?


texts: Number of Combinations of Connected Bipartite Graphs

texts:
Given two sets of vertices $U$ (size $n$) and $V$ (size $m$), how many possibilities of set of edges $E$ exist that make the bipartite graph $G = (U, V, E)$ connected?

Obviously there are $2^{n m}$ different set of edges but many will be disconnected.


texts: Algorithm to establish a global ranking given individual rankings

texts:
I am looking for an algorithm(s) that can compute a global ranking (partial ordering) given individual rankings, in some kind of principled manner.

I want to establish a partial-ordering of some projects, and had some users create their own partial orderings.

I've looked at these algorithms so far:

borda-0
borda-1
Dowdall

My problem is that these algorithms were not really designed to establish partial-ordering and are instead for choosing N winners. I haven't been able to find any widely-used algorithms for this purpose.

I looked at adapting STV to this purpose, but raw STV gives no instructions on how to resolve ties, and it's unclear to me what properties it would have when applied to partial ordering.

Is there a widely-used algorithm/family of algorithms for the problem?


texts:
For example, we have $T(N) = T(N/2) + T(N/5) + O(N)$.
So:

$2T(N/2) + O(N) \leq T(N) \leq 2T(N/5) + O(N)$

$O(N) \leq T(N) \leq O(N)$. Thus, $T(N) = O(N)$. Is it correct?


texts:
Problem:

I am trying to solve the $N$-Queens problem using Constraint Satisfaction and Heuristic Repair (also known as Min-Conflicts). I wrote a program to do this for any given $N$ queens and $N * N$ board.

I observed that a solution should be found in $N$ passes or less (since we need to find $N$ non-conflicting locations, for which we might need to rearrange all queens at most $N$ times in one pass).

I noticed that, given a random start, some starting states would not be able to resolve to a solution. This was due to circular behaviour where two or three queens would alternate positions, always moving to positions where:

$$conflict(new-pos) \le conflict(old-pos)$$

but never decreasing global conflicts.

The presence of these states seems to increase as $N$ increases. So 64-queens seems more likely to have "cycles" than 4-queens (which never seems to have cycles).

I would like to know how I can reason about these difficult states, and what extension of the algorithm could be made such that the algorithm will always obtain a solution, provided one exists?

What I have tried so far:

I have tried to randomise the board state after $N$ unsuccessful passes. This probably guarantees an eventual solution, but does not solve the fact that the likelihood of these states seems to increase exponentially, and so a solution becomes intractable quickly.

For those interested you can find my program here. It is not fantastically documented, but it is not terribly long, and I believe most of the names are self-documenting.


texts: Are QR codes Turing-complete under the rules of Conway's Game of Life?

texts:
This is a bit of a weird question, but I was wondering earlier if QR codes are Turing-complete when interpreted as initial states for Conway's Game of Life.

My intuition is "yes", as there are infinitely many QR codes (they just get bigger as you add more information), and the Game of Life itself is Turing-complete. However, it's not inconceivable that the restrictions imposed by the QR code format mean that no QR codes are Turing-complete.

Another way to phrase the question would be "can all Turing machines be encoded as a string which, when converted into a QR code and used as the initial state for Conway's Game of Life, produces equivalent output to the original Turing machine"


texts: I just finished watching these 3 Coursera videos on back propagation in neural networks. I get the idea of what we're trying to do, but I don't get how we achieve that by calculating error in each step as weight * cascaded error (eg. the formula at the top right of screen at 12:07 in the linked video). Let's say we start off with all the weights (theta) at zero. Wouldn't back propagation always calculate 0 error for everything, causing nothing to change?


texts: Finite number of Turing machines running concurrently on multi-tapes Turing-machine-equivalent?

texts: So basically, there are several (finite number of) Turing machines being able to read off and write to the same set of tapes (the number of tapes is finite, but each tape may have infinite tape spaces). And then we consider a group/machine of these machines to solve a problem. Would this machine be Turing machine-equivalent?


texts: How would I convert separate digits to an actual number?

texts:
In Dr. Racket, how would I combine the digits w, x, y, z to wxyz (for example 3, 7, 8, 9 to 3,789)?
I haven't gotten very far on this:
(define digits-to-numbers w x y z)


texts: does a non-terminated string count as a token in c?

texts:
so, I am preparing for an exam which includes lexical analysis from compiler design. I was wondering what is the number of tokens in the following code-

int main() {
  /* comment
  printf("Hello */ There ");*/
  return 0;
}

so, I am thinking upto first "*/" it will be a multiline comment, so, after "there" a string will start without terminating. will the last string is counted as a token?