texts: Can you convert a positively weighted DAG into a non-weighted DAG in polynomial time?

texts:
Given a positively weighted DAG (directed acyclic graph) $D = (V,E)$, can you create a new non-weighted DAG $D'$ by converting each edge with weight $w(e) = x$ into x non-weighted edges and vertices? I believe this would take $O(|E|+W)$ time where $|E|$ is the number of edges and $W$ is the total weight of all edges. My concern is whether I can include this weight variable and still consider this algorithm to be in polynomial time.

(NOTE: This algorithm may apply to all positively weighted graphs, not just DAGs.)


texts:
I took my theory of computation exams a few weeks ago, and this was one of the questions:

Assume language $L=\{(a^nb^m)^r \mid n,m,r\ge 0\}$
Is L regular? If yes provide a regular expression or an automaton for it.

After I briefly asked him the answer after the exam, it appears it really is regular (I believe he said the expression is the simple $(a^*b^*)^*$). However I cannot seem to understand why that is. The way I see it, its concatenating $a^nb^m$ r times, like this:

$a^nb^ma^nb^ma^nb^m...a^nb^ma^nb^m$,

which isn't regular since there is no way for an automaton to recall n and m every time. Where am I at fault here?
EDIT: I talked to the professor again, he admitted it was a mistake. The language is indeed not regular.


texts: How can I prove that a build max heap's amortized cost is $O(n)$?

texts: Suppose a build max-heap operation runs bubble down over a heap. How does its amortized cost equal $O(n)$?


texts:
Assume that the model of computation is a standard Turing machine model with input alphabet $\Sigma = \{0,1\}$, work alphabet $\Gamma = \{0,1,\_\}$, 1 input tape, 1 work tape and 1 output tape.

We can build a Turing machine $U$ that accepts a (reasonable) binary representation of a Turing machine $M$ and simulates it (possibly doing additional computation before and/or after the simulation).

Such concept of simulation is used massively and in different contexts (e.g. in the proof of the time hierarchy theorem).

  I'm wondering if there is a formal definition of "simulation" (or  different definitions) and when such definition(s) appeared for the first time.

Something like "Given a description $p$ of $M$, $U$ on input $p$ simulates $M$ if during the computation there is a one-to-one mapping between the internal state of $U$ and the internal state of the simulated $M$, and between the content of the work tape of $U$ and the simulated work tape of $M$"

Note 1: as commented by Zonko we could use this definition: "Given a description $p$ of $M$, $U$ simulates $M$ if $U(p,x)=M(x)$, $\forall x$ accepted by $M$"; but if $U(p,x)=M(x)+1$ then probably $U$ needs to "simulate" $M$ as well.


texts: Gale Shapley - Everyone ends up with second choice of partner

texts:
So I was asked to prove (or not) whether, in gale shapley algorithm, everyone can end up married to their second partner of choice or not. I think not but then I am not able to come up with a proof.

Thanks! :)


texts: Check whether a directed, rooted spanning tree is actually some shortest-paths tree in $O(V + E)$ time

texts:
Given a directed graph $G = (V, E)$, with all edge weights being non-negative, someone has written a program that he/she claims implements Dijkstra's algorithm.
For a fixed starting vertex $s$, the program produces $v.d$ (shortest distance from $s$) and $v.\pi$ (immediate predecessor in the shortest path) for each vertex $v \in V$.

  Question: How to check whether the $d$ and $\pi$ values match those of some shortest-paths tree of $G$ in linear time (i.e., $O(V + E)$)?

My attempts:

Feed the $d$ and $\pi$ values into a running instance of our real Dijkstra algorithm and check if some step would go wrong.
The key point here is how to reduce the running time of the real Dijkstra algorithm from $O(E \log V)$ to $O(V + E)$, taking advantage of the existing $v.d$ and $v.\pi$ values.
To check the triangle inequality condition: For all edges $(u,v) \in E$, we have $d(s,v) \le d(s,u) + w(u,v)$.

  Question: However, is the triangle inequality condition a sufficient one for some directed, rooted spanning tree to be a shortest-paths tree?


texts:
I want to ask about petri net(PN) boundedness. When I have a state s1 = (2 0 0) then i  find state s2 = (2 0 1) so since s1 < s2 can I declare PN as NOT bounded ? Because when  I have this PN:

PN is bounded but u can find there (2 0 0) < (2 0 1).
So my question is. Am I wrong about boundedness of petri net or is something wrong with PT on the picture ?


texts: Decidability of factoring algebraic equations

texts:
Given an arbitrary algebraic equation, say for example the likelihood of the bernoulli distribution:

$$\prod_{i}^{n}\theta^{x_i}(1-\theta)^{1-x_i}$$

And some arbitrary factorization constraints, say:

$$f(x)g(\theta)e^{\phi(\theta)^{T}u(x)}$$

Can I factor the equation into the form above where f, g, and phi are functions depending only on x, theta, or x respectively? This is something as humans we do all the time. The problem I gave above is an instance of "is this distribution in the exponential family", but of course there are simpler and less puffy versions of this:

Given the equation:

$$f(x,y,z) = x^2 + y^3 - e^{z}$$

Can I factor this into:

$$ f(x)*g(y)*h(y,z)$$

This feels undecidable to me. The tree of legal "algebra moves" from the root is infinite. If a program cannot find a solution in n moves, there is no guarantee that the solution is not at n + 1 moves, so I can't think of a halting condition. There doesn't even seem to be a good greedy solution to this, other than human intuition.

Any mathematica wizards out there know how to write a one liner to this?


texts:
Given a flow-network $N=(G,c,s,t)$ and an edge $e=(u,v)$, I am trying to build an algorithm that finds a minimum $(S,T)$ cut in the given network, that includes e.

So, I tried couple of steps, first, I know I must saturate $e$ so it could be in any min-cut. I tried to add a supersource that connects to $u$ (with infinite capacity) and a supersink that connects to $v$. But that will only saturate $e$ if it is not yet been saturated, not force it to be in a min cut $s,t$.
I also thought maybe to reduce an epsilon from the capacity of $e$, but I am not sure if it is enough.

I also tried to connect the supersource to all of u neighbors and the supersink to all of v neighbors and then reduce an epsilon from e. Again I don’t know if that’s enough.

I’m not sure how to continue (or if i can) from here or if I’m missing something.


texts: Find a polynomial in two or three queries

texts:
Black box of $f(x)$ means I can evaluate the polynomial $f(x)$ at any point.

Input: A black box of monic polynomial $f(x) \in\mathbb{Z}^+[x]$ of degree $d$.
Output: The $d$ coefficients of polynomial $f(x)$.

My algorithm: let

$$f(x) = x^{d} + a_{d-1} x^{d-1} + \cdots + a_1 x + a_0$$

Evaluate polynomial $\mathcal{f(x)}$ at $d$ many points using the black box and get a system of linear equations. Now I can solve the system of linear equations to get the desired coefficients.

However, in this case, I need $\mathcal{O(d)}$ many queries to the black box. I want to minimize the number of queries. Is there any way to reduce the number of queries to just two or three?


texts: Enumerating programs as graphs, or executing graphs?

texts:
Both programs and simple graphs can be enumerated using natural numbers (positive integers).

However, what languages or ideas most naturally combine the two?

For example enumerating programs using graphs instead of natural numbers.

Or executing graphs, in other words code described by a graphs shape instead of by text, and not just for tree shaped graphs.


texts: How does progress fail in system $F_{\omega}$ when types $T_1 \to T_2$ and $T_2 \to T_1$ are equivalent?

texts:
Pierce's TAPL book gives in exercise 30.3.17 the setting where $T_1 \to T_2 \equiv T_2 \to T_1$ (the function type are assumed to be equivalent). In the solutions, he claims that this assumption breaks the progress property.

It is easy to see that preservation fails. How can progress:

$\vdash t:T \implies t  \text{ is  a value } \lor \exists t'. t \to t'$

be wrong in this setting?


texts: A schedule is not conflict-serializable. Is it serializable?

texts:
While reading this solved quiz on concurrency control, I got stuck on exercise 2, which reads as follows:

  2) Consider the following schedule:

  S: r1(X), w2(X), r3(X), r1(Y), w2(Z), r3(Y), w3(Z), w1(Y)

  (a) (2 points) Draw the precedence graph.

  (b) (1 point) Is S conflict serializable?

  No.

After reading that S is not conflict-serializable, my question is: can we say that S is serializable? Any suggestions?

Thanks to anyone who help me.


texts: Understanding $DSPACE(s(n)) \subseteq DTIME(2^{O(s(n))})$

texts:
I'm having trouble understanding this statement: $DSPACE(s(n)) \subseteq  DTIME(2^{O(s(n))})$.

The logic is that $2^{O(s(n))}$ is the total number of different configurations a Turing Machine M that runs in $s(n)$ space can have as a combination of the number of states, head positions, and contents of the tape, but I do not see how this number is arrived at.

Can someone explain?


texts: Implementing Gauss–Legendre algorithm using arbitrary-length rationals

texts:
I am trying to re-implement SuperPI myself in Rust, but the results I get are not very accurate.  SuperPI computes pi using the Gauss-Legendre algorithm.

The Gauss–Legendre algorithm is quite simple, but the problem is how to store values with full precision. I store all numbers as arbitrary sized rationals, but I am still getting weird results.

Pseudocode:

a0 = 1/1;
b0 = 470832/665857; // an approximation to 1/√2
t0 = 1/4;
p0 = 1;

for i in 0..n {
    a_i+1 = (a + b)/2;
    squared_b_i+1 = a * b;
    b_i+1 = sqrt(squared_b_i+1); // calculated as sqrt(numerator)/sqrt(denominator)
    t_i+1 = t - p * (a_i - a_i+1)^2;
    p_i+1 = 2 * p;
}

let result = (a_n+b_n)^2 / (4t_n);

(actual code may be found here)

My implementation has at least two problems:

It doesn't matter how good 1/√2 approximation I take (470832/665857 in this example), the algorithm doesn't converge to the correct value.
Calculating √(a/b) as √a/√b is not very accurate, because it does  ⌊√a⌋/⌊√b⌋ which can introduce a large error.

As a result, my implementation calculates 11 true digits per 20 iterations, while SuperPI does 1M digits.

How do I implement the Gauss–Legendre algorithm efficiently, given the above challenges?


texts: PERT Chart exercise - is there enough information to solve?

texts:
I'm posting this here as my question is from a computer science textbook. It is not a homework question as I am self-studying and I have the answers available.

In the exercise below, I can't see how I'm supposed to know which activity to place on which arrow. I can't tell if there is insufficient information provided or if it is a lack of understanding on my part which makes it impossible to decide which arrow out of node 2 should have be labelled B and which with C for example.

If it is solvable given the information provided, could someone please exaplain the method?


texts: What is the most compact (space efficient) method of storing an array of distinct integers?

texts:
I have an array of distinct integers which I want to save in the most compact manner. I may have to do occasional lookups, deletions, and insertions in this array so the compression algorithm must adjust for such cases.
What is the appropriate algorithm/ data structure that I should think of?

Is there anything along the lines of Huffman encoding but for numbers?


texts: Undirected graph find minimal wight sum so every cycle has at least one weighted edge included

texts:
I am given weighted undirected and non-planar graph G=(V,E). I don't understand much about complex graph and how to work with them. So any tips will help.

For example like this

I don't know how to explain it but i will try.
Result should me like this: In every simple cycle (for example A-B-C-A) there should be at least one weighted edge, but weight sum for all cycles should be minimum. (One edge can belong to more than one cycle and one cycle can have more than one weighted edge). And it should be done in polynomial time.

Result for previous given graph will look like this

 Sum will be 6.

Thank for any tip!


texts: Computing Follow sets of Grammar for LL(1) parser

texts:
I am trying to compute the Follow set of the following Grammar:

E -> E' E A
A -> + | *
E -> num
E' -> num

I start by adding the end of string symbol, via. some non-terminal S such that:

S -> E$
E -> E' E A
A -> + | *
E -> num
E' -> num

Becomes the Grammar. With this I get the following set constraints for the productions:

Production             Set Constraint
S -> E$                {$} <= Follow(E)
E -> E' E A            First(A) <= Follow(E)
A -> + | *             {+,*} <= Follow(A)
E -> num               {num} <= Follow(E)
E' -> num              {num} <= Follow(E')

With the above constraints, I can solve these with the following result:

set           initial      Iteration 1          ...
Follow(E)     {$, num}     {$, num, +, *}       ...
Follow(A)     {+,*}        {+,*}                ...
Folloe(E')    {num}        {num}                ...

With further iterations no changes are made to the Follow sets and thus the final result I get is:

Follow(E)  = {$, num, +, *}
Follow(A)  = {+,*}
Follow(E') = num

However, can anyone verify if what I have done above is correct? I just recently learned how to compute these sets - and I am exercising with LL(1) parser construction.


texts: solving large nonlinear systems in parallel

texts:
I am solving a large (~1e5 equations & unknowns) set of nonlinear equations using Newton-Raphson iterations.  Currently I am using the GPU accelerated Krylov methods implemented in ViennaCL to solve the linear system to get the update increment.  I am  solving the system on a single 24 core, 64GB  workstation with a NVIDIA Quadro K4000 GPU. However as the number of unknowns exceeds 1e5 and/or the Jacobian matrix gets more dense, there is not enough memory on the GPU to fit the compressed Jacobian matrix on the device.  Using the CPU cores allows the Jacobian matrix to fit into memory, however the compute time is very long.

I would like to use a cluster of the above mentioned workstations to solve either the nonlinear system or the linear update increment system, however I am not sure how to go about decomposing the system of equations into pieces that can be tackled via a distributed memory approach.  The equations include radiative transfer, and therefore it is not easy to decompose the domain geometrically as the Jacobian matrix is dense.

Does anyone know about distributed memory approaches to solving large dense linear equation systems?

All help is greatly appreciated!

PS I have looked into the parallelised nonlinear solvers implemented in PETSc, however this is a clunky c library and one must write there entire problem in terms of the PETSc interface which I would like to avoid if possible.  I would be more interested in understanding the details as to how a distributed memory parallelised nonlinear or linear solver works...


texts: Why is a heap better than a linked list for implementation of a priority queue?

texts:
Using a heap, you have O(log(n)) insertion and O(log(n)) removal. Using a linked list, you have O(n) insertion and O(1) removal.

Why is it better to have log-n for both than n for one and constant time for the other?


texts: Algorithm: Finding median in a sorted array with duplicates

texts:
If array is sorted we can generally find median in O(1) by returning the element at the middle.
But what if there are duplicates?

E.g [2, 2, 3, 3, 3, 3]


texts: Minimum and maximum of sum of inverse degree of a graph

texts:
Suppose we have a simple undirected graph $G(V,E)$, where $V$ and $E$ are the set of vertices and edges respectively. we denote $d(v)$ as the degree of a vertex $v \in V$. I am interested to find closed form or a tight bound  of the following quantity

$$
D = \sum_{e=\{u,v\} \in E} \frac{1}{d(u)+d(v)}
$$

For example, suppose we have a complete graph with $n$ vertices. Then $D$ becomes $$ D = \frac{n(n-1)/2}{2(n-1)} = n/4$$.

For a path graph with $n$ vertices ($(n-1)$ edges) $D$ is $ \frac{(n-3)}{4}+2/3 $. My question is

Is there any closed form of $D$ for general graph that involves $|V|$?
If not is there any tight lower bound on the sum?
Can we claim something like that the $D \geq |V|/k$ where k is a constant and $k<<|V|$?

*Yuval conjectured that $D \geq 1−1/n$ for a connect graph with $n$ vertices.


texts: Why weak scaling is easier to achieve than strong scaling?

texts:
When we parallelize tasks and measure the perforamnce,two common measures of parallel scaling are

Strong Scaling: Time for fixed problem size as number of processor is increased

Weak Scaling: Time for fixed computational work per processor as problem size is increased

Some documents mention that the weak scaling is easier to achieve (most of the cases) than the strong scaling.

Is this correct? if then, why?


texts:
Floyd–Warshall calculates minimum distance between any two vertices in the graph.

for(int k=0;k<n;k++){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
        }
    }
}

So, it basically calculates distance between every two nodes i,j having 1 intermediate node in the shortest path, then having 2 intermediate nodes in the shortest path and so on until there are N intermediate nodes in the shortest path.

So, basically this algorithm uses the previous computed distances to compute the new shortest distances.

But, for a graph like 0->2->3->1. It wouldn't be able to compute the shortest between 0 and 1 because in starting it doesn't know the shortest distances from 0 to 3 or 2 to 1 in the distance matrix.

In dynamic algorithms, we start from shorter problems and then use them to compute solution to larger problems. But, here we don't know which one are our shorter problems.

So, how are we able to use this algorithm here?


texts: Probabilistic algorithm with two-sided error

texts:
I am currently studying probabilistic algorithms and came across three major complexity classes:

BPP: worst-case polynomial time, two-sided error
RP: worst-case polynomial time, one-sided error
ZPP: average-case polynomial time, no error

At first I couldn't understand why one would use an algorithm that could err. I figured it does make sense in some cases though, like primality testing for RSA encryption. The algorithm used there has a one-sided error only, though.

Even after hours of thinking about it, I failed to think of an algorithm with two-sided error that actually makes sense and could be / is used in practice.

Any pointers would be greatly appreciated.


texts: A polynomial reduction from HAMPATH to LONG-PATH

texts:
$\text{HAMPATH} = \{(G=(V,E),s',t')| \text{ G has a Hamilton path from s' to t' } \}$

$\text{LONG-PATH} = \{(G,s,t,k) |  \text{G has a simple path p from s to t, length(p) $\geq$ k}  \}$

I'm trying to prove a polynomial reduction, $\text{HAMPATH} \leq_p \text{LONG-PATH}$.

My thought was to take an instance of $\text{HAMPATH}$ and add exactly $k-|V|$ nodes and edges from $t'$ to $s'$, so i have an Hamilton path from $s=s'$ to $t'$, and a simple path(which is also an Hamilton path) from $t'$ to $t$.

I tried to prove that but i couldn't finish the proof and it seems that this is not good reduction.

any thoughts?


texts: Quicksort with Hoare's Partition Algorithm

texts:
I've came across Hoare's partition algorithm in Cormen. After analysis I think that the algorithm isn't working as I expected. Let's suppose that we've array [4,3,2,1], then  in my opinion partition is returning 0, so next quicksort calls will be QS(A,1,0), QS(A,1,4), the second one is the same as first call so this array won't be sorted ever (infinite recursion).

Partition(A,p,r)
x = A[p]
i = p-1
j = r+1
while True do
   repeat j-=1
      until x>=A[j]
   repeat i+=1
      until x<=A[i]
   if i<j then
      swap(A[i], A[j])
   else
      return j

QS(A,p,r)
q = Partition(A,p,r)
QS(A,p,q)
QS(A,q+1,r)


texts: Is the term $(\lambda x.x)(y y)$ a normal form in call-by-value reduction strategy?

texts:
I am learning λ-calculus and I have some confusion about it.
Is the term $(\lambda x.x)(y y)$ a normal form in call by value reduction strategy? (where $y$ is a free variable)
From the wikipedia, it says:

Call by value
Only the outermost redexes are reduced: a redex is reduced only when its right hand side has reduced to a value (variable or abstraction).

Here the term $(\lambda x.x)(y y)$ is a beta redex, but the argument  $(y y)$ is not a value.
So the term $(\lambda x.x)(y y)$ is a normal form, because there is no further beta reduction possible.
Is my understanding correct?
Very thanks.

Sorry for updated the question, because I just realized that there may be 2 questions behind:

In λ-calculus, does the terminology "normal form" depend on the evaluation strategy? i.e. When we say a term is a normal form or not, is there any evaluation strategy behind it? For example, CBV ⊢ (λx.x)(yy) be a normal form and CBN ⊢ (λx.x)(yy) be not a normal form?

When we say "a λ-calculus with call-by-value", is it equivalent to say "λ_v-calculus"? I am reading Sabry and Felleisen's paper "Reasoning about Programs in Continuation-Passing Style". That paper mentioned λ_v-calculus and in p.8 it says (λx.x)(yy) has no βv-redex.


texts: Probabilistic test of matrix multiplication with one-sided error

texts:
Given three matrices $A, B,C \in \mathbb{Z}^{n \times n}$ we want to test whether $AB  \neq C$. Assume that the arithmetic operations $+$ and $-$ take constant time when applied to numbers from $\mathbb{Z}$.

How can I state an algorithm with one-sided error that runs in $O(n^2)$ time and prove its correctness?

I tried it now for several hours but I can't get it right. I think I have to use the fact that for any $x \in \mathbb{Z}^n$ at most half of the vectors $s \in S = \left\{1, 0\right\}^n$  satisfy $x \cdot s = 0$, where $x \cdot s$ denotes the scalar product$\sum_{i=1}^{n} x_is_i$.


texts: What is the complexity of the following problem?

texts:
Input: $M$ is non deterministic Turing machine that always halts in $cn^k$ moves/steps, where $c$ and $k$ are constants and $n$ is the length of the input string of $M$, $w$ is any string in $\Sigma^*$ and $a$ is another string in $\Sigma^*$ where $\Sigma=\{0,1\}$.

Output: Does $a$ represent a valid computation of $M$ on $w$?

$a$ indeed encodes truth assignment, when the symbol $0$ encodes false value and the symbol $1$ encodes true value.

If $a$ satisfies $\Phi_{M,w}$, where $\Phi_{M,w}$ is the boolean formula that deterministic Turing machine can compute in polynomial time by the Cook Levin reduction that is satisfiable if and only if $M$ accepts $w$, then $a$ is indeed represents a valid computation of $M$ on $w$ since the Cook Levin reduction is parsimonious.

But if $a$ falsifies $\Phi_{M,w}$ then this is not necessarily true
that $a$ represents a valid computation of $M$ on $w$, because it is possible that the given non deterministic Turing machine $M$ accepts the given string $w$ on all computations, paths and routes and the given truth assignment $a$ still falsifies $\Phi_{M,w}$.

So in case that $a$ falsifies $\Phi$, how do I decide whether or not $a$ represents a valid computation of $M$ on $w$?

What is the complexity of this problem?

Does exist polynomial time deterministic algorithm that decides/solves this problem or nobody doesn't know if such algorithm exist yet?


texts: Small step vs big step semantics for static analysis?

texts:
To be an honest question poster I do not yet fully grasp the difference between small step and big step semantics. There was a good discussion here

My question is if I were to do static analysis on a file to determine if it is malware, what would be better to use: small step or big step semantics?

To take this a step further if I am doing dynamic analysis which would be best: small step or big step semantics?

Preferably a simple example as to why would be much appreciated.


texts: Can you share some pointers to get better at working alone in projects?

texts:
I am an ML Engineer who works alone in projects most of the time. I don't have people who are much smarter than me working alongside.

Most of the time, I feel that working alone is a tedious job,one may get stuck at a lot of problems. In such cases my only go to option is Google. What effective techniques you use while you work on a project alone, because at the moment googling feels like looking for a needle in haystack (80% of the stuff will be useless for you).

Apart from that, some answers you search for lead you to more questions related to stuff explained there and it becomes a vicious circle of googling things leading to frustration. (And most of the developers out there suggest the top down learning methodology, where you do a problem at first and then breaking down to solve it which ends up in above problem.)

So would you like to weigh in with your experiences, like what thinking style you adopt, what are effective search methodologies, good ways of breaking down the problem, here you get quick help apart from SO etc. It's good if you can link to books, resources etc as well.


texts: Approach needed to solve a ABS based scenerio by ML

texts:
Problem Statement: Want to find out what impact Insurance markets will have if ACA (Obamacare) is repealed. This can be done by creating an ABM (agent based model) and trying out simulations. What I want to do is solve this as a machine learning problem.

The Approach I thought of is training a classifier(or an ensemble model) on pre ACA data and post ACA data and then, if it does a good job on previously unseen data, try to give it some fictional data , based upon new market conditions and see how it performs - (Sales of New policies).

There must be some better solution out there, can anyone point out to something?

Let me know if additional details are required.


texts: Construct a TM for checking if a set of parentheses are well formed

texts:
This was a solved example given in my textbook. When I tried to solve this, I got a different TM that was given as the solution. I tried running a sample string through my TM,  and somehow got the correct answer.
Still the answers dont match. Please let me know if there isvsomething I've missed.
This may sound a simple school homework but I would be grateful for any help

The one in ink is my solution
(https://i.stack.imgur.com/PiJX6.jpg)

This is the textbook answer.
(https://i.stack.imgur.com/p6HY7.jpg)


texts:
I know the Dijkstra algorithm to solve the "single source shortest path" problem in a graph. And I've seen people discuss solutions in a dynamic graph where edge/vertices are subject to change. Retrieving the shortest path of a dynamic graph

My question is a little different.

  Given the entry node $S$, while the entire graph $G(V, E)$ is unknown at the beginning. There's a function public List<Edge> get(Node node) to figure out the outgoing weighted edges at each node. Also, there's another function public boolean isExit(Node node) tells you when to stop if the node is an exit node.

The question is a lot like the shortest path finding problem in a maze, where you're at the entry, you only know the next moves of the current node and past nodes, you'd like to find the exits (multiple) in the shortest path. In this analogy, we care more about how to find the "exit" quickly, rather than finding the global optimal shortest path.

I'm wondering if the normal Dijkstra algorithm (Greedy + Relaxation) still applies in the case.

  Because we don't know the full graph, the shortest path to a node might haven't been explored yet, and exist in the unknown part. (That's my biggest concern).

I hope my explanations are clear enough, thank you very much!


texts: Adjacent house , dynamic programming problem

texts: I have to be honest this is a homework problem, but I just need to discuss this with some one. The problem is there is a row of n houses, with different profit e.g profit1 for house 1, it can be either positive or negative value. But the aim is to maximize the profit by buying a subset of these houses. So infact, you should buy houses which are >0 value. However, you cannot buy houses that adjacent to the house you are buying, e.g i-1 and i+1 should not be bought. I am not quite sure where to start to look at this problem, I mean what exactly will be the difference of looking it from the greedy or dynamic programing way. Thanks for any suggestion.


texts: Can the regular image of a context-free language be undecidable?

texts:
I just need to know the truth or falsity of a simple statement.

Let $L_1$ be a context-free language over an alphabet which contains some number of characters $\Sigma$, as well as a single, special metacharacter “|”. Suppose that every string in $L_1$ contains exactly one metacharacter. Let the left half and right half of a string in $L_1$ denote the part of the string before the “|” and the part after, respectively.  Let $L_2$ be the language over $\Sigma$ containing all the right halves of the strings in $L_1$.

Then is membership in $L_2$ decidable? What about if $L_1$ is restricted to be nice in some way? I'm fairly sure there are counterexamples in any case, but I can't find them.


texts:
Can one build a priority queue using stacks, such that the priority queue has the same complexity for each operation.
Could it be done? If so how? If not what is the best solution that can be done?

Each operation of a stack using an array is $O(1)$ whereas almost all operation of priority queue is $O(logn)$.
an implementation can be done using $2D$ stacks, each elements of the stack is again a stack.
When the first element of the main stack is the first element of the other stacks.
The dequeue operation will take $O(n)$ as it is LIFO and the priority queue is FIFO.


texts: Little Man Computer Simulator Input Code

texts:
I'm just learning about the Little Man Computer CPU simulator, and am using a version online here: http://peterhigginson.co.uk/lmc/

The instruction set used by the simulator is the same as the one here, I believe: https://en.wikipedia.org/wiki/Little_man_computer#Instructions.

I have got confused right at the beginning of my learning due to the way the instruction INP is handled.

If I have a program with just 1 line - INP and then watch the simulation, I see that the code901 is fetched into the CPU, and split into 9 in the instruction register and 01 in the address register.

I am having trouble understanding how the 01 part can be considered to reference a memory location, as the value which is input goes straight onto the accumulator.

My initial theory is that the instruction/memory (or opcode/address) split doesn't apply to the INP, OUT and HLT commands, but only to the remaining ones (ADD, STA etc.), but that the simulator is not built to account to this distinction.

However, I don't have enough experience to know is that is a reasonable assumption or if I am missing something conceptually.

Any clarification much appreciated.


texts: Clarification of the proof involving the regularity condition in Master Theorem

texts:
I was going the text Introduction to Algorithms by Cormen et al. Where I came across the following statement in the proof of the third case of the Master's Theorem.

(The Statement of Master theorem) Let $a \geqslant 1$ and $b > 1$ be constants, let $f(n)$ be a function, and let $T (n)$ be deﬁned on the nonnegative integers by the recurrence( the recursion divides a problem of size $n$ into $a$ problems of size $n/b$ each and takes $f(n)$ for the divide and combine)
$T(n) = aT(n/b)+ f (n)$ ;
where we interpret $n/b$ to mean either $\lceil b/n \rceil$ or $\lfloor b/n \rfloor$. Then $T(n)$ has the following asymptotic bounds:

If $f(n)=O (n^{\log_ba - \epsilon})$ for some constant $\epsilon > 0$, then $T(n)=\Theta (n^{\log_ba})$.

If $f(n)=\Theta (n^{\log_ba})$, then $T(n)=\Theta (n^{\log_ba}\lg n)$

If $f(n)=\Omega (n^{\log_ba + \epsilon})$ for some constant $\epsilon > 0$, and if $af(n/b) \leqslant cf(n)$ for some constant $c < 1$ and all sufﬁciently large n, then $T(n)=\Theta (f(n))$.

For $n$ as exact powers of $b$ we restrict the domain of T(n) as follows:

$$T(n)= \Theta(1), n=1$$
$$T(n)=aT(n/b)+f(n) ,n=b^i$$

Now in the proof of Master's Theorem with $n$ as exact power of $b$ the expression for $T(n)$ reduces to :
$$T(n)=\Theta(n^{\log_ba})+\sum_{j=0}^{\log_bn -1} a^jf(n/b^j)$$

Then the authors assume the following,
$$g(n)=\sum_{j=0}^{\log_bn -1} a^jf(n/b^j)$$
Then for the proof of the 3rd case of the Master's Theorem the authors prove the following lemma,

Lemma 1 : If $a\cdot f(n/b)\leqslant c\cdot f(n)$ for some constant $c<1$ and for all $n\geqslant b$ then $g(n)=\Theta(f(n))$

They say that:
under their assumption that $c<1$ and $n \geqslant b$,they have $a \cdot f(n/b)\leqslant c \cdot f(n) \implies f(n/b)\leqslant (c/a) \cdot f(n)$
then iterating $j$ times yields, $f(n/b^j)\leqslant (c/a)^j \cdot f(n)$
I could not quite get the mathematics used behind iterating $j$ times.
Moreover I could not quite get the logic behind the assumption of $n\geqslant b$ for the situation that $n$ should be sufficiently large. (As the third case of the Master's Theorem says.)
The proof of the lemma continues as follows:

$$f(n/b^j)\leqslant (c/a)^j\cdot f(n) \iff a^j\cdot f(n/b^j)\leqslant c^j\cdot f(n)$$
So, $$g(n)=\sum_{j=0}^{\log_bn -1} a^jf(n/b^j)$$
$$\leqslant \sum_{j=0}^{\log_bn -1} c^jf(n)$$
$$\leqslant f(n)\sum_{j=0}^{\infty} c^j,$$ as $c<1$ we have an infinite geometric series
$$= f(n) \left(\frac{1}{1-c}\right)$$
$$=O(f(n))$$ as $c$ is a constant. (Note that $T(n)=\Omega(f(n))$ from the recursion diagram.)

Then the authors proof the third case of the Masters Theorem for $n$ as exact power of $b$:

Lemma 2: Let $a \geqslant 1$ and $b>1$,  if $f(n)=\Omega (n^{\log_ba + \epsilon})$ for some constant $\epsilon > 0$, and if $af(n/b) \leqslant cf(n)$ for some constant $c < 1$ and all sufﬁciently large n, then $T(n)=\Theta (f(n))$.

So $$T(n) = \Theta(n^{\log_ba}) + g(n) = \Theta(n^{\log_ba}) + \Theta(f(n)) =\Theta(f(n))$$ as $f(n)=\Omega (n^{\log_ba + \epsilon})$

Moreover in the similar proof for the third case of the general master theorem (not assuming $n$ as exact powers of $b$) there again the book assumes that $n\geqslant b+b/(b-1)$ to go with the situation of sufficiently large $n$.
I do not quite understand what the specific value has to do and why such is assumed as sufficiently large $n$
(I did not give the details of the second situation as I feel that it shall be something similar to the first situation but however it can be found here)


texts: Reducing TSP to HAM-CYCLE to VERTEX-COVER to CLIQUE to 3 CNF-SAT to SAT

texts:
In Cormen's Algorithms book on NP-completeness they prove various problems are NP-complete by reducing a previously proved NP-complete problem (call $K$) to current problem (call $L$). Each proof involves some clever construction which reduces all instances of $K$ to few instances of $L$. Here is the proof order they follow. CIRCUIT-SAT, SAT, 3 CNF-SAT, CLIQUE, VERTEX-COVER, HAM-CYCLE, TSP. e.g. in reducing VERTEX-COVER to HAM-CYCLE they use a widget which does the trick.

After this previous question of mine, I think one can reduce back. i.e. one can reduce HAM-CYCLE to VERTEX-COVER problem. I tried searching web for such reductions, but most of the link return the normal reduction order. I'm interested to see if one can reduce in reverse order. i.e. TSP to HAM-CYCLE to VERTEX-COVER to CLIQUE to 3 CNF-SAT to SAT

I'm looking for reverse constructive proofs. I know all of these problems belong to NP-complete hence equivalent.

You don't have to give complete proof as an answer. Proof sketches are fine too. If you can point me where these proofs are available online, that's completely fine too. I'm just trying to lean how constructions are leveraged among problems that look so different on surface. Thanks!


texts: Relationship between message entropy and complexity of the best algorithm

texts:
Is it possible to estimate number of steps in best possible algorithm for classification of messages, using entropy of messages?

E.g. linear search problem. We have an ordered set of incomparable elements (no < and >, equivalence only) of length $N$, and element for search – A, which could be in set maximum once. Set could be represented as sequence like 00001000, length $N$, where 1/0 means that element here equals A/not equals A. Algorithm parses the message and responds "not contains" (for one message 00000...0 ) and "contains" (all other messages). For uniform probability of being equal A for each position, entropy of responses equals:
$$H=-\frac{1}{N+1}\cdot \log_2\left(\frac{1}{N+1}\right) - \frac{N }{N+1} \cdot \log_2\left(\frac{N}{N+1}\right)$$
$H$ goes to zero quickly:

We also know that $\lfloor\text{entropy}\rfloor+1$ equals the mean message length in case of best coding (Shannon's source coding theorem for symbol codes). That means we could index any message with binary string, and it will take us only one symbol – one step in algorithm!

But existing codes for linear search (e.g. brute force) require $\frac{N+1}{2}>1$ steps, and all improved techniques require comparability (e.g. binary search).

This suggests that entropy of message does not equal the number of step in best possible algorithm of problem solution (=message classification).

But then what is the link between both? Is there any relationship between the number of steps for the abstract "best code" and the entropy of message?


texts: How can I talk about priority inversion if it's impossible to specify priority?

texts:
In the paper:

  Leslie Lamport: What It Means for a Concurrent Program to
  Satisfy a Speciﬁcation: Why No One Has Speciﬁed Priority; ACM Symp Principles of Programming Languages, (POPL-12):78-83, 1985.

Lamport shows that "...existing specifications that claim to describe prioirty are either vacuous or else too restrictive to be implemented...", and in the conclusion says

  Waiting is an implementation-level concept that I feel cannot be expressed in a general way.

Yet, we have vigorous conversations about priority inversion in real operating systems.  Take, for example, this argument I found between Victor Yodaiken and Doug Locke about whether it is a good or bad idea to implement priority inheritance in a real-time Linux scheduler.  Yodaiken cites the classic Lampson and Redell paper about monitors (CACM, 23(2):105-117, 1980) to describe what priority inversion is.

I thought I had a concrete but informal notion of priority inversion and priority inheritance, and have been teaching these concepts to unwitting undergraduates for over a decade.  Should I stop trying to teach about priority since the concept is apparently vacuous?


texts:
I was watching a lecture on determining the strongly connected components of a graph using Kosaraju's algorithm and the lecturer claimed one can easily walk the edges in reverse fashion.

While I see this happening with an adjacency matrix representation(the reverse is the matrix transpose, and you can determine its elements on demand), I'm having a hard time coming up with a solution in the case of the adjacency list representation.

Any hints?


texts: Quickly determine if insertion sort or quick sort is better

texts:
I'm in a scenario where ~30% of the time, my array is almost completely sorted, and the other 70% of the time, it is basically completely random. I want to quickly determine if my list is almost sorted, use insertion sort if it is, or quicksort otherwise. I've been searching this up all day but no luck.
The alternative solution is to shuffle the array and use quicksort every time, but this passes up on the opportunity to do 30% of the sorts faster.
The way I thought of is to compare consecutive terms, find the number of consecutive pairs out of order, and use that to estimate the entire array, but its not very reliable.
This seems like a common problem, so I was wondering what the "official" solution(s) is.


texts: Two-way finite automaton: How does the automaton remember the state

texts:
I have been going through a theory of Two-way finite automatons and I did not understand the given example when there were a DFA A = (Q, Σ, δ, q1, F). the 2-DFA B = (Q ∪ Q| ∪ Q|| ∪ {q0, qN, qF}, Σ ∪ {#}, δ|, q0, {qF}) and a following language  L = { #u# | uu ∈ L(A)}. In following paragraph  I will describe how would it works, if we are reading a word that belongs to the language. In the first procedure automaton B follows the states of automaton A, when it reach right '#', it stops, remember the accepting state and starts to move back through the copied states of automaton A: Q| as long as it come to right '#'. Afterwards it starts moving on through the copied states Q|| of automaton A, and once it reaches out the right '#' checks if it is the saved accepting state. Image below shows the movements where qN is a failing/non-accepting state and +1 movement of head to right and -1 movement of the head to left.

Question

How does the 2-DFA remember that it reached out during first walk through the states of automaton A the accepting state for the second walk?


texts: Any suggestions about a known NP-complete problem that can be reduced to the following problem?

texts:
Given an undirected graph $G$, where nodes represent towns and edges represent roads, and given a positive integer $k$, is there a way to build $k$ McDonald's at $k$ different towns so that every town either has its own McDonald's, or is connected by a (direct) road to a town that does have a McDonald's?

I believe that this problem is NP-complete. I am trying to find a well-known NP-complete problem, so I can use it to prove that this problem is NP-complete, too. Any suggestions?


texts:
I came to know that the graphic processing unit have something called memory coalescing. On reading on it I was not clear on the topic. Is this any way related to Memory Level Parallelism.

I have searched in Google but was not able to obtain a satisfactory answer.

It would be helpful if someone gives a more comprehensive, easy-to-understand explanation.


texts:
Recursion schemes are structured methods for expressing recursive functions, of increasing interest due to their ubiquity in functional programming. For example, catamorphisms (familiar in the guise of 'fold' on lists) can be defined for all inductively-defined (i.e. algebraic) data types and in the particular case below, for natural numbers ("A natural number is either zero, or the successor of a natural number).

Q. Can (floor) log2 on the natural numbers (setting log2(0) to be 0) be readily expressed as a single recursion scheme (e.g. a catamorphism), as opposed to via a hylomorphism (which is an anamorphism followed by catamorphism)?

A formulation of log2 via metamorphisms is given in Martin Erwig's Metamorphic Programming. Can it instead be expressed simply as a catamorphism?


texts: Can partial sums of a counter array be computed in O(log n) time?

texts:
Let $A[1 . . . n]$ be a given array of $n$ integers, where $n = 2^m$. The following two operations are the only ones to be applied to A:

Add(i, y): Increment the value of $A[i]$ by $y$.

PartialSum(k): Print the current value of $\sum_{i=1}^{k} A[i].$

One needs to perform these two operations multiple times in any given
order. Design a data structure to store A such that each invocation of
these two operations can be done in $O(m)$ steps.

What I have designed is the following :
Since the number of elements is $2^n$, $O(m)$ steps implies $O(\log n)$ steps.
We can think of the array as a binary tree represented in array format with the root at $A[0]$ which is the standard notation for a binary tree in array format. I am using an auxiliary array $B[]$ which stores the cumulative sum of elements at each level of the binary tree.
Thus, for an array $A[] = \{1,2,3,4,5\}$ the value of $B$ would be $B[] = \{1,6,15\}$ since in level $0$, we have the element $A[0] = 1$. Similarly, in level 1, we have the elements $A[1]$ and $A[2]$ whose cumulative sum is placed at $B[1] = 6$
Assumption: We have a helper function findlevel(i) which finds the level in the binary tree for a node $i$.
Thus for the Add(i, y) operation, we can perform the $A[i] = A[i] + y$ operation in constant time, and we can call findlevel(i) which would return the value of the level of the node in the binary tree. Once we know the level, we can increment $B[i]$ by $y$ for all $i = level(i)$ to $end$. Thus, it can be carried out in $O(\log n)$ time.
Can the PartialSum(k) operation be computed in $O(\log n)$ time using this data structure?


texts: Efficient data structures for building a fast spell checker

texts:
I'm trying to write a spell-checker which should work with a pretty large dictionary. I really want an efficient way to index my dictionary data to be used using a Damerau-Levenshtein distance to determine which words are closest to the misspelled word.

I'm looking for a data structure who would give me the best compromise between space complexity and runtime complexity.

Based on what I found on the internet, I have a few leads regarding what type of data structure to use:

Trie

This is my first thought and looks pretty easy to implement and should provide fast lookup/insertion. Approximate search using Damerau-Levenshtein should be simple to implement here as well. But it doesn't look very efficient in terms of space complexity since you most likely have a lot of overhead with pointers storage.

Patricia Trie

This seems to consume less space than a regular Trie since you're basically avoiding the cost of storing the pointers, but I'm a bit worried about data fragmentation in case of very large dictionaries like what I have.

Suffix Tree

I'm not sure about this one, it seems like some people do find it useful in text mining, but I'm not really sure what it would give in terms of performance for a spell checker.

Ternary Search Tree

These look pretty nice and in terms of complexity should be close (better?) to Patricia Tries, but I'm not sure regarding fragmentation if it would be better of worse than Patricia Tries.

Burst Tree

This seems kind of hybrid and I'm not sure what advantage it would have over Tries and the like, but I've read several times that it's very efficient for text mining.

I would like to get some feedback as to which data structure would be best to use in this context and what makes it better than the other ones. If I'm missing some data structures who would be even more appropriate for a spell-checker, I'm very interested as well.


texts: What does up arrow ($\uparrow$) mean in pseudocode?

texts:
I'm learning vantage point trees, and I met this while reading the paper Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces by Peter Yianilos (Proceedings of SODA 1993, SIAM, pages 311–321; PDF).  The following pseudocode appears in Algorithm 1.

$$\begin{align*}
\hspace{2em}&\hspace{-2em}
\textbf{function}\text{ Make_vp_tree(}S\text{)}\\
&\textbf{if }S=\emptyset\textbf{ then return }\emptyset\\
&\text{new(node);}\\
&\text{node}\!\uparrow\!\!\text{.p} := \text{Select_vp(}S\text{);}\\
&\text{node}\!\uparrow\!\!\text{.mu} := \text{Median}_{s\in S}\, d(p,s);\\
&\dotsc
\end{align*}$$

node is a node of vp-tree, so I know what node.p means, but what do that up arrow means in this context?


texts: How to efficiently find line-segment intersections between two sets?

texts:
So I'm building this iterative simulation of a surface (composed of line segments) that cannot self-intersect, which means I have to check intersections at the end of a timestep. The thing is, I know, at the beginning of every timestep, that no intersections exist within the set of all line segments that constitute the surface, and at every timestep, a fixed number of nodes is altered (if this produces intersections, the simulation resets). Let's call the set of all lines after an alteration N and the lines that have been altered K. I then know that I should only look for intersections within K and between K and {N - K}, because I know there can be no intersections within {N - K}. This is equivalent to wanting to find intersections between K and N.

When I first tackled this problem, I just implemented sweepline, but now I realize that it finds intersections within a set. As far as I can tell, adapting the algorithm to find intersections between segments in a set X and segments in a set Y is quite tricky; I haven't been able to work that out. The only things I thought of is doing brute force (which amounts to |K| * |N|) and just ignoring K and applying sweepline, which is |N|lg|N|. If there's a way to combine the best of both approaches,I'd expect there to be a big difference in the performance of my code. Is there such a way?


texts: What are the implications of Lean not having the type `Set`?

texts:
In Coq we have an impredicative base type, called Prop, and a predicative base type, called Set, both of type Type 0.

On the other hand, in Lean we only have an impredicative base type. We do not have an equivalent to Set. Instead we use directly Type 0(a synonym of Sort 1).

What are the implications of this design decision?


texts: Can element uniqueness be solved in deterministic linear time?

texts:
Consider the following problem:

Input: lists $X,Y$ of integers

Goal: determine whether there exists an integer $x$ that is in both lists.

Suppose both lists $X,Y$ are of size $n$.  Is there a deterministic, linear-time algorithm for this problem?  In other words, can you solve this problem in $O(n)$ time deterministically, without using randomness?

Unfortunately, you cannot assume that the list elements are all small.

I can see how to solve it in $O(n)$ expected time using a randomized algorithm: randomly choose a 2-universal hash function $h$, store the elements of $X$ into a hashtable (using $h$ as the hash function), and then look up each element of $Y$ to see if it is in the hashtable.  The expected running time will be $O(n)$.  However, I can't see how to find a deterministic algorithm with $O(n)$ running time.  If you try to derandomize this and fix a single specific hash function, there will exist a worst-case input that causes this procedure to run in $\Theta(n^2)$ time.  The best deterministic algorithm I can find involves sorting the values, but that won't be linear-time.  Can we achieve linear running time?

Also, I can see how to solve it in linear time if you assume that all of the list elements are integers in the range $[1,n]$ (basically, do counting sort) -- but I am interested in what happens in the general case when we cannot assume that.

If the answer depends on the model of computation, the RAM model jumps to mind, but I'd be interested in results for any reasonable model of computation.  I'm aware of $\Omega(n \log n)$ lower bounds for decision tree algorithms for element uniqueness, but this isn't definitive, as sometimes we can find linear-time algorithms even when there is a $\Omega(n \log n)$ bound in the decision-tree model.


texts: Efficient set data structure supporting insert and set equal

texts:
What's the best way to represent sets that support the following two operations:

Insert(s, i)  - adds nonnegative integer i to set s
Equal(s1, s2) - Tests if s1 and s2 are the same set.

In addition, I have an upper bound on the integers added to each set. That is, I know $N$ such that $0 \le i < N$.

I'm also willing to accept that Equal is only approximate. ie Equal(s1,s2) could be true even if s1 != s2. I guess in that case I'm looking for a hash function. Does anyone know a good hash function?

We can assume that an integer is only inserted once into a set. $N$ can be about 3-5 million, and the number of sets I want to test for equality can be in the thousands.


texts: Prove grammars with long derivations generate infinite languages

texts:
Suppose $G$ is a CNF (Chomsky normal form ) grammar which has $v$
  variables. ($|V| = v$) If there is a string that $G$ derivatives in
  more than $2^v$ steps, prove that $L(G)$ is infinite.

Any ideas how can i prove this?

I know derivation tree in a CNF grammar is binary. So my idea is to calculate maximum number of leaves in the tree and prove that if $L(G)$ is finite this can't be reached in more than $2^v$ steps. Can anyone help me how to prove this part?


texts: Halting problem under spatial restrictions

texts:
Let $A(n, B, d)$, $B(n, d)$ be a {Turing machine, random-access machine, C program} with finite tape (which I'm going to denote "Turing machine*" and "random-access machine*" respectively), $n \in \mathbb{N}$. $A$ and $B$ are the same type of machine. For any $N \in \mathbb{N}$, statements where $n \leq N$, don't matter.

$n + |d|$ is the number of spatial units on $B$'s tape if $B$ is a Turing machine* or random-access machine*. If it is a C program, $n$ is the number of Bytes in $B$'s read-write memory (registers are neglected, see last sentence of previous pragraph). The memory $d$ takes up is read-only and not accounted for. All spatial units regarded are capable of holding the same amount of information.

$d$ is the argument data. You may assume $n$ to be included in $d$.

If $A$ is a Turing machine* or random-access machine*, it may access $2 \cdot (n + |d|) + c$ spatial units where $c$ is constant.

If $A$ is a C program, it may access $n + c$ Byte of read-write memory. The memory $d$ takes up is read-only and not accounted for. It may have a function which for any $p, k \in \mathbb{N}, B \in \{\text{C program}\}, d$ returns the $k$th Byte of $B(n, d)$'s memory after $p$ steps.

For any of the situations $B \in \{\text{Turing machine*}, \text{random-access machine*}, \text{C program}\}$: Is there an $A$ which decides whether $B(n, d)$ will halt?

I care about the reasons as to why this is the case. Unfortunately, I forgot a lot of what I learned about computability. I'm sorry if this is super trivial or unknown.


texts: What's the complexity class of determing the halting problem of a finite memory Turing machine?

texts:
What's the complexity class of determining the halting problem of a finite memory Turing machine?
What is the computational complexity class of determining whether a machine halts on any input if it is allowed to access no more than $n$ bits of memory.

I know this problem is decidable because due to the limited memory, if it runs for longer then $2^n$ it must be caught in a loop.


texts: There is an  exercise which says : Al and Bob are arguing about their algorithms. Al claims his $O(n \log n)$-time method is always faster than Bob’s $O(n^2)$-time method. To settle the issue, they perform a set of experiments. To Al’s dismay, they find that if $n<100$, the $O(n^2)$-time algorithm runs faster, and only when $n\ge 100$ is the $O(n \log n)$-time one better. Explain how this is possible.


texts:
Here the author describes the Random Access Stored Program machine and the problem of indirect addressing.
The author states:

But this does not solve the problem (unless one resorts to Gödel numbers). What is necessary is a method to fetch the address of a program instruction that lies (far) "beyond/above" the upper bound of the finite state machine's instruction register and TABLE.
However, with only 4 registers, this machine has not nearly big enough to build a RASP that can execute the multiply algorithm as a program. No matter how big we build our finite state machine there will always be a program (including its parameters) which is larger. So by definition the bounded program machine that does not use unbounded encoding tricks such as Gödel numbers cannot be universal.
problem of the RASP without indirect addressing

Steven Wolfram weighs in saying:

The results of page 100 suggest that with 2 registers and up to 8 instructions no universal register machines (URMs) exist.

My question is: Why does using an encoding trick like Gödel numbers make a register machine universal?


texts: What computational model supports arbitrarily sized integers?

texts:
I want to do some research, but I don't think it's important the number of bits it takes to represent the integer input and arithmetic on the abstract machine.  So what is the model that addresses this?

Specifically, I want to prove that integer factorization is not in P.  If the above is a bad idea, then what model should I be using?  Clearly, I would be needing add, sub, mul, and divide instructions.

Or, should something else be used such as algebraic complexity theory?


texts: Comparison of matrix determinant in less than $O(n^2)$

texts:
I was reading this question and I think maybe somebody here could help.

This is the idea: Given a matrix $M$ of integers, and a number $d$ is there a way to compare the determinant of $M$ and $d$ in a fast way? Note that we don't need the calculation of the determinant, only comparison.

The motivation is this: if one could find a good (maybe less than $O(n^2)$) algorithm, and with an upper and lower bounds for the determinant, one could perform binary (or linear?, no, I don't think so) search over the interval in order to determine the determinant of the matrix.


texts: Classification training data, but regression prediction

texts:
Suppose I'm performing machine learning on a simple dataset, and have a bunch of training data of the form:

x (feature)   y (label)
-----------------------
1             0
2             1
3             1
4             0
5             1
6             1
...

Where the labels are values in two classes, $[0, 1]$.  Clearly, this training data lends one to believe that it will be a classification task.

However, suppose I want to output instead the probability that a feature will take the class $1$.  Then, my output is more of a regression task.

Consequently, when I'm designing a simple neural network with just a single input layer and single output layer, how many output units should I have?  Should I have two output units, one for each class, and if so, how do I ensure that each pair of outputs will be a valid probability distribution (i.e. sum to one)?  Or should I have only one output unit, and treat the entire problem as a regression task?

There are probably pros/cons to each approach... thanks for your help!


texts:
I was wondering in how to solve this question, I feel a bit confused: for $\Sigma = \{1,\#\}$, consider

$$D=\{w \mid w=x_1 \# x_2 \# \cdots \# x_k \text{ for } k \geq 0, \text{ each } x_i \in 1^*, \text{ and } x_i \neq x_j \text{ for } i \neq j\}.$$

I want to know how to prove this is not regular using pumping lemma.


texts:
After reading an answer at this link:
https://serverfault.com/questions/503345/three-duplicate-acknowledgementss
I am confused. Do ACK values repeat when a packet is lost or when an out of sequence packet is received? For example in the diagram, the ACK values are same at the 12th and 13th segment. However, there's a drastic change in the window size. What exactly is the link?
I also read that selective acknowledgments could be used in segement 8. I know what they do by definition but I don't understand why we could use them here in segment 8 particularly. Any ideas? If it's because of the same SEQ & ACK numbers in the corresponding segments, it would be the same for segment 10, right?


texts:
This answer claims that  $ LL \subseteq  LR \left( 1 \right )$ where $LL = \bigcup_k LL(k)$.

But is this true? Is this grammar a valid counterexample?

$ S \rightarrow a | Aaa $, $ A \rightarrow \varepsilon $

It's easy to show that this grammar is not $LR \left( 1 \right )$, but I think that it is in $LL(2)$ - the longest string that can be derived is two letters so a lookahead of two tokens should be sufficient.


texts: Can Fiedler vector be used for displaying an undirected graph in a sequential manner?

texts:
My problem is to display an undirected unweighted graph in a grid format ( $ (n \times 3) $ - matrix for simplicity) without compromising on the connections displayed on the screen (the only connections that would be displayed are between adjacent nodes in the grid).

One way I could think of is to bisect the graph recursively by calculating the fiedler vector of the Laplacian matrix so that at each step the number of connections lost is minimum. However, after bisecting the graph, the sequence of displaying the bisections of these two graphs could also increase the number of connections displayed. Thus this method is not very satisfactory to me.

My question is whether we could sort the nodes in increasing order of the fiedler vector and display them in the same order in the grid? Are there other easy and intuitive grid layout algorithms for graphs?


texts: Using logic to prove non-regularity of a language

texts:
A language $L$ is regular if and only if it is definiable by a sentence in monadic second order logic (MSO) over strings (J.R. Buchi, Weak second-order arithmetic and Finite automata; Z. Math. Logik Grundlagen Math. 6 (1960) 66-92).

  Are there proofs of non-regularity of a language $L$ (e.g. $L = \{ a^n b^n \}$) that are based on the non expressibility in MSO of $L$?
  What are the (logic) techniques (if any) that can be used?

I googled a little bit, but didn't find anything relevant (but I'm not an expert, so I'm probably using the wrong terms).


texts:
BFS Algorithm for Finding Minimum Steps for Knight Eliminating a Moving Pawn.

As the Title suggests, I'm trying to intuitively understand this problem. Suppose we have a Pawn and a Knight taking turns. Both pieces must move on their turn, and both pieces have a starting position, and suppose the board is sufficiently large enough for the Knight to eventually catch up to and eliminate the Pawn, where the Pawn is avoiding being captured. I want to find the minimum amount of moves the Knight takes to eliminate the Pawn.

I know that we can use a BFS algorithm to find the shortest path between the Knight and a stationary spot on the board, but I'm not sure how to do this for a moving target. What if we do a BFS on every square of the column the Pawn is travelling on and then compare the number of moves that takes and check if one of these sequence of moves ends up on the Pawn's location. But this doesn't seem like it will always work, because finding the minimum amount of moves to where the Pawn will eventually be could be less than the actual minimum amount of moves to catch up to the Pawn because the Knight could "stall" a bit until it's in the right position to eliminate the Pawn.


texts: Chinese Postman Problem: finding best connections between odd-degree nodes

texts:
I am writing a Program, solving the Chinese Postman Problem (also known as route inspection problem) in an undirected draph and currently facing the problem to find the best additional edges to connect the nodes with odd degree, so I can compute an Eulerian circuit.

There might be (considering the size of the graph that wants to be solved) an enormous combination of edges which need to be computed and evaluated.

As an example there are the odd-degree nodes $A, B, C, D, E, F, G, H$. The best combinations could be:

$AB$, $CD$, $EF$, $GH$
$AC$, $BD$, $EH$, $FG$
$AD$, $BC$, $EG$, $FH$
$AE$ ....

where $AB$ means "edge between node $A$ and node $B$".

Therefore my question is: is there a known algorithm to solve that problem in a complexity better than pure brute force (computing and evaluating them all)?

€:After some research effort I found this article, speaking about the "Edmonds' minimum-length matching algorithm" but I cannot find any pseudo-code or learners-descriptions of this algorithm (or at least I do not recognize them, as Google offers a lot of hits an matching algorithms by J. Edmonds)


texts: Spanning hypertree which connects the vertices as slowly as possible

texts:
I want to find a reference for the following problem or a similar problem for my paper. I found a greedy algorithm for this problem, but writing such an algorithm in a paper is not common in my area, and finding a reference is the best solution.
We have a connected hypergraph. We want to choose a list of hyperedges satisfying the following property: if you add the hyperedges to the empty hypergraph one by one, in each step the number of connected components reduces. At the beginning we have $n$ components, and at the end of these steps we have a single component. Suppose that in the $i$-th step, the number of components reduces by $a_i$. If we have $t+1$ steps, we want to minimize $\max(a_1,a_2,\dots,a_t)$.
I have an algorithm in which the complexity of each step is $O(n^{a_i})$.  I would be glad to find a reference for this problem.


texts:
What is the best way to detect repeating sequences of random numbers?

For example, say I got two random number generators (RNG). One of them has been tampered with and is repeating the sequence of random numbers after every N iterations.
The other RNG has not been tampered with and is producing random numbers like it should.

However, one of them is repeating its output every N bytes. N can be small or very large. How to detect this in a reliable and economic way?

Is using rolling hashes (like rsync does) a viable approach?


texts: Maximal combinations in a Boolean algebra

texts:
Consider a finite set $X$ and the boolean algebra $\mathcal{P}(X)$ of the subsets of $X$. While I focus on $\mathcal{P}(X)$ in this question, the problem could be expressed more generally in any boolean algebra.

I have $n$ elements $P_1,P_2....P_n$ of $\mathcal{P}(X)$. I am interested in the unions of any combination of these elements that I simply write $P_I=\bigcup_{i\in I}P_i$ for any $I\subseteq \{1,2,...,n\}$.

Possibly there could be up to $2^n$ such unions. But I know in my situation that there is a lot of redundancy, and that there are much fewer different unions: there are many combinations $I$ such as $P_I$ is the same.

I want to find the maximal combinations $I$ producing a fixed union: $I$ is such as for all $J\supset I$ we have $P_J\supset P_I$ (inclusion is strict). It is a combination such as any super-combination produces a strictly bigger union. Minimal combinations are also interesting to me, even though the problem is not exactly the same.

Any thought about an algorithmic idea to produce (efficiently) the list of all such combinations?


texts: Can we represent $\sqrt{2}$ exactly even with infinite bits in mantissa in floating  point notation or otherwise. We actually have to prove this is not possible. But why can't we if we have infinite bits? Infinite bits means the binary representation of the mantissa can be indefinitely large. The mantissa is in IEEE 754 32 bit format and in a hypothetical world where we don't have a bound on the number of bits which can be used to represent it.


texts:
Looking at this video starting at 1:45, the author claims to be using a second-order approximation for a Markov text generation. He has one letter which he outputs followed by another letter which tells him which state to go to - so in other words, he might first pick AC, so he outputs A and then goes to state C, where he picks CB, so he outputs C and goes to state B, etc. So he has a uni-gram output followed by a uni-gram transition piece of information.

But from my understanding, a second-order approximation would be like this, with a bigram followed by a unigram as the "transition" state.

  This is the same character-level order-2 n-gram analysis of the (very
  brief) text “condescendences” as above, but this time keeping track of
  all characters that follow each n-gram:

  co    n

  on    d

  nd    e, e

  de    s, n

  es    c, (end of text)

  sc    e

  ce    n, s

  en    d, c

  nc    e

  The table above doesn’t just give us some interesting statistical
  data. It also allows us to reconstruct the underlying text—or, at
  least, generate a text that is statistically similar to the original
  text. Here’s how we’ll do it: (1) start with the initial n-gram
  (co)—those are the first two characters of our output. (2) Now, look
  at the last n characters of output, where n is the order of the
  n-grams in our table, and find those characters in the “n-grams”
  column. (3) Choose randomly among the possibilities in the
  corresponding “next” column, and append that letter to the output.
  (Sometimes, as with co, there’s only one possibility). (4) If you
  chose “end of text,” then the algorithm is over. Otherwise, repeat the
  process starting with (2).

I'm extremely confused because both these sources consider themselves to be of order 2 in approximation, but it seems to me that the second source is of a higher order than the first. Is this true, or am I just completely misunderstanding what's happening?


texts: What is the role of mathematics in programming?

texts: I am almost totally uneducated in programming and computer science in general, though I am really fascinated by these topics. I read that mathematics is important in programming and that nowadays many mathematicians specialise in applied mathematics in this field. So, I wonder how these two branches are linked with each other. What are the fields of mathematics that are useful (maybe unavoidable?) in writing a computer program?


texts: What is the average-case running time of Fun-sort?

texts:
I read this paper: http://www.sciencedirect.com/science/article/pii/S0166218X04001131?np=y (you can check the PDF online for free), and I translated section 4's Fun-sort algorithm (correct me if I'm wrong):

binary-search(A,x):
    A[0]=-∞
    A[n+1]=∞    //|A|=n
    l=0
    h=n+1
    m=⌊(l+h)/2⌋
    while (h != l+1)
        if (x<=A[m])
            h=m
        else
            l=m
        m=⌊(l+h)/2⌋
    return h    //success if A[h]=x

fun-sort(A):
    for i=1 to n:
        success=false
        while (!success):
            success=true
            h=binary-search(A,A[i])
            if (A[h]!=A[i]):
                success=false
                if (i<(h-1)):
                    swap(i,h-1)
                elif (i>h):
                    swap(i,h)

As you can see, this sorting algorithm uses a binary search on a not necessarily sorted array. I realized that to get the average-case running time for Fun-sort, I needed the average number of iterations for its while cycle which I defined to be a random variable X. X would be geometrically distributed, so E[X]=1/p, where p is the probability of success of the binary-search procedure. I am stuck trying to get this probability of success.

So... any help would be very much appreciated =)

EDIT: I've been considering that binary-search will definitely fail when i < m and A[i]<=A[m]. In fact, every time the elements being compared in binary-search are an inversion, it will fail (thanks to Jorge M.). In other words, binary-search will end up in success if (x,A[m]) is not an inversion in each of the log n iterations. Now: what is the probability of (x,A[m]) being an inversion, in general?

EDIT2: I posted this on stackoverflow before I realized cs.stackexchange was a better option.


texts: What's the directory structure on disk that keeps the information of all files?

texts:
I'm reading Operating System Concepts by Avi Silberschatz(9thE), in chapter 11 File-System Interface, when the author explains the concepts of file, he states that

  The information about all files is kept in the directory structure, which
  also resides on secondary storage. Typically, a directory entry consists of the
  file’s name and its unique identifier.

I think the directory structure that holds the information of all files is of critical importance， which the author does not extend in depth though. I don't even know the terminology for this concept of directory structure. It should be somewhere on the disk and well maintained. Could anyone clarify it for me? Any literature and links will be appreciated.

Thanks in advance!


texts: Find reduction from Hamiltonian Cycle to Double Hamiltonian Cycle

texts:
$$DoubleHC=\{G\,| \text{G has at least two Hamiltonian Cycles}\}$$
I think about take a graph with HC and add to it two vertexes and edges to two randomally vertexes, but without success. Is my try good? or I have to go in other way?
Also full solution is good.


texts: Anyone knows an algorithm that finds minimum distance for all permutations?

texts:
Let $A$ and $B$ be two finite sets of the same size $n$. Let $P(A),P(B)$ be the set of all permutations of $A,B$ respectively. A distance function $d(a,b)$ is defined for any $a\in P(A),b\in P(B)$. We want to find $\min \{d(a,b):a\in P(A), b\in P(B)\}$ (note: $d$ is fixed).
For example, suppose we have two sets $\{1,2\}$ and $\{3,4\}$, and the distance $d$ is Euclidean distance, then all possible distance values are

$d((1,2),(3,4)) = \sqrt8$
$d((1,2),(4,3))=\sqrt {10}$
$d((2,1),(3,4)) = \sqrt{10}$
$d((2,1),(4,3)) = \sqrt{8}$

So the minimum value is $\sqrt 8$.
I think this is a very common problem so there should be some known algorithm out there. Anyone knows an efficient algorithm to solve this problem and help provide the name or reference? Thank you!


texts: Given n strings, how to output their order after k phases of the radix sort (huge constraints)?

texts:
Disclaimer

This is not from an ongoing contest, this is from my course of ITMO on edx.org, which is a paid code so I cannot give you a direct link to the course.

Problem

You are given $\displaystyle n$ strings. Output their order after $\displaystyle k$  phases of the radix sort.

Input

The first line of the input file contains three integer numbers: $\displaystyle n$ , the number of strings, $\displaystyle m$, the length of each string, and $\displaystyle k$, the number of phases of the radix sort , , .
 $$(\displaystyle 1 <= n <= 10^{6}, 1 <= k <= m <= 10^{6}, n * m <= 5 * 10^{7})$$
Then the description of the strings follows. The format is not trivial. The i-string ($\displaystyle 1 <= i <= n$) is written as the i-th symbols of the second, …, ($\displaystyle m + 1$)-th lines of the input file. In simple words, the strings are written vertically. This is made intentionally to reduce the running time of your programs. If you construct the strings from the input lines in your program, you are doing the wrong thing.

The strings consist of small Latin letters, from "a" to "z" inclusively. In the ASCII table, all these letters go in a row in the alphabetic order. The ASCII code of "a" is 97, of "z" is 122.

Output

Print the indices of the strings in the order these strings appear after $\displaystyle k$ phases of the radix sort.

Example:

input
3 3 1
bab
bba
baa
output
2 3 1

In all examples the following strings are given:

"bbb", with index 1;
"aba", with index 2;
"baa", with index 3.

Consider the first example. The first phase of the radix sort will sort the strings using their last symbol. As a result, the first string will be "aba" (index 2), then "baa" (index 3), then "bbb" (index 1). The answer is thus "2 3 1".

Other example:

input
3 3 2
bab
bba
baa
output
3 2 1

input
3 3 3
bab
bba
baa
2 3 1

One way to go for this problem might be sorting first k characters of each strings, this can be done using hashing + binary search but the languages that I know (Java, C++, Python) don't support hashing substring quickly.

Another way might be using a Trie, after $\displaystyle k$ phases of radix sort, it might equal with traversing the Trie in lexicographical order for nodes with depth $\displaystyle k$.

Because the constraints is huge and these methods are both error-prone. Running k steps of radix sort is not also an option because of the huge constraints. I really need help on this problem.


texts:
I am somewhat aware of the correspondence between (tuple and domain) relational calculus, relational algebra, and SQL. To the best of my understanding, one should be able to automatically convert a formula in relational calculus to an SQL query whose run on a database produces rows that make the original formula satisfiable. However, I cannot find any rules for such conversion and I would expect them to exist.

Is my understanding wrong? Where can I find these "conversion" rules? I am specifically interested in how to systematically (automatically) convert predicates involving existential quantifiers.


texts: How do I construct a doubly connected edge list given a set of line segments?

texts:
For a given planar graph $G(V,E)$ embedded in the plane, defined by a set of line segments $E= \left \{ e_1,...,e_m \right \} $, each segment $e_i$ is represented by its endpoints $\left \{ L_i,R_i \right \}$. Construct a DCEL data structure for the planar subdivision, describe an algorithm, prove it's  correctness and show the complexity.

According to this description of the DCEL data structure, there are many connections between different objects (i.e. vertices, edges and faces) of the DCEL. So, a DCEL seems to be difficult to build and maintain.

Do you know of any efficient algorithm which can be used to construct a DCEL data structure?


texts: Can an Earley Parser be made into a fuzzy parser similar to the Levenshtein Automata Algo for DFA?

texts: There's a way to perform fuzzy parsing (accepts strings even with typos to a certain edit distance), with a DFA and a run-time constructed Levenshtein Automata of the input word.  Can something similar be done with an Earley parser?  I'm finding it hard to understand the algorithm, let alone answer this question.


texts: What is the complexity of multiplying a matrix by a scalar?

texts:
I would like to know the complexity of multiplying a matrix of $n\times m$ size by a scalar $\alpha$?

In fact, I have a directed graph $G=(V,E)$ represented by an incidence matrix $M$. I would like to calculate the transpose of this graph, i.e., inverse the directions of the edges. I think that if I multiply $M$ by $-1$ I will get the transposed graph. Am I right?

If I am right, what is the complexity of multiplying a matrix by a scalar?
If I am not, where is my mistake and what is the complexity of multiplying a matrix by a scalar anyway?

I think the complexity is $\Theta(n\cdot m)$.

Thanks.


texts: How is this formula for dynamic array reached?

texts:
I am reading through Skiena's "The Algorithm Design Manual". He analyses the number of copy operations performed in a dynamic array.

  "Suppose we start with an array of size 1, and double its size from $m$ to $2m$ each time we run out of space. This doubling process involves allocating a new contiguous array of size $2m$, copying the contents of the old array into the lower half of the new one. The apparent waste is in the recopying of the old contents, on each expansion."

Skiena then asks:

  "How many times might an element have to be recopied after a total of $n$ insertions?".

He then gives a formula for calculating the total number of movements $M$, for $n$ insertions, which is

$$\mathbf{M}=\sum_{i=1}^{\log n} i\cdot\frac{n}{2^i}.$$

His explanation is:

  "Well, the first inserted element will have been recopied when the array expands after the first, second, fourth, eighth, ...insertions. It will take $\log_{2}n$ doublings until the array gets to have n positions. However, most elements do not suffer much upheaval. Indeed, the $(n/2 + 1)$st through $n$th elements will move at most once and might never have to move at all."

But I really don't understand how he draws the formula from that. Can anyone help me understand how he reaches it? Mainly what I can't understand is why he is multiplying $\frac{n}{2^i}$ by $i$.


texts:
I am searching the content of this topic but I am not sure what should be the content for this topic. This is relate to Computer Network.
My topic is Physical layer services & hardware protocols.

What should be content for this topic.


texts:
Why should computer designers trade off clock rate against cycle count? Can somebody explain this sentence for me? Shouldn't it be that when the clock rate increases the cycle count decreases?

I don't understand why the cycle rate and the cycle count are not proportional.


texts: Sum weighted nodes between nodes in a DAG efficiently

texts:
Suppose we have a directed acyclic graph $G=(V,E)$, such that all vertices have a addible weight, e.g. there is a function $weight: V \to \mathbb{R} $. Moreover two vertices $v,w \in V$ are given and we write $G_{v,w}$ for the subgraph of $G$ that consists of all vertices and path between $v$ and $w$, both included.

The task is to compute the sum of the weight $weight(u)$ of all vertices $u \in G_{v,w}$.
In addition if $v'$ and $w'$ are two vertices, with $G_{v,w}\subset G_{v',w'}$, then the computation on $G_{v,w}$ should not be repeated (kind of divide and conquer, but on subgraphs) to compute the weight of $G_{v',w'}$.

Is that possible?


texts: How can one simulate a PDA with a FIFO queue PDA?

texts:
I'm trying to figure out how a pushdown automata (PDA), which we know uses a stack (LIFO) can be simulated by a queue (FIFO). I understand that in a regular PDA, we only have access to the top most element which can be popped. When we push something, it goes to the top of the stack.

In a queue, as I understand, elements get "pushed" to the top, but pop from the bottom. Thus, first in first out.

In a stack (LIFO) PDA, let's say we push 'a'. It's at the top of the stack, and when we pop, we pop 'a' since it is at the top.

In a queue (FIFO) PDA, when we push 'a', it is at the top, but when we pop, it will be from the bottom of the queue and thus it will not be 'a' (assuming the size is greater than 2).

So how can we simulate a regular PDA which uses a stack, with a FIFO (queue) PDA?


texts: How to we prove if a right linear language is ambiguous?

texts:
Considering the following language as an example:
$$\begin{align}
S &\rightarrow aS \mid bA \\
A &\rightarrow bA \mid aB \mid aD \mid \varepsilon \\
B &\rightarrow aB \mid \varepsilon \\
D &\rightarrow aD \mid \varepsilon
\end{align}$$
This has ambiguous transitions on the string $ba$, but how do we prove in general that a right linear language is ambiguous. Is there an algorithm for this?


texts: Given a set of disjoint line segments in the plane, prove (or disprove) that you can always join the line segments to make a near-triangulation where the vertices are the endpoints of the segments, the outer face is a cycle and every segment is an edge of the triangulation.


texts: What is the worst case time-complexity of removing the root of a Binary Search Tree?

texts: My answer is constant time O(1) since an implementation would naturally have the pointer to the root. However, the solution guide I am looking at argues it is O(logN).


texts: What is an optimal online algorithm and how to design it to solve NP-hard problems?

texts:
To solve an NP-hard optimization problem optimally, we can use mathematical programming or brute force techniques. I would like to know if it is possible to solve the problem in an online fashion optimally? Is there any mathematical tool that can perform this task? I can design an online algorithm to solve the problem but I cannot say it gives the best possible online solution. However, with brute force methods, I can guarantee for sure that the solution produced is the best possible offline solution.
This question comes to my head when trying to compare my online algorithm to something; an online optimal algorithm, to see how well my online algorithm is performing. In the offline case, it is easy for me to compare. Once I have my offline algorithm, I implement a brute force or a mathematical program and I do the comparison. How to do the comparison for the online case?
EDIT: An online algorithm should make decisions in an irrevocable way.


texts: How to determine enumerability after applying Rice's theorem?

texts:
To my knowledge, lots of languages can be classified as undecidable after applying Rice's theorem, for example {"M" | L(M) is regular}.

But what I am not sure is, how to determine if a language is enumerable after applying Rice's theorem? I reckon we can examine that whether the M halt on some specific input, i.e. test if L(M) is an empty set. Am I right? Is there any principled way to determine a language's(composed of lots of Turing machines) enumerability?


texts: Easy-to-describe example of uncomputable function

texts:
After teaching my philosophy of cognitive science undegraduates what a Turing machine is, I mentioned that there are functions that can't be computed using a Turing machine.  A curious philosophy major asked for an example of such a function.  Most of the students in the class are not CS students and need not be mathematically adept, so I am limited as to what I can say, except to those students who want to hear more outside of class.

The only example of a particular function that is uncomputable that I could come up with off the top of my head was the halting problem, but that would have required a substantial digression, and it would seem quite obscure to most of the students if I walked them through it.  It would also not be sufficiently useful to explain to the class why there must be uncountably many functions that are not Turing-computable.  (First step: teach the countable/uncountable distinction.)

Is there an example of an uncomputable function that's relatively easy to describe and understand--more so than the halting problem?


texts: What is the contradiction in the proof of the halting theorem?

texts: In the standard proof of the halting theorem, you are asked to assume that a TM_0() exists that takes another TM_1() and a string W and outputs whether TM_1() halts or executes forever right on string W, right? The proof seems to be to assume that such a TM_0() exists. Now a new TM_2() is taken that takes TM_0() as input as halts if TM_0() executes forever, and executes forever if it halts. Now from what I understand such a TM_2() is supposed to mean a contradiction, which in turn implies that TM_(0) is a contradiction. I have trouble understanding how this step in TM_2() constitutes a contradiction. All these steps seem reasonable to me.


texts: How is $ n^{log(n)} > n^c $ always for any c?

texts:
I was going through the questions in MIT quiz : Question 2 g
and I found this

How is  $ n^{log(n)} > n^c $ always for any c ?

what if c > log(n) ?


texts: The Interleaved Transition System for 2 Independent and Concurrent Transition Systems

texts:
This question is about Model Checking for Software Formal Verification
How do you model the joint behavior of 2 independent and concurrent transition systems?

Specifically, given the two independent and concurrent Transition Systems below; TS1 and TS2 (left to right).

A tutor proposed that the resulting Interleaving Transition System ITS is

I understand how all the shown states and transitions of this ITS were gotten, however, why is there no transition from state (l1,q1) to (l3,q2)--as would be expected if both TS1 and TS2 transitioned on action a?


texts: Does $P/O(1)$ equal to $P$ if solver needs to consider smaller inputs?

texts: Suppose that $F$ is a problem such that for every $n$, there is a program of length $O(1)$, running in polynomial time to $n$, that solves $F$ correctly on all instances of size less than $n$. Can $F$ be solved in polynomial time? That is, does there exist a single polynomial time algorithm that solves $F$ on all instances?


texts: Turing Machines: What is the difference between the language realised by a problem and the language for which the TM accepts on?

texts:
A decision problem A corresponds to the language L1 if L1 contains all of the solutions to A.

A language L2 is defined as the set of all inputs to which a TM halts and accepts.

What is the link between these two languages?


texts: Minimum number of moves to reach a grid point by modified knight in variant chessboard

texts:
I apologize if this is not the right board to post this question but I'm cross-posting from the mathematics board. I am dealing with a computational question that extends the question posed in https://math.stackexchange.com/questions/104700/minimum-number-of-moves-to-reach-a-cell-in-a-chessboard-by-a-knight to the variant form of chess posed in https://math.stackexchange.com/questions/710815/knight-move-variant-can-it-move-from-a-to-b. Specifically, what is the number of minimum moves for a modified knight (call it ($\alpha,\beta$)-knight) that moves with $\pm\alpha$ and $\pm\beta$ along the coordinates (instead of the usual $[\pm 2, \pm 1]$)) in any direction to reach a point $(x, y)$ starting from the origin (0,0)? This would mean moving from $(x,y)$ to any of the following: (±$\alpha$,±$\beta$), (∓$\alpha$,±$\beta$), (±$\beta$,±$\alpha$) or (∓$\beta$,±$\alpha$). We can assume without loss of generality that $x \geq y$.

This is similar to the question posed in this forum here: Knight on a chessboard. I'd like to know if there is a closed form answer rather than a solution that requires BFS because I would like to work with a chess board (or coordinate grid) that is $N \times N$ where $N$ is large (e.g. $10^6$).

My initial thoughts of how to approach this is as follows:

Modify the equation to reach either the $x$-axis or the diagonal as well as the number of subsequent moves from the diagonal to reach the origin as solved in https://math.stackexchange.com/questions/104700/minimum-number-of-moves-to-reach-a-cell-in-a-chessboard-by-a-knight.
Solve this problem computationally with a recurrence equation that can be solved using dynamic programming (thought I suspect for larger$N$ in a $N\times N$ chessboard for large $\alpha$ and large $\beta$, this becomes intractable). Would this be more feasible than the BFS solution posted in: Knight on a chessboard?
Use the logic behind the proof posted in https://math.stackexchange.com/questions/710815/knight-move-variant-can-it-move-from-a-to-b to come up with an analytical solution for a recurrence equation rather than try to solve it computationally.
Graph approach using Dijkstra's algorithm akin to solution posted in https://math.stackexchange.com/questions/1585538/chess-knight-move-in-8x8-chessboard. Again, this may become computationally intractable unless this is solved using sparse graphs.

Any suggestions would be appreciated.


texts: Complexity of $O(\log(n^n))$ vs $O(\log(n!))$

texts:
Is $O(\log(n^n)) < O(\log(n!))$? Is there any good/practical algorithm with this kind of complexity?

And also, to check my understanding of algorithmic complexity, are these two $> O(n\log(n))$?

I'm just starting with this topic and not really sure if I'm getting it right.

Thanks and stay safe.


texts:
I am studying about Particle Swarm Optimization (PSO) and I was wondering what the user-defined constants in the update equations are for.

First update equations:
$v(t) = w*v(t) + c_1*rand*(x_{best} - x) + c_2*rand*(g_{best} - x)$

$w$ is known as the weight/inertial constant. Usually values here are in the interval $(0,1)$.
What are $c_1$ and $c_2$ for?

Thanks


texts: Exact meaning of $2^{\mathcal{O}(f(n))}$

texts:
In Sipser's Introduction to the Theory of Computation he uses the notation $2^{\mathcal{O}(f(n))}$ to denote some asymptotic running time.

For example he says that the running time of a single-tape deterministic turing machine simulating a multi-tape non-deterministic turing machine is

$\mathcal{O}(t(n)b^{t(n)})=2^{\mathcal{O}(t(n))}$ where $b$ is the maximal number of options in the transtition function.

I was wondering if someone can clarify the exact definition of this for me:

My assumption is that if $g(n)=2^{\mathcal{O}(f(n))}$ then there exists $N \in \mathbb{Z}$ and $c \in \mathbb{R}$ s.t.

$g(n) \leq 2^{cf(n)}=(2^{f(n)})^c$ for all $n>N$.

Thank you


texts: How many possible policies in a Markov Decision Process?

texts: If a policy yields an action for a state, how come a 3-state MDP with 2 possible actions, i.e. $S = \{Hot, Mild, Cold\}$,  $A = \{East, West\}$, has 8 possible policies? Isn't it 6 if there are 2 possible action for every state?


texts: XOR operation to swap to value without additional variable

texts:
I'm breaking my mind to find a good explanation to split two variables with the XOR operation.
The operation is the following:
x ^= y # =>                      (x ^ y, y)
y ^= x # => (x ^ y, y ^ x ^ y) = (x ^ y, x)
x ^= y # => (x ^ y ^ x, x)     = (y, x)

and my doubt is about the second line, in particular (x ^ y, y ^ x ^ y) = (x ^ y, x)  how I can have the result X from the operation y ^ x ^ y?
I know that y^y = 0, but in the previous case I can not say that y^x^y is equal to x.
What I'm losing here?
Source


texts: Time Complexity - Reducing Square Matrix to Diagonal Matrix (using Gaussian Row Elimination)

texts:
Given: A Square Matrix where each entry is an integer (either positive or negative). The magnitude of each integer entry is at most $m$ bits. The size of the Square matrix is $nXn$.

Objective: Reduce the Square Matrix to a Diagonal Matrix form using Gaussian Row Elimination.

Query: What is the most efficient algorithm and its time complexity for the above?

Comment: Most sources discuss the number of operations but not the total computational complexity. The obvious method is to use the text book method of row elimination. But i am assuming in the worst case, it is possible for the intermediate matrix entries to blow up exponentially in their size (w.r.t. to $m$). Thus, i am not clear.

Can someone help with the most efficient algorithm to achieve the above and its time complexity? (a clear reference to a textbook/source where that algorithm as well as its complexity is derived would be equally great).

P.S. I was suggested this link 1 but it is not very clear (either Algorithm or its complexity)


texts: Mini-Games for Artificial Intelligence Course

texts:
I am going to have Introduction to Artificial Intelligence in this semester & I know that our main resource would be "Artificial Intelligence A Modern Approach", since I want to learn deeply and Implement all the algorithms we are going to learn, I want to implement a simple intelligent mini-game for each material in the course.
so my question is that what games would be best for each topic? the only ones I could come up with were a Sudoku Solver and a simple player vs. computer Tic-Tac-Toe.


texts: I am trying to understand what is MaxSNP-complete. I have read the wiki definition. I would like to get the intuition behind it. My knowledge of computational complexity is very basic.


texts:
I have a (stupid ?) question about complexity theory. It's about a "proof technique".

I want to compare 2 models of computation. I want to prove that for each langage recognized in polynomial time by a machine of the first model, there exists a machine of the second class that recognizes the same langage in polynomial time. Can I use this argument in my proof :

  Let M be a machine of the first class that recognizes a langage L in time T(n) (where T is a polynomial, and n the size of the input word). Let N be a machine of the second class that is able to computes T(n) ...

The idea is to use the knowledge of T(n) to have a bound on the space used on each input by the machine of the first class, which that makes the construction of the machine of the second class easier. However, it seems a bit strange to say that we explicitly know T(n)... Is it allowed ?


texts: Does every undecidable problem contain a decidable subset?

texts: I know being a decidable language doesn't necessarily mean that every subset is of it is decidable, but does every undecidable language contain a decidable subset?


texts: Output distribution of neural network with normally distributed weights

texts:
I stumbled upon a statement like the following, in the context of prediction (classification) with a neural network: "If we predict the class of a given data point $x$ with random weights, the output will be random and thus the classification will be wrong in most cases." This is true, no doubt about that. But what would be the distribution of the output in the following example:
input dimension=1, 0 hidden layers, weight $w$ distributed $N(0, 1)$ (standard normal distribution), activation function=sigmoid$=\sigma(x)=\frac{1}{1+exp(-x)}$, and input=1? We would have to compute the distribution of $\sigma(w)$. The expected value is, which seems reasonable, $\frac 12$, because $\int_\mathbb{R} \frac{exp(-\frac 12 x^2)}{(1+exp(-x))\sqrt{2\pi}}dx=\frac 12$, according to Wolfram Alpha. The variance is not as easy anymore, with an approximate 0.043379. Does anyone of you know how to compute the complete distribution?

Thanks,

Leon


texts: How can I understand the multi-class version of "shattering" intuitively?

texts:
I'm learning machine learning. VC dimension is a good way to measure the complexity of hypothesis class for binary classifier and has a very good intuitive explanation from shattering.
When we discuss multi-class problems, we will use Natarajan dimension.
I know that both dimensions are based on the "shattering" concept.
When we discuss VC-dimension, shattering means $H$ have all the behaviors on a set of size less than $VCdim(H)$. That is:
Let $C=(c_1,\dots,c_d)$ be a shattered set by $H$.
Denote the restriction of $H$ to $C$ by $H_c$.
$$H_c = \{(h(c_1),\dots,h(c_d)):h\in H\}$$
Then $$|H_c| = 2^d$$
However, according to the definition of shattering on Page 403 of the book "Understanding Machine Learning: from theory to algorithms"(You can click the link to download the book.), the multiclass version of "shattering" is as follows:

We say a that a set $C\subset X$ is shattered by $H$ if there exist 2 functions $f_0,f_1\colon C\to [k]$ such that

for every $x\in C$, $f_0(x) \ne f_1(x)$.

for every $B\subset C$, there exists a function $h\in H$ such that

$$\forall x\in B, h(x)=f_0(x)\ and\ \forall x\in C \backslash B, h(x) = f_1(x)$$

Here, $H$ does not have all the behaviors on a set of size less than the Natarajan dimension. That is,
$$|H_c| \ne k^d$$ when $k>2$.
How do you understand the definition of the multiclass version of shattering, especially this point?


texts: Is this FA really equivalent to the given regular expression?

texts:
From the picture, the automata can accept $(\text L|\text D)^*$ following say $\_\text L\text D$, but in the formula above $(\text L|\text D)^*$ can't follow the $\_\text L\text D$.

So the Automata in the picture is not equivalent to the RE?


texts: is there any hardware device to convert source code into machine language?

texts: Is there any hardware device inside computer that helps to convert high level language into machine, like compiler and assembler ?


texts: Kripke Models - evaluating the meaning of $\Box\Box p$

texts:
In Kripke models the evaluation of $x \vdash \Box p$ would be that every world reachable from $x$ satisfies $p$.

But how would the truth of $\Box\Box p$ be evaluated in Kripke models?