texts: Upper bound for set disjointness under product distributions

texts:
For the set disjointness problem in the 2-party model of communication complexity, Alice is given an input $X$ and Bob is given input $Y$, $X$ and $Y$ are $n$-length bitstrings (sampled from some distribution), which are interpreted as subsets of $[n]$, i.e., $X_i=1$ means the $i$-th bit of $X$ is in the subset. The goal is for Alice and Bob to answer whether the subsets represented by $X$ and $Y$ are disjoint by using as little communication as possible. It is known that $\Omega(n)$ bits are necessary in the worst case for randomized protocols.

I came across this draft of the textbook Communication Complexity by Anup Rao and Amir Yehudayoff, where Exercise 6.8 mentions that 2-party set disjointness can be solved with an expected number of $O(n^{2/3}\log^2 n)$ bits if the inputs of Alice and Bob are sampled independently.

  Consider the following protocol. If there is a coordinate $j \in [n]$ such that $H(X_j)$ and $H(Y_j)$ are both at least $\epsilon$, then Alice and Bob communicate $X_j,Y_j$. They condition on the values that they see and repeat this step until no such coordinate can be found. At this point, Alice and Bob use Shannon’s coding theorem to encode $X$, $Y$. Show how to set $\epsilon$ so that the expected communication can bounded by $n^{2/3} \log^2 n$. Hint: Use the fact that $H(X_j ) \ge \epsilon$ implies that $Pr[X_j = 1] \ge \Omega(\epsilon/(\log(1/ε)))$.

I suppose the idea is to first communicate all indices where $X$ and $Y$ have large entropy and then use the fact that the remaining indices must have small entropy. However, the details of the protocol and where the independence of $X$ and $Y$ is coming in, aren't clear to me.


texts: Call by need compared to pass by function

texts:
SML uses pass‑by‑value, Haskell uses call‑by‑need. Unless I'm wrong (the purpose of this question), one can do call‑by‑need with SML, passing a function instead of a value; a function to be later evaluated when needed.

Adapting a classical example:

(* This will print `0` *)

fun pass_by_function (cond, a1, a2) =
   if cond then a1
   else a2

val e1 = fn () => 1 * 0
val e2 = fn () => 1 div 0

val _ = print (Int.toString (pass_by_function (true, e1, e2) ()))

(* This will fail with a divide error *)

fun pass_by_value (cond, a1, a2) =
   if cond then a1
   else a2

val _ = print (Int.toString (pass_by_value (true, 1 * 0, 1 div 0)))

It's a big matter for Haskell to be call‑by‑need. I'm just wondering if there is something else or if it's just, say “syntactic sugar”, compared to the way it needs to be done with SML.

Is this just a different way to write the same or is there a semantic difference I'm not aware of? Passing a function, is it indeed always the same as call‑by‑need? If not, when and how does it differs?


texts:
First question, and my apologies if it is off-topic!  This question suggests to me I may not be totally off-base.

Where did our present regex notation originate?  I am particularly wondering how $ came to mean "end," particularly since its most common use in the English-speaking world (as far as I know) is as a prefix to numbers.  I also wonder about . for "any".

* I know came directly from Kleene, and + seems like a logical extension of *, if only because they are closely related in mathematics.

I have been several pages down in a couple different Google Web and Scholar searches.  I have also looked here and on SO and softwareengineering.SE, but I can't find an answer.  I checked Perl 6's Apocalypse 5, but it doesn't explain how we got our present notation.  I seem to recall that Kernighan's Software Tools might have had some information, but I can't put my hands on a copy at the moment.  Thank you!

Edit Another data point - TECO dates from 1962, and terminated input strings with Esc, displayed as $ (source).  Unfortunately,

  the Escape character ... is written as "$" (for historical reasons, of course).

Id.  That considerably predates UNIX v3 (1973), but doesn't explain the then-existing "historical reasons."


texts: What is standardization in computer science?

texts:
I was reading about the differences  standards and specifications for C.
I understood that programming languages are usually stadardized and I learnt that there are different approches to stadardization.
Anyway I did not understand yet what this terms refer to.
If I think to C, I believe it refers to a standard API, the API of the C standard Library (libc).
 This seems to make sense to me, as if someone told me "Look these are the only functions, types, Macros....etc you can use", because they're the only thing you "see" after you downloaded the library and they make your code portable.
 Anyway, I don't know if my idea of standardization is in some-ways correct, if it's totally wrong or if it's a simplified version, so here I am.


texts: Given a directed weighted graph $D = (V, A, w)$ with weight function $w \colon A \to [0,\infty)$ and a source vertex $s$.  How can I find, for each vertex $v \in V$ a shortest (with respect to $w$) cycle that contains both $v$ and $s$ (it is allowed to repeat the same arc in a cycle).


texts:
I have this finite-state process with the corresponding labeled transition system:

The FSP is:

MAKER = (kochen -> fertig -> MAKER).
USER = (fertig -> essen -> USER).

||MAKER_USER = (USER||MAKER).

Why is essen possible after the second kochen? USER needs to have fertig in order to able to essen right?


texts: Prove correctness of a solution to the critical section problem in general?

texts:
I was wondering if there is any formal, general way to prove the correctness of a candidate solution to the critical section problem in synchronisation. For example, in the image enclosed, i have considered the petersons solution to the critical section problem(reference : operating system concepts by gagne)

The example is worked out for all possible scenarios of concurrent execution and an observation is made that in any scenario, atmost one process enters inside the critical section, hence proving the mutual exclusion condition of the solution.
Doubt
Is there a better way to formally prove the above condition(and other conditions, such as bounded waiting and progress)? I wondered because the method I used above is really a brute force method and things can get pretty messy as the number of instructions increases. Thanks in advance.


texts: Is SAT a single language or a union of languages?

texts:
I know that a language is in NP if a Turing machine can decide the language of its checking relation $\{\text{boolean formula }\#\text{ truth assignment | truth assignment is correct}\}$ in polynomial time.

Here is my confusion. All Turing machine have a finite input alphabet $\Sigma$. Thus, none of them can solve any SAT problem with, say, $|\Sigma|+1$ variables. Thus, do we need another Turing machine with a larger input alphabet and its associated language to cover this problem? By induction, does this make SAT a union of an infinite number of languages?

If SAT is indeed a union of languages, and any Turing machine only responsible for solving boolean satisfiability problems with variables within its input alphabet, a Turing machine can simply "memorize" all possible 3-SAT problems without redundant clauses over this finite set of variables, and regurgitate the answer in linear time?

In other words, is there a loophole in the definintion of NP that allows for solving SAT by looking up pre-prepared answers? If such cheating is allowed, P=NP?


texts:
I've come across a problem which at first appeared to be a markov process however the transition matrix of the graph is non-stochastic. That is, the probabilities among edges leaving a node do not sum to 1. However,the probabilities on edges entering the node do sum to 1. Therefore the transpose of the transition matrix IS stochastic.

I've built up a model in excel and noticed a few properties of this "transpose markovian process":

all nodes reach the same steady state value.
the steady state *is* dependent on the initial state (unlike a markov process).
the steady state value can be computed as S0 x MT (the initial state vector times the transpose of the markovian steady state vector... obtained by transposing the transition matrix and solving as a markov process).

My question is this: Is there a name for such a process? In searching for it I've found it to be beyond obscure, so my hope is some well-informed human can catalyze me with some search terms.


texts: Comparison-based lower-bound for finding duplicates in an array of $n$ numbers

texts:
Decision Problem: Given $n$ real numbers, give an algorithm that outputs "1" iff there are at least two numbers that are identical and outputs "0" otherwise.
  (Assume that comparison between any two numbers works in $O(1)$-time).

The problem is obviously solvable in $O(n\log n)$-time via augmenting mergesort, and when we limit the numbers to integers or bitstrings, we might be able to use hashing to improve the runtime.

However, an acquaintance told me that there is an $\Omega(n\log n)$ lower bound to this problem on the comparison model, meaning that this problem is as hard as sorting. Is he correct? If so, give a proof.


texts:
A Boolean function $F(X_1, X_2, X_3, X_4, X_5, X_6)$ of six
variables is defined as $F = 1$, when three or more input variables are at logic 1. otherwise 0.
How many essential prime implicants does F have?

How to visualize this problem. A Six Variable k-map is very difficult to manage. Any hints?


texts: Algorithm to test whether a language is context-free

texts:
Is there an algorithm/systematic procedure to test whether a language is context-free?

In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n a^n : n \in \mathbb{N}\}$), test whether the language is context-free or not.  Imagine we are writing a web service to help students with all their homeworks; you specify the language, and the web service outputs "context-free" or "not context-free".  Is there any good approach to automating this?

There are of course techniques for manual proof, such as the pumping lemma, Ogden's lemma, Parikh's lemma, the Interchange lemma, and more here.  However, they each require manual insight at some point, so it's not clear how to turn any of them into something algorithmic.

I see Kaveh has written elsewhere that the set of non-context-free languages is not recursively enumerable, so it seems there is no hope for any algorithm to work on all possible languages.  Therefore, I suppose the web service would need to be able to output "context-free", "not context-free", or "I can't tell".  Is there any algorithm that would often be able to provide an answer other than "I can't tell", on many of the languages one is likely to see in textbooks?  How would you build such a web service?

To make this question well-posed, we need to decide how the user will specify  the language.  I'm open to suggestions, but I'm thinking something like this:

$$L = \{E : S\}$$

where $E$ is a word-expressions and $S$ is a system of linear inequalities over the length-variables, with the following definitions:

Each of $x,y,z,\dots$ is a word-expression.  (These represent variables that can hold any word in $\Sigma^*$.)
Each of $a,b,c,\dots$ is a word-expression.  (Implicitly, $\Sigma=\{a,b,c,\dots\}$, so $a,b,c,\dots$ represent a single symbol in the underlying alphabet.)
Each of $a^\eta,b^\eta,c^\eta,\dots$ is a word-expression, if $\eta$ is a length-variable.
The concatenation of word-expressions is a word-expression.
Each of $m,n,p,q,\dots$ is a length-variable.  (These represent variables that can hold any natural number.)
Each of $|x|,|y|,|z|,\dots$ is a length-variable.  (These represent the length of a corresponding word.)

This seems broad enough to handle many of the cases we see in textbook exercises.  Of course, you can substitute any other textual method of specifying a language in algebraic form, if you like.


texts: Casting to boolean in integer linear programming

texts:
I have variables $x \in \{0,1,\dots,5\}$ and $y \in \{0,1\}$, where

$$y = \begin{cases} 0 & \text{if } x = 5\\ 1 & \text{if } x \neq 5\end{cases}$$

My problem is to maximize $y$. How can I use linear constraints for this?

I tried certain cases like Cast to boolean, for integer linear programming but that won't work if the problem is to maximize $y$.


texts:
The kernel is $K(x,z) = \sum_{i=1}^D (x_i+z_i)$

My approach was trying to express  $K = \phi(x)^T\phi(z) = (x_1 x_2 ... x_D \quad 1 1 ...1)(1 1 ...1\quad z_1 z_2 ... z_D )^T$ where $\phi$ is 2Dx1 and thus a Kernel.

The solution says:

K is not a kernel. Consider $x_1 = [1 \quad 0]^T \quad x_2 = [0 \quad 2]^T$. Their kernel matrix has eigenvalues −1 and 5.

What explains this discrepancy?


texts: if an argument of a lambda only passes itself if it is further evaluated, is runtime always finite?

texts:
In order for a lambda expression to run forever, there must be at least one lambda in the expression
in which an argument is passed to itself. For example the following runs forever.

$$
(\lambda x.xx)(\lambda x.xx)
$$

However, I am curious if an expression could run forever if arguments were only passed to themselves
like in $\lambda x.x(xy)$ in that each time it is passed, it becomes further evaluated. I suspect that
this is true (that it can be evaluated in finite time) however am unsure how to prove this formally.
Informally the idea is that each recursive call is guaranteed to leave the lambda in a further reduced state
since the original cannot be preserved.

So my question is:

 What is a formal proof or counterexample to this claim?

A few notes:

The opposite is definitely not true, expressions of the form $\lambda xy.(xy)x$ can run forever. For example,
the following runs indefinitely.

$$
(\lambda xy.(xy)x)(\lambda xG.(Gx)G)(Lx.x)
$$

Also, if when passed to itself both parts are passed an additional argument, such as $\lambda xy.(yx)(yx)$ it
can run forever. For example

$$
(\lambda xy.(yx)(yx))(\lambda x.x)(\lambda xy.(yx)(yx))
$$

Additionally, I am assuming all lambdas within the expression meet the criteria, not just some subset of them.
So something like the following would not be a counterexample

$$
(\lambda x.x(xy))(\lambda x.xx)(\lambda x.xx)
$$

Edit:

As chi pointed out below, I had not given a very good definition of the criteria for this question, so I've added one.

A lambda is reduced in X if it can be written in the following form (as <reduced-lambda>)

<id> := [[all valid variable names except X]]
<id-list> := <id> <id-list> | <epsilon>
<filler> := <epsilon> | <nonempty-filler>
<nonempty-filler> := (lambda <id> <id-list> . <nonempty-filler>) <filler> | <id> <filler> | (<nonempty-filler>) <filler>
<reduction> := (X <filler> <reduction>) | (X <nonempty-filler>)
<base-reduction> := (lambda <id> <id-list> . <filler> <base-reduction> <filler>) | (<filler> <base-reduction> <filler>) | <reduction> | X
<reduced-lambda> := (lambda <id-list> X <id-list> . <filler> <base-reduction> <filler>)

An expression E is reduced if for every lambda L in E, for every argument A in L, L is reduced in A.

And the more precise question becomes: does every reduced expression terminate?

Edit 2:

I did change the above formulation slightly, the old version is in the edit history and is incorrect (twice)


texts:
I've become interested in blockchain databases. Everywhere I've read it said that each user has to have his/her own copy of database.

Why can't distributed blockchain database be 'distributed' to reside partly on many computers to achieve say fixed 10 times redundancy, not times number of users redundancy? Will speed be times slower or other reason it's not done?


texts: Finding the nearest neighbour of an existing 2d point in a set of points within $\mathcal{O}(\log{}n)$ time

texts:
Question

Is it possible to find an existing point's nearest neighbour within a logarithmic upper bound?

What I've tried

I have:

the set of points $P$,
a point $p$, where $p\in P$,
a point $q$, where $q\notin P$,
a Voronoi diagram, $V(P)$, of the points in $P$.

I know it's possible to query for a new point $q$'s nearest neighbour in $\mathcal{O}(\log{}n)$ time using $V(P)$ but is it possible to find the nearest neighbour of an existing point, such as $p$?

I've thought that if it wasn't possible, then I could delete the point $p$ in $V(P)$, assuming I could somehow create a dynamized Voronoi structure that allows for timely deletions (this paper notes that there is a way to insert points in constant time, so hopefully there's a Voronoi structure that allows deletions in logarithmic or less time), then search for the now non-existing point in logarithmic time. This would also solve my problem. Is there a dynamized Voronoi structure that allows deletions in $\mathcal{O}(\log n)$ time?


texts: Is the proof for the undecidability of $A_{TM}$ still valid if we change certain parts?

texts:
i have a question based on a question i saw exists on the site, but with wrong information in it and no answer there, so i am reposting it with valid information(cited wrong from the book).

on page 207 of the book "introduction to the theory of computation", there's a proof that $A_{TM}$ is not decidable.

the proof is constructed using contradiction, while assuming there's a machine $H$ that is a decider for $A_{TM}$ and takes input of $\langle M,w\rangle$ where $M$ is a turing machine and $w$ is a string, and H halts and accepts if $M$ accepts $w$, and assuming that $H$ halts and rejects if $M$ fails to accepts $w$.

then, they construct a new turing machine $D$ with $H$ as a subroutine that does the following:

  $D$ = "On the input $\langle M\rangle$ where $M$ is a TM:

  Run $H$ on input $\langle M,\langle M\rangle\rangle$
  Output the opposite of what $H$ output. that is, if $H$ accepts, reject; and if $H$ rejects, accept.

the questions: will the proof still hold true if we change the following changes independently, i.e., each change is separate and does not affect the other separate situation:

1) if we change step 1 so that it will be: Run $H$ on input $\langle M,\langle M\rangle^R\rangle$,

2) if we change step 2 so that it will be: If $H$ accepts, loop. if $H$ rejects, accept.

my attempt:

1) the proof will remain true, because  we are proving by contradiction that on machine $D$, running $H$ as a subroutine will not allow us to decide $A_{TM}$. furthermore, running $D$ with input of itself, i.e $D(\langle D\rangle)$, forces the machine to do the opposite, thus creating the contradiction. so it doesn't matter if we run $D(\langle M\rangle)$ or $D(\langle M\rangle^R)$, the result will be the same when we run $D(\langle D\rangle)$ and the $D$ will be forced to decide the opposite(accept if not accept $\langle D\rangle$ and reject if $D$ accepts $\langle D\rangle$).

2) well, here i am not sure. because in the original proof if $H$ accepts, then it reject, and if $H$ rejects, then it accepts. now if we say "If $H$ accepts, loop. if $H$ rejects, accept", well, we have a problem, because now $H$ Halts and then it is decided, even though incorrect. the loop is the main problem here and i hope i interpreted it right.

have i done it correctly? i am really not sure, especially regarding 2. is it enough to be an acceptable explanation?

thank you very much for helping. did my best to elaborate it and fixing the question in the site that lacks correct information from the book (also gave sources from it).


texts:
what is meant by support of a filter in context of image processing?
In the attached link of a short tutorial for detecting bar in an image by gabor filter,it is said that γ=1 helps in finding the support of the filter.
link1


texts: How to solve the optimization of bin packing using the decision version

texts:
Let us say the optimization version of the bin packing problem asks you to give a packing using the fewest bins possible and the decision version asks if it is possible to pack the bins into $k$ bins.

  How can you reduce the optimization version to the decision version?

If you only have to answer what the fewest bins possible is then it is clear you can use binary search. But if you actually have to give the packing, I can't see how to do it.


texts: Prove that the following algorithm has STOP property (number of steps is finite)

texts:
Prove that the following algorithm has STOP property. I am not sure if this term is widely know, so the definition of STOP property that I got during classes looks as follows:

  STOP property (for all input data satisfying $ \alpha $ the computation halts - the number of steps is finite)

$\alpha: x \in N $

void BB(int x)
{
    int y = x;
    int z = 0;
    while((z != 0) || (y <= 300))
    {
        if(y <= 300)
        {
            y = y + 3;
            z = z + 1;
        }
        else
        {
            y = y - 2;
            z = z - 1;
        }
    }
}

I do not really have any idea how to approach such a problem. I was thinking about using the method of loop counters, but I couldn't success with it.


texts: Difference of simulated annealing and random search for generating crossword puzzles?

texts:
I heard that when one wants to write a program to make a crossword puzzle, he can use for example simulated annealing as in the thesis Crossword Construction using Constraint Satisfaction and Simulated Annealing
 by Pavel Tomozov or random search as in http://raksy.dyndns.org/sqpack2.py. What is the difference of simulated annealing and random search?


texts: Prove that there is no computability reduction HP $\le$ $\Sigma$*

texts:
I tried to prove in negative way that there is computability reduction  HP $\le$ $\Sigma$* and accept contradiction because of HP $\in$ RE and $\Sigma$* $\in$ R but it feels that is not strong argument.

There is a more solid way to prove it?


texts: Proving the set of finite languages is countable without using the union of countable sets

texts:
The list of finite languages over a finite alphabet is countable.

I could prove it by saying that the list of languages of size 1 is countable, the language of size 2 is countable, and so on. Then I can prove that the infinite union of countable set is countable.

However, I am sure that there is a simpler proof. Can someone help?

In my example $|\Sigma=\{0,1\}|$


texts: Which memory holds the copy of the program that is to be executed?

texts: I don't know whether it is RAM or cache; I can say that isn't the registers since their memory capacity is very small.


texts: Can you explain this improvement to this frequency distribution algorithm?

texts:
I came across the following in a text book:

  Frequency distribution – Given a set of n items, which element occurs the largest number of times in the set? If the items are sorted, we can sweep from left to right and count them, since all identical items will be lumped together during sorting.
  To find out how often an arbitrary element k occurs, look up k using binary search in a sorted array of keys. By walking to the left of this point until the first the element is not k and then doing the same to the right, we can find
  this count in O(log n + c) time, where c is the number of occurrences of k. Even better, the number of instances of k can be found in O(log n) time by using binary search to look for the positions of both k − ε and k + ε (where ε is arbitrarily small) and then taking the difference of these positions.

The part I don't understand is the part I have emphasised in bold text - I can't understand how you might choose 'ε' and how you would know that the list even contains this 'ε'..


texts: Meaning of polynomially larger or smaller in the context of the master method

texts:
I'm studying the master method of solving recurrences and I have a somewhat decent math background but I'm having difficulty understanding the concept of $n^{\log_ba}$ being polynomially smaller or larger than $f(n)$.

What I mean is $n^{\log_ba}$ being polynomially larger or smaller than the function $f(n)$ for recurrence relations of the form: $T(n) = aT(\dfrac nb) + f(n)$.

Case 1 is the case in which $n^{\log_ba}$ is polynomially larger than $f(n)$.
Case 2 is the case in which $n^{\log_ba}$ is equal to $f(n)$.
Case 3 is the case in which $n^{\log_ba}$ is polynomially smaller than $f(n)$.

As my book defines it, for case 1 to apply $n^{\log_ba-\epsilon}$ for some $\epsilon > 0$ must be larger than $f(n)$. in other words, $n^c > f(n)$ where $c< \log_ba$.

Similarly, for case 3 to apply $n^{\log_ba+\epsilon}$ for some $\epsilon > 0$ must be smaller than $f(n)$ or in other words $n^c < f(n)$ where $c > \log_ba$.

Another way to think of subtracting $\epsilon$ is to think of $\dfrac{n^{\log_ba}}{ n^e}$ for some $\epsilon > 0$.

and another way to think of the adding of the $\epsilon$ is to think of $n^{\log_ba}*n^\epsilon$ for some $\epsilon > 0$.

In my class slides on the master method the first example uses the recurrence $T(n) = 4T(\dfrac n2) + 1$ and suggests the possibility that case 1 applies. $n^{\log_ba}$ would be $n^2$ and $f(n)$ would be 1.

The slide points out that $f(n)$ is NOT polynomially smaller than $n^2$.

I do not fully understand this because if you take $0 > \epsilon > 1$ such as $1/2$ for example.

You can then subtract this epsilon from $n^2$ and you'd have $n^{1.5}$ which would still be greater than $f(n) = 1$ for any $n > 1$.

So how is this not an example of being polynomially smaller?

Further, the slide which explains that $f(n)$ in this example is not polynomially smaller, indicates that $T(n) = 4T(\dfrac n2) + \dfrac{n^2}{\log n}$ doesn't work

but why would they have attempted to divide $n^2$ by $\log n$ in the first place? I get the the division is equivalent to subtracting an $\epsilon$ from the exponent of $n$, but why $\log n$, what is the significance?

*Edit: my professor's response:

As an example (assuming all numbers are positive to keep it sjmple), the idea is that for any numbers $p$ and $q$, if $q > p$, $(n^p)*log(n) < n^q$ asymptotically, no matter how close to $p$ the number $q$ is.

So $n^p*log(n)$ is not polynomially larger than $n^p$ because for any $q > p$, eventually it will be smaller then $n^q$


texts:
In context of data mining, what does it mean for an association rule measure to be maximal?

I cannot understand the term maximal in this context.

I know of maximal independent sets in algorithms but cannot make out this term.


texts:
Show that the following languages are not regular in two ways: first by using
closure properties then by using the Pumping lemma:

$$\text{(1) L1} = {a^n b^k c^{n+k} : n >= 0; k >= 0}$$

$$\text{(2) L2} = {a^n b^k : n \ne k}$$

So far for

What I tried: Assume that L is regular. By P.L, there exists a P such that $w = a^pb^pc^{2p}$  there is $w_i = xy^iz  , \mid y \mid \ge 1 , \mid xy \mid \le p $. We can imply  $y = a^k$ and assuming k = 1  $w_0 = xy^0z = xz = a^{p-1}b^pc^{2p}$ which is not an element in L. Therefore there a contradiction and it is not regular.
I don't know what to do for the closure properties
Assume that L is regular. By P.L, there exists a P such that $w = a^pb^p$ from here im lost since it says $n \ne k$
for 2) can we say that $ w \notin L $ since $n = p = k$ thus it is a contradiction?


texts: Let say we have a Language $L = \{0^m1^n \mid m,n \geq 0 \land m \neq n \}$. If I want to use the pumping lemma to disprove that the language is regular or context-free, how do I choose the word in dependence of the number $n$? The problem is that I got an $m$ and an $n$ in the exponent and they cannot be equal. Can I choose $0^{n+1}1^n$ for the word?


texts: NP-completeness of scheduling to minimise tardy tasks with release times

texts:
In "Computers and Intractability A Guide to the Theory of NP-Completeness" textbook pp 236, "Sequencing to minimize tardy tasks" is NP-complete.
To be specific the problem is as follows:

For each task $t \in T$, partial order $<$ on $T$, a length $l(t)$, and a deadline $d(t)$ and a positive integer $K \leq |T|$. Is there a one-processor schedule $s$ for $T$ that obeys the precedence constraints, that is $s$ is such that $t < t'$ implies $s(t)+l(t) < s(t')$, and such that there are at most $K$ tasks for which $s(t) + l(t) > d(t)$?

Now we associate each task with a release time $r(t)$ and $s(t)$ should be $\geq r(t)$. Does the revised problem stay NP-completeness ?


texts: How to prove that the language { ww | w ∈ {a,b}* } is / isn't context free?

texts:
Is the language { ww | w ∈ {a,b}* } context free?
I have tried to create a pushdown automaton but I didn't find any solution. I think you need a queue and not a stack.

Is there a way to prove this statement using the pumping lemma?


texts:
I have the following problem I am trying to prove NP Complete.

Tutors have two jobs- grading exams and homework help. Suppose we have a set of $n$ tutors. Each of them can tutor any amount of $m$ classes.

The tutors rent a large study room to offer help to students. But, note that ALL tutors for a specific class can't be in the study room. Otherwise, that class will have no one left to grade the exams.

Question is, can we have $k$ tutors in the study room?

Attempt at solution:

I feel like this is a set or vertex cover problem and have interpreted as follows.
We create a bipartite graph... connecting the left hand side (class) to right hand side (tutor). We have to see if we can choose $k$ tutors from the right hand side such that no left hand side vertex has all its edges used up.

For example, if $k = 1$ the answer is yes. Choose any person.
If $k = 2$ answer is yes. $\{A, D\}$ works but not $\{A, B\}$ because they make up the tutors for $C2$.
$k = 3, 4$ also do not work for the same reasoning.

I am trying to decide if I should approach this with set-covers, clique, independent set? I'm not entirely sure but feel this approach is on the right track.


texts: For what data structures is jump search practically useful?

texts:
Jump search is a search algorithm for sorted lists which runs in $O(\sqrt n)$ time, but has the advantage of only making backwards steps at the end (and given the ability to make arbitrarily long backwards steps, guarantees only a single backwards step); thus, it may be preferable to binary search if reverse traversal is significantly more expensive than forward traversal.

Now, it's not hard to contrive situations in which that is the case--say, a skip-list which is doubly-linked at the lowest level (so that reverse traversal is possible) but singly-linked for every skip-link (so reverse traversal isn't fast). But what are contexts in which jump search actually makes sense as the most efficient method of searching data that was not specifically constructed to be ideal for jump searching?


texts: Is the height of the tree the number of edges or number of nodes?

texts: I'm so confused by some of the theorems online about tree heights. Does tree height mean the number of edges or nodes? if nodes, does it include the node it is counting from? Can the height of a tree start from 0?


texts: Cliques in an alternate graph representation

texts:
EDITS: corrected $r$ to add edges just like $f$ does in paragraph 8 per the first comment below. Also specified the Clique problem of interest in paragraph 2.

Having received no response to this question on math.SE, I'm asking it here. Thanks for your help.

In the Wikipedia article on the Clique problem, we are told that under the brute-force algorithm, there are potentially exponentially many subgraphs of a given graph that must be checked as possible cliques. The particular Clique problem I'm interested in is the problem of finding a clique larger than a given size.

Informally, the question here is whether an unknown representation of graphs will also have a possibly exponential number of subgraphs that must be checked as possible cliques under the brute-force algorithm.

I'll try to make this more precise by first giving a function to build up normal graphs, and then a new, different function to build up the unknown representation with properties that the new function must satisfy. The whole discussion here is about undirected graphs.

Let's start by defining an operation that will build up a normal undirected graph. Let $E$ denote the null graph: $0$ nodes, $0$ edges. Let $f$ be the following operation:

$f(n_1, n_2, G)$

$f$ takes a graph $G$ and returns a graph with the edge from $n_1$ to $n_2$ added to $G$. So while the null graph $E$ is definable without $f$, all other standard graphs in our discussion are built by $f$: $f(n_1, n_2, G)$ where $G$ could equal $E$.

As an example, the expression $f(n_1, n_2, E)$ returns the graph $(\{n_1, n_2\}, \{(n_1, n_2)\})$.

Now consider an alternate graph representation $H$, built by a function we'll call $r$ that adds edges like $f$ does. But $H$ is an unknown representation that must obey the properties below.

First let's describe a similarity relation ($\sim$) between $G$ and $H$:

Case 1. $G \sim H$ if $G = E$ and $H = E$.
Case 2. $G \sim H$ if $G = f(n_1, n_2, G_1)$, $H = r(n_1, n_2, H_1)$, and $G_1 \sim H_1$.

As before, the null graph $E$ is definable without $r$, but all others in the unknown representation are built by $r$: $r(n_1, n_2, H)$ where $H$ could equal $E$.

The representation $H$ must obey the following properties:

Just as $G$ is built by successive applications of $f$ to the null graph $E$, $H$ is built by successive applications of $r$ to the null graph $E$.
The order in which the edges of a graph are added doesn't matter:
in ordinary graphs, $f(n_1, n_2, f(n_3, n_4, G)) = f(n_3, n_4, f(n_1, n_2, G))$; in the unknown representation, $r(n_1, n_2, r(n_3, n_4, H)) = r(n_3, n_4, r(n_1, n_2, H))$.
Since we're talking about undirected graphs, the order in which the nodes of an edge are specified doesn't matter: in ordinary graphs, $f(n_1, n_2, G) = f(n_2, n_1, G)$; in the alternate representation, $r(n_1, n_2, H) = r(n_2, n_1, H)$.
Just as for $G$, $H$ has an operation $hasClique(\{n_1,...,n_k\}, H)$ which is true exactly when there is a clique among the nodes $\{n_1,...,n_k\}$.
Consider a graph $G$ with nodes $\{n_1,...,n_m\}$ and a subset $\{n_i,...,n_j\}$ and $G \sim H$ for some $H$. Then we require that nodes $\{n_i,...,n_j\}$ form a clique in $G$ if and only if the nodes $\{n_i,...,n_j\}$ form a clique in $H$. What I'm trying to capture here is that $H$ has a clique wherever $G$ does and vice versa for $G \sim H$.

Question: Can we conclude that $H$ has potentially exponentially many subgraphs that must be checked as possible cliques under the brute-force algorithm, just as in normal graphs?


texts: Which is the best data structure for searching under these conditions

texts:
I have a system with some factors, say A, B, C, and D.
There can be different values of all these factors.
Let us consider few values to have a better understanding.

Let's say A has 4 different values, A1, A2, A3, A4.
B may have 3 or 5(anything, no order or logic here), similarly C and D may also have many different values.

What I have to do is keep count of is how many times a given combination occurs.

For e.g., one combination is A1, B1, C1, D1. Another may be A1, B1, C2, D1 and so on.

I need to read the count of occurrences of these combination once from a text file, and search for it when queried, and give the corresponding count. There is one more condition. There is a threshold for the count. For example, let's say the threshold is 10. If the count for (A1, B1, C1, D1) is less than 10, then I need to find the count of (A1, B1, C1, Dany), if this is less than 10, then just (A1, B1, Cany, Dany) or (A1, B1).

A trie might have been an option, but searching will take more time than hashmaps there.

Which would be the best data structure to do so in Java?

Of course, the simplest and most obvious solution is to use hashmaps. But the factors(A,B,C,D) may be ten or twenty, and may take thousands of values. Though the file where I am reading values from is updated only once a day, so updating the hashmap is not a problem, but I am not sure if storing this amount of data at once in a DS is possible or not. Also loading it into hashmaps is going to take a lot of space I guess, as we are going to store all the possible permutations in the hashmaps.

Thank you in advance for all your suggestions and efforts, much appreciated.


texts: Algorithm to split an ordered, undirected graph into subtrees?

texts:
I have an undirected graph, whose nodes have some sorting order defined on
them.
I have to split it into subgraphs such none of the subgraphs have any cycle.
I am trying the following procedure

listOfSubGraphs = empty
currentSubGraph = empty
for each node do
    if "node + currentSubGraph" do not form a cycle
        add node to currentSubGraph
    else
        add currentSubGraph to listOfSubGraphs
        currentSubGraph = empty
    end if
 end for

Is there a standard algorithm or better way to do this?

The context for the problem is thus

The graph is a map, with nodes as towns, and weighted edges as distance between towns. I need to convert the graph data into a .dot file for rendering.
I want to maintain the relative positions of the towns, in the resulting .dot diagram consistent with ground reality. I will do this by using rank feature of .dot.
I need to group the nodes such that those with similar longitude are in the same group, and assign them same rank. Adding a node that causes a cycle will be pushed to the next .dot rank (subtree)


texts: Equation to find the collaboration between neighbors in SOM in unsupervised learning

texts:
In Kohonen's SOM algorithm, the equation to find the collaboration is:

$$
\mathit{Damp}(i,j) = \exp\left(-\frac{\mathit{LDist}(i,j)^2}{2\sigma^2}\right)
$$

I know that LDist is the lattice distance and $\sigma$ is the standard deviation. I am just wondering why they are squared? Can anyone help me to visualize the equation or explain to me what is going on in the above equation?


texts: Solving a recurrence in which $n$ decreases by $\sqrt{2n}$

texts:
I'm trying to solve the recurrence
$T(n)= 2T(n-\log f(n))+ f(n)$, where $f(n) = 2^{\sqrt{2n}}$,
using the master theorem. Which case applies here?


texts: How to fool the "try some test cases" heuristic: Algorithms that appear correct, but are actually incorrect

texts:
To try to test whether an algorithm for some problem is correct, the usual starting point is to try running the algorithm by hand on a number of simple test cases -- try it on a few example problem instances, including a few simple "corner cases".  This is a great heuristic: it's a great way to quickly weed out many incorrect attempts at an algorithm, and to gain understanding about why the algorithm doesn't work.

However, when learning algorithms, some students are tempted to stop there: if their algorithm works correctly on a handful of examples, including all of the corner cases they can think to try, then they conclude that the algorithm must be correct.  There's always a student who asks: "Why do I need to prove my algorithm correct, if I can just try it on a few test cases?"

So, how do you fool the "try a bunch of test cases" heuristic?  I'm looking for some good examples to show that this heuristic is not enough.  In other words, I am looking for one or more examples of an algorithm that superficially looks like it might be correct, and that outputs the right answer on all of the small inputs that anyone is likely to come up with, but where the algorithm actually doesn't work.  Maybe the algorithm just happens to work correctly on all small inputs and only fails for large inputs, or only fails for inputs with an unusual pattern.

Specifically, I am looking for:

An algorithm.  The flaw has to be at the algorithmic level.  I am not looking for implementation bugs.  (For instance, at a bare minimum, the example should be language-agnostic, and the flaw should relate to algorithmic concerns rather than software engineering or implementation issues.)
An algorithm that someone might plausibly come up with.  The pseudocode should look at least plausibly correct (e.g., code that is obfuscated or obviously dubious is not a good example).  Bonus points if it is an algorithm that some student actually came up with when trying to solve a homework or exam problem.
An algorithm that would pass a reasonable manual test strategy with high probability.  Someone who tries a few small test cases by hand should be unlikely to discover the flaw.  For instance, "simulate QuickCheck by hand on a dozen small test cases" should be unlikely to reveal that the algorithm is incorrect.
Preferably, a deterministic algorithm.  I've seen many students think that "try some test cases by hand" is a reasonable way to check whether a deterministic algorithm is correct, but I suspect most students would not assume that trying a few test cases is a good way to verify probabilistic algorithms.  For probabilistic algorithms, there's often no way to tell whether any particular output is correct; and you can't hand-crank enough examples to do any useful statistical test on the output distribution.  So, I'd prefer to focus on deterministic algorithms, as they get more cleanly to the heart of student misconceptions.

I'd like to teach the importance of proving your algorithm correct, and I'm hoping to use a few examples like this to help motivate proofs of correctness.  I would prefer examples that are relatively simple and accessible to undergraduates; examples that require heavy machinery or a ton of mathematical/algorithmic background are less useful.  Also, I don't want algorithms that are "unnatural"; while it might be easy to construct some weird artificial algorithm to fool the heuristic, if it looks highly unnatural or has an obvious backdoor constructed just to fool this heuristic, it probably won't be convincing to students. Any good examples?


texts: Is there any intersection in the applications of multi-agent reinforcement learning and more traditional branches of machine learning?

texts:
From my limited understanding, it seems like the structure of problems that multi agent reinforcement learning attempts to attack is quite different from the structure of problems in more traditional areas of machine learning. Is this a correct assessment?

If so, is multi agent reinforcement learning doomed to be relegated to the backwaters of machine learning, in terms of applications?


texts: Derive a while loop (which seemingly have some logarithmic traits) runs in $\Theta(n)$

texts:
I know for a fact that algorithm A runs in $\Theta(n)$, but how does one derive that?

Algorithm A

i = 1
while i ≤ n
  s = 0
  while s ≤ i
    s = s + 1
  i = 2 ∗ i

The inner loop is clearly $O(i)$ (linear time).

The outer loop is clearly $O(\log n)$ (logarithmic time).

A visualitation of the loop in terms of an input $n$ would look as follows:

, the black lines represents the amount of work or iterations required in terms of $n$.


texts: 'meet in the middle' combined with Dynamic Programming for subset sum

texts:
What is the reason why nobody has combined the 'meet in the middle' approach with the Dynamic Programming for subset sum?

I found it curious that is a kind of a open problem.. as a matter of fact I never have seen both them combined.

On a paper (1), the author questions if by their combination would be possible to obtain an algorithm with time complexity $O(T^{1/2}*n^{O(1)})$.

Is that time complexity something reasonable?

Could it get better or worse than the above estimation?

(1) SETH-Based Lower Bounds for Subset Sum and Bicriteria Path, Amir Abboud et al. arXiv:1704.04546


texts: confusion with worst case for direct addressing

texts:
In CLRS there is an exercise for direct address table

  Suppose that a dynamic set S is represented by a direct-address table
  T of length m. Describe a procedure that finds the maximum element
  of S. What is the worst-case performance of your procedure?

for this question i have seen a lot of websites indicating the worst case possibility is O(m) by starting and examining every non null slot up to end and then returning the maximum index,
but i think it can be done in a faster way than that.
 If direct addressing tables has m slots , then obviously the highest value should be in the end (i thought keys are treated as indexes in direct addressing,correct me if i am wrong) , so if we start iterating from the end then worst case would be O(m-n) where n is the number of elements examined by our iterator before reaching  non null value from end of the direct addressing table

is something wrong with my approach? Can any one clear this topic?


texts:
I was chatting with a friend about my love/hate relationship with XML.  He made the comment that, "xml is broken primarily because parsers for recursive self-defined document are basically impossible to get right."
I've heard the critique that XML is very difficult to parse before, but my understanding is limited to difficulties around balancing memory usage (i.e. streaming) and the impedance mismatch between XML and most programming languages (such as not supporting basic primitives like an array).
What is unique about XML as a self-defining document that makes parsing difficult?


texts:
I modeled the function double_sided_breadth_first_search after the ideas in "improving Dijkstra" in Cormen et al, and the OCW course on algorithms. Note that I expand the smaller boundary, in an effort to improve efficiency. I have not seen this applied to bfs before. Does anyone know the name of this algorithm? Does it have a name? I saw the technique for doing a double sided Dijkstra algorithm, doing the iteration on the smaller vertex with smaller degree described online but can't find the page now. Does anyone know of a references for the Dijkstra style algorithm I just described?

More detailed description of algorithm I am trying to research:
  Do a two sided breadth first search starting at both vertices. At each iteration expand the boundary of the smaller boundary.

The pseudo code is as follows

double_sided_breadth_first_search( ug, vertex0, vertex1 )
  #ug undirected graph as an adjacency list, ie hash map from vertex to set of neighbor vertices
  # vertex0, vertex1 - the two vertices that we wan't to connect
  boundary0 = { vertex0 }
  boundary1 = { vertex1 }
  visited = hashmap from vertex => vertex0 or vertex1
  common_vertex = null
  distance = 0
  while |boundary0| > 0 and |boundary1| > 0 and common_vertex is null {
    distance = distance + 1
    if |boundary0| <= |boundary1| then
       expand boundary0, mark vertices in new boundary with vertex0
        set common_vertex if one is marked as vertex1
    else
       expand boundary1, mark vertices in new boundary with vertex1
        set common_vertex if one is marked as vertex0
  }
  if common_vertex not null {
    return distance
  } else {
    error
  }

Here is python code that implements the algorithm


texts: Example of exponential algorithm performing better than a polynomial one?

texts:
I have a weird question.

I was just wondering if there were some problem with two solutions; one (A) being exponential time, the other one (B) being polynomial time. However the constants involved are such that, in "practice", the algorithm (A) performs better.

For instance, we could have something like $(1 + 10^{-100})^n$ versus $n^{10^{100}}$.

(I said exponential vs. polynomial, but any other distinction would do.)


texts: How to calculate the entropy of a system with multiple states

texts:
I'm stuck in trying to compute an overall entropy calculation with an agent.
Let me first introduce some background of the problem. Basically, I'm doing some work with the contextual bandit problems. Let's say I have an agent with $m$ actions to select from and in different contexts (I use states in the following), it will choose different actions according to the actions' probabilities. For example, for state $1$, the action probability distribution is $[0.7, 0.1, 0.2]$ and the agent will select an action based on this distribution. So, in other words, the agent selects an action based on the probability distribution associated with a specific state. With the selection probability distribution of actions under each state, we can compute the entropy of an individual state by $SE(s)=\sum_{i}{p(a_{i}) \log p(a_{i})}$. This is kind of the entropy of a random variable of action selection at a certain state, and I call this state entropy. State entropy is supposed to represent the uncertainty of action selection at an individual state.
Suppose an agent has $n$ states. I'm wondering if there is a way to represent the overall uncertainty or entropy of the agent? I've found this equation in a paper $H=\frac{\sum _{j=1}^{n}SE(s_{j})}{n\log m}$ where $n$ and $m$ is the number of states and number of actions respectively. The paper didn't give any explanation regarding this equation though.  Is this a well-proved equation for the entropy of such a situation? Please can anyone give their opinion about this or can anyone guide me the way to find the answer? Appreciate your help!


texts: Showing that the quotient function is primitive recursive

texts:
I'm asked to show that the quotient function is primitive recursive. I know that the operation of integer division $div$ is not total, as it is not defined when the denominator is zero, and a recursive function has to be total by definition.

So I could give a function $div'$ and define a value for the case that the denominator is zero:
$div'(x,y) = 0$ if $y = 0$, otherwise $div'(x,y) = div(x,y)$. But this is still not primitive recursive because of $div$. How can I go about proving that the quotient function is actually primitive recursive? Should it somehow be built from scratch? Any help would be appreciated.


texts: Showing that tournament sort requrires O(n log n) comparisons

texts:
I wish I could think of a better way to word my question. Maybe some one here could offer s suggestion for that, as well.

On to my question. Before I do, this is a class question that has been asked, answer, and considered to be over; however, I'm struggle accepting the answer. For this reason, I'm here hoping someone can word it in a way that I understand it.

The problem is as follows:

Show that if n is a power of 2, tournament sort requires O(n lg n) comparisons.

I refer to a rooted tree graph of six levels (0-5) with the vertices doubling at each level: i.e  1, 2, 4, 8, 16, 32. I see a pattern very similar to binary. I'm not implying the problem is binary related, but it is powers of 2 and I'm very comfortable with binary.

Using that 2^5 = 32, n=32; therefore, n is a power of 2. No argument here. Now I read the problem to say that 32log32 (nlogn) will result in the number of comparisons. The aide answering my question said, "the calculated results of the nlogn were immaterial. I just needed to know there were 5 levels down, and therefore 5 levels up." Additionally, he kept referring to 5log5 which I still don't see a result that makes any sense to me.

As I study the question, I read it to say that the nlogn should provide me with a number of comparisons, based on n. I cannot make that happen with a known values.

Can someone please help me to follow this better?


texts: Rigorous proof against pseudorandom generator

texts:
I am trying to teach myself the principles of cryptograhpy, and want to solve the following question:

Let G be the algorithm that takes an input x = (x1, . . . , xn) from
{0, 1} n (so each xi ∈ {0, 1}) and outputs the string G(x1, . . . ,
xn) = (x1, . . . , xn, x1 ⊕ x2) in {0, 1} n+1. Rigorously prove that G
is not a pseudorandom generator.

So, we would want to prove that either expansion doesn't hold (for all n, l(n) > n), which, in this case, would mean that for each x, the corresponding G > x, or pseudorandomness doesn't hold ( For efficient algorithm D, there is a negligible function 'n' such that:

Pr[D(r) = 1]-Pr[D(G(s)) = 1] $\leq$ $\epsilon$(n),
where 'r' is uniform on {0,1}$^{l(n)}$ and 's' is uniform on {0,1}$^n$

), which, in this case, means that we need to prove that there does not exist a function n such that the difference of the probabilities of the function D(r) and D(G(s)) is very small.
Now, I understand these concepts, but I am  having trouble approaching this problem practically... what would be the best way to start?


texts:
I came across a book where the author uses the following property of mutual information:

Let $X$,$Y$,$Z$ be arbitrary discrete random variables and let $W$ be an indicator random variable.

$$
(1)\ \ I[ X : Y \mid Z ]
  = Pr(W=0) I[ X : Y \mid Z, W=0 ]
  + Pr(W=1) I[ X : Y \mid Z, W=1 ]\
$$

I don't understand why this property holds in general.
To show this I was thinking to proceed as follows:
\begin{align}
I[ X : Y \mid Z ]
  &= E_z[ I[ X : Y \mid Z = z ]] \\
  &= E_w[ E_z[ I[ X: Y \mid Z = z]\ |\ W=w ] ] \\
  &= Pr(W=0)E_z[ I[ X: Y \mid Z = z]\ |\ W=0 ] \\
  &+ Pr(W=1)E_z[ I[ X: Y \mid Z = z]\ |\ W=1 ].
\end{align}
where the second line follows by the law of total expectation.
However, this does not seem to be the right approach since it's not clear to me that
$$
E_z[ I[ X: Y \mid Z = z]\ |\ W=w ] = I[ X : Y \mid Z, W=w ]$$
holds.

What is the right way to show  (1)?


texts: I have two langages $ A, B \in \mathrm{coRE}$.  How can I prove that $ A \triangle B= ( A - B) \cup (B - A)$ is also in $\mathrm{coRE}\,$?


texts: Prove that this language is decidable or undecidable

texts:
Is the following language decidable?

L = {(M) : M performs at least 100 steps on every accepted input.}

I tried to use reduction from the halting problem, but still no dice.


texts:
I want to add a points one by one into sorting tree. I have less then function to order them by angle from absciss: for points $\mathbf p_i = (x_i,y_i)$ and $\mathbf p_j = (x_j,y_j)$ it just sign of cross product of radius vectors to them:

$$
f_<(\mathbf p_i, \mathbf p_j) \stackrel{def}{\equiv} (x_i \cdot y_j < x_j \cdot y_i)
$$

How can I modify RB tree implementation (or is there more general approach for any sorting tree) to make it looped (i.e. modulo $2 \pi$)? Is there "symmetrical" approach to make tree equally well arranged with no dependence on direction for points in general positions?


texts: Is there a *natural* problem that is NP-hard on trees, but in P on non-trees?

texts:
It seems intuitive that any natural problem that is NP-hard on trees, should be hard on graphs that are not trees. But perhaps this is wrong?

Question: Is there some natural decision problem on graphs that is NP-hard when we are promised the graph is a tree, but in $P$ when the graph is promised to not be a tree.

Thoughts:

Here's a list of problems that are NP-hard on trees: https://cstheory.stackexchange.com/questions/1215/np-hard-problems-on-trees
The ones I saw were all also hard on non-trees.
Given any NP-complete language $M$ that is NP-complete on trees, you can obtain a tautological example via the decision problem $L$ where $x \in L$ iff $x \in M$ and $x$ is a tree. This is pretty unnatural though.
Is there some object that trees have a lot of of, but non-trees only have a few of?


texts: Doubt with the halting problem undecidable proof

texts:
The Halting problem proof can be seen as the following programs:

Ends(P, I) is a program that detects (returns true or false) if the program P will halt or
not with the input I
Diag( P ): is a program that

2.1 Halts if P( P ) doesn't halt

2.2 Doesn't halt if P (P) halts

If we use (2) with input Diag it state:

Diag(Diag) halts if Diag(Diag) doesn't halt
Diag(Diag) doesn't halt if Diag(Diag) doesn't halt

Which by contradiction is proven that the program Ends can't exist.

Until here everything is fine. But What if instead of thinking on halt or never halt, we think in steps.

What if I do the following analogy:

Ends( P, I, S ) is a program that detects (returns true or false) if the program P with the input I, it will halt in less or equal S steps.
Diag( P, S) = Diag( P ): is a program that:

2.1 That halts in less or equal than S steps if Ends( P, P, S ) doesn't halts in less or equal than S steps.

2.2 That doesn't halts in less or equals than S steps if Ends( P, P, S ) halts in less or equal than S steps.

if we use (2):

Diag( Diag) halts in less or equal than S steps if Ends( Diag, Diag, S ) doesn't halt in less or equal than S steps.
Diag ( Diag ) doesn't halt in less or equals than S steps if Ends(  Diag, Diag, S ) halt in less or equal than S steps.

Which is the almost the same contradiction, and in this case Ends is possible to build.

What I'm doing wrong?


texts: Answering questions about the recurrence of certain aspects of an algorithm

texts:
I am thoroughly confused by a problem that was brought up in class:

Given the following pseudocode for a function RANDOM which generates a random number based off of recursion:

function RANDOM(n)
1.  if n = 1 then
1.1     return 1
1.2 else
2.1     assign x = 0 with probability 1/2, or
2.2     assign x = 1 with probability 1/3, or
2.3     assign x = 2 with probability 1/6
3.      if x = 0 then
3.1         return (RANDOM(n-1) + RANDOM(n-2))
3.2     end-if
4.      if x = 1 then
4.1         return (RANDOM(n) + 2*RANDOM(n-1))
4.2     end-if
5.      if x = 2 then
5.1         return (3*RANDOM(n) + RANDOM(n) + 3)
5.2     end-if
6.  end-if
end-RANDOM

Answer the following three questions:

Give the recurrence equation for the expected running time of RANDOM.
Give the exact recurrence equation for the expected number of recursive calls expected by a call to RANDOM(n).
Give the exact recurrence equation for the expected number of times the return statement at line 5.1 is executed, in all calls to RANDOM(n), recursive or not.

Our professor gave us a version of this pseudocode that goes like this:

function RANDOM(n)
1.  if n = 1 then
1.1     return 1
1.2 else
2.1     assign x = 0 with probability 1/3, or
2.2     assign x = 1 with probability 1/3, or
2.3     assign x = 2 with probability 1/3
3.      if x = 0 then
3.1         return (RANDOM(n))
3.2     end-if
4.      if x = 1 then
4.1         return (RANDOM(n-1) + 1)
4.2     end-if
5.      if x = 2 then
5.1         return (3*RANDOM(n-1) + RANDOM(n-1) + 1)
5.2     end-if
6.  end-if
end-RANDOM

And answered the three questions as follows:

1)

T(n) = expected running time of RANDOM

$$
T(1) = 1
$$

$$
T(n) = 1 + \frac{T(n)}{3} + \frac{T(n-1)}{3} + \frac{T(n-1) + T(n-1)}{3}
$$

which, after some algebra, comes out to equal:

$$
T(1) = 1
$$

$$
T(n) =\frac 32 * T(n-1) + 1,
$$
, where $n>=1$.

I have one question about the answer to this problem. Why does the constant $1$ in the original equation not matter to the equation? Is it because it is being lumped in with constant time?

2)

R(n) = the expected number of recursive calls executed by a call to RANDOM(n). $$
R(1) = 0
$$

$$
R(n) = \frac{1+R(n)}{3} + \frac{1+R(n-1)}{3} + \frac{2+2*R(n-1)}{3}
$$

, which, after some algebra, comes out to:

$$
R(1) = 0
$$

$$
R(n) = \frac 32 * R(n-1) + 2
$$

, where $ n>0 $.

I have a couple of questions about the set-up of this problem.

Why is 1 added to the numerators of the first two rational numbers?
Similarly, why is 2 added to the numerator of the last rational number?

Finally,

3)

C(n) = the exact number of returns from line 5.1 of RANDOM(n), recursive or not.
$$
C(1) = 0
$$

$$
C(n) = \frac {C(n)}{3} + \frac {C(n-1)}{3} + \frac {1+2*C(n-1)}{3}
$$

, which, after some algebra, comes out to be:

$$
C(1) = 0
$$

$$
C(n) = \frac 32 * C(n-1) + \frac 12
$$

, where $n>0$.

My main question for this answer is: why is 1 added to the last rational number in the expression? What does that 1 represent?

I am so lost, and desperate. Any attempt to shine light on these answers would be such a great help to me. Thank you.


texts:
A zero-knowledge proof system for a language $L$ is an interactive
proof system where a prover $P$ (a Turing machine) tries to convince a
verifier $V$ (a polynomially bounded Turing machine) in a sequence of
message exchanges that $x \in L$ so that $V$ learns nothing from the
interaction except whether $x \in L$ or not.

Question. Is it known how iterate this, i.e.: how to produce a ZK proof that I
possess a ZK proof for membership in $L$?


texts: A genetic algorithm modified for a specific problem

texts:
I have a problem whose solution can be written as a binary string with a given length $N$, where $N$ is a given parameter. Standard GA works well on this problem. From runs of small values $N$, I found that optimal solutions are binary strings that contain only 01 or 011. For example, the optimal solution for $N=16$ is 0101011010101101. So I think it would be a good idea to only search the solutions space where all solutions/chromosomes only contain 01 or 011. But clearly the standard GA cannot restrict the search in the subspace I desire. One mutation or one crossover will make the new solution go into the larger solution space.

My question is: is there a way to adapt the standard GA to restrict its solution space to one where the chromosomes contain only 01 or 011?


texts:
My problem statement is that my agent has to visit multiple pickup points once to collect orders, say Item A, Item B, Item C...... etc. We are using TSP for that.
Now say Item A are stored in 3 places and each place has stocks which are 20,30 and 40 respectively. If my total quantity of pickup for Item A is 45 then how do I choose the optimal path?
Do we have any particular algorithm for this? I have heard of the Travelling Producer problem but did not find much details on it.


texts: Validating a sequence of points as a convex hull

texts:
I'm familiar with the classical convex hull calculation algorithms. The lower bound for computing the CH of a set of points $P$ is $n\log(n)$.

However, what if I'm given a sequence of points and told they form a CH? One check is to "walk the points" in order and check for "left turns" (CCW). However, this doesn't handle the case of self-intersections (you could imagine a counter-example that "winds around starting from the center" making only CCW turns.

I've been told this "validation" can be done in $O(n)$ time, but to check for self-intersection naively, I see $O(n^2)$ time.

My next thought is to run Graham's Scan. Since the points are presumably on a CH, it takes $O(n)$ to find the lower left point, say $p_0$, and from there, I THINK you can guarantee that all points $p_1, p_2,\dots,p_n$ are already sorted by angle between $p_0$ and $x$-axis. As you move the three-point-window forward along the hull, the points ahead are still properly sorted. The reasoning for $O(n)$ then follows per normal reasoning for Graham's scan, minus the need for $O(n\log n)$ sorting.

1) Is my assumption, in bold, correct?
2) Is there an easier method that wouldn't involve running Graham's scan?


texts: Japanese Multiplication simulation - is a program actually capable of improving calculation speed? Or am I doomed from the start?

texts:
On SuperUser, I asked a (possibly silly) question about processors using mathematical shortcuts and would like to have a look at the possibility at the software application of that concept.

I'd like to write a simulation of Japanese Multiplication to get benchmarks on large calculations utilizing the shortcut vs traditional CPU multiplication. I'm curious as to whether it makes sense to try this.

My Question: I'd like to know whether or not a software math shortcut, as described above is actually a shortcut at all.

This is a question of programming concept. By utilizing the simulation of Japanese Multiplication, is a program actually capable of improving calculation speed? Or am I doomed from the start?

The answer to this question isn't required to determine whether or not the experiment will succeed, but rather whether or not it's logically possible for such a thing to occur in any program, using this concept as an example.

My theory is that since addition is computed faster than multiplication, a simulation of Japanese multiplication may actually allow a program to multiply (large) numbers faster than the CPU arithmetic unit can. I think this would be a very interesting finding, if it proves to be true.

If, in the multiplication of numbers of any immense size, the shortcut were to calculate the result via less instructions (or faster) than traditional ALU multiplication, I would consider the experiment a success.


texts:
When we analyze algorithms using the $O$ notation, we usually use only a small set of the space of all functions. E.g., we use $\Theta(n)$ but not $\Theta(2n)$, as these two are equally well represented by $\Theta(n)$. This makes me ask whether it is possible to define a set of "representative functions" which are totally ordered by the $o$-notation?

Concretely, let $F$ be the space of all positive, monotonically increasing real functions on $N$ (the natural numbers). I am looking for a subset $G\subseteq F$ with the following properties:

For every two functions $g_1,g_2 \in G$, either $g_1(n) = o(g_2(n))$ or $g_2(n) = o(g_1(n))$.
For every function $f\in F$, there is a function $g\in G$ with $g(n)=\Theta(f(n))$

Does there exist such a set? If so, how can it be represented (e.g. how many real parameters are required?)


texts: Give CFG and PDA for the words that start and end with the same symbol

texts:
I need to give a PDA and CFG for a language that contains all binary strings that start and end with the same symbol. I've created the CFG with no problem, but I'm stuck with the PDA and don't quite know how to accomplish it.

The best I can figure is that I need to use non-determinism, but I don't quite know how to apply it in this circumstance.

Here's the CFG that I came up with:

\begin{align*}
A &\to 1B1 \mid 0B0 \mid \epsilon\\
B &\to 1B \mid 0B\mid \epsilon
\end{align*}

The PDA, insofar as I managed to come up with:

The notation here, just in case it's not universal: $a,b \to c$ means "When you see symbol $a$, pop symbol $b$ off the stack and push symbol $c$ onto the stack."

Any pointers on how to accomplish this?


texts: How are weak references in a reference counted system implemented?

texts:
When reference counting is used for automatic memory management (e.g. Objective C or Swift), it is well know that “loops” give problems.   E.g.

class Car
{
     Engine engine;
}
class Engine
{
     Car installedIn;
}

Swift (along with other systems) avoids this problem by allowing the reference from the car instance to the engine instance to be weak.   So that the engine instance does not keep the car instance alive, and when the car instance is freed, then the reference from the engine instance is set to null.

What are the standard ways of implementing this within a runtime/compiler?


texts:
We have a large file that can't fit into internal memory. How do we randomly pick one line so that each line has the same probability to be picked?

And how do we randomly pick such n lines so that they all have the same probability?

We don't know the number of lines beforehand.

Any hint on where to start solving this, which algorithm to use, or at least an idea where to start would be appreciated.


texts: A Quine–McCluskey variant for conjunctive normal formal?

texts:
There is the Quine–McCluskey algorithm for finding a minimal expression of a boolean expression in dis-junctive normal form. Would applying DeMorgan's rule to the minimal DNF result in the minimal CNF?

Is there an equivalent algorithm for con-junctive normal form? Not necessarily looking for something efficient as the results will be cached, just if such an algorithm exists.


texts:
Possible Duplicate:
  Negation of nested quantifiers

The problem is:

∃x∀y(x ≥ y)

With a domain of all real positive integers.

The negation is:

∀x∃y(x < y)

so, if y = x + 1

the negation is true.

That means the negation of the negation (or, the original problem) is false.

My question is, that if the original problem is ∃x∀y(x ≥ y), why can't x = y and prove the problem true?


texts: Does applying a homomorphism to the intersection of two CSLs yield RE languages?

texts:
For each language $L \in L(RE)$ there are a homomorphism $h$ and two context-free languages $L_1$ and $L_2$ such that $L = h(L_1 \cap L_2)$.

I understand that this is because context-free languages are not closed under intersection so $L_1 \cap L_2$ will produce non-context-free languages. Since context-sensitive grammars doesn't allow erasing rules which context-free grammars allow to, then the language must be recursively enumerable language. Then recursively enumerable languages are closed under homomorphism.

If $L_1$ and $L_2$ are context-sensitive languages, does $L = h(L_1 \cap L_2)$ still result in $L \in L(RE)$, as context-sensitive languages do closed under intersection but not morphisms?


texts: Longest cycle, existance of approximate algorithm implies existence of better one

texts:
This is an exercise from an old exam that I don't know how to solve.

  For any undirected graph $G$, let $c(G)$ be the length of the longest (simple) cycle in $G$. Show that if there exists a polynomial time algorithm which, for every graph $G$, returns some cycle in that graph which length is at least $\frac{c(G)}{2}$, then there exists a polynomial time algorithm which, for every graph $G$, returns some cycle in that graph which length is at least $\frac{c(G)}{\sqrt{2}}-1$

My solution attempt:
Let's name the algorithm from the problem statement $A$. Now I'm constructing algorithm $A'$. $A'$, when given graph $G=(V, E)$, first creates $G^2=(V^2, E')$, where $E'$ is defined as: for every $\{u,w\} \in E$, the following edges appear in $E'$:

for every $x \in V$ $\{(x, u), (x, w)\} \in E'$ ($x$ here represents one of the copies of original $G$)
for every $x, y \in V$ $\{(u, x), (w, y)\} \in E'$ (this means all the copies of $G$ are connected with scheme "every vertex in one with every vertex in second")

Observation:

  $c(G^2) \ge c(G)^2$

This is true because having some cycle in $G$, we can mimic such cycle going through the copies of $G$, so that we visit $c(G)$ vertices in $c(G)$ copies, amounting to $c(G)^2$ vertices in total.

Let $R$ be result of running $A$ on $G^2$. Now, we should probably extract somehow some cycles from $R$ that are easily embeddable into $G$ and argue somehow that the longest of those will be at least $[\frac{c(G)}{\sqrt{2}}]$.
One candidate (call it $C1$, is a cycle extracted from first component of vertices (as if we have shrunk all copies of $G$ into single vertices). If length of $C1$ is smaller than  $[\frac{c(G)}{\sqrt{2}}]$, then in at least one of the copies of G, there are at least $\frac{c(G^2)}{2} / \frac{c(G)}{\sqrt{2}} \ge \frac{c(G)}{\sqrt{2}}$ vertices on the cycle (I'm a bit sloppy about the floor function here, I hope it doesn't make much difference).
Now, the problem is that in such one copy of $G$, the cycle can be fragmented into some number of disjoint paths, so it's not obvious how one could recover a proper cycle from that. If, for instance, the problem statement were asking about a clique of size at least something, then this solution would work, because we would be certain that such vertices in one copy of $G$ form a clique as well. In case of a cycle however, we don't have this nice "subgraph also is of the same kind" property.
So the question is:

  Is it possible to alter the solution slightly to make it work for cycles?


texts: Which in-memory data structure can accommodate billions of md5 value?

texts:
For my application, I have to store billions of md5 values, and before storing new md5 I wanna make sure that it doesn't exist already in it.
I tried using hash data structure, it worked well but no of lookups goes high with table entries.
I tried using trie, each node storing a byte, but the memory consumption is too high. As each node required 256 pointer for successor on next level.
Can anyone suggest better data structure which could use less space as well as no of lookups is The ?


texts: When are invariants true inside of a loop?

texts:
I am new to the idea of invariants and hope to find more information about it.

It can make an algorithm or loop show a high level of certainty / confidence that the code is correct, such as in the case of a binary search, as described in the book Programming Pearls, 2nd Ed.

Are invariants true at most part of the loop and can be untrue at some part? That is, in the middle of the loop:

while a <= b
    if (...)
        // Point A
    else
        // Point B
    end
    // Point C
end

is it true that at Point A or Point B, something can change that cause the invariants to break, and it depends on the next iteration to "correct the invariants"?  The same with Point C, something can change that can cause the invariants to break?

Maybe Point C is more likely the place where the invariants may break, as it is getting ready for the next iteration? So if it is a for-loop:

for(i = 0; i < n; i++) {
    // ...
}

then the i++ is a place where the invariant may break? I am looking if there is any rule that says what time may invariants not hold true, or should they always hold true?

It seems for binary search, the invariants are always true, while for mergesort or quicksort, the invariants are only true at a certain point, such as for mergesort, the array is divided into 2, and it is in sorted order, but this invariant is only true only after the code recursively calls itself to sort both the left and right subarrays. But this is recursion, so I don't know if there is any difference between that or just a loop.


texts: Dynamic Programming Solution to 0,1 KnapSack Problem

texts:
I am trying to understand the DP solution to the basic knapsack problem.However even after reading through a variety of tutorials ,its still beyond my comprehension.I am taking an algorithmics course and need to solve questions based on the classic knapsack problem.However unless I understand the classic problem clearly , I won't be able to make any headway to the advanced ones.Please help pointing me out in the right direction.

The recursive equation is way too confusing for me.


texts: Minimum Path cover in a Directed Acyclic Graph

texts:
Given a weighted directed acyclic graph $G=(V,D,W)$ and a set of arcs $D'$ of $D$, where the weights of $W$ are on the vertices. The problem is to partition $G$ into a minimum number of vertex-disjoint paths that cover all the vertices of $G$ subject to the constraints that:

the weight of each path is at most $k$.
each path should include at least one edge of $D'$.

What is the complexity of this problem?


texts: How is a program stored before compiling?

texts:
When we write code, after compilation the code will be converted to machine language and then stored in the hard disk. But before compiling the code, it is still in the high-level language. How and where is the memory allocated for the source code before compilation?
I assume that before compiling the code is stored in RAM. How is the code stored in RAM? Because I think we can store only machine language in RAM.
If there is any wrong with my question or it is a wrong way of asking, please comment below. It will be helpful.


texts: Proof with induction even number of letter

texts:
I have to proof that in a word $w$ the number of the letter d is always even.
Let $L \subsetneq \Sigma^*$ be a language over the alphabet $\Sigma = \{a,b,c,d\}$
such that a word $w$ is in $L$ if and only if it is $a$ or $b$ or of the form $w = ducvd$  where $u$ and $v$ are word of $L$.
Examples:
$dacad$, $ddacbdcad$, $dddbcbdcdbcbddcad$
I know there are three cases:

$|w| = 0$ the number of the letter d is zero and even

$|w| = 1$ and $w = a$ or $w = b$ same as number 1

$|w| = 5$ and $w = ducvd$ the number of letter d is even
I know how induction works, but I don't know to write the base, hypothesis and
step. I think it works with the length of $w$. Does somebody have a hint?


texts: Can this language be defined by a Context Free Grammer?

texts:
I was solving one of my practice questions, defining a language with Context Free Grammar Productions , but I am stuck on one question , Here are my attempt:

Question: $L = \{a^n b^m c^p \mid n = m + p + 2\}$

My Attempt:

S -> aaBC

B -> aBb | ^

C -> ?  (Now how can i increase length of `a` Terminal by C as i increased from B)

Is this language not context free / impossible ?


texts:
my assumption:
- we have an undirected graph with only positive edges
- the edges are sorted alphabetically:
    e.g A-B, A-C, B-D
    and e.g not C-A, D-B, A-B

I do not understand, why we need the first loop (line 1) here.
I executed the algorithm on paper on 3-4 different undirected graphs.
And everytime the first iteration of line1 ends, the algorithms finishes to find the shortest path and the remaining iterations are doing just garbage check.

Can anyone give a concrete graph example where we need the first loop?
Does the first loop to do something with the negative edges or edge direction perhaps ?

1 for i=1 to vertices.length-1
2    foreach e in edges
3        if e.v2.cost > e.v1.cost + e.weight
4            e.v2.cost := e.v1.cost + e.weight
5            e.v2.pre := e.v1


texts:
What's wrong with the following argument that $NP \subset coNP$?

let $L \in NP$; then there exists an NTM $N$ that decides $L$ in $f(n)$ time where $f(n) = O(n^k)$ for some natural number $k$.

Define $H = $ on input $z$:

run $z$ on $N$ for at most $f(|z|)$ steps.
if $N$ accepted, reject. If hasn't accepted, accept.

Then if $z \in \bar{L}$ then $N$ will not have accepted $z$ after any number of steps, so $z \in L(H)$.

If $z \in L(H)$ then $N$ hasn't accepted $z$ after $f(|z|)$ steps. If $z \in L$ then $N$ would have accepted it after $f(|z|)$ steps.

Is the problem here that computing $f(|z|)$ may not take polynomial time, in $|z|$? It seems like it should.


texts: I was thinking of radix sort, and at a sudden thought that it uses de facto the paradigm  of dynamic programming, but I soon changed my mind to greedy algorithm. Is it really a greedy algorithm?


texts: Construct a semi decidable but not decidable set using the diagonal argument

texts:
Not using anything other than the definition of SD and D

I know if A is SD, then there exists a TM M such that A = L(M), and A can be enumerated, and if A is decidable, then everything in A can be enumerated in some order.

How do I set up the diagonal matrix?


texts:
I have some difficulties performing the worst case analysis on this algorithm.
The outermost loop is executed $2N$ times.
The while loop, in the worst case, will increase by $2$ each time, so it performs $i/2$ basic operations ($*2$ because double call)

for (i=1; i<=2*N; i++) {
        j = 0;
        while (j <= i) {
            a[i] = function (function (a[i]));
            if (c[i][j] != 0)
                j = j + 6;
            else
                j = j + 2;
        }
    }

function is the basic operation.
Am I going the right way?


texts: Quick Sort: Randomized Pivot vs Median of 3/'Ninther' Pivot vs Uniform Shuffle of Input

texts:
Is the jury still out on this or do we now know which of the above mentioned ways of randomizing Quick Sort is the most optimum as far as average case running time (averaged over all possible input arrays, with all permutations of the numbers being equally likely) is concerned?

Or perhaps, has a case been made for the assertion that a generalization is not possible?


texts: importance of alternate storage in external sort

texts:
I'm trying to understand how external sorting works from the book "Data Structures and Algorithm Analysis" by Mark Allen Weiss.

The author illustrates an example where he tries to sort 81,94,11,96,12,35,17,99,28,58,41 with a memory which can hold upto M=3 numbers. He uses two input tapes Ta1,Ta2 and two output tapes Tb1,Tb2.

Ta1    81,94,11,96,12,35,17,99,28,58,41
Ta2
Tb1
Tb2

In the first step M numbers are read into memory then, sorted and written to Tb1 and Tb2 alternatively.

Ta1
Ta2
Tb1    11,81,94   17,28,99   15
Tb2    12,35,96   41,58,75

I understand how the algorithm works but, don't understand why it is important to write results alternatively. Couldn't this be achieved without alternating?


texts: Prove that the coding $\pi_k$ is effective

texts:
I have to prove that the coding $\pi_k$ is effective given that $\pi_k$ is a surjective coding of $\mathbf N^k$ and $\pi_k$ is a recursive function.

What I've got:

A coding by definition is an injective function from a set $X$ to $\mathbf N$.
I know by definition that a coding $\pi_k$ is effective if it is recursive and there exist decoding functions $J_0^k, ..., J_k^k$ for which $J_i^k=x_i$ in $(x_0, ..., x_k)$ and which are also recursive functions.

How can I find such functions or prove they exist?


texts:
I'm trying to solve this problem - https://codeforces.com/problemset/problem/711/E
I've already found and proved that the result is equal to:
$$
    1 - \frac{2^n (2^n - 1) \cdots (2 ^ n - k + 1)}{2^{nk}}.
$$
Now I need to compute it, and it's hard as $n$ and $k$ could both be as large as $10^{18}$. Computing $2^{nk}$ is easy. But I have a problem with this factorial. Result, of course, only need to be found modulo $10^6 + 3$.
EDIT:
Note that A and B must be coprime before their remainders modulo $10^6 + 3$ are taken.


texts:
From Wikipedia about randomized algorithms

  One has to distinguish between algorithms that use the random
  input to reduce the expected running time or memory usage, but always
  terminate with a correct result in a bounded amount of time, and
  probabilistic algorithms, which, depending on the random input, have a chance of producing an incorrect result (Monte Carlo
  algorithms) or fail to produce a result (Las Vegas algorithms) either
  by signalling a failure or failing to terminate.

I was wondering how the first kind of "algorithms use the random
input to reduce the expected running time or memory usage, but
always  terminate with a correct result in a bounded amount of time?
What differences are between it and Las Vegas algorithms which may
fail to produce a result?
If I understand correctly,  probabilistic algorithms and randomized algorithms are not the same concept. Probabilistic algorithms are just one
kind of randomized algorithms, and the other kind is those use the
random  input to reduce the expected running time or memory usage,
but always  terminate with a correct result in a bounded amount of
time?


texts: How to find all paths with n-distance from a node in a graph with cycles?

texts:
I have to find all the paths that have some n-distance from a start node. The destination node is not given. It seems that this problem is very hard to solve because in this scenario I am working with a geographical map, thus there exist cycles as well. Finding all of these paths must take a large amount of time because there exist so many possible paths. Let's take this example:

I have given some node on my map and have to find all paths that are 5km from that node. This would result in many paths with the same edges. Also there are extremely many different paths to calculate, so it would not be possible to calculate this in a reasonable amount of time.

Does anyone have some suggestion to this? I have considered modifications of BFS or DFS, but these, at least what I understand would take O(n!) because they have to find each path that possibly exists.


texts: Find all group of neighbors with a constraint weight

texts:
Forgive if this seems like a repeated question. However, I couldn't find a specific algorithm to my needs.

I have nodes that have weights with each other. I want to find all unique groups of nodes, with the constraint that every node in the group has a weight with every other node a value that is less than a certain pre-specified constant.

Let's take an example. The following is a table of weights where the row number and column number can be considered as node numbers.

6   15   25    4    6    1    4
15  28   19   20   15   28    6
25  19    4   26    2   10    2
4   20   26   15    1   15   29
6   15    2    1   13   20   15
1   28   10   15   12    5   16
4    6    2   29   15   16    7

Considering a weight limit of 15 the result I generated using my brute force solution looks like the following:

1  5  4
1  6  4
1  7  5  2
1  7  6
2  7  5  3
3  7  5
3  7  6
4  5
4  6
5  7
6  7

Now consider the first result 1 5 4 the weight between 1 and 5, w(1,5)=6; w(1,4) = 4; w(5,4) = 1. we can't add node 6 to this group because w(5,6) = 20.

The solution I have now takes forever when the dataset is larger. Is there an optimized algorithm that I am missing? Thanks for the help.


texts: Show that the local feature size is Lipschitz continuous

texts:
In class we defined "local features size" $\rho$ as follows:

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

Furthermore in class it was said that it "trivially" holds that $\rho(x) \le \rho(y) + d(x,y)$ for all $x,y \in C$, where $d$ is the Euclidean Metric. However, I do not see why.
I strongly suspect that we have to use the triangle inequality here, but I do not see how.
My attempts so far look as follows: Let $\rho(x) = d(x,c_1)$ for some $c_1 \in M(C)$ and $\rho(y) = d(y,c_2)$ for some $c_2 \in M(C)$. Then we have
$$\rho(x) - \rho(y) = d(x,c_1)-d(y,c_2) \le d(x,c_1)+d(y,c_2) \le d(x,c_1)+d(y,c_1).$$
(The last inequality is due to the definition of $\rho$ as the shortest distance. This is close to what we want, but I can not go further from here.
Could you please give me a hint?


texts: Assignment to make formula unsatisfiable

texts:
Lets imagine we have a satisfiable formula $F(A_0, A_1,...A_k,S_0,...,S_n)$ The problem to solve is "Is there an assignment for variables $(S_0,...,S_n)$ which will make F unsatisfiable?". One way of solving is to find all solutions for F in terms of variables $S_0,...,S_n$ and if the count is < $2^n$, the missing solution will be the answer, but the complexity of this algorithm is huge, if the number of such assignments is small.

My questions are:

Is there a way to solve the problem with less SAT solver calls?
Is it a well-known problem in theory (What I should google to read about it)?


texts: Working of PDA for $\{a^m b^n c^k \mid m=n \text{ or } n=k\}$

texts:
I understand that the language $L = \{ a^mb^nc^k \mid m=n \text{ or } n=k \}$ is context-free because it can be represented as the union of $L_1 = \{a^mb^mc^k\}$ and $L_2 = \{a^mb^kc^k\}$, which are both context-free. But I can't figure out the working of the PDA accepting $L$.
To check whether $m=n$, first of all $m$ many $a$'s will be pushed, then on every occurrence of $b$, one $a$ will be popped out, or if stack becomes empty, then remaining $b$'s will be pushed. After this, either stack will be empty, meaning $m=n$, or $m-n$ many $a$'s or $n-m$ many $b$'s will remain in the stack, meaning $m \neq n$. How can we check whether $n=k$ now?


texts: Depth of any node x in Weighted Quick-Union Algorithm

texts:
I know from Sedgewick's book on algorithms that the max depth of any node x from a set of N nodes is at most log2(N) applying the algorithm(which says to put the shorter tree beneath to avoid tall trees) and he gives an understandable proof by induction. The thing is that I have trouble visualising that result apart form the mathematical manipulations, I mean besides proving that that assumption is correct my question is how do you get to that assumption.
This are some remarks he makes before the proof:

1)The depth of the node x increases by one when merged to another tree

2)When the depth increases the size of the tree at least doubles.

But here is the thing, he says : "The size of the tree containing x can double at most log2N times" And I don't understand why.

Here is the link to a presentation he gave on the topic. http://algs4.cs.princeton.edu/lectures/15UnionFind-2x2.pdf the proof's sketch is on slide 33.

Thanks :)


texts:
I am trying to understand if someone can apply an NTM to recognize a $coNP$ language.

From the definition we know that:

$NP$ - set of languages that can be recognized by NTM in polynomial time.

$coNP$ - set of all languages that are complement to $NP$ language.

as with $P$ vs. $NP$ question, we have $NP$ versus $coNP$ question.

Unfortunately, is not defined explicitly if can one recognize $coNP$ language with NTM.

However, if we take a look at few examples from the set of $coNP$ languages, few questions emerge.

$TAUTOLOGY$ = {$\varphi$: $\varphi$ is satisfied by every assignment}

$UNSAT$ = {$\varphi$: $\varphi$ is unsatisfiable}

These languages are known to be $coNP$ language and intuitively it seems like one can construct NTM to recognize these languages. On the other hand, if one can construct NTM to recognize them why them not in $NP$ class (by definition)? Maybe not all languages of $coNP$ can be solved by NTM, just few of them which are in  $NP\cap coNP$. And if every language from $coNP$ class cannot be solved by NTM, does it mean that limitation of NTM is located in $coNP$. Does NTM have limitation at all?

I am a little bit confused, I would appreciate anyone that is willing to shine the light on this topic.


texts: Construct a PDA for at least one $w_i$ $\neq$ $w_{i + 1}^r$?

texts:
My assignment asks
Let $S =
\{
w_1\#w_2\# \dots \#w_k | k ≥ 2; (∀i ≤ k)w_i ∈ \{0, 1\}^\star
; (∃i < k) w_i\neq w_{i + 1}^r$
, i.e., not every string $w_i$ is equal to the reversal of $w_{i+1}$. Note $S ⊆ \{0, 1, \#\}^\star$.

Show that S is a CFL by a PDA, P, that accepts it.

I have been stuck on this question for approximately 20+ hours. I tried to sketch the PDA about 20 pages but still fail some cases. My friend's suggestion as store the word $w_i$ then the next state is to compare $w_{i + 1}$ to $w_i$, however, what I'm struggling is how do we compare $w_{i + 2}$ to $w_{i + 1}$ after comparing $w_{i + 1}$ to $w_{i}$. This seems impossible since the stack has to be pop out an element in order to compare the previous word. Once it's empty, we can never fill up the stack with the same elements that already popped.

Another way that I found is referring to this link:
https://cseweb.ucsd.edu/classes/su99/cse105/hw2sol.pdf.

On question 3, it has a construction for non-palindrome over $\{0,1\}^\star$. Which is similar to our case but we have a $\#$ sign between words. I.e., we have many different strings instead of this construction only need to handle one string and compare it's left and right. I have been stuck for a long time, I think I'm missing something here. Any suggestions?


texts: Does this shuffle have non-zero probability for all permutations?

texts:
I was trying to do some code golf, when I created the following algorithm to shuffle a string:

for(;k-->0;y=s,s="")for(var c:y.split(""))s=Math.random()<.5?s+c:c+s;

To explain better what it does, I've recreated it in Python:

import random
str = "Randomize me!"
print('[',str,']',sep='')
temp=""
for _ in range(len(str)): # repeat as many times as the string is long
  for char in str:        # take the string's chars and randomly construct a temporary
    temp = temp + char if random.choice([True, False]) else char + temp
  temp, str = "", temp    # use the temporary as the basis for the next iteration
print('[',str,']',sep='')

Also, per request, here it is in pseudocode:

SHUFFLE(STR)
 0 TEMP ← ""
 1 LOOP STR.LENGTH TIMES:
 2     FOR EACH CHAR ∈ STR:
 3         IF COIN-FLIP
 4             TEMP = TEMP + CHAR
 5         ELSE
 6             TEMP = CHAR + TEMP
 7         END IF
 8     END FOR
 9     STR ← TEMP
10     TEMP ← ""
11 END LOOP
12 RETURN STR

The output looks randomized to me. However, if you only consider one iteration of the algorithm, the first character put into temp is always str[0]. The second character put into temp on this iteration is always str[1], which must be next to str[0] according to the way characters are appended. Therefore, after one iteration, the probability that the shuffled string has the first character outside of the center is 0, and the probability that it is not adjacent to the second character is 0.
I tried to remedy this problem by repeating the shuffle once for each character in the string. Intuitively, it seems to work, but I can't seem to prove that all permutations of the input string can show up.

So, here's the question: do all permutations of the input string have non-zero probability as output from this shuffle?


texts: Optimal distribution of N points in non euclidean volume, where each point is furthest away from the others

texts:
Given N points, I want to find the optimal configuration for which all the points are as far away from each other as possible.

The metric I'm considering is an approximation to the perceived distance between two colors:

The colors are constrained between 0 and 255. And there are N colors of maximum pair distance I want to find, in addition to these N colors, there's a point in the origin (black) and in the topmost right-front corner (white) which are fixed in place.

This reminds me of sphere packing, but I don't know the optimal size of the sphere so that they'd fill the whole volume... And since this metric is not translation invariant, I'm not sure how to calculate the sphere positions even if I knew the sphere size.

I've tried minimizing some cost functions, such as

or the columb force inspired

But it's not very efficient, and is very dependent on initial guess (and it seems my euclidean grid-based guess isn't optimal).

Is there a generalized form of the sphere packing algorithm which would give me the global minima, without the need to minimize these complex cost functions and fall into the many local minima, or get stuck in zero gradient areas?


texts:
Assume $A$ is an array that contains sorted integers , ie $\forall\ i,j$ where $1 \le i \le j \le |A|$, $A_i \le A_j$. The numbers do not have to be unique, and the task is to check if there is at least one pair of indices $i$ and $j$ where $A_i + A_j = n$. Simple enough, here's an algorithm that does it:

CheckForPair(A, n, i, j):
    if i >= j or outOfBound:
        return false
    v := A[i] + A[j]
    if v = n:
        return true
    if v < n:
        return CheckForPair(A, n, i + 1, j)
    if v > n:
        return CheckForPair(A, n, i, j - 1)

CheckForPair(A, n):
    return ChcekForPair(A, n, 1, |A|)

Mathematically,

  $$
\begin{align}
CheckForPair(A, n, i, j) &=
\begin{cases}
false  & \text{if $i \ge j$ or $i < 1$ or $j > |A|$,} \\
true & \text{if $A_i + A_j = n$,} \\
CheckForPair(A, n, i + 1, j) & \text{if $A_i + A_j < n$,} \\
CheckForPair(A, n, i, j - 1) & \text{if $A_i + A_j > n$} \\
\end{cases} \\
\\
CheckForPair(A, n) &= CheckForPair(A, n, 1, |A|)
\end{align}
$$

This is an algorithm I have seen somewhere else and I am trying to prove its correctness. For $i$ and $j$ that are on the very ends on the array (ie $i = 1$ and $j = |A|$), it's easy to see why it is correct since:

if $A_i$ + $A_j < n$, then $i$ must increase because $j$ cannot increase.
if $A_i$ + $A_j > n$, then $j$ must decrease because $i$ cannot decrease.

However, for $i$ and $j$ that are in between, I fail to see why the above still holds.


texts: Difference between Response time, Execution time, and CPU time

texts:
I studied Computer Architecture from David A. Patterson and have came across the idea of Response time.

  Response time also called Execution time. The total time required for the computer to complete a task, including disk accesses, memory accesses, I/O activities, operating system overhead, CPU execution time, and so on.

In above definition of Response time, it is interchangeably called Execution time.

But, in Operating System Response time is one of the criteria of scheduling algorithm

I was watching a tutorial on all of the criteria of scheduling algorithm. Where Burst time or Execution time is the time process require for running on CPU

And Response time is the time between a process enters ready queue and get scheduled on the CPU for the first time.

In Operating System and Computer Architecture the idea of Response time in both cases are similar. But, Execution time is not Response time in Operating System.
I also searched in google for difference between execution time and response time. Here what I got...
Difference between Response time and Execution time

Again,

  CPU time is the actual time the CPU spends computing for a specific task.

from David A. Patterson

CPU time concept match with the concept of Burst time.

Whole concept of Response time, Execution time and Burst time making confusion.

What are the differences between Execution time and Response time?
Response time and Execution time are interchangeable?
What are the differences between Burst time and CPU time?
Burst time and CPU time are interchangeable?
CPU time and Execution time is interchangeable? If not then what are the differences between them?


texts: Is it possible to build regex-based-map with search asymptotically faster then hashmap?

texts:
From time to time I stumble across a problem of matching hashmap keys to a regular expression. In such situations I am forced to loop through all of map's elements and try to match every single key to the regex. With regex compiled to DST it should have complexity class of O(n * m) where n is number of elements in map and m is the length of the longest key in the map. Assuming m is reasonably small, we can assume it is O(n).
Above solution to this problem, although it is reasonably good, makes me think every time - is it possible to construct a data structure that would be faster (at least in theory) in searching all the keys that match the given regex. Probably it would not be linearly dependent on the number of the keys in the data structure. Is it possible? If it is possible - what would be the main idea reducing complexity?


texts: Can CPU's 'shortcut' adding 0, multiplying by 1, and multiplying by 0?

texts:
I am currently writing a program where a lot of adding 0 to numbers and multiplying by 1 and 0 occurs and it got me to wondering if the CPU 'shortcuts' (drops), these operations. I'm a CS student and this hasn't been brought up ever.

Can a CPU do this? What are the trade-offs in designing a CPU that detects +1, *1 and *0 and executes them faster?