texts: Matching participants to activities over many rounds

texts:
I have a group of N participants, and I need to assign them to M activities. Each activity has a different capacity, from 1 to N.

Each participant ranks the activities in order of preference, and no two activities can share the same ranking.

This happens for many days, and the goal is to:

ensure that no participant is in the long run, worse off than most other participants
ensure that if a participant ranks an activity with excess capacity as first, they are always assigned that activity
ideally, assign no one to their last choice

So for example, Alice can always get her first choice even if Bob only gets his first choice half the time, but only if Alice never picks oversubscribed activities.

I'm sure this is an existing problem, but I'm struggling to find out what it's called. Does anyone know? Or if it's not an existing problem, any thoughts as to a good algorithm for solving it?


texts: P Vs NP can never be proven one way or the other!

texts:
Okay, so I was reading a bit about P vs NP problems. And I found out that proving P Vs NP is an NP problem.

And since if we prove that any problem in NP is a P that would mean that we have NP=P.

So by that logic either NP==P or it can never be proven that NP is not P and if somebody proves that, then won't they be contradicting the result itself. I mean they solved one NP problem which was this proof so by that logic all other problems should now be in class P.

Let me know if I got something wrong here.


texts: Why does ε-greedy $Q$-learning not oscillate?

texts:
I have a intuitive question on the convergence of $Q$- learning. In $Q$ learning for each step a $Q$- value is learned for the state-action pair where the action is selected according to the $\epsilon$-greedy policy determined by $Q$ values.

Now my question is due to $\epsilon$-greedy policy (i.e. due to exploration) is it not possible that the $Q$ values oscillates and does not converge ? each time I am giving chance to non-greedy action his value is improved and may be higher than the value of greedy action after some steps and this becomes greedy now and the same thing continues. Is choosing a small $\epsilon$ enough to prevent this ?


texts: Chomsky Hierarchy of a Computational Model

texts:
I am interested in knowing the Chomsky hierarchy of a particular computation model.  Also, I would like to know if it is equivalent to Finite State Machine or is Turing complete.
This computation model is called marbles and circles. For this model, the variables take a constant word size w which matches the problem. A marble contains a unique key and a value. A marble can not contain another marble. A circle contains a unique key and a value. A circle can intersect another circle or be completely inscribed by another circle. The marbles only exist once if they overlap the circles. This is shown by the marbles on the intersection of the two circles.
There are computer operations in this model. The operations take a constant time and constant space. The operations are below. The rest of operations like increment a loop counter are free (zero cost).
add marble(circle)
remove marble(circle, marble)
move marbles(marble, from circle, to circle)
remove marble (marble, circle)
add circle (overlaps, inside of)
remove circle(circle)
Restrictions:

circles are a countably infinite set
axiom of countable choice is allowed, but not the whole axiom of choice
marbles do Not contain other marbles
rest of software operations such as loop counter increment is free (zero cost)


texts: How do I know how many matrix operations a GPU can do in parallel?

texts:
My code projects have relied quite a bit on GPU acceleration. But I work with the GPU not through a low level language like OpenGL, but through a few layers of abstraction, namely GPU.js on top of WebGL. So I didn't really have to learn the lower level fundamentals of how exactly the matrix operations get assembled on the hardware.
But I notice that in WebGL, each GPU has a limit to how large of a matrix I can operate on, usually limited to the maximum screen resolution the GPU supports. So if I had to guess, I would think the maximum number of matrix operations I can execute at one time in parallel on a GPU is 7680 x 4320 x 3 (width x height x 3 color channels), with the RTX 3080 for example:

99.5 million operations.
But I suspect it's more complicated than that. Is this in any way accurate? If not, how can I figure out how many matrix operations a GPU is capable of at one time?


texts: What is the state-of-art ML techniques for the problem of writing algorithms?

texts: Could any existing ML technique be used, for example, to solve the problem of building a lazy Sieve of Eratosthenes in Haskell? By that, I mean a program that, given a specification (a dependent type inhabited by infinite, ordered lists of prime numbers), builds a program of that type, with the same complexity of the known, manually designed algorithm?


texts: Do we need both path compression and union by rank together in disjoint set data structure?

texts:
I was studying disjoint set data structure. I studied path compression and union by rank. Initially all the elements are single in their own set and by performing unions we can combine different sets.
Now since we are performing union by rank the height of the resultant tree is always minimum. At this point i think that we might not need path compression at all. Am i right? If i am wrong please explain me with an example.


texts: Have non-regular language classes of infinite words been studied?

texts:
For regular languages we have $\omega$-regular languages which extend them to infinite words.

Are there such extensions for CFG's, CSG's and recursively enumerable languages?


texts: How to propose a method to construct an automaton?

texts:
Given $0 \leq m < k$ and $p \geq 2$ it's defined $$A_{k,m,p} = \{ \alpha \in  \{0,1,\dots,p-1\}^* | \alpha \text{ is a p-ary representation of } x \backepsilon x \text{ mod } k = m \}$$

It is needed to give a general method to construct an automaton which accepts this language. I'm trutly lost about the procedure in this. Any hint would be helpful.

Some observations about this: The automaton is not specified (i.e. could be NFA or DFA) and the numbers are static.


texts: Definition of Turing Machine as a language acceptor

texts:
The following is an excerpt from the book "An Introduction to Formal Languages and Automata" by Peter Linz.

My question is, why is $\Sigma^+$ used and not $\Sigma^\ast$?


texts:
I'm sure that in my following question my reasoning is extremely simplistic and flawed, but I think if someone answered this it would help me understand what the P vs NP conundrum is. So here is my question: why is the following not a proof that NP does not equal P?

Scenario: A computer is given an n digit number that it must guess. The digits of this number were randomly chosen. Since the digits are randomly chosen, there is no pattern for a computer to spot and therefore simplify the problem. It must try all solutions, of which there are 9^n.

Does the problem with my reasoning lie with the assumption that the numbers are truly random? Is randomness impossible and there will always be an underlying pattern to how seemingly "random" numbers were chosen


texts: If P = NP, can all NP problems be solved within time $O(n^k)$ for fixed $k$?

texts:
I came across this question while studying for an exam:

  T/F: Suppose we can show for some fixed $k$, an NP-complete problem P has a time $O(n^k)$ algorithm. Then every problem in NP has a $O(n^k)$ time algorithm.

I think the answer is false, since we can't reduce NP-complete to NP-hard in linear time, right? Or am I completely misunderstanding reductions/NP problems? Any help would be greatly appreciated. Thank you.


texts: Are Context-Free Grammars with only one Production Rule always Unambiguous?

texts:
Consider the following (Context-Free) Grammars with only one production rule (not including the epsilon production):

$S \rightarrow aSb\;|\;\epsilon$
$\require{cancel} \cancel{S \rightarrow aSSb\;|\;\epsilon}$
$S \rightarrow aSbS\;|\;\epsilon$
$S \rightarrow aSaSb\;|\;\epsilon$
$S \rightarrow aaSaaSbb\;|\;\epsilon$
$S \rightarrow aSbScSdSeSf\;|\;\epsilon$
$\require{cancel} \cancel{S \rightarrow aSSbcSd\;|\;\epsilon}$
etc...

Are all these Grammars unambiguous? Will every Grammar with only one production rule (not including the epsilon production) always be unambiguous? It would seem so, but I'm not totally sure.

  Edit: Vimal Patel has shown that examples like the 2nd and last are, in fact, ambiguous. Discounting these examples and assuming that the non-terminal symbol $S$ never appears next to itself, does my belief still hold?

Grammars that only contain one unique terminal symbol could be ambiguous. (ex. $S\rightarrow aSaSa\;|\;\epsilon$) However, Grammars with at least two distinct terminal symbols seem like they should always be unambiguous.

  Edit II: Vimal Patel has also shown that production rules which both begin and end with the non-terminal $S$ are ambiguous (i.e. $S \rightarrow SaSaSbS\;|\;\epsilon$) discounting this as well, does my belief still hold?

I've tried showing that Grammars like these are $LL(1)$. However, it seems only Grammars of the form  $S \rightarrow aSb\;|\;\epsilon$ are $LL(1)$. Grammars like $S \rightarrow aSaSb\;|\;\epsilon$ are not $LL(1)$. (Illustrated in the parse table below.)

Despite the example Grammar above not being $LL(1)$, it still seems to be unambiguous. Maybe it's simply a matter of using a higher $k$ for $LL(k)$?

In short, are (Context-Free) Grammars with only one production rule (not including the epsilon production) and at least two unique terminal symbols always unambiguous?

I would really love some help, any at all would be greatly appreciated.


texts: using orientation sensor data to predict image points

texts:
I want to use Android's gyro/accelerometer/magnetometer to predict (over a very short time interval) how image points corresponding to a fixed object will change (without trying to scan for them in the image).  In particular, suppose we have an object of known size with model points $v_1, \dots, v_N$.  In this question, all vectors are assumed to be in homogenous form.

Here is what I am trying:

Detect the object.  Let the pixel coordinates of the model points be denoted by $u_1, \dots, u_N$.  Given the calibration matrix $K$ and negligible lens distortion, solve the PnP problem to get rotation $R_0$ and translation $t_0$ from the coordinates in which the vectors $v_1, \dots, v_N$ are defined into camera-centric coordinates, shown in black in the image above.
In particular, the solution to the PnP problem solves the following equation.
$$
u_i = K \begin{bmatrix} R_0 &  t_0 \\ 0^\top & 1\end{bmatrix} v_i.
$$
Simultaneously query the Android rotation sensor for a rotation matrix.
This is the relative orientation from Earth coordinates to the device coordinates (colored frame in the picture above).
The direction of the this transformation is discussed informally in the Android developer site:

  The rotation vector represents the orientation of the device as a combination of an angle and an axis, in which the device has rotated through an angle $\theta$ around an axis ($x$,$ y$, or $z)$.

Let $R_1$ denote this rotation matrix.

Rotate the phone a small amount and query the rotation sensor again for $R_2$.
Render the predicted location to the pixel coordinates.  For this, lets assume the sensors and the camera are collocated, so that the transformation from camera coordinates to device coordinates is a pure rotation:
$$
D=
\begin{bmatrix}
0 & -1 & 0 & 0\\
-1 & 0 & 0 & 0 \\
0 & 0 & -1 & 0 \\
0 & 0 & 0 & 1
\end{bmatrix}
$$
This matrix maps the black frame to the colorful frame in the picture.
Note that the $+z$ axis of the camera frame (black in the picture) is meant to point out of the back of the phone, so that it constitutes a right-handed coordinate frame.

The transformation from the body coordinates of the object $v_1, \dots, v_N$ to the image coordinates in the perturbed camera frame $u_1', \dots, u_N'$ are given by
$$
u_i'
=KD\begin{bmatrix}R_2 R_1^\top & 0 \\ 0^\top & 1 \end{bmatrix} D \begin{bmatrix} R_0 &  t_0 \\ 0^\top & 1 \end{bmatrix} v_i,
$$
where we used the fact that $D=D^{-1}.$

Right now, I am stuck tying to verify that this equation actually works.  Here is a simple experiment (that I have tried in Python).
Let $v = (0, 0, 1)^\top,$ and suppose it is already defined in the camera coordinate frame, i.e., $R_0=I$ and $t_0=0.$
Moreover assume that $R_1= I,$
Then, I rotate the device by a small angle about the $x$ or $y$ axis (which are the same for the device and for the Earth because $R_1=I.$)
This rotation constitutes $R_2$ from the equations above.
When I try this in Python, this is what I observe for various counter-clockwise rotations:

test rotation of device :: expected result :: observed result

rotate device about $+x$ :: $x$ pixel coordinate increases ::  opposite behavior

rotate device about $-x$ :: $x$ pixel coordinate decreases :: opposite behavior

rotate device about $+y$ :: $y$ pixel coordinate decreases :: as expected

rotate device about $-y$ :: $y$ pixel coordinate increases :: as expected


texts: If a DFA can be simulated by a real program, can it be simulated by a TM

texts:
In proofs of decidability, we often want to simulate another model of computation by a Turing machine. But if I can simulate a $\mathsf{DFA}$ by, say, a C program, then is there some result which says that the $\mathsf{DFA}$ can be simulated by some $\mathsf{TM}$? Could a program be used in place of a $\mathsf{TM}$ in a proof of decidability?

I know that Java being Turing-complete would mean that it can simulate any $\mathsf{TM}$, so this is sort of the reverse of Turing-completeness I guess.


texts: Does the performance of matrix multiplication depend on the storage of the array?

texts: Two matrices can be stored in either row major or column major order in contiguous memory. Does the time complexity of computing their multiplication vary depending on the storage scheme? That is, I want to know whether it will work faster if stored in row major or column major order.


texts:
On a Turing machine, the state changes during the execution of the program. Von Neumann architecture implements this machine theory and typical computer hardware uses Von Neumann architecture.

Imperative programs uses the state to describes their computations.

Semantically, is correct to say that imperative program works like a Turing machine? If not, theoretically, what is the origin of state used by imperative programming?


texts: Reasoning about resources: "resource logics"?

texts:
Are there extensions of predicate logic which focus on resource models, possibly even in actor models?

And if so, would it be possible to reason on a meta-level on how many resources should be expended to find further proofs in the same or other systems?


texts: Is $n^2 \log n$ in $O (n^2)$ am confused

texts: I graphed the functions and when $n_0$ is greater than $3$, $cg(n)$ is always greater than $n^2 \log n$ so it would seem to me by definition that $m^2 \log n$ is in $O (n^2) $. I tried to prove it by dividing both sides of inequality by $n^2$ . The $c \ge \log n $. As n tends to infinity there will be values of c that are > than logn . I have to say if $n^2 \log n $ is in $O(n^2)$ . My classmate says it isn't to me it looks like it is.  It is 6.00 am here and my brain is mush so apologies if this is a really trivial questions and you are all laughing at my stupidity. It is a little confusing I admit. It seem to me that $n^2 \log n$ above $n_0= 3$ is always greater than $n^2$


texts: How come correctness proofs aren't tautological?

texts:
Consider the following function on binary trees, which is supposed to tell whether a given int is a member of a binary tree t:

type tree = Leaf | Node of int * tree * tree;;

let rec tmember (t:tree) (x:int) : bool =
  match t with
      Leaf -> false
    | Node (j,left,right) -> j = x || tmember left x || tmember right x
;;

If one wants to prove that this function is correct, one would need to define first what tree membership actually means, but then I can find no formal way of doing this except for saying that x is a member of t if and only if it is either equal to the root of t, or it is a member of the left or right subtree of t. This is essentially saying that x is a member of t if and only if  tmember t x outputs true.

What am I missing here?


texts: How was von Neumann's architecture turned into a parallel capable architecture and is there any limitations to that?

texts:
Back when von Neumann came up with his computer architecture parallel machines and multi-core processors weren't a thing but now almost all machines have multiple cores and are able to run programs in parallel since von Neumann's architecture was designed to fetch and execute instructions sequentially how did we turn it into a parallel capable architecture and is there any limitations that might make us consider other architectures for parallel programming in the future?
I tried doing some digging and all I have found was that modern computers used a modified version of von Neumann's architecture and such but nothing answering what I really want.


texts:
WhereTo(H,X) is searching for the place to set X (an integer) in a minimum heap-H.
The function is executing a binary search on a path of a heap.

Assumption: We have the specific path because it starts on the last available leaf which is the last index in the array that doesn't contain any value, and there is only one path to the top from there.  Returns the specific index where we should put variable X.
The main idea is to achieve time complexity of O(loglogN) to know exactly the index of the place to put X.

Implementation of the heap:
The element at index i has children at indices 2i
and 2i + 1 and parent at index floor((i) ∕ 2).

The problem is, I don't really sure how should I define 'Mid' using 'Low' and 'High'.

EDIT: I think I found the formula:

$Mid$ = $Floor(High/2^{Floor(Log(High/Low)/2)})$

Maybe it is an easy arithmetical problem.

Example(In the picture): While executing WhereTo(X), I want a binary search to start on the yellow path (next available slot from the leaf to the root and the mid to be 14 or 7 (at the beginning) and of course to be updated in every iteration

Thanks a lot for the help.


texts:
Some problems such as sorting have famous complexity lower bounds (ex: $O(n \log (n))$ in this case) but I feel that doesn't totally remove the possibility of improving algorithms by shaving constants. Are there any really non trival, perhaps not practical sorts, that have excellent constant performance? For example do there exist algorithms that say achieve $\frac{1}{2} n \log(n)$ number of comparisons as opposed to say mergesorts $1.44 n \log(n)$, and can this leading constant, be reduced arbitrarily low?

It oculd be the case these algorithms have running time

$$ 0.0001 n \log(n) + 9^{\text{Graham's Numbers}}n + \pi^{\pi^\pi} $$

But I am still curious if non trivial reduction of constants exists, or if someone has proven tight bounds on what the constants must be.


texts: What is the difference between a page and thread?

texts:
"Each process that is executed is divided into blocks of same size, called pages."
"Thread is a part of process being executed."

Are pages and threads both part(s) of process? Whats the difference between thread as a part of process and page as a part of process?


texts: Why do particles in particle swarm optimization converge to the global best when their personal best has just as much weight?

texts:
I know this is probably a really basic question but I just cant wrap my head around it right now.
So the basic PSO update formula is as follows:
$$\bar{v}_{n+1} = \omega \cdot \bar{v}_n + c_k \cdot r_1 \cdot (\bar{p}_{best}-\bar{p}_n)+ c_s\cdot r_2 \cdot (\bar{g}_{best}-\bar{p}_n) $$
velocity(n+1) = momentum_component + cognitive_component + social_component
Now both the cognitive part and the social part have the same weight to them on the updated velocity.
So when a particle is moving around the space and lets say the cognitive part pulls the particle in a certain direction while the social component pulls the particle in the opposite direction, shouldnt the particle be stuck forever? Or at least go back and forth never converging?
However if I run the basic vanilla PSO algorithm the particles always seem to converge to the gbest as if their pbest has barely any influence.


texts: Methods for generating DAG with small Minimum Path Cover

texts:
On a directed acyclic graph $G=(V,E)$ the Minimum Path Cover (MPC) is the minimum number of paths that can be constructed on the DAG such that all vertices are covered by at least one path.
If one was attempting to create examples of DAGs with small MPCs (i.e. use a program to create examples of DAGs with small MPCs), how could this be done? What condition would have to be satisfied?


texts: What is the difference between $x:A$ and $x \Xi A$?

texts:
Given a type hierarchy $(\tau,\sqsubseteq)$ and a signature $(VSym, FSym, PSym, \alpha)$, one says that the typing function $\alpha$ assigns to each variable symbol $x \in VSym$ a non-empty type $A \in \tau \setminus\{\bot\}$ and is written as:
$$ x: A \tag1$$
Furthermore, for every type $A \in \tau \setminus\{\bot\}$, there is a predicate symbol $\Xi A \in PSym$ called the type predicate which tells us if or not a certain $x$ is an instance of type $A$. We write it as:
$$x \Xi A \tag2$$
That makes me think what set constitutes the domain of a predicate symbol. Clearly, if the domain is $VSym$, then $(1)$ and $(2)$ mean exactly the same thing, and therefore, would be a redundancy of definition.
If not, which is surely the case, how do they differ? In particular, can you tell if a certain object is an instance of a certain type and not just a variable symbol with the given type assigned to it (or vice versa)?
More precisely, if a predicate symbol is a function from a certain domain to the set $\{\mathrm{True},\mathrm{False}\}$, what exactly is the domain of this map? Is there any overlap of this domain with $VSym$?
I am reading the chapter on first order logic from Deductive Software Verification – The KeY Book. (I am not fully sure if this question fits in a mathematics or a computer science forum.)
Thank you for your time.

Background:
Please refer to this document (the first couple of pages actually) to update yourself with the relevant ideas and definitions. Here's a brief summary.

A type hierarchy is a pair $\mathscr T = (\tau,\sqsubseteq)$, where

$\tau$ is a set of type symbols;
$\sqsubseteq$ is a partial ordering on $\tau$, called the subtype relation;
there are two designated type symbols, the empty type $\bot \in \tau$ and the universal type $\top \in \tau$ with $ \bot \sqsubseteq A \sqsubseteq \top \forall A \in \tau$.

A signature (for a given type hierarchy $\mathscr T$) is a
quadruple $\Sigma = (VSym, FSym, PSym, \alpha)$ of

a set of variable symbols $VSym$,
a set of function symbols $FSym$,
a set of predicate symbols $PSym$, and
a typing function $\alpha$,

such that

$\alpha(v) \in \tau_q := \tau \setminus\{\bot\}\ \forall v \in VSym$,
$\alpha(f) \in \tau_q^* \times \tau_q\ \forall f ∈ FSym$, where $\tau_q^*$ is the set of all (possibly empty) sequences of elements in $\tau_q$, and
$\alpha(p) \in \tau_q^*\ \forall p \in PSym$.
There is a function symbol $(A) \in FSym$ with $\alpha((A)) = ((\top),A)$ for any $A \in \tau_q$, called the cast to type A.
There is a predicate symbol $\doteq \in PSym$ with $α(\doteq) = (\top,\top)$.
There is a predicate symbol $\Xi A \in PSym$ with $\alpha(\Xi A) = (\top)$ for any $A \in \tau$, called the type predicate for type A.

Notation: We write

$v : A$ for $\alpha (v) = A$,
$f : A_1,...,A_n \to A$ for $\alpha(f)=((A_1,...,A_n),A)$,
$p: A_1,...,A_n$ for $\alpha(p)=(A_1,...,A_n)$,
$x \Xi A$ (read: $x$ is an instance of $A$) for $\Xi A(x)$,
$x \doteq y$ for $\doteq(x,y)$.

NOTE: Some texts (such as the document linked above) implicitly do the type assignment carried out by $\alpha$ and write down the definition in the standard notation mentioned above.


texts: Shortest path that passes through specific node(s)

texts:
I am trying to find an efficient solution to my problem. Let's assume that I have positive weighted graph G containing 100 nodes(each node is numbered) and it is an acyclic graph. So there cannot be any edge like 2,2 or 2,1. I have got a list of nodes let's say 10 from graph G. Let's say each of these nodes are also in an array. I am looking for a way to find the shortest path's total weight from node 1 to 100 that passes through at least some particular(let's say 5) of those nodes from that list.

To simplify it, consider graph with 6 nodes, 0...5, now node 1 and 4 are marked as points where we could specify to pass. Let's say existing paths are 0-1-2-5, 0-3-4-5, and 1-4. Now let's say all edges are weighted as 5 except 3 to 4 is weighted as 1. If we run a shortest path algorithm this would basically find the path 0-3-4-5 as it is weighted 11. However if we run an algorithm specifying minimum amount of specified points and try the amount 2. Then the algorithm should be running on 0-1-4-5 which is weighted as 15.

I have written this way

    shortestPath(destinationNode, minAmount)

        if(destinationNode == srcNode && minAmount < 1)
            return 0

        else if(destinationNode == srcNode && minAmount > 1)
            return INFINITY

        int destNo = destinationNode get number
        int cost = INFINITY
        for (int i = 0; i < destNo; i++)
            if (d[i][destNo] != null)
                int minimumAmountCount = minAmount;
                for (int j = 0; j < marked.length(); j++)
                    if (marked[j] == i)
                        minimumAmountCount = minimumAmountCount - 1;

                cost = MIN(cost, shortestPath(Node(i), minimumAmountCount);

        return cost;

Basically we call this algorithm by using the our destination node and minimum amount of nodes from that list. Firstly we want to make sure that this is a recursive function and it should have a stopping point, which would be when passed destination is equal to source node(which is essentially node #0). The second case we need to check is whether we visited enough amount, so if it is less than 1(0 or negative number) then we visited enough points and return 0 as distance from node #0 to node #0 would be 0. If we did not visit enough amount then we return infinity so that algorithm would consider other paths.

So in order for the returning part to work, we have to define the destination node's number(if we consider that we have 100 nodes it would be node #99 at the initial start) and initialise cost as infinity.

Then we run a for loop that starts from 0(essentially node #0) till our current node number, this is because there are no backwards edges on the graph. By using node number we check from the matrix whether there is an existing weight for those nodes. If it exist then we initialise a variable for our current minimum amount and then run a loop and check if source to the current destination is in the list of marked nodes. If it is marked then we simply decrement the minimum amount.

For the final step we run the function again by changing destination as the current source and with the current minimum amount.

But it seems very expensive, considering the fact that the worst case complexity of  nested loop takes O(|Node|^2) and total recurrence would take O(|Node|^2 * |Edges|). So is there any other efficient solution for this problem?


texts: Traversing a graph in finite time, maximizing utility

texts:
I am working on a problem in robotics, where we have a problem of having finite time horizon T, and a set of actions. Each take some time to perform and each have a utility. We can transition from any action to another after completing that particular action, and each transition takes a unique, finite time. Our goal is maximize the sum of the utilities after the time horizon has ended.

I am currently thinking of this as a graph problem, and have some trouble formalizing it.

Let the nodes be the actions, and the edges be the transition between the actions. Each node have some value, and take some time T. How do I find the path in this graph which maximizes the utility, and takes time less than or equal to T?


texts:
What is the regular expression for the following language?
$$L = \{acbc: a,b,c \in \{0,1\}^+ \}$$
maybe we can say  $$L = ((0 + 1)^+ 0 (0 + 1)^+ 0) + ((0 + 1)^+ 1 (0 + 1)^+ 1)$$
Is it true??


texts: Stacking things of different thickness to approximate desired thickness

texts: I have $N$ objects of different thickness. Is there an algorithm to determine which of those objects should be stacked on each other to get as near to a desired thickness as possible? (I don't want to numerically check every combination.)


texts: Can languages that are not closed against the Kleene star be regular?

texts:
I've been working on finding a regular expression for the following language for quite some time now ($\Sigma =\text{{0, 1}}$):

  $
\text{L = {w | the difference between the number of 0's and 1's in each prefix of the word is less than or equal to 1}}$

I haven't been able to find an expression for this particular language so far, so I was wondering if the language is regular at all.

The following came to mind, but I'm pretty dubious about its validity :

  Since $010$ belongs to said language, and by concatenation $010010$ does not, it would follow that this language isn't closed under Kleene star, hence it's not regular.

Am I wrong? If so, could you help with finding the solution to this problem?

Regarding the meaning of prefix in this context, the prefixes of the string $abcd$ are $\text{{$abcd, abc, ab, a$}}$.


texts: Primitive recursive functions and unbounded quantifiers

texts:
From what I know If the predicate $P(t,x_1,...,x_n)$ belongs to some PRC class $\zeta$ then so do the predicates

$(\forall t)_{\le y}$  $P(t,x_1,...,x_n)$

$(\exists t)_{\le y}$  $P(t,x_1,...,x_n)$

But what about the unbounded quantifier? what difference does it make if I replace $(\forall t)_\le$ with $(\forall t)$ and also $(\exists t)_\le$ with $(\exists t)$ ?

Davis in his book page 43 says:

  Theorem 3.3: A function is primitive recursive if and only if it belongs to every PRC class

I saw a problem related to what I said that I couldn't solve, here it is :

  If $P(x)$ and $Q(x)$ are primitive recursive predicates which one of the following may not be primitive recursive:

$P(x) \rightarrow Q(x)$
$Q(z) \wedge P([\sqrt{x}])$
$\forall x(x \le y \rightarrow P(x))$
$\exists x(P(x) \wedge Q(x)) $

Since only one of the above choices is right, so I don't know 3 is the answer or 4!


texts: Algorithm to compute partitions of a graph in N cliques

texts:
does anyone know of an efficient algorithm to compute the partition of a graph in N cliques?

Notice that N is the number of the cliques and not the size of them.

I have heard of the 2 cliques problem, but I'm interested in the more general version.


texts: Is the 2nd parity bit in RAID 6 a simple calculation?

texts: I'm trying to understand how the 2nd parity bit or byte is set in RAID 6. I'm reading a paper by H. Peter Anvin, and it goes into Galois field algebra, which is somewhat new to me. Anyway, a rep from HP was trying to explain RAID 6 to me and she thought it was merely two XOR operations, one for the 1st parity bit and one for the 2nd.  This doesn't make sense to me, but since I'm still working through the paper I don't know if it reduces to something simple for RAID 6 as opposed to RAID n. It looks to me like the 2nd parity bit is quite a bit more complicated than the XOR based 1st parity bit. Is that true?


texts: Interval scheduling, unclear greedy proof

texts:
I am having trouble understanding the proof of the theorem, which states that the greedy scheduling algorithm produces solutions of maximum size for the scheduling problem.

The proof that I am referencing is here: Greedy Algorithm Proof

I don't understand how the proof tells us to make the the problem smaller and smaller, iteratively to select the first element, see whats left, then select the first element of the new set, see what's left, and so on.

Does anyone have an easier way to understand the proof?


texts: Kernel Perceptron vs Polynomial Perceptron

texts:
I was looking at Support Vector machines (SVM) kernels. Looking at Polynomial Kernel and Kernel Perceptron I was curious how they differ?

Work Done

Polynomial Kernel:

$d_{k+1}(x)=d_{k}(\bar{x})+\rho k(\bar{x}_{k}, \bar{x})\; \mbox{if}\; \bar{x}_k\epsilon\,C_1$

$d_{k+1}(x)=d_{k}(\bar{x})-\rho k(\bar{x}_{k}, \bar{x})\; \mbox{if}\; \bar{x}_k\epsilon\,C_2$

where $k(\bar{x}_{k}, \bar{x}) = (\bar{x}\cdot \bar{x}_{k}+1)^{q}$

Kernel Perceptron:

This is given by

$g(x)=\sum_{j=1}^{N}a_{j} K(\bar{x},\bar{x}_j)$

So as per my understanding a bias constant is added in former case when compared to later. So how does that impact and what difference does it make? Or am I missing something?

Any insights are appreciated.


texts: Why do all recent SAT solvers work on CNF instead of circuit SAT?

texts:
After the release of the AIGER library to handle and-inverter graphs sometime in 2006 (I think), some circuit SAT solvers were released in 2006-2008, and in a few SAT Races/Competitions there were AIG tracks. However since then it seems the focus has been entirely on either SMT or improving clausal SAT solvers.

Intuitively to me concentrating on circuit SAT seems to make a lot of sense: Many if not most problems are more naturally expressed as circuit SAT than CNF; circuits provide structural information that cannot be reverse engineered from CNF, but circuits can always be transformed into CNF; and at least the industrially significant field of logic synthesis seems to be a particularly good fit for AIGs.

So, what happened? Did it turn out that the extra structural information does not help solvers? Was AIG-based SAT solving a failed experiment?


texts: The space complexity of recognising Watson-Crick palindromes

texts:
I have the following algorithmic problem:

  Determine the space Turing complexity of recognizing DNA strings that are Watson-Crick palindromes.

Watson-Crick palindromes are strings whose reversed complement is the original string. The complement is defined letter-wise, inspired by DNA: A is the complement of T and C is the complement of G. A simple example for a WC-palindrome is ACGT.

I've come up with two ways of solving this.

One requires $\mathcal{O}(n)$ space.

Once the machine is done reading the input. The input tape must be copied to the work tape in reverse order.
The machine will then read the input and work tapes from the left and compare each entry to verify the cell in the work tape is the compliment of the cell in the input. This requires $\mathcal{O}(n)$ space.

The other requires $\mathcal{O}(\log n)$ space.

While reading the input. Count the number of entries on the input tape.
When the input tape is done reading

copy the complement of the letter onto the work tape
copy the letter L to the end of the work tape

(Loop point)If the counter = 0, clear the worktape and write yes, then halt
If the input tape reads L

Move the input head to the left by the number of times indicated by the counter  (requires a second counter)

If the input tape reads R

Move the input head to the right by the number of times indicated by the counter (requires a second counter)

If the cell that holds the value on the worktape matches the current cell on the input tape

decrement the counter by two
Move one to the left or right depending if R or L is on the worktape respectively
copy the Complement of L or R to the worktape in place of the current L or R
continue the loop

If values dont match, clear the worktape and write no, then halt

This comes out to about $2\log n+2$ space for storing both counters, the current complement, and the value L or R.

My issue

The first one requires both linear time and space. The second one requires $\frac{n^2}{2}$ time and $\log n$ space. I was given the problem from the quote and came up with these two approaches, but I don't know which one to go with. I just need to give the space complexity of the problem.

The reason I'm confused

I would tend to say the second one is the best option since it's better in terms of time, but that answer only comes from me getting lucky and coming up with an algorithm. It seems like if I want to give the space complexity of something, it wouldn't require luck in coming up with the right algorithm. Am I missing something? Should I even be coming up with a solution to the problem to answer the space complexity?


texts: Prove $ L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $ (mod$ $13) \} $ is regular or context-free or neither

texts:
$ L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $ (mod$  $13)  \} $

Exercises: If the language L is regular (build a DFA or regular expression)
else if the language L is context-free (build a grammar or PDA)
else if the language L is not context-free (Prove)

so

We know that $ww ^ {R}$ without any restrictions isn't regular, but it is context-free. but with additional above restrictions $ L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $ (mod$  $13)  \} $ I have no idea how to prove this. I think this language still isn't regular :

Let's take $n, m > p$ where $p$ is from pumping lemma and $n mod 13 = 0$ and $m mod 13 = 0$ and chose word
$s = a^{m}b^{n}b^{n}a^{m}$ and use the pumping lemma that is not regular. Well?

Any idea?


texts: number of comparison in sort algorith with special operation

texts:
Let's define: $ a_i:a_j \Longleftrightarrow  a_i < a_j;\ a_i=a_j;\ a_i > a_j $
So it is similiar to normal operation $<$, but $:$ give information when elements are equal.
I want show that lower bound for sort array of $n$ elements with this operation is $\Omega (n\log n)$.

I know proof for normal comparison. Nevertheless I can't solve it, I thought about it a long time, but without effect.  Can you help me ?

(It isn't homework, nowadays I am on holiday :))


texts: Is there an equivalent of lambda calculus for object oriented languages?

texts: Lambda calculus serves as a foundation for all sorts of functional languages and its various extensions are compiler targets for languages like Haskell, ML, etc. So what is the equivalent for object oriented languages? Is there a minimal object calculus that serves as the foundation for object oriented languages?


texts: Applications of the (cumulated) ruler function in algorithm analysis

texts:
In Chapter 2 (Page 76) of the book "An Introduction to the Analysis of Algorithms (2nd edition)" by Robert Sedgewick and Philippe Flajolet, the authors introduce two functions:

  Definition Given an integer $N$, define the ruler function $\psi_N$ to be the number of trailing $1$s in the binary representation of $N$ and the cumulated ruler function $R_N$ to be the number of trailing $1$s in the binary representations of all the numbers less than $N$.

For example, $\psi_{83 = 1010011} = 2$ and $R_{15} = 11$.

However, no applications of these functions in algorithm analysis have been shown in this chapter. Are you aware of any applications of $\psi_N$ or $R_N$ in algorithm analysis, particularly of divide-and-conquer algorithms?

I ask applications for $\psi_N$ or $R_N$ because the book does provide nice relation between the analysis of binary divide-and-conquer algorithms (mergesort, in particular) and the other two binary representations related functions: one for counting the number of bits in the binary representations of the numbers less than $N$ and the other counting the number of $1$s in the binary representations of the numbers less than $N$.


texts: Can I include some manual effort in creating an otherwise automated research prototype tool?

texts: I am a research student in the area of programming language/software engineering. I am claiming to provide an automated technique to solve a research problem in one of my papers. The prototype tool that I am creating for this paper is required to test some real-world libraries. I am using a symbolic execution tool in my research and it crashes on encountering native functions in some third-party libraries. To mitigate this problem, I provide my own model class that is basically a dummy class with non-native functions. Instead of using the original class which contained the native functions, I change the library to use this model class so that symbolic execution works better. Will this be called manual effort in my tool? Can't I call my technique an automated one now? Moreover, is it cheating?


texts: Why is the difference of two NP-complete languages not in NP?

texts:
I found something in my notes I don't really understand, maybe you could help.

Let $A$ = Independent Set and $B$ = Clique. Then, we clearly have

$A \in \mathsf{NPC}$ and
$B \in \mathsf{NP}$.

Now, the claim is that $A \setminus B \notin \mathsf{NP}$ with the following explanation. If it was in $\mathsf{NP}$ then $\mathsf{NP} = \mathsf{NPC}$.

Can you explain why this argument is true?


texts: Why models of computation are primarily focused on machines?

texts:
It seems a lot of courses (like this and this) on theory/models of computation (and even formal languages) cover DFA, NDFA, PDA, and TM in the order of increasing computational power. This of course makes sense, but why aren't various other computation models included in general? For example, we could take the route from untyped lambda calculus to simply typed lambda calculus and so on with decreasing expressiveness. (I know they are detailed in PLT, but aren't they models of computation as well?)

In brief, since all the above (and a lot more) count as different models of computation with different powers, is there any specific reason, historical or else, that the machine-like models are adopted, sometimes even exclusively?


texts: Why is the distinction between linear and context-free grammars useful?

texts:
The linear grammar is a grammar that's either left, right or left and right linear.

The context-free grammar can contain any kind of productions of non-terminals and terminals.

All linear grammars are context-free grammars.

But what is useful about distinguishing linear and context-free separately?


texts: what would be the time complexity of DBSCAN algorithm?

texts: what would be the time complexity of DBSCAN algorithm if we use it for graph(sparse) clustering $O(n^2)$ or $O(n \log{n})$?


texts: Turing Completeness + Dataflow Unification = Arbitrarily invertible (pure, nonrecursive) functions?

texts:
Assume we are working in a Turing-complete, referentially-transparent, higher-order language that supports arbitrary dataflow unification.  Shouldn't it then be possible to construct the following function (using Haskell-like syntax, because that's what I'm most familiar with)?

-- Takes an arbitrary pure function and constructs its inverse.
-- If the passed-in function is recursive, the result is not guaranteed to terminate
invert :: (a -> b) -> b -> a
invert f r = declare a in let r =|= f a in a

(if =|= is the dataflow unification operator).

Is this indeed possible in such a language?  If so, why haven't people leapt at this before?  If not, where did my reasoning go wrong?


texts: Is transitivity required for a sorting algorithm

texts:
Is it possible to use a sorting algorithm with a non-transitive comparison, and if yes, why is transitivity listed as a requirement for sorting comparators?

Background:

A sorting algorithm generally sorts the elements of a
list according to a comparator function C(x,y), with

\begin{array}{ll} C(x,y) = \begin{cases}
-1  & {\text{if}}\ x\prec y   \\ 0 & {\text{if}}\ x\sim y \\
+1 & {\text{if}}\ x\succ y  \\ \end{cases} \end{array}

The requirements for this comparator are, as far as I
understand them:

reflexive: $\forall x: C(x,x)=0$
antisymmetric: $\forall x,y: C(x,y) = - C(y,x)$
transitive: $\forall x,y,z, a: C(x,y)=a \land C(y,z)=a \Rightarrow C(x,z)=a$
C(x,y) is defined for all x and y, and the results depend only on x and y

(These requirements are always listed differently accross different
implementations, so I am not sure I got them all right)

Now I am wondering about a "tolerant" comparator function, that accepts numbers x,y as similar if$ |x - y| \le 1$:
\begin{array}{ll}
C(x,y) = \begin{cases}
-1  & {\text{if}}\ x\lt y-1   \\
0 & {\text{if}}\ |x - y| \le 1 \\
+1 & {\text{if}}\ x\gt y+1  \\
\end{cases}
\end{array}

Examples: both [ 1, 2, 3, 4, 5] and [1, 4, 3, 2, 5] are correctly sorted  in ascending order according to the tolerant comparator ($C(x,y) \le 0$ if x comes before y in the list)
but [1, 4, 2, 3, 5] is not, since C(4,2)=1

This tolerant comparator is reflexive and antisymmetric, but not transitive.

i.e. C(1,2) = 0 , c(2,3) = 0, but C(1,3) = -1, violating transitivity

Yet I cannot think of any sorting algorithm that would fail to produce a "correctly sorted" output when given this comparator and a random list.

Is transitivity therefore not required in this case? And is there a less strict version of transitivity that is required for the sorting to work?

Related questions:

Why is antisymmetry necessary for comparison sort? (about antisymmetry)
Sorting algorithms which accept a random comparator (about a random C(x,y))
OrderBy with a non-transitive IComparer (about the c# sort algorithm, by me)


texts: How to reconcile the different definitions of asynchrony?

texts:
There are 3 definitions of asynchrony that I know of:

In event-based programming, asynchrony refers to the execution of tasks in a non-sequential way, which may involve creating another thread. For example with AJAX, we can perform HTTP requests and handle their response in a new thread so that the program doesn't block to wait for results.

In communication, a channel is asynchronous if both parties don't need to be present at the same time (e.g., emails), and synchronous if they do (e.g., telephone).

In distributed systems, an asynchronous model is one where messages may take an arbitrary long time to transit. It implies that there is no way to know for sure if a node has crashed or it/the network is just being slow.

However I struggle to reconcile these 3 definitions. Is there a common denominator that I'm missing, or is the term asynchrony used in 3 completely different contexts?
Thank you for your help.


texts:
I know that the Knapsack problem is weakly NP-complete. I also notice that on Wikipedia:

  "A problem is said to be strongly NP-hard if a strongly NP-complete problem has a polynomial reduction to it [...]"

The way I prove the NP-hardness is by a reduction chain: SAT $\leq$ 3SAT $\leq$ Tripartite Matching $\leq$ Exact cover by 3-sets $\leq$ Subset sum $\leq$ Knapsack.

Does it mean all these problems are weakly NP-complete? Because it seems that according to Wikipedia if one of them is strongly NP-complete, Knapsack will be strongly NP-complete.


texts: Why does the explanation of auxiliary carry flag differ from the article to article?

texts:
These two images are from Google search.

  AUXILIARY CARRY FLAG: This flag is set to a 1 by the instruction just
  ending if a carry occurred from bit 3 to bit 4 of the A Register
  during the instruction’s execution

Explanation from Quora

  It indicates when a carry or borrow has been generated out of the
  least significant four bits of the accumulator register following the
  execution of an arithmetic instruction. It is primarily used in
  decimal (BCD) arithmetic instructions.

Explanation from Wikipedia

These two different definitions really confuses me.
As I experimented this on Keil using 8051, and it showed that AC is set when the carry occurs out of four low bits.
What is the precise definition?


texts: How do I work out the recurrence relation of the given function?

texts:
I am looking to find the recurrence relation of the following function:
int fnA(int[] array, int low, int high) {
  if (low >= high)
    return array[low];
  else {
    int gap = floor((high - low) / 5);
    return (fnA(array, low, low + 2 * gap) +
            fnA(array, low + gap, low + 3 * gap) +
            fnA(array, high - 2 * gap, high));
  }
}

The problem I am having is that I don't understand what is happening to $n$ in the recurrence relation.
Note: I am not looking for the answer per se, but rather how I should be going about problems like these.


texts: Is the sum $f+g$ of two one-way-functions a one-way-function?

texts:
Since there exists a bijection of sets from $\{0,1\}^*$ to $\mathbb{N_0}$, we might view one-way-functions as functions $f :\mathbb{N_0} \rightarrow \mathbb{N_0}$. My question is, suppose $f,g$ are one-way-functions, is then $(f+g)(n):=f(n)+g(n)$ a one-way-function or can one construct a counterexample? (The length of $n$ is $\text{ floor}(\frac{\log(n)}{\log(2)})=$ the number of bits to represent $n$)

Comment on answer of @Bulat:
Suppose $f$ is an owf. If (?) there exists a $k \in \mathbb{N}$ such that for all $x \in \mathbb{N_0}$ we have $f(x) \le x^k$. Then as @Bulat mentioned, construct $g(x) = x^k-f(x) \ge 0$. Then $g(x)$ is an owf as $f$ is, but $h(x) = g(x)+f(x) = x^k$ is not an owf. So the question is, if there exists such an $k$.
The argument would also work considering $k^x$ instead of $x^k$. But the same question remains? Why would such an $k$ exist?

Thanks for your help!


texts:
I'm a bit new to automata theory, I'm sorry if this question is a bit too simple. If this question has been answered somewhere already, please point me to it.

One basic problem I wanted to solve was defining the minimal set of states need to construct a (minimal) DFA that accepts

$$(a^+)+bcd^*\,.$$

I'm not sure how to treat the OR operator here, though.

I assume it means I can accept either ($a^+$) OR $bcd^*$ OR both (but in the given order), but does it mean I can ignore the order as well (meaning that, e.g. $bcdddaa$ would be acceptable as well)?

If anyone could explain, I would appreciate it. I understand the meaning of other operators.


texts:
I have to build a cycle with fixed length $n$ that includes exactly $k$ corners inside $w$ x $h$ rectangle.

For example:
$w = 5\\h=3$

$n = 12\\k = 6$

I have already found out that I need at least $4$ corners and number of corners and number of non-corner elements needs to be even number.

Then I write an recursive algorithm that runs in exponential time complexity, but I have a strong feeling that this thing can be done much faster.

Problem is that I do not know which square will definitely be in the cycle so I run my algorithm on first $\frac w2$ fields to cover all chances, but I am aware that I search some branches multiple time.

I have also discovered that if the cycle exist it will start with corner in (0, 0) or corner in (0, 1)

Does anybody have an idea on how to speed this thing up?

Have a nice day!


texts: Is this "cycle" condition sufficient for unique minimum spanning tree?

texts:
Given a connected, undirected, weighted graph $G$, the condition

  The maximum-weight edge in any cycle of $G$ is unique.

is not necessary for $G$ to have a unique minimum spanning tree (MST).

However, is this condition sufficient for $G$ to have a unique MST?


texts:
This is homework, so please only hints. I didn't want to put this on StackOverflow since this is mostly about theory, and SO gets inundated with too many questions.

I am asked to find a method of arranging items in a skiplist, with height limited to 3 and unlimited number of elements, in such a way such that searching takes worst-case $\Theta (n^{1/3})$. No restriction on how expensive the arranging part is; just describe what subset of the keys go into which level.

I am somewhat confused. How can a skiplist with a limited number of items have search complexity anything other than $\Theta(n)$? Clearly, with any clever algorithm, I can just fill the skiplist with a horrendous amount of elements, and as the number of elements goes up, surely the handicapped skiplist can't do any better than a linked list asymptotically? I think I can prove this for the simple set of rearranging algorithms that put a random proportion $q$ of the items into the second layer, and another random proportion $p$ of items within these items to the top layer.

Am I missing anything obvious? Is the question faulty?


texts:
I'm working exercises on solving recurrences, just using subsitution, master theorem is after this chapter. I'm sort of stuck on one of the exercises. It states that:

The solution of $T(n) = 2T(\lfloor n/2 \rfloor) + n$ is $O(n \lg n)$. Show that it's also $\Omega(n \lg n)$ and conclude that the solution is $\Theta(n \lg n)$.

For showing that it's $O(n \lg n)$, I've to show that $T(n) \leq cn \lg n$. This can be solved by choosing an $m < n$, like $\lfloor n/2\rfloor$, and substituting.

But if we arrive at the conclusion that $T(n) \leq cn \lg n$ for any appropriate $c > 0$ and $n \geq n_0$, than how can we say that it is also $\Omega(n \lg n)$ which implies that $T(n) \geq cn \lg n$?

Some more clarification would be nice!


texts: How to get from factorial to a y-combinator?

texts:
In one of his conference talks Jim Weirich derives the applicative form of the y-combinator by refactoring a partial definition of factorial. The starting point in his talk is different than what follows here but the ideas are all the same.

Let's start with the following function

# partial definition of factorial
f = \g -> \x -> x == 1 ? 1 : x * g(g)(x - 1)
# factorial = f(f)

Notice that we never name something simultaneously on the LHS and the RHS, i.e. there is no recursion. With the above starting point getting to a y-combinator is pretty simple

# first factor out g(g)(x - 1)
\g -> (\h -> \x -> x == 1 ? 1 : x * h(x - 1))(\y -> g(g)(y))
# next factor out \h -> \x -> ...
(\f -> \g -> f(\y -> g(g)(y)))(\h -> \x -> x == 1 ? 1 : x * h(x - 1))

Now if you look at the function that is being applied to the partial definition of factorial

\f -> \g -> f(\y -> g(g)(y))

we just need to apply it to itself after applying it to a partial definition of factorial to get the full factorial. Spelling that out with lambdas gives us

y = \p -> (\h -> h(h))((\f -> \g -> f(\y -> g(g)(y))(p))

It is still pretty incomprehensible standing on its own but deriving it from the partial definition of factorial makes sense to me. One problem I have with it though is that you somehow have to guess the expression g(g) and it is not at all clear why. Let's say we start with the recursive definition of factorial

factorial = \x -> x == 1 ? 1 : x * factorial(x - 1)

The obvious thing to do if you can't refer to the name of the function within the body of the function is to try to abstract it

factorial = (\g -> \x -> x == 1 ? 1 : x * g(x - 1))(factorial)

The problem is that this is a dead end. I don't see how you can guess that the right thing to do is to factor g(x - 1) into g(g)(x - 1) and start the chain of reasoning at the top of this post. In his talk Jim Weirich does the equivalent of what I did by basically pulling g(g) out of a hat.

So the question is does anyone know a motivating reason for why the proper placeholder in the partial definition of factorial is g(g)(x - 1)?


texts:
In my formal languages class, we discussed DIV, defined as following:

$\mathrm{DIV} = \{\langle a,b\rangle : \text{$a, b \in N$ and $a$ has a divisor $d$ for some $1 < d \leq b$ }\}$

($\langle\cdot\rangle$ means encoded, let's say as binary)

We were told that it isn't known whether DIV is in P and were tasked to prove it was in NP. I naively and mistakenly assumed that DIV was in P because of the following algorithm:

   On input <a,b>
   For all 1<d<=b
       check if d divides a.
       If so, accept.
   reject.

I thought that this algorithm would run in polynomial time because we do $b$ many divisions at worst. Division is polynomial time, therefore, $b$ many divisions is also polynomial time. (also note, $b < a$, or DIV is trivially true, where $d = a$).

However, i was told that this algorithm is not polynomial time with respect to the input. I don't really understand this part. Something along the lines of since $a$ and $b$ are encoded in binary, the input is of order $O(\log n)$. And that means our b many divisions is actually $O(b) \cdot O(\text{divisions})$, and that $O(b)$ is $O(2^{\log b})$. However, isn't $2^{\text{log base $2$ of $b$}}$ the same as $b$? How is that not polynomial time?


texts: Designing CFG that accepts $b^m a^n$ ($m ≤ n$)

texts: I am trying to design a CFG that generates the language $\{a^k b^m a^n a^k \mid m \leq n\}$. However, I am having trouble with the $b^m a^n$ where $m \leq n$. How do I solve this?


texts: Find a hole while travelling along an infinite wall

texts: There is an infinite wall with a hole somewhere, you are placed on that wall at an unknown position. Let the distance between your initial position & the hole be $x$. Find the average distance traveled in terms of $x$ until you find the hole. What's the complexity of this problem in terms of $x$ and how does an algorithm look like that solves it?


texts: What is the time complexity of finding the FIRST and FOLLOW sets?

texts:
Given how important these are for parsing, I'm surprised I wasn't able
to find anything about their complexity. I'm interested in all combinations of:

What is the (edit: best known) time complexity of calculating
<FIRST | FOLLOW | FIRST and FOLLOW> of a <single | all> nonterminals of a <context-free | LR> grammar?

Links to resources or partial answers are welcome.


texts: How to distinguish whether a sample is from distribution $\chi_1$ or $\chi_2$?

texts:
I am given an oracle $A$ that takes input samples from two distributions $\chi_1$  and $\chi_2$.

Suppose we have $Pr_{x \sim \chi_1}[A(x) = 1] = p_1$ and $Pr_{x \sim \chi_2}[A(x) = 1] = p_2$, where $p_1 \neq p_2$.

In general, how can we use $A$ to construct a distinguisher to determine whether the input samples are from $\chi_1$ or $\chi_2$? And how good is the running time of such distinguisher?

Thank you very much! :)


texts: Trying to understand the question(well spaced points ?) better

texts:
Let us have a sorted array of n numbers and we would like to find a well spaced set of C of them, More specifically, we want to get a subset $ S\subset T$ with |S| = C and with $min_{i,j  \in S,i\ne j} |i-j|$ as large as possible. Come up an algorithm for fining the best S.

What is the correct output if the sorted array as 1, 2, 3, 4 ,5 ,6 and c is 3. What about if the sorted array as 1, 10, 11, 12, 23, 24, 25 and c is 3 ?
also appreciated any hints to approached this question if you clearly understand what the question is asking.


texts: Time complexity of a triple nested loop with squared indices

texts:
I have seen this function in past year exam paper.

public static void run(int n){
    for(int i = 1 ; i * i < n ; i++){
        for(int j = i ; j * j < n ; j++){
            for(int k = j ; k * k < n ; k++){

            }
        }
    }
}

After give some example, I guess it is a function that with time complexity in following formula

let make m = n^(1/2)

[m+(m-1)+(m-2)+...+3+2+1] + [(m-1)+(m-2)+...+3+2+1] + ...... + (3+2+1) + (2+1) + 1

*Edit: I have asked this math question here, the answer is m(m+1)(m+2)/6

Is this correct, if no, what is wrong, if yes, how would you translate to big O notation.
The question that I want to ask is not only about this specific example; but also how would you evaluate an algorithm, let's say, I can only give some example to watch the pattern it appears. But some algorithm are not that easy to evaluate, what is your way to evaluate using this example.

Edit:
@LuchianGrigore
@AleksG

public static void run(int n){
        for(int i = 1 ; i * i < n ; i++){
            for(int j = 1 ; j * j < n ; j++){
                for(int k = 1 ; k * k < n ; k++){

                }
            }
        }
    }

This is an example that in my lecture notes, each loop is with time complexity of n to the power of 1/2, for each loop there is another n^(1/2) inside, the total are n^(1/2) * n^(1/2) * n^(1/2) = n^(3/2).
Is the first example the same? It is less than the second example, right?

Edit,Add:

How about this one? Is it log(n)*n^(1/2)*log(n^2)

for (int i = 1; i < n; i *= 2)
            for (int j = i; j * j < n; j++)
                for (int m = j; j < n * n; j *= 2)


texts: DFA for strings with number of 0's odd only in substring longer than 1

texts:
I'm trying to design and DFA that accept string with an odd number of 0`s, but counting only the ones within sub-strings with two or more 0.

So, for example, 011000, will be accepted since it has 4 0`s, but only three or them are inside a sub-string of two or more. But 0001000, wont be accepted.


texts: 3-dimensional matching approximation algorithm (implementation details)

texts:
I have a run-time implementation question regarding the 3-dimensional (unweighted 2-)approximation algorithm below:
How can I construct the maximum matching M_r in S_r in linear time in line 8?

$X, Y, Z $ are disjoint sets; a matching $M$ is a subset of $S$ s.t. no two triples in $M$ have the same coordinate at any dimension.

$
\text{Algorithm: unweighted 3-dimensional matching (2-approximation)} \\
\text{Input: a set $S\subseteq X \times Y \times Z$ of triples} \\
\text{Output: a matching M in S}
$

 1) construct maximal matching M in S;
 2) change = TRUE;
 3) while (change) {
 4)   change = FALSE;
 5)   for each triple (a,b,c) in M {
 6)     M = M - {(a,b,c)};
 7)     let S_r be the set of triples in S not contradicting M;
 8)     construct a maximum matching M_r in S_r;
 9)     if (M_r contains more than one triple) {
10)       M = M \cup M_r;
11)       change = TRUE;
12)     } else {
13)       M = M \union {(a,b,c)};
14)     }
15) }

[1] http://faculty.cse.tamu.edu/chen/courses/cpsc669/2011/notes/ch9.pdf, p. 326


texts: Total functional computable real numbers

texts:
Is there any computable real number which can not be computed by a higher order primitive recursive algorithm?

For computable real number I mean those that can be computed by a Turing machine to any desired precision in finite time. For higher order primitive recursive algorithm I mean common primitive recursive functions theory extended with first-class functions (as in Ackermann function).

Turing machines are more powerful than higher order primitive recursive functions so there exists the possibility that some computable reals numbers are not expressible by them.


texts: Shortest Path problem(Single Source&Destination)

texts:
Given: A completely connected directed acyclic graph.

What would be the most efficient(Least Time complexity) way to find a shortest path among a very large number of nodes?

Constraint:
1)The result should be optimal.
2) The cost between any two connected nodes is computed in time complexity of O(layer-no). For, e.g., if we consider the graph to be layered(Since its a DAG) then the cost between Layer 'K-1' & 'K' can be computed in a time complexity of O(K)

Known Solutions:
1) A* - But heavily dependent on the heuristic function
2) Dynamic programming - requires to compute the cost of path for all possible path.

So, Is there any way to compute it more efficiently or with similar time complexity?


texts: 4-partition elements summation NP completeness

texts:
How can we prove that the following problem $A$ is NP complete?

Given a set of integers $S={a_1, ..., a_n}$ and a number $D$, is it possible to find disjoint sets $S_1, S_2, S_3, S_4$ such that $S_1 \cup S_2 \cup S_3 \cup S_4=S$ and

$$ -\sum_{j=1}^{4}\frac{\sum_{a_i \in S_j}a_i}{\sum_{a_i \in S}a_i}\log_2(\frac{\sum_{a_i \in S_j}a_i}{\sum_{a_i \in S}a_i})\geq D$$

I was thinking on using some NP complete problem $B$ and showing that $B \leq_P A$, but I can't figure out what reduction would work.

Here is what I tried (simplified the problem to 2 sets):
Given a set $S$ of n elements, I tried to prove that $S \in \text{Partition-Problem} \iff  \langle S, 1 \rangle \in A$.
If $S$ is an instance of the partition problem, it means there are 2 subsets in $S$ that have the same sum ($n/2$). Therefore the expression in $A$ (with 2 sets instead of 4) evaluates to $-\log_2 (1/2)=1$. Then proving $S \in \text{Partition-Problem} \Rightarrow \langle S, 1 \rangle \in A$ is trivial. However I am still stuck at proving the $\Leftarrow$ part.


texts: Mutual information and moment generating functions

texts:
I went to listen to a workshop and someone from the audience asked the presenter how the moments can improve the mutual information. I am learning about MI (Mutual Information) so didn't have enough knowledge to understand what it means. Then, I did some research but I still have some confusion. I am wondering if someone who has more knowledge about this can clarify things for me. Here are my questions:

Mutual information is usually calculated by bin functions to estimate the probability of two random variables which can be a case of two vectors $X$ and $Y$. Is the moment generating function another way to estimate probability?
If moment generating functions can present the probability of $X$ and $Y$, how do we calculate it?
Does a MI have a moment generating function?
If MI has a moment generating function, how can we present a MI of $X$ and $Y$ by its moment functions?


texts: Under what conditions does the function C = f(A,B) satisfy H(C|A) = H(B)?

texts:
Suppose we have a function $f$,

$$
C = f(A,B),
$$

where $A$, $B$ and $C$ are random variables.

I notice that when the random variables are binary ($\{0, 1\}$) and $f$ is the XOR operation, we have the following identity:

$$
H(C|A) = H(B),
$$

where $H(B)$ is the entropy of $B$ and $H(C|A)$ is the conditional entropy of $C$ given $A$.

Obviously this is not true for a general $f$. What I am interested to know is, is there a set of conditions on $f$ and $A,B,C$, under which the identity above holds.


texts: solving recurrence by substitution, calculations doesnt add up

texts:
I have this recurrence $p(n) = 2p(n-2) + n$, and I have guessed that the solution is $O(n^2)$, however, when I do the following calculations, I cannot get the inequality to hold

$p(n-2) \leq c(n-2)^2$ (induction hypothesis)

$2c(n-2)^2 + n \leq cn^2$ (substitution)

$cn^2-8c + n \leq cn^2$

Can anyone see where I go wrong? I also tried for even larger $O(n^x)$ but it still doesn't work.


texts: How would one construct conjunctively local predicate of order k for checking if a shape is Convex?

texts:
I was reading Minsky's and Papert's book on perceptrons and it had the definition of conjunctively local as follow (look at the last images if its still unclear):

A predicate $\psi$ is conjunctively local of order k if it can be computed by independently computing a set of functions $\varphi_1(X)$...$\varphi_n(X)$ and then combined by the results of another function $\Omega$ of n argument by a set $\Phi $ of predicates $\varphi$ such that each $\varphi$ depends no more than $k$ points on a 2D Euclidean plane $R$ and:
$$
\psi(X) = \begin{cases}
1 \text{ if } \varphi(X) = 1 \text{ for every } \varphi \text{ in } \Phi \\
0 \text{ otherwise. }
\end{cases}
$$

Then in the book they claim that testing if a figure $X$ drawn on a 2D Euclidean pixel plan $R$ is conjunctively local of order 3. First recall how one would text for convexity on $R$. Essentially one woul look at three points/pixels and draw a line segment joining the points and if the third chose point between them is not in the drawn figure $X$, then it would not be convex.

My question is given this knowledge, how does one show that $\Psi_{convex}(X)$ is conjuctively local of order 3? The order 3 seems sort of clear to me because each $\varphi$ only needs look at 3 points to test convexity. However, it remains unclear to me how one would construct a general $\Psi(X)$ such that it always test correctly for any drawn geometric shape if its convex or not. I guess maybe part of my quesiton is that the definition of conjuctively local is not clear to me. Is it correct to think of $\Psi$ as a function only on the given geometric shape or is it also a funciton fo the whole plane $R$? It seems clear how to construct $\Psi$ if we know the shape in advance but otherwise it doesn't seem we can fix one single architecture and be able to text for convexity.


texts: NFA equality for automata with partial transition functions and all states accepting

texts: Given two nondeterministic finite state automata with partial transition functions, such that all states are accepting, except for the implicit failure sink state, is it possible to decide in polynomial time whether the two automata recognize the same language? Or is it perhaps PSPACE-hard, like the same problem for general NFAs?


texts: Debugging the issues on Megiddo's algorithm

texts:
I have done code for the algorithm to obtain the Optimal Basis but as I calculate the optimal solution $Xb=B^{-1}b$, I only get the correct value for some of the variables. For some variables, $Xb_i$ is not equal to the $X_i$, where $X_i$ is the result of some LP solver, used in Megiddo's algorithm.

What can be the possible issue?

In my problem, $Xb$ need not be always positive. Can this be a problem in the implementation of the algorithm?


texts: Measure objects length and width by picture (pixels)

texts:
I am quite new to image processing. I have experimented with opencv and tried to measure the lenght and width of an object from a picture using a reference object where I know the dimensions.

See this Link https://www.pyimagesearch.com/2016/03/28/measuring-size-of-objects-in-an-image-with-opencv/

Thats working quite well, as long as the objects have the same depth.

Is there a way to determine the distance of the object by algorithms when the camera is fixed? I was thinking about ultrasonic sensors, but I would need quite alot of them to make this work. Any other ideas? I appreciate any help :)


texts: Among a number of sets, how to find the one that includes the highest number of other sets?

texts:
I have a large number of sets, A, B, C, ... where each set includes a few integers. I would like to find the set that includes the highest number of other sets.

A brute-force solution is to compare each set with all other sets and count the number of sets that are included in this set. Finally, pick the set with the highest count. This brute-force solution has a quadratic complexity and is very slow for my large number of sets. Is there a better solution with lower complexity?


texts: If all edges are unweighted AND DIRECTED, can one use BFS to obtain a MST?

texts:
I've looked through CS SE and I've found a page that said you could find use BFS to find a MST if the edges are unweighted, but what if the edges are directed?

Given a directed graph between V vertices, I'm trying to find the minimum directed edges I need to add in order for every vertex to be connected to every other vertex.

Is MST the way to go? Or, is there another way I'm not thinking of.

I apologize if this question is too easy, as I am very new to programming. I appreciate any help. Thanks!


texts: How to find the smallest of the maximum edges of all paths between two nodes in a graph

texts:
Say I have an undirected weighted graph G = (V, E), and I have two vertices s and t. Now there may be a number of paths between s and t, and each path has an edge that has the maximum weight in that path. Out of all these maximum weight edges of all the possible paths, how do I find the smallest one most efficiently?

I suppose I could use a modified Dijkstra's algorithm to find all the shortest paths first, while keep record (like an array) of the maximum weight edges of all possible shortest paths, then maybe use linear time selection to find the smallest one. In this case I think I would have a running time of O((|V| + |E|) log|V|). Is this correct and is there a faster way?

Could I use Kruskal's or Prim's algorithm to find the MST of the graph, and then look at all the edges between s and t in the MST to find the largest one? I am not sure if this is correct at all.


texts: Need help with this runtime of algorithm with double loops that results in 0

texts:
I know with absolute certainty that this is the wrong runtime, but I just wanted to show you how I got to it.

for (i = 0; i <= n; i++) do
     j = 2*i
     while j <= n do
         j = j + 1
         print("Hello World")
end

Then I get the runtime
$Θ(\sum_{i=1}^n 1 + n -2i)=Θ(n+n^2-n(n+1))=Θ(0)$??


texts: Myers' Fast bit-vector algorithm in plain English?

texts:
Inspired by this question on Suffix Trees, and the fabulous winning answer, I would hereby ask for a similar explanation of Myers' Fast Bit-Vector Algorithm for Approximate String
Matching Based on Dynamic Programming.


texts: Context-Free Languages where every rule produces at most one non-terminal

texts:
Consider a context-free grammar where all rules produce at most one non-terminal (i.e., there is at most one non-terminal on the right-hand side of a rule). What is the class of languages which are accepted by such a grammar?

If you like, we may assume that all rules are one of the following forms, where $V, V'$ denote non-terminals and $a$ denotes a terminal:

(i) $V \to aV'$

(ii) $V \to V' a$

(iii) $V \to \epsilon$

If all rules are of the form (i) or (iii) we get the class of regular languages. On the other hand, we can also recognize more languages, such as the language of palindromes.

Therefore, it is somewhere between regular languages and context-free. Does it perhaps coincide with unambiguous context-free or deterministic context-free?


texts: Computing the k shortest edge-disjoint paths on a weighted graph

texts:
Looking for k shortest paths that do not share edges. i.e if the paths were represented as sets of edges, their intersection has to be empty.

We could use Dijkstra to find the 1st "disjoint" (edge unique) shortest path from the origin to all vertices. However, to naively find the 2nd disjoint path, one would need to create $|V|$ versions of the graph, each one with a specific set of set of edges missing, corresponding to a path that was discovered with the original Dijkstra results.

Is there a more computationally efficient method to find the $k$ shortest, edge disjoint paths? Even a heuristic would help me.

Edit:

I think this article posted by Raphael is exactly what I need to $k=2$ but I would like to support a great k if possible, up to 4. One more thing, I don't understand the following instruction:

  Replace each edge of the shortest path (equivalent to two oppositely directed arcs) by a single arc directed towards the source vertex

What does "equivalent to two oppositely directed arcs" mean? What does replacing an edge with a single arc directed towards the source vertex mean?

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

Wait, the problem with the above algorithm is that it doesn't lessen the complexity. It is just as efficient as running Dijkstra twice for each pair of vertices. I'm looking for a better way to get the k disjoint shortest paths between each $v_i$ and $v_j$


texts: Assignment algorithm for symmetric matrices

texts:
I stumbled on the Hungarian algorithm during my personal research when I was assigned interesting problem as homework:

Given a list of objects $L$ and a pairing function $\delta : L \times L \rightarrow \left[0, 1\right]$, pair each object $\alpha$ in $L$ with exactly one $\beta$ in $L$ such that:

$\sum_{i = 1}^n \delta(\alpha_n, \beta_n)$ is maximal
$(\alpha, \beta) \iff (\beta, \alpha)$
$(\alpha, \beta) \implies \alpha \neq \beta$

Now, since we just started programming as a class, our TA wants us to use a heuristic approach to solve the problem - e.g. swap assignments until you reach a local maximum etc.

I thought of using the Hungarian algorithm to guarantee an optimal matching in (relatively) feasible time. For this, I constructed a graph with all $\alpha$ having nodes to all $\beta$ and initializing the edge of two same elements to $\infty$.

However, as it turns out, the implementation I wrote disregards the symmetric aspect of this matrix - in other words my algorithm does not guarantee that $\alpha$ is also it's the partner of the partner of $\alpha$.

I suspect that reason for this is that this is not a bipartite graph anymore. Even though there is a difference between an $\alpha$ on the left and a $\beta$ on the right, it's not a "real" bipartite graph. Is this correct?

According to the Math stack exchange I should use the more general blossom algorithm in this case, but somehow I have a feeling that I could make better use of the properties of my matrix. Is there a better algorithm for this case?


texts: Constructing a PDA with an unequal number of a/b

texts:
I'm looking at this pdf for problems: http://www.public.asu.edu/~ccolbou/src/355hw5solf10.pdf

I found question 3g to construct a pushdown automata for the following:

{$ {a^i b^j}$ | ${i \neq j}$}

The solution they provided is below:

The issue is, when I use JFLAP to test out, I get aabb to pass - when it should just be aabbb, aaabb, etc.

I looked around, and found another solution that also failed:

Can someone explain to me why these fail on JFLAP and if they are right or wrong? The PDA I'm looking for can accept even if there are objects on the stack. Perhaps these two rely on the fact that acceptance is only reached if there is nothing on the stack?


texts: Do you know of a brute-force algorithm for optimizing polynomial expressions?

texts:
For instance, given the polynomial expression $xy + x + y + 1$ it will output $(x+1)(y+1)$.

Thanks!


texts:
I'm given the set $T = \{\langle M, w\rangle : M $ is a Turing Machine that accepts $w^\mathcal R$ whenever it accepts $w \}$ and I want to show it's undecidable but recognizable. (I'm using the bracket notation to denote the encoding of the TM and input string)

Given that I know the set $A = \{\langle M,w\rangle : M \text{ accepts } w \}$ is undecidable but recognizable, I'm trying to show that $A$ reduces to $T$.
I start by assuming that $T$ is decided by a Turing Machine $R$ and then attempt to construct a new Turing Machine, $S$, that will decide $A$ by using $R$ as a subroutine.

To construct this new machine $S$, I will run $R$ on input $\langle M,w\rangle$. If $R$ accepts, then $\langle M,w\rangle$ is in $A$. However, $R$ rejecting doesn't necessarily mean that $\langle M,w\rangle$ isn't in $A$, since $M$ might reject $w$ reversed but accept $w$. So now I'm confused on how to actually construct the reduction. Any help would be great


texts: Do compression tables exist and where are they used?

texts:
Let's take the zip compression for example, from what scraps I can gather on the Internet, the 2 major simplified ways it works is by looking for arrangements of bits that repeat throughout the file, and by compressing certain bit orders.

So for example, we have 010111111111110101

A zip file would look something like:

x = 0101

x|repeat(1,8)|x

So the zip compression creates its own table of arrangements that it finds.

But, is there anything that already uses a predetermined table? For example you'd have a table like:

x = 010101010101010101010110010101010101010101010101...
y = 10101...
...

And then I'd download a file that follows this compression table, without having to download the table because you already have it.

So my question is, is this method used anywhere, and why or why not?


texts: If we can train a ML algorithm to recognize letters with 95% accuracy, why does OCR software still suck?

texts: So I've seen all these leaps in machine learning alorithms these past years and they've only gotten better and better at recognizing handwritten text. I remember reading once that some algorithms have 95% accuracy. So then, why when I use an OCR software, it spits out garbage? Even with printed text, which I feel should have even better accuracy?


texts: Fastest algorithm to find all the possible paths of length $n$ from a give node in a directed graph?

texts:
I am trying to find the fastest algorithm to find all the possible paths of length $N$ from a given node in a directed graph.

My solution is to do a modification of breadth first search from the given node for $N$ iteration. Its time complexity is around $\theta(V+E)$. But the problem is $|V|$ & $|E|$ becomes exponential because as long as there is an edge, the same node can be visited again.

Can there be a solution of this problem with polynomial time complexity? It seems this problem has optimal substructure solution. Is there any solution using dynamic approach?


texts: What are the effects of the alphabet size on construct algorithms for suffix trees?

texts: For what size alphabet does it take longer to construct a suffix tree - for a really small alphabet size (because it has to go deep into the tree) or for a large alphabet size? Or is it dependent on the algorithm you use? If it is dependent, how does the alphabet size affect Ukkonen's algorithm?


texts: How to prove prove $L(G) = \{~w\in\{a,b\}^*~|~\#_aw= \#_bw\}$ for my CFG $G$?

texts:
For language $L = \{ x \in \{a,b\}^* \mid \#_a x = \#_b x \}$, I came up with the following CFG:
$$S \rightarrow aSbS \mid bSaS \mid \varepsilon.$$
It can be easily shown that it is correct (quick example, for string $x = aabb$ we have these derivations: $S \rightarrow aSbS \rightarrow^* aaSbSb\varepsilon \rightarrow^* aa\varepsilon b \varepsilon b \rightarrow aabb$). Then I was asked to provide a mathematical proof, which is more like to be intended as a formalism, to prove, indeed, the correctness of such CFG.

Arguably, by induction, one could assume it holds that $\forall k\leq n$, $|x| = 2k$ and then test a string $x$ with number of characters $|x| = 2n + 2$. So string $x$ is in the form of $x = au'bu''$. But now how can I show that $u'$ and $u''$ still contain an equal number of $a$'s and $b$'s? Sorry if I'm missing something and might be easier than I think.


texts:
In Cormen et al.'s Introduction to algorithms, section 15.3 Elements of dynamic programming explains memoization as follow:

  A memoized recursive algorithm maintains an entry in a table for the solution to each subproblem. Each table entry initially contains a special value to indicate that the entry has yet to be filled in. When the subproblem is first encountered as the recursive algorithm unfolds, its solution is computed and then stored in the table. Each subsequent time that we encounter this subproblem, we simply look up the value stored in the table and return it.

And it adds, as a footnote:

  This approach presupposes that we know the set of all possible subproblem parameters and that we have established the relationship between table positions and subproblems. Another, more general, approach is to memoize by using hashing with the subproblem parameters as keys.

Is there any well-know DP problems that requires (or makes it easier) to store memoized values in a dictionary rather than in a (multi dimensional)array?

Background: if this is of any use, the reason for this question is that I'm trying to motivate the notion of (self-balanced) binary search trees to people that has just seen dynamic programming.


texts:
Recently I sort of stumbled on a problem of finding an efficient topology given a weighted directed graph. Consider the following scenario:

Node 1 is connected to 2,3,4 at 50 Mbps. Node 1 has 100 Mbps network card.
Node 3 is connected to 5 at 50 Mbps. Node 3 has 100 Mbps card.
Node 4 is connected to Node 3 at 40 Mbps. Node 4 has 100 Mbps card.

(Sorry about not having a picture)

Problem: If Node 1 starts sending data to its immediate nodes (2 and 3), we can clearly see it's network card capacity will be drained out after Node 3. Whereas if it were to skip node 3 and start sending to node 4, the data will eventually reach to node 3 via 4 and hence, node 5 will be getting data via node 3.
The problem becomes more complicated if all the links were of 50 Mbps and we can clearly see that node 2 and node 4 are the only way to reach all nodes.

Question: Is there an algorithm which gives the optimal path to ALL nodes keeping the network (card) capacity in mind?

I read the shortest path algorithm,max flow algorithms but none of them seem to address my problems. perhaps,im missing something. I'll appreciate if someone can help me out.


texts: Data structure to know if something was calculated

texts:
There's the typical interview question about how to create a distributed and scalable URL shortener.
One of the issues is to know if a URL was shortened already or not. There's a special data structure that tells you if no or maybe. So it can have negatives or false positives but at least you know it wasn't calculated and you spare the visit do the database.
The question is: what's the name of that structure? I forgot it and searched a lot but can't find it.
Thanks!


texts:
It is possible to prove the correctness of algorithms, and two algorithms can be compared to see which has better performance using $O$ and $o$ notation.

Is it possible to prove the efficiency of an algorithm? I.e. That that algorithm is the most efficient possible algorithm for a problem.

Let $K_i$ be the set of all algorithms(both known and unknown) for solving a particular problem $P_i$
$$K_i = [A_{i1}, A_{i2}, ... ,A_{in}]$$

Is it possible that given an Algorithm $A_{ij}$, one can prove that
$$\forall A_{ix} \in K_i, A_{ij} = o(A_{ix})$$

If the answer is yes, is there a known method to do this?


texts: is the empty language L = ∅ a subset of every languages?

texts:
I need to show false the following claim

  Every language L which is a subset of $A_{TM}$ ($L \subseteq A_{TM}$) is undecidable.

For this, I wish to use the empty language L = ∅ (I know is decidable).

Is it correct that the empty language L = ∅ is a subset of every languages (and also of $A_{TM}$)?


texts:
I recently came across the paper "QMDD: A Decision Diagram Structure for Reversible and Quantum Circuits" by Thornton and Miller. It deals with a way of compactly representing transformation matrix for a given quantum circuit or a quantum gate. I tried very hard to construct a QMDD of a Toffoli gate but I failed. Then I realized maybe I didn't understand QMDDs.

Can anyone please explain me QMDDs and a way to construct a QMDD for a given circuit or gate?


texts: Global Optimization of a well-defined function with gradient information

texts:
I try to minimize the function
$$ f(x_1, …x_n)=\sum\limits_{i}^n-a_i\cos(4(x_i-b_i)) +\sum\limits_{ij}^\text{edge}- \cos(4(x_i-x_j)), \quad
x_i,b_i\in (-\pi, \pi)$$
where $\sum\limits_{ij}^{edge}$ only sums over predefined edges (the edges are sparse, typical there are 4 edges for each $i$). The variables $a_i, b_i$ are constants, $ a_i \in (0,1)$; many $a_i$s are 0.
The gradient at each iteration can be directly computed. I observe that Gradient Descent converges very fast, but produces very bad results (very easily falls into local optimal). I have no idea whether Conjugate Gradient Algorithm or BFGS algorithm will make a significant difference.$$$$
While general optimization such as simulated annealing and GA do not use the gradient information (they seem powerful but blind to local derivative), thus I am looking for techniques making good use of gradient information.


texts: Converting a digital circuit to two layers of OR and AND gates

texts:
The other day someone mentioned to me that you could take an arbitrary digital circuit which mapped N input bits to M output bits, and replace it with a layer of OR gates and a layer of AND gates.  I believe he said there would be 2^N ANDs and ORs each.  I haven't been able to find any more information about this though.

Is this true?

And are there similar techniques for say using only XOR and AND gates?


texts:
I understand the basics of Skip Lists and their implementation also the basic Search Insert Delete functions and their run time complexity. Recently after a lecture, a professor proposed an interesting question. He asked what we suspected the total time building a skip list using randomization.

A few hints were given:

$n \times (1/2 + 1/4 + \dots + 1/2^{k})$.
I understand this as, For every level of the skip list their is said to be half the nodes working from bottom level to the next one above it.
Using a geometric equation we came up with this formula: $n \times \frac{1/2^{k+1} - 1/2}{1/2 - 1}$

So ultimately what is the time complexity? $\Theta(n^2)$?


texts: In a DFA, does the restriction for a total transition function apply to accepting states?

texts:
I recently discovered the idea of a total transition function in Automata Theory. To my understanding this means that every state has at least one outgoing state.

My question is whether this restriction applies to accepting states, since my initial intuition tells me that this would be an overly strict enforcement of the state machine.

Thanks in advance for any answers.


texts: Is a language that sits between two regular languages also regular?

texts:
Suppose that L0, L1, L2 are languages over the same alphabet and that

L0 ⊆ L1 ⊆ L2.

Is it true that if L0 and L2 are regular, then L1 must be regular as well?

By regular = the set of words accepted by a finite automaton.

Suppose

L0 = { $a^{\textrm{n}}$ | n = 2}

L2 = { $a^{\textrm{n}}$ | n => 0}

how can i find a set for L1 that is NOT Regular when there are no parameters or syntax on what the machine accepts or not?

I'm thinking

L1 = { $a^{\textrm{n}}$ | n = prime number }

but I'm not sure how to start proving it


texts: What did Dijkstra think about Monte Carlo algorithms?

texts:
In A Discipline of Programming, Dijkstra wrote:

  Two circumstances have changed the scene since then.* The one is the insight that, even in the case of fully deterministic machines, program testing is hardly helpful. As I have now said many times and written in many places: program testing can be quite effective for showing the presence of bugs, but is hopelessly inadequate for showing their absence. The other one is the discovery that in the meantime it has emerged that any design discipline must do justice to the fact that the design of a mechanism that is to have a purpose must be a goal-directed activity. In our special case it means that we can expect our post-condition to be the starting point of our design considerations. In a sense we shall be "working backwards".

*[i.e., since the time of irreproducibility/indeterminism (real bugs!) in computation]

A Monte Carlo algorithm is only partially "a goal-directed activity": We know very little about how the algorithmic form of the pseudorandom number generator relates to the ultimate goal of the Monte Carlo algorithm.(which, for example, might be computing the area of a circle)

Thus, it would seem Dijkstra would be opposed to Monte Carlo algorithms, either for problem-solving or for testing, because it is unclear what the algorithmic form of a random number generator has to do with what Monte Carlo tasks are designed to accomplish.


texts: How to predict the number of comparisons done by QuickSort if you know the percentage to which the array is pre-sorted?

texts:
I've noticed that correlating the number of comparisons done by a naive implementation of QuickSort with the percentage of elements that were already sorted gives you a curly-brace-shaped-curve if you use logarithmic scale:

So, how can this curly-brace-shaped curve be mathematically described (the red curve represents the behavior of the c++ "sort" function, and it appears much more complicated)? If it can be done precisely, then one can precisely predict how many comparisons QuickSort would do simply by passing through the array, counting the number of elements for which array[i]<array[i+1], and inserting that number into a formula. I've tried to find a mathematical formula that approximates that using a genetic algorithm, here is what I ended up with:

f(n,s)=exp((ln(n)+ln(ln(n)))*1.05+(ln(n)-ln(ln(n)))*0.83*abs(2.38854*pow(s,7)-0.284258*pow(s,6)-1.87104*pow(s,5)+0.372637*pow(s,4)+0.167242*pow(s,3)-0.0884977*pow(s,2)+0.315119*s))

Here, 'f' signifies the number of comparisons done by QuickSort, 'n' signifies the number of elements in the array and 's' signifies the proportion of the elements that are already sorted: it's -1 if the array is reverse-sorted, 1 if it's already sorted, and approximately 0 if it's randomly shuffled.

Can you come up with a better formula?


texts:
I am reading PCA in Bishop's Pattern Recognition and Machine Learning pg. 562, here in Lagrange multiplier but I don't get it in the highlighted: I wonder is it $u_1$ or $u^T_1$?

Your help is appreciated!


texts: Compute median in unsorted array in $\mathcal{O}(\log{}n)$ space and $\mathcal{O}(\log{}n)$ passes

texts:
I want to compute the median in an array of size $m$ which consists of distinct integers from $\{0, 1, ..., n-1\}$, I have $m<n$. By median I mean the middle element (rounding up/down if the array size is even) in the sorted version of the array.

Ideally, the expected number of passes over the array should be $\mathcal{O}(\log{}n)$, the used memory should be $\mathcal{O}(\log{}n)$ bits and the solution should be exact. I'm flexible with the time complexity as long as it's feasible.

Since finding the median in an unsorted array is such a common problem I expected to quickly find some solution which suits my needs but after some research I'm wondering if this is even possible. Does anyone know a solution or where I could expect to find one?


texts: How to verify that a heuristic is consistent?

texts:
A heuristic function is said to be consistent, or monotone, if its estimate is always less than or equal to the estimated distance from any neighboring vertex to the goal, plus the step cost of reaching that neighbor.

I know I can be sure if a heuristic is consistent by verifying the property for each couple (node, child), but is there a smarter and quicker way for doing that?


texts: Is there a faster algorithm for chinese postman problem on a unweighted graph?

texts:
Given a undirected graph $G=(V,E)$,find a shortest circuit(it ends at the same point it starts) which through every edges at least once.As we all know,we can easily solve it with Edmond's algorithm which has a complexity of $O(|V|^3)$
If we assume that the weight of each edge is 1,and $|V|=O(|E|)$,is there a fast way to get the answer?


texts: Why is learning DNF harder than learning CNF?

texts:
In the PAC-learning setting, it is easy to learn a CNF formula when we know each clause has at most $c$ variables.

We go through each positive sample, and eliminate every clause that contradicts the sample.

Learning a DNF formula is said to be much harder, but it seems a similar procedure can be used, so it is unclear to me why DNF is more difficult.

Start with all conjuctive clauses that have at most $c$ variables.  Go through each negative sample, and eliminate clauses that contradict the sample.


texts: N-Grams - how to predict further into the future and how far can we predict?

texts:
I am using N-Grams to predict future character input. For n+1, it performs really well.

I've been looking, but I have not been able to find any information on what the feasible maximum distance into the future N-Grams are capable of.

One way I could do this is to predict the next character (n+1) and then use that result to predict n+2, use n+2 to predict n+3... etc... but obviously an incorrect prediction will cascade and impact the future predictions as there is a dependency.

Is there a better (more accurate, reliable) way to do this? Also, I can easily use N-Grams to predict the next (n+1) character in an incoming stream, but what about n+2? How about n+3? When does it become unrealistic to predict further?

I'm sure there is some research on this, so I'd love it if you could link me to a paper or give me a brief overview to get me going.


texts:
From Skiena's book The Algorithm Design Manual, chapter 6, problem 22:

Let $G = (V,E,w)$ be a directed weighted graph such that all the weights are positive. Let $v$ and $u$ be two vertices in $G$ and $k \leq |V|$ be an integer. Design an algorithm to find the shortest path from $v$ to $u$ that contains exactly $k$ edges. Note that the path need not be simple, and is permitted to visit vertices and edges multiple times.

This is not homework, its me preparing for an interview. I have no clue how to approach this.


texts: Is it possible to tell if two sequences of assembly instructions are semantically equivalent?

texts:
In a modern instruction set like x86-64 there are many many many ways to accomplish the same task using a series of old simple instructions all the way up to the complex SIMD instructions. If one wanted to determine the semantic equivalence of a series of instructions, could this be done rationally or must it only be done experimentally?

For the sake of simplicity I am restricting the number of instructions in a series to something like ten.

The naive way to solve the problem would be to generate all of the potential inputs and experimentally check the results.

A slightly smarter way might be to determine the edges of the input states and only test those.

But I'm wondering if there's a way to represent each of the assembly instructions (and series of instructions) as a data structure that could be compared. Is this a tractable problem? Or is this clearly something like the halting problem?

Intuitively this feels like something similar to what happens inside a compiler.


texts: How to avoid cascading resizes when resizing hash tables?

texts:
With conventional collision resolution methods like separate chaining and linear/quadratic probing, the probe sequence for a key can be arbitrarily long - it is simply kept short with high probability by keeping the load factor of the table low. Collisions during rehashing thus aren't a problem as they don't affect the load factor.

However, with cuckoo hashing (and other methods offering worst-case O(1) lookup time?), a resize must happen when the probe sequence for a key gets too long. But when the keys get shuffled around during the rehash, it may be that they create a too-long probe sequence for one key, necessitating another resize - possibly several, if this happens multiple times in a row. The probability is small, especially with a good hash function, but I've seen it happen.

Is there a way - short of explicitly generating a perfect hash function during the rehash - to ensure that resizes can't cascade in this manner? Possibly specific to a given collision resolution scheme? The literature I've encountered thus far seems to gloss over the matter entirely. Bear in mind that I'm also interested in shrinking hash tables, not just growing them.