texts: What is a good path for self-study of CS foundations/fundamentals?

texts:
I’m a self-taught software engineer who’s been working in industry for 12 years. I don’t have any formal education in CS and math was never my strong suit (although I’m willing to do the work to make it my strong suit!), but when I first started learning how to program I went through some basic courses offered by Stanford, MIT, etc.
Anyhow, I’m looking to gain a more rigorous understanding of CS, starting from the most basic, foundational pieces. I’m looking for some guidance on a good course of self-study - the order to go in, suggested resources, etc.
Given that I’m looking to understand CS fundamentals more rigorously, as I said, I’m beginning with some basic math (not my strong suit). What I’ve mapped out so far is going through the following books (and investigating prerequisites/dependent concepts for these materials on an as-needed basis):

Discrete Mathematics with Applications 4th edition by Susanna Epp
Practical Analysis of Algorithms by Dana Vrajitoru, William Knight
Book of Proof Richard Hammack
Mathematics for Computer Science by Lehman, Leighton, Meyer

I have a bit of a tendency to get down the rabbit hole and go on detours, whereby the main purpose of my study recedes into the distance as I investigate yet another area that I don’t seem to have a solid foundation in. But I’m unsure how to avoid this as some things really do need to be understood before other things. For example, without understanding some basic discrete maths, it will be difficult to talk about recursion, time complexity in a way that is more rigorous than my current understanding.
Perhaps I’d be better suited just starting immediately with MIT’s “Mathematics for Computer Science” course (6.042J) and only looking into things I don’t have a grasp on as needed?
Anyhow, sorry for the ramble. Would love some general guidance and direction for getting to where I’m trying to go. Thanks in advance.


texts: For any DFS of a directed graph, is the strongly connected component containing the vertex with the lowest post order number also contains the sink?

texts:
I am stumped on the following question:
For any depth first search of a directed graph, is it true that the strongly connected component containing the vertex with the lowest post order number also contains a sink?
I know that the sink has the highest post-order number, so I am inclined to say False, but I do not know if that reasoning is accurate.


texts: Time Complexity of the Kruskal Algorithm after sorting

texts: In case I have sorted edges already, What is the best time complexity of Kruskal Algorithm?


texts: probability wheel, redistribution of probabilities

texts:
I have a contiguous ordered data structure (0 based index):

x= [1/3, 1/3, 1/3]

Let's say I selected index 1 and increased the probability by 1/3. Rest of the probabilities each decrease by 1/6 and the total probability remains P = 1.

x= [1/6, 2/3, 1/6]

Let's say I selected index 2 and increased the probability by 1/3. Rest of the probabilities in total need to decrease by 1/3 to make the total probability remain P= 1.

x= [1/10, 2/5, 1/2]

Is there a name for this kind of data structure? I'd like to research that name and use a library instead of my custom rolled code if possible.


texts: How is CLR(1) grammar more powerful than LALR(1) grammar

texts: I am unable to understand how Canonical LR(1) grammar is more powerful than LookAhead LR(1). Both have lookahead symbols in their items and works almost similarly, so how can CLR(1) derive a larger set of languages than LALR(1).


texts:
Before we start, my textbook declares lgn as base two.

I only have one question, how did log2 become n (both highlighted in yellow in the picture)? Is it because log2 = 1, which is too small to even matter?


texts: Thompson Regular Expression Search Algorithm 3rd Stage

texts:
My professor assigned us to read Thompson' Regular Expression Search Algorithm paper. I am struggling to understand the third stage of the compiler. The first two stages are as follows:

Check that the RE is syntactically correct
Convert RE to reverse polish form

The paper states "the third stage is at its heart a pushdown stack." I don't get what that means.

It seamlessly walks us through pushing and popping off the stack to translate the RE $a(b|c)^*d$ with CNODES and NNODES.

But what is this for? I know that the purpose of the algorithm is to find all substrings in a given text that match the given RE, but I don't see how the third stage achieves this.


texts: Proving language K is undecidable using the diagonalization method

texts:
I have a problem proving the following properties of given language K:

$K = \{< M > | M\ accepts < M >\}$

I am trying to prove that language K is Turing-recognizable but undecidable using the diagonalization method.

What I tried regarding proving K is undecidable using diagonalization:

Suppose there exists a Turing machine H that decides K, denoted by H. Then H accepts if M accepts M and rejects in any other case, for any input $<M,<M>>$,so if D is a Turing machine that negates diagonals, then we construct it as following:

Run H on $<M,<M>>$.
If H accepts then reject.
If H rejects then accept.

We deduce that D is a decider because H is a decider, so D on $<D>$ - accept, but: $H<D,<D>>$ - reject, so it makes D on $<D>$, reject and that's a contradiction, so language K  is undecidable.

Proving K is Turing-recognizable:

Constructing a recognizer H for K: on input $<M,<M>$:

Simulate M on $<M>$
If M accepted - accept. if M rejected - reject.

So if $<M> \in K$ then M run on $<M>$ and halt in accept state, and if not in K, then just reject it or loop.

Would very appreciate your input and explanations on how to show it is not turing decisive using the diagonalization method. Tried to do my best and prove it the best I could.


texts: Why is the unit of image size not Pixel²?

texts:
If you calculate the area of a rectangle, you just multiply the height and the width and get back the unit squared.
Example:
5cm * 10cm = 50cm²

In contrast, if you calculate the size of an image, you also multiply the height and the width, but you get back the unit - Pixel - just as it was the unit of the height and width before multiplying.
Example:
What you actually calculate is the following:
3840 Pixel * 2160 Pixel = 8294400 Pixel

What I would expect is:
3840 Pixel * 2160 Pixel = 8294400 Pixel²

Why is that the unit at multiplying Pixels is not being squared?


texts: LL(1) grammar for postfix ternary operations

texts:
Suppose the task is to make an LL(1) grammar for postfix operations, where the only operation is ternary.

Obvious approach is

  $N$ - number
      $O$ - operation
      $S$ - expression

  rules:

  $S \rightarrow SSSO \mid N$

This grammar is obviously not LL(1), and refactoring it (removing left recursion and right branching) gives:

  $S \rightarrow NS'$
      $S' \rightarrow \epsilon \mid SSO$

which also is not LL(1). To show this, consider FOLLOW(S') and FIRST(S) - they have N in common.

Am I doing something wrong? Are there other ways to turn grammar to LL(1) or LL(1) grammar cannot be built in this case?

Note that for binary operations this approach gives LL(1) grammar:

  $S \rightarrow NS'$
      $S' \rightarrow \epsilon \mid SO$


texts: Assume we have an algorithm HC for HAMILTONIAN CIRCUIT. How is it possible to convert the HC algorithm to an algorithm HP for HAMILTONIAN PATH?

texts:
My understanding is that I have to use the algorithm for Hamiltonian Circuit to help solve the Hamiltonian Path problem.

My understanding is that we have to perform a reduction from Hamiltonian Path---> Hamiltonian Circuit (since we have an alg for Hamiltonian Circuit the reduction should be from Ham path---> Ham circuit)

But in contrast, the question says CONVERT the Ham Circuit algorithm to an algorithm to an algorithm of HP. Does this imply that the Ham Circuit problem should be reduced to the Ham Path problem?

Any guidance/feedback greatly appreciated.


texts: Check if a binary tree is a perfect tree

texts:
I'm trying to write an algorithm to check if a given binary tree is a perfect binary tree, and of course with the lowest complexity.

I was thinking to calculate the height of the tree $h$ and the number of the nodes $n$, then if $2^{h+1} -1 = n$, it's a perfect tree.
But then again, it's not very efficient.

The I thought to find the minimum tree height, and maximum tree height, and if they are equal, it's a perfect tree.
But also this case, isn't much of improvement.

Any idea how to make it better?


texts:
What are the open activation records of a recursive algorithm ?

Edit:

Activation records are the number of times that we call a function that is not finished yet. Correct?

So we can find the number of activation records only when we are given a specific input array and we cannot say something for a general array with dimension n. Or can we?


texts: How large is the seed in an encryption algorithm such as stream cipher?

texts: The stream cipher is an encryption algorithm that was designed to approximate an idealized cipher, known as the One-Time Pad. It's crucial for a stream cipher to remain secure is to have a pseudorandom generator that hard to predictable and a seed that was never used. For this to be achieved, I assume we need to have a really large seed that the most powerful computer can't predict, but I can't approximate how large the number is.


texts: counting arithmetic progressions $a, a+r, a+2r$ in a list

texts:
I have a large list $L$ of numbers and I need to count instances of elements $a,b,c \in L$ such that $a +c = 2b$. A brute-force approach would be to check all possible triples $(a,b,c)$ and this will run in $L^3$ time.

Can I do any better?


texts: Is the maximum coverage variant of Vertex Cover also NP-hard?

texts:
In Chapter 3 of "Approximation Algorithms for NP Hard Problems" edited by Prof. Dorit S. Hochbaum, there is such a sentence that "Maximum Coverage Problem is clearly NP-hard, as Set Cover is reducible to it" in p.135.

  Given a set system G and a parameter k, Maximum Coverage Problem is to find k sets such that the elements covered is maximized, and Set Cover Problem is to identify the smallest size of sets so that all elements are covered.

I am curious about how this reduction is conducted?

Further, considering the Vertex Cover problem which is to find a cover with smallest number of vertices, can I reduce this problem to the following problem in the same way:

The problem of concern:

  Given a Graph and a parameter k, find k vertices such that the number of edges linked to these vertices is maximized.

Is this problem also NP hard?


texts: Different topologically sorted order based on DFS vertex ordering

texts:
The algorithm for topological sort, in CLRS goes as follows :

call DFS(G) to compute finishing times v.f for each vertex v
as each vertex is finished, insert it onto the front of a linked list
return the linked list of vertices

Let's we have a directed graph, as in the figure here:

If we start DFS from arbitrary vertices, we get different topological orders -- for instance, if the top level DFS loop goes through vertex b first, then d, then i and finally a, one possible ordering of finishing times (largest to smallest) is :

(a), (i), (d,h,l,k,j), (b,c,f,e,g)

where each grouped term within the parenthesis indicates one iteration of DFS from the starting vertex.

If the vertices are taken in a different order, say a first, then d, and then i, the order of finishing times becomes:

(i), (d,h,l,k,j), (a,b,c,f,e,g).

If these were to indicate valid orders of events, how can they both be valid topological orders? The sorting algorithm does not mention any specific order of vertices to use in DFS.


texts:
I was reading this that details a polynomial reduction from $SAT$ to $3SAT$.

In case $k = 1$ or $k = 2$, why don't we just replace those clauses with $C_i' = \{{z_1, y_{i, 1}, y_{i, 2}}\}$ and $C_i' = \{{z_1, z_2, y_{i, 1}}\}$  respectively? Instead, it suggested to replace them by $C_i' = \{(z_1, y_{i, 1}, y_{i, 2}), (z_1, y_{i, 1}, \overline{y_{i, 2}}), (z_1, \overline{y_{i, 1}}, y_{i, 2}), (z_1, \overline{y_{i, 1}}, \overline{y_{i, 2}})\}$ and $C_i' = \{(z_1, z_2, y_{i, 1}), (z_1, z_2, \overline{y_{i, 1}})\}$ respectively.


texts:
I am relatively new to $\pi$-Caculus and have a doubt wrt sequential execution in In $\pi$-Calculus .

Does passing of common names over common channels shared between two Agents, represent a sequential execution ? so is the below reduction semantics correct if I have to represent a sequential execution between Agent A,B and C where A and B share common channel x and share data c' and similarly B and C share channel y?

\begin{equation}
\begin{gathered}  \label{eq23}
 \frac{A \xrightarrow{\overline{x}(c)} A' \quad B \xrightarrow{{x}(c').\overline{y}(c'')} B'  \quad C \xrightarrow{y(c''')}C'
 \ }
 {A|B|C  \xrightarrow{\tau} A'| B'\left\{c/c' \right\}|C'\left\{c''/c''' \right\}}
\end{gathered}
\end{equation}


texts: What areas of geometry are used in computer graphics?

texts:
I've taken intro to graphics and am interested in diving deeper into the subject.  My understanding is that the field depends a lot on geometry, but I'm having trouble figuring out exactly what geometry I should learn now that I've tackled the basics.

I found https://www.springer.com/us/book/9781852338343, but it basically doesn't go past high school geometry and linear algebra.  On the opposite end of the spectrum, I've found papers on arxiv about homological groups in geometric topology, but I assume that it would not be necessary to understand the cutting edge of extremely theoretical areas of geometry.  What areas of geometry would it make sense for me to study in order to survey the kind of math one would find while doing research in computer graphics?  Are there any resources you can recommend?


texts:
I have a problem that is similar to this that I am trying to solve:
"Given a randomly-shaped field, what is the best (fastest I guess) way to plow it? Every part of the field must be plowed, plowing outside the area is not a problem, and turning around is slower than going straight."
Basically, I'm in the situation of a farmer that wants to plow as fast as possible a weirdly-shaped field with no obstacle.

As far as I can tell, this is a covering problem for a simply-connected 2D space, but with some special restrictions.

It seems like it should be a common enough problem, but I can't seem to be able to find anything. I guess most fields have a shape similar enough to a rectangle and thus it is not an issue.
Is there any algorithm or numerical method that allows to solve this problem?

Thanks.


texts:
I would like to confirm below understanding,

  A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

  Insertion:

  In binary trees, a new node before insert has to specify 1) whose child it is going to be 2) mention whether new node goes as left/right child. For example(below image),

  To add a new node to leaf node, a new node should also mention whether new node goes as left/right child.

  Deletion:

  For deletion, only certain nodes in a binary tree can be removed unambiguously.

  Suppose that the node to delete is node A. If A has no children, deletion is accomplished by setting the child of A's parent to null. If A has one child, set the parent of A's child to A's parent and set the child of A's parent to A's child.

  In a binary tree, a node with two children cannot be deleted unambiguously.

Is this understanding correct ?


texts: Given a Turing Machine M, are there infinitely many Turing machines that recognize L(M)?

texts:
I want to show this problem is decidable by describing a TM that answers the question.
I originally thought this was quite simple, and that the answer would just be a TM that outputs "yes" for any valid input of a TM M. My reasoning was that given any TM M, we can just add a new unreachable state to it and the new machine M' will still recognize the same language as M.
However, a Turing machine can only have a finite set of states so now I'm unsure if this reasoning is correct in order to produce infinitely many Turing machines and I'm unsure where to go from here.

Any help would be much appreciated.


texts: Maximizing the rank of a binary matrix by zeroing matrix entries

texts:
Given a Square Binary Matrix.

The entries of the Matrix are the integers modulo 2 (i.e., GF(2)). The Rank of the Given Matrix is an Integer value R0.

What is the fastest known Algorithm to maximize the Rank of the matrix if the following operations are permitted:

Each 1 entry in the matrix can be replaced by a 0.
No 0 entry can be set to 1.

Approaches Tried:

Since Rank is the measure of number of independent vectors, the current attempt involved using a Gaussian elimination to simplify the matrix. The idea behind it was, if a larger Rank is possible we would be able to obtain the matrix for that Rank, by using the original and the simplified matrix. I am not sure if that is going to work.

Tried searching for some references, but not much success.


texts: Computing the minimum distance between each pain of points

texts:
I am trying to read an algorithm for computing minimum distance between each pair of points  from the book: Algorithm Design

Algorithm Design

It considers the points in a line. If the points are in a line why we need to sort them? We can start from the beginning and compute the distances from starting pint to  all the points on the  right.

Some body please guide me why we need sorting?


texts:
For my job, I need to pick up a working understanding of the implementation of type systems (in particular, how to write typing rules based on a design document). I've been given a copy of Types and Programming Languages and that's great, but I'd really like to watch someone work through it.

In my school, the course that teaches this is called "Programming Languages," but searching for "video lectures programming languages" turns up lots of stuff about how to learn C++, which I'm not interested in. I couldn't find anything on MIT Open Courseware.

I'd really like video lectures that go through TAPL, but I'll settle for anything useful. Are there good resources out there?


texts:
L = { < M > | M is a turing machine and   }

Obviously, the language which L(M) is polynomially reducible to, is context free and hence recursive, so it is a decidable language .

Now, L(M) is reducible to decidable language.

I think this language is not decidable, as this language is non-trivial in the sense of rice theorem, as no recognizable language can be a part of L(M) and even this context free language belongs to L(M).

Is my understanding right ?


texts: Without using pumping lemma, can we determine if $A =\{ww \mid w \in \{0,1\}^* \}$ is non regular?

texts:
Without using pumping lemma, can we prove $A =\{ww \mid w \in \{0,1\}^* \}$ is non regular?

Is $L= \{w \mid w \in \{0,1\}^* \}$ non regular? I'm thinking of using concatenation to prove the former isn't regular. If L is non regular then so is LL


texts: Why strokes are treated differently than fills in modern graphics pipelines

texts:
This article shows some of the issues. But basically, on the web, you have fillStyle and strokeStyle, and in WebGL you have those different ways of rendering primitive lines, but you end up needing workarounds to draw more complex lines. In CSS borders don't have patternable backgrounds, etc.

Wondering why this limitation is placed on strokes/borders, if it has some history or background on why. It seems like in many cases you want a line to have as much freedom as a "fill", such as gradients, patterns, animations, text, etc. For example, pen strokes vary in thickness all over the place, but strokes typically only support 1 width.


texts: How to calculate the efficiency of an algorithm?

texts:
So I was given this algorithm to compute the efficieny in which I found sorts an array into ascending order.

solvethis(T[1..n])
    for i = 1 to n-1 do   //n
       minJ = i           //n-1
       minX = T[i]        //n-1
       for j = i+1 to n do  //sum_{i=1}^{n} t
          if T[j] < minX then ** //sum_{i=1}^{n} t-1
             minJ = j             //sum_{i=1}^{n} t-1
             minX = T[j]         ////sum_{i=1}^{n} t-1
      T[minJ] = T[i]      //n-1
      T[i] = minX         //n-1

I also listed the number of times the line of code is run. I need to find the efficiency and how many time the line at ** is calculated. Any help is appreciated thank you.


texts:
Suppose I have a directed graph $G = (V,E)$. Suppose that $v_1$ and $v_2$ are two nodes in the graph. Am I correct the number of simple paths (that is, it has no cycles) from $v_1$ to $v_2$ is $O(E)$? Is it true for the special case of directed acyclic graphs?

Bob


texts: Recover PRNG description from consecutive outputs

texts:
Given the outputs of the pseudorandom numbers generator how can one determine the type (e.g. Linear Feedback Shift Register), Multiply-With-Carry, Linear Congruential Generator etc.) and recover the function and the seed?

The given array of numbers is for sure generated by PRNG (not Cryptographically Secure) - this is known in advance. The outputs are clean, the PRNG is a black box returning consecutive numbers (no modified, no skipped values. Now the task is to find the function and seed from the values.

The simple idea is try all schemes until match is found, but I am interested in more algorithmic approach.


texts:
I'm not sure if my logic is correct when it comes to the algorithm for decision problems. The concept is confusing me when I fail to distinguish its answer from that of a proof.

For example:

Given two finite automata $M_1, M_2$ that operate on a common alphabet, find an algorithm to show that:

$$L(M_1) \subseteq L(M_2)$$

And how I viewed it was:

Find a string $w$ from the alphabet $\Sigma$
Feed $w$ to $M_2$; if accepted then $w$ is part of $L(M_2)$
Feed $w$ to $M_1$; if accepted then $w$ is part of $L(M_1)$
If $w$ was accepted by $M_2$ and $M_1$, then $L(M_1) \subseteq L(M_2)$
Otherwise reject

Unlike proofs which require mathematical arguments, algorithms for decision problems seem more like a logical flow or sequence description. If it were a proof I would have to perhaps design a language or expression using properties and lemmas where as here I just describe the process of determining if the statement can be answered (via "yes" or "no").


texts:
A question from chapter 3 of Michael Nielsen's [Neural Networks and Deep Learning]:

  It's tempting to use gradient descent to try to learn good values for hyper-parameters such as the regularization parameter $\lambda$ and the learning rate $\eta$. Can you think of an obstacle to using gradient descent to determine values of $\lambda$ and $\eta$?

What are the challenges of using gradient descent on hyper parameters λ and  η to find out their optimum values?

C is the L2 regularized cost function.

n is the length of the training data

w is the weight

The Learning rule for the weights will be:

I am having trouble understanding how λ and η will affect the cost function.
I know that we should decrease η as we get closer to the Cost function minima.
I don't have a clue how to optimize λ.
I think that the values of the hyper parameters will change for every epoch so there can't be constant optimal values.


texts: Simple shape matching, refine 'best' candidate based on contour deviation ? Or alternative (Python/C++ and OpenCV etc.)

texts:
apologies if this question is not composed correctly I can revise if necessary.
I am essentially doing template matching from a large array of candidate images. I am actually interested in the 'best' available match - best being subjective, but ultimately what a human would likely perceive as closest (smooth outline, retaining shape, etc).
I have done a lot of work on identifying close matches, but Hu and Zernike scoring aren't getting me that final step.
The image I have attached shows (I just drew these, to illustrate the point, they are not actual data) a template and two matches showing the deviation from the templates contour.
The red image shows (theoretical) deviations for a lower quality match and green a better quality match. Essentially I am defining the lower quality match as more extreme swings in the deviation from my templates contour - which I am trying to illustrate on my (poorly drawn) graph - I'm not sure how to extract this data, or analyze it effectively - just considering it.
I am really looking for advice or concepts on how I can refine my 'top 500' hu scored matches to get the best defined shape match (or, at least improve my ranking). My actual data is a similar complexity ie not photos and I am certainly seeing some better matches with a worst hu score in my current ranking. I'm primarily using Python/C++ and OpenCV etc.
Any advice ?


texts: Deterministic construction for trapezoidal decomposition

texts: There is a nice decomposition called trapezoidal to process point location queries given a set of disjoint generally curvilinear segments. I found the randomized algorithm for building this type of decomposition in Berg's book on computational geometry. Can someone point me out papers which report deterministic algorithms with only a little polynomial overhead which provides the same capabilities of trapezoidal decomposition for point location ?


texts: Computational models - proving language is decidable

texts:
I tried to prove that the following language is recursive/decidable/in R: for $\Sigma=\{0,1\}$, $k$ a positive integer:
$$
L_k= H_\text{TM,epsilon}\cap \Sigma^k
$$
where $H_\text{TM,epsilon}=\{\langle M\rangle\mid M \text{ is a TM that halts on epsilon input}\}$

It is easy to prove because $L_k$ is finite, but I didn't notice this and tried to prove it by finding a decider TM for it.
I thought that since the encoding of the TM is of length $k$ then it can't have more than $2^k$ states, and by running it on epsilon for $2^k$ steps, if it halts by then than accept otherwise reject.
I was told that it's incorrect - is it a wrong solution. How can I prove this using this method (and not the way I mentioned about $L_k$ being finite)?


texts: How to solve recurrences with transcendental terms?

texts:
Problem:

  A number is said to be a magic number, if the sum of its digits, taken again and again till it becomes a single digit number, is 1.
  Example: $289 => 19 => 10 => 1 => 289$ is a magic number
  but, $20 => 2 =>$ not a magic number.

So the simple algorithm is to keep doing the digit sums till we reach a single digit number. I tried to calculate the time complexity of this algorithm, and came up with the following recurrence:

$$T(n) = T(lg\ n) + O(1)$$

Let us say we have a number $N$ to test for magic number. The number of digits in this number is $O(lg\ n)$, so the sum of its digits is at most $9*lg\ n$ which is $O(lg\ n)$. So we have one smaller subproblem of size $lg\ n$ and some constant work to return data.

How do I solve this recurrence? The answer would be, ostensibly, the number of times I have to take $log $ of a number to get to 1. Is there a direct equation for this?


texts: Explanation for the regular expression for the set of all string over the alphabet {0,1}

texts:
Why does set of all strings over the alphabet {0,1} is represented by (0+1)*? As per my understanding (0+1) means either 0 and 1 and * means 0 or more occurrence of the given string. Now when we do (0+1)* it looks like we have to select either 0 or 1 and do a * on that so the resulting should be something like

$\{\epsilon,0,1,00,11,000\dots\}$

but why is it following?

$\{\epsilon,0,1,00,01,10,11\dots\}$


texts:
Wikipedia defines the IP complexity class as follows:

  A language $L$ belongs to IP if there exists $V,P$ such that for all
  $Q$, $w$,
  $$w\in L\Rightarrow Pr[V\leftrightarrow P\text{ accepts }w]\geq2/3$$
  $$w\notin L\Rightarrow Pr[V\leftrightarrow Q\text{ accepts }w]\leq1/3$$

Note that this definition is asymmetric; it says (if we are polynomial-bound) we can be convinced $w\in L$, but says nothing about convincing us that $w\notin L$. We could define a class coIP containing the complements of languages in IP; that is

  A language $L$ belongs to coIP if there exists $V,P$ such that for all
  $Q$, $w$,
  $$w\notin L\Rightarrow Pr[V\leftrightarrow P\text{ accepts }w]\geq2/3$$
  $$w\in L\Rightarrow Pr[V\leftrightarrow Q\text{ accepts }w]\leq1/3$$

It turns out IP=PSPACE and clearly PSPACE is symmetric under taking complement. Thus IP=coIP. Is there a direct way to see this? That is,

  Given a proof system $(V,P)$ for proving membership in $L$, can we use
  it to construct a proof system $(V',P')$ for proving membership in
  $\bar L$?


texts: Average Branching factor with implicit graphs

texts:
i have to calculate the average branching factor of the given successor function(pseudo-code) for every $m,n \in N$:

succ (x,y) = {(x-1 `mod` m, y), (x+1 `mod` m, y), (x, y-1 `mod` n), (x, y+1 `mod` n)}

with $n \geq m^{2}+2, n \geq 1$ and {} represent a mathematical set.

What i know is that the average branching factor is the sum of all outdegrees divided by the amount of nodes(without leaves).


texts: Why are there two not operators in lambda calculus?

texts:
From Wikipedia:

$\mathrm{true} = \lambda a. \lambda b. a$
$\mathrm{false} = \lambda a. \lambda b. b$
Because true and false choose the first or second parameter they may
be combined to provide logic operators. Note that there are two
version of not, depending on the evaluation strategy that is chosen.
$\mathrm{and} = \lambda p . \lambda q . p \, q \, p$
$\mathrm{or} = \lambda p . \lambda q . p \, p \, q$
$\mathrm{not}_A = \lambda p . \lambda a . \lambda b . p \, b \, a$   (This is only a correct implementation if the evaluation strategy is applicative order.)
$\mathrm{not}_N = \lambda p . p \, (\lambda a . \lambda b . b) \, (\lambda a . \lambda b . a) = \lambda p . p \, \mathrm{false} \, \mathrm{true}$   (This is only a correct implementation if the evaluation
strategy is normal order.)

I know what applicative order and normal order are (eager evaluation vs lazy evaluation of arguments to functions). But I don’t understand why the two nots don’t work in both of these evaluation strategies.


texts: Isomorphism of finite dimensional polynomial algebras over finite fields

texts:
For a prime power $q$, consider polynomials $f_1,f_2 \in \mathbb{F}_q[x]$. Then, do we have an efficient way of checking whether there exists an algebra isomorphism between:

$$\frac{\mathbb{F}_q[x]}{\langle f_1 \rangle} \text{and} \frac{\mathbb{F}_q[x]}{\langle f_2 \rangle},$$

and computing one such isomorphism if it exists?

I think an intermediate step will be to factorise $f_1$ and $f_2$ into products of irreducible polynomials over $\mathbb{F}_q$, which can be done efficiently using Cantor-Zassenhaus algorithm. Any hints on how to proceed?


texts: Number of ways to choose same number of elements from two different sets

texts: Given two sets of elements S and R, with p elements and q elements respectively. 1 <= p,q <= n. Now, the number of ways to choose same number of elements from set S and R is $$\sum_{i=0}^{\min(p, q)} pCi * qCi$$. I want to calculate the result for all possible combinations of p and q. I can think of a O(n^3) solution by first calculating all the mCr values for all possible combinations of m and r. And then for each pair of (p, q) answer is the sum of products of the pre-calculated terms. Is there any way to do it within O(n^2) time?


texts: Can specific programs or software be ascertained from the hardware?

texts: I having been thinking about software and hardware and their relationship. I am a layman and do not have specialized knowledge on the subject. I wondered whether if studying a particular hardware a scientist could find out what software or programs are within the computer and if possible could I be given resources to read more about such similar subject matter. Thanks!!


texts: Which languages, if any, implemented parametric polymorphism before ML?

texts:
In particular, was there any kind of implementation at the time Christopher Strachey wrote Fundamental Concepts in Programming Languages?

In that work, Strachey lists Ad Hoc and Parametric polymorphism as the two main classes of polymorphism.  But while examples of limited ad hoc polymorphism can be found in languages at that time, I can't find any examples of contemporary languages genuinely implementing parametric polymorphism.  The IFIP Working Group produced a proposal for parametrised type constructors in Algol 68 but it was never implemented.

According to The main features of CPL, CPL had the general type.  At the time the article was written, this was just a placeholder indicating the expectation that some variety of runtime polymorphism would be added later. The most recent version of the manual that I can find describes only ad hoc polymorphism (operator overloading and type-casting) and gives no indication that the general type was intended for anything other than that.   I've found claims that CPL had parametric polymorphism but no evidence.  The FCPL lecture notes describe what looks like syntax for algebraic data types that might be parametric, but that detail isn't covered and in any case this is syntax which it says will "probably be adopted in CPL" (and there's no evidence that it or anything like it ever was). Of course, it doesn't help that the CPL compiler wasn't implemented till around 1970, and the project abandoned a few years later.

Was Strachey describing contemporary practice at all?  Or was this largely a summary of academic thinking and his ambitions for CPL?


texts: An edge that connects more than two nodes in a graph?

texts:
Is there a way to create a single edge on a graph that connects 3 or more nodes? For example, let's say that the probability of Y occurring after X is 0.1, and the probability of Z occurring after Y is 0.001, but the probability of Z occurring after both X and Y occur is 0.95. If the probabilities are assigned to each edge as weights, how can I make this happen?

$$X _\overrightarrow{0.1} Y$$

$$Y _\overrightarrow{0.001} Z$$

$$\overrightarrow{X \underrightarrow{} Y \underrightarrow{0.95}} Z$$


texts: Big-O Solving Recurrence Relation by iteration with fractions

texts:
I was trying to solve the recurrence relation in order to get a some big-O bound $$ B(n) = B(n-4) + \frac{1}{n} + \frac{5}{n^{2} + 6} + \frac{7n^{2}}{3n^{3} + 8}$$  by following the accepted answer here. I expanded which resulted in $$ B(n) = B(n-8) + \frac{1}{n-1} + \frac{5}{(n-1)^{2} + 6} + \frac{7(n-1)^{2}}{3(n-1)^{3} + 8} + \frac{1}{n} + \frac{5}{n^{2} + 6} +  \frac{7n^{2}}{3n^{3} + 8}$$

This lead to $$ B(n) = B(n-4k) + \frac{1}{n-k} + \frac{5}{(n-k)^{2} + 6} + \frac{7(n-k)^{2}}{3(n-k)^{3} + 8} + \frac{1}{n-k} + \frac{5}{(n-k)^{2} + 6} +  \frac{7(n-k)^{2}}{3(n-k)^{3} + 8}$$ However, I get stuck when replacing $k$ with $n$ since this results in dividing by zero. How do I proceed? Can it solved by the iteration?


texts:
I'd like to devise an algorithm which, given n non-intersecting line segments in
the plane and a point p that does not lie on any of these segments, determines the region of the plane that is “visible” to p (see the image I've provided below). Ideally, this algorithm should run in O(n log n) time.


texts: Prove that $I(A;B|C)=0$ given $I(A;B)=0$

texts: Let $A$, $B$ and $C$ be 3 discrete random variables. If $A$ and $B$ are independent ($I(A;B) = 0$, where $I$ represents the mutual information), how can we prove that $I(A;B|C)=0$? When I draw a Venn diagram this seems trivially true, but I just cannot find a way to prove it.


texts: minimum number of states for the regular expression

texts:
Could somebody please tell me if there is a way to create a DFA with 8 states for the regular expression $$(111 + 11111)^*$$
I was able to create a DFA with 8 states, but the place I saw the question has answer as 9 states. And if possible, could you please show me the DFA.

Thanks


texts: Is it possible to make a Turing Machine that accepts the language $\{\alpha\alpha\alpha | \alpha \in \{a, b\}^∗\}$?

texts: I'm having a lot of problems trying to make a Turing Machine that accept that language, is it even possible to make it? and if so, how can I proceed to make the Turing Machine?


texts: Do Approximation Algorithms Analyzed in the Worst Case?

texts:
From wikipedia:

For some approximation algorithms it is possible to prove certain properties about the approximation of the optimum result. For example, a $ρ$-approximation algorithm $A$ is defined to be an algorithm for which it has been proven that the value/cost, $f(x)$, of the approximate solution $A(x)$ to an instance $x$ will not be more (or less, depending on the situation) than a factor $ρ$ times the value, OPT, of an optimum solution.
$$\begin{cases}\mathrm{OPT} \leq f(x) \leq \rho \mathrm{OPT},\qquad\mbox{if } \rho > 1; \\ \rho \mathrm{OPT} \leq f(x) \leq \mathrm{OPT},\qquad\mbox{if } \rho < 1.\end{cases}$$

For a maximization problem, a $\rho$-approximation algorithm means that, for an instance $x$, $\rho \mathrm{OPT} \leq f(x) \leq \mathrm{OPT}$, for any $\rho<1$. Is this mean that in the worst case the algorithm produces a solution that is at least $\rho \mathrm{OPT}$? Or is this in the average case? Because there are some instances where the algorithm find the optimal solution.
I mean, if the algorithm is executed, say $10000$ times (with randomly generated instances) and produces $\mathrm{OPT}$, say $9995$ times and $5$ times it produces a value that is greater than $\rho\mathrm{OPT}$. What can we say about the algorithm then?


texts: Finding paths with smallest maximum edge weight

texts:
I need to find the easiest cost path between two vertices of a graph. Easiest here means the path with the smallest maximum-weigth edge.

In the above graph, the easiest path from 1 to 2 is:

1 > 3 > 4 > 2

Because the maximum edge weight is only 2. On the other hand, the shortest path 1 -> 2 has maximum weight 4.

So it's an MST problem. I am thinking I will use Kruskal's algorithm to build the tree, but I'm not sure how exactly. I will know the edges but how do I "reconstruct" the path? For example, given vertices 3 and 2, how do I know to go left (top) of right in the tree? Or do I try both ways?


texts: How can we design an efficient warehouse management program?

texts:
Assume that we want to develop a warehouse management system, which picks up plastic boxes and stacks them on a pallet. A pallet has a maximum of 5 vertical box stacks and the maximum height of a box stack is 1400 mm. There are 3 box sizes with varying heights (other dimensions are the same). The heights of the boxes are 170 mm, 200 mm and 270 mm. An item is possible to place only in one type of box. All boxes are compatible to stack with each other. There are only two objectives: the number of completed pallets should be minimal, and the height difference of towers of boxes can be at most 500 mm.

The goal is to design a warehouse management program, which takes the order as an input, that is, the information of ordered items and how many boxes has been ordered. The program should determine how many boxes of each product should be stacked on a determined pallet and on a specific stack. A single product is always associated with only one box type.

How should one construct this kind of a program? I'm looking for general design guidelines and the methods to achieve the desired result. All tips and advices are welcome. I appreciate your effort.


texts: Bounds on the number of rotations in the insertion operation of a Red Black Tree

texts:
I am having some trouble understanding why people say that contrary to what happens with AVL trees, there is a bound on the number of rotations occurring in an insertion with a Red Black Tree.

From what I've gathered, there are several special cases to take into consideration in the fixUp algorithm posterior to the standard BST insertion on the tree. But from all those cases, only one will put the grand-parent node as red, so only this case may require subsequent work (if the grand-grand parent exists and is a red node).

Consider this (extreme) case:

This tree would force an lot of rotations, as the black nodes will keep moving down and creating a red-red collision upper in the tree.

I can only imagine that such a tree cannot effectively be built, so that this is not a situation that could feasibly arise?

Thanks


texts: Counting and finding all perfect/maximum matchings in general graphs

texts:
Recently i've been dealing with a problem that led me to the following questions:

Is there a good algorithm to enumerate all maximum/perfect matchings in a general graph?
Is there a good algorithm for finding all maximum/perfect matchings in a general graph?
Are these two problems equivalent in their complexity?

I've stumbled upon the following references:

Algorithms for Enumerating All Perfect Maximum and Maximal Matchings In Bipartite Graphs- Suggesting an algorithm for enumerating all maximum matchings in a bipartite graph.
Finding All the Perfect Matchings
in Bipartite Graphs- Suggesting an algorithm for finding all perfect matchings in bipartite graphs

Both algorithms' complexity depend on the number of perfect matchings in the graph (meaning exponential running time in the worst case).

Moreover, both articles deal with bipartite graphs, I couldn't find similar articles dealing with the same problem in general graphs.

I'd appreciate information and references about the above problems.


texts: Traveling Salesman's Tour Approx Algorithm: is this really a Hamiltonian Path?

texts:
I'm given this problem:

Consider the following closest-point heuristic for building an approximate traveling-salesman  tour. Begin with a trivial cycle consisting of a single arbitrarily chosen vertex. At each step, identify the vertex u that is not on the cycle but whose distance to any vertex on the cycle is minimum. Suppose that the vertex on the cycle that is nearest u is vertex v. Extend the cycle to include u by inserting u just after v. Repeat until all vertices are on the cycle. Prove that this heuristic returns a tour whose total cost is not more than twice the cost of an optimal tour.

This is the same as Prim's algorithm.  Unless I'm missing something, this is not an approximate traveling salesman tour since the traveling salesman requires a Hamiltonian path where we don't revisit any nodes, but on many graphs this algorithm seems to require revisiting nodes to get back to the source node.  Am I wrong or is this problem unclearly worded?


texts: Confusing notation in concatenation of error correcting codes

texts:
Define an $(m,q,d,k)$-(block) code $C$ to be a code with block size $m$, alphabet $0\ldots ,q-1$, and (non-relative) rate $k$. Meaning: $k=log_q (|C|)$ (if we think of $C$ as a set of legal codewords) ($d$ is the distance which isn't important for this particular question). Such a code could also be thought of as a function:
$$C:[q]^k\rightarrow[q]^m$$
As it takes a word of length $k$ over $[q]$ and encodes it into a word of length $m$.

To my understanding, given an $(m,q,d,k)$ code $C_{out}$ and an $(m',q',d',k')$ code $C_{in}$ such that $q'^{k'}=q$, we can define the concatenation of $C_{out}$ with $C_{in}$ to be a code which takes an input for $C_{out}$, encodes it using $C_{out}$, and then encodes each letter of the resulting word using $C_{in}$.  If this is how a concatenated code truly works, then if we denote the concatenated code $C'$ it should be thought of as a function:
$$C':[q]^k\rightarrow [q']^{m*m'}$$
However, the common notation for such a codes (as can be seen here, for example) is:
$$C_{out}\circ C_{in}$$
Which is exactly in the opposite order to what we would expect if we think about the concatenated code as a composition of functions.

Is there a problem with my understanding of concatenated codes, or is the notation simply confusing? And if my understanding is good, is there a reason the aforementioned notation is common?


texts: Converting a number from N to 0 in binary

texts:
Trying to solve this problem since 2 days. Still unable to figure out even a basic approach.

Given a number $N$ in binary ($1$ to $10^5$), we need to convert it to $0$ using only 2 operations. Given a binary value of a number with length $M$ ($0$ indexed), we can:

flip the $i$th bit from $0$ to $1$ or $1$ to $0$ only if the $(i+1)$th bit is 1 and all bits at positions from $i+2$ to $M-1$ are NOT $1$, or
flip the rightmost bit unconditionally.

So the problem is to figure out the minimum number of steps to do the conversion.

For example:
if $N=8$,
then its binary representation is $1000$.

So to convert $1000$ to $0000$, the following steps apply:

1 -  1001 (flipping the rightmost bit unconditionally).
2 -  1011 (flipping bit at position 2 as bit at position 3 = 1 and there are no more 1 after it. There are no more characters infact. It is the last character).
3  - 1010 (flipping the rightmost bit unconditionally).
4  - 1110 (flipping the 1st bit as 2nd bit is 1 and no other bits after that are 1)
5  - 1111 (flipping the last bit unconditionally).
6  - 1101 (flipping 2nd bit as 3rd bit is 1 and no other 1 after 3rd bit).
7  - 1100 (flipping the last bit unconditionally).
8  - 0100 (flipping 0th bit as 1st bit is 1 and no other 1 after 1st bit).
9  - 0101 (flipping the last bit unconditionally).
10 - 0111 (flipping 2nd bit as 3rd bit is 1 and no other 1 after 3rd bit).
11 - 0110 (flipping the last bit unconditionally).
12 - 0010 (flipping 1st bit as 2nd bit is 1 and no other 1 after 2nd bit).
13 - 0011 (flipping last bit unconditionally).
14 - 0001 (flipping 2nd but as 3rd bit is 1 and no other bit after 3rd bit).
15 - 0000 (flipping last bit unconditionally).

So the result is $15$ as it took $15$ steps.

Unable to solve this problem. Please help.


texts:
I am programming CPU cache simulator and I am supposed to implement removing of entries. I will not use LRU but just random.

I am not really clear, when should I call the removing function? When cache (2 or 4 caches) are full and CPU wants to write into cache where all (data and tag) of specific indexes are same? Are there some other possible situations, or maybe I am completely wrong?

Hope you understand my question, if no, please tell me and I will edit my question. Thank you in advance.


texts: Are two languages regular if the union is regular?

texts:
Statement:

  For any two languages $L_1$ and $L_2$ if $L_1 \cup L_2$ is regular, then $L_1$ and $L_2$ are regular.

Why is this statement false? Could somebody give me an example.


texts: Converting DFA to Regular Expression "equation-method(?)"

texts:
I have trouble understanding my text-book on how to convert a DFA to a Regular Expression using "equation-method"(don't no what it's called).
If someone could explain step by step in detail what's going on it would be great(or maybe a few steps to get me going). (Old exam-task)

I have this DFA:

And the solution is:

I think I understand the left column.
First expression in left column: $E_0 = 0E_1 + 1E_2$. $E_0$ is a regular expression that "represents the start-state $q_0$". You can choose two paths from $q_0$. On a zero you go to $q_1$ (Zero concatenated with the regular expression $E_1$).
Or on a one you go to $q_2$ (one concatenated with the regular expression $E_2$).
And the same principle goes for the rest of the column. How do I continue from this?


texts: Algorithm for fastest division below threshold

texts:
Take a number i. You need to split it in two pieces as many times as necessary so that all splits are less than or equal to j. How does one obtain this with the minimum number of splits? Examples:

Splitting it in half is optimal here:

i = 4, j = 2
4 -> 2, 2 // (1 split)

However, splitting in half is not optimal here:

i = 9, j = 3
9 -> 5, 4 // Split nine in half
5 -> 3, 2 // Then you have to split the 5
4 -> 2, 2 // and the 4 (3 splits)

The optimal solution here would be:

i = 9, j = 3
9 -> 6, 3
6 -> 3, 3 // (2 splits)

Is there some straightforward way to obtain the optimal split without brute-force iteration?


texts: Doesn't a formula that tests each boolean string of length $N$ force SAT to execute at least $2^N$ tests?

texts: Since you are free to chose any formula for the SAT problem, doesn't the choice of a formula that requires a test for each subset of the group of variables force it to perform $2^N$, essentially making SAT unsolvable in polynomial time in respect to the number of variables on the input?


texts: Prove Product Partition is NP-complete in the strong sense

texts:
I am trying to understand how to prove that the Product Partition problem is NP-complete in the strong sense. The problem is similar to the normal Partition problem, except in this case the product of the subsets is taken instead of the sum.

I have only managed to find one paper discussing the issue: paper

This proof is very complicated and tough to understand. Could someone provide a simpler explanation of the process?


texts: Difference between $F(n)=O(n)$ and $F(n)\le O(n)$?

texts:
In a research paper I read $F(n) \leq O(g(n))$ and $F(n) \geq \Omega(h(n))$.

Isn't this the same as $F(n) = O(g(n))$ and $F(n) = \Omega(h(n))$?

Is there a difference?


texts: Do any programming languages use general recursive functions as their basis?

texts:
This is a naïve and, therefore, possibly malformed question, so apologies in advance!

My view is that a Turing Machine can be seen as the computational basis for procedural/imperative programming languages. Similarly, the lambda calculus is the foundation for functional programming languages.

I have recently learnt that the Church-Turing Thesis also shows mutual equivalence with a third model of computation: general recursive functions. Are there any programming languages that use this as their model of computation? If not, is there a technical reason why; i.e., besides "No one's tried yet"?


texts: Multiple knapsack problem with equal profit and different weight

texts:
I am doing a research about the load balancing problem in 5G system, but I am not sure if my problem is a NP-complete problem.

The problem is:

given a set of n items and a set of m knapsack
capacity of knapsacks are equal
the weight of item j in knapsack i is w[i][j],that means weight of a item in each knapsack are different
each profit of items are equal

I am not trying to put all item in least knapsack like bin packing problem.
I saw some similar question answered, but no one is identical to this case.
In this case, the goal is to put as more as possible item with m knapsacks.
Is the problem a NP-complete problem?


texts: Can a context-senstive gramma contains production rule $cB\rightarrow Bc$?

texts:
Some textbook show that the grammar $G=(N,T,P,S)$ below belongs to context-senstive grammars:

S->aSBC
S->abc
cB->Bc
bG->bb

where N={S,B}, T={a,b,c}.

I am confused by the fact that the production rule cB->Bc cannot satisfy the definition of a CSG. So, why is the above grammar belongs to CSG?


texts: Distance preserving projection for Euclidean distance

texts:
Suppose I have two vectors $V_1, V_2 \in R^l$. Can they be converted into bit vectors $B_1,B_2 \in \{0,1\}^l $ such that if $V_1, V_2$ is close in Euclidean distance, $B_1,B_2$ is close in hamming distance?

Please note that this is a little different from locality sensitive hashing, where    each vector will be hashed into a bucket with certain probability and $l$ such hash functions will be combined to generate $B_i$. The problem appears to be simpler than that as I am not concerned with dimensionality reduction, which is a goal of LSH.

Side note: Please feel free to add new tags as I am not sure which tags should go here.


texts:
I need to come up with an algorithm that iterates through an array and if any element appears m times, then the array needs to be modified so that it only appears min(2, m) times. For example, if A = [2, 2, 2, 3, 4, 4, 5, 5, 5] and m = 3, A = [2, 2, 3, 4, 4, 5, 5]. It is easy to do with extra space or nonlinear time but I want to know how to do it in O(n) time and space. The array is already sorted.

It is apparently a variant of the "remove all duplicates of a sorted array" problem, but the O(n) algo for that works because it finds all distinct elements and inserts them one by one. In the problem above, you can't do that because you need to check how many times the particular element occurred.

I've tried the following algorithm:

def variant2(arr, m):
    vacant = 1
    for i in range(1, len(arr)):
        if not arr[i] == arr[vacant - 1]:
            if i - vacant + 1 == m:
                vacant += min(2, m) - 1
                arr[vacant] = arr[i]
                vacant += 1

    temp = arr[:vacant][:]
    return temp

but this doesn't work as the overwriting of the "vacant" index will cause an element that wasn't duplicated before to be duplicated. For example, A = [2, 2, 2, 3, 4, ...] with m = 3 will become A = [2, 2, 3, 3, 4....].


texts: Connecting islands to the mainland via flood fill

texts:
Say I have a large area filled using floodfill:

Where the area in white has been flooded, and all other ares are not connected. I would like to "bridge" these islands to the main area in white, but I'm not sure of the best algorithm to use that would do this most efficiently.

My current method is to find the nearest non-flooded valid space (that I'll call point $x$) to all grid squares, then use their distance as their priority in a priority queue, with smallest distance going first. I then destroy all walls in a straight line between the two with shortest distance, re-flood from point $x$, and after doing so examine all the newly flooded spaces and find their shortest distance to non-flooded areas, adding them to the priority queue. Repeating this until eventually there are no islands left.

Pseudo code below:

bridge_check = priority_queue()
for each space in flooded_area:
    dist, other_space = nearest_non_flooded(space)
    bridge_check.add(val=(space,other_space), priority=dist)
while(!bridge_check.isEmpty()):
    flooded, non_flooded = bridge_check.get()
    if non_flooded in flooded_area:
        continue
    remove_walls(flooded, non_flooded)
    newly_flooded = reflood(flooded_area, from=flooded)
    for each space in newly_flooded:
        dist, other_space = nearest_non_flooded(space)
        bridge_check.add(val=(space,other_space), priority=dist)


texts: Periodic Pattern recognition In a Sales Log

texts:
I'm pretty new in this field and I need some advice for my first professional challenge.

I'm trying to create a sort of client segmentation from a my company's sales log which has the peculiarity that the clients has a pretty long-term relationship and a periodic behavior.

Based on when does he has bought (Ex: Twice a month, once a week, once every three months...) determine the frequency of purchase.
I need to figure out the phase of this client, so I can know in what stage of his/her period is.
I would like to know how much does it buys each time purchase amplitude

Once i have his three elements I want to be able to use that info to detect when the client changes his behavior (specially when they have an missing period or they decrease the buying amplitude)

I would like to get a really neat result, because i think that i will use it to a Markovian process.

So far I've tried astropy's lomb-scargle implementation but it seems that is too-precise and needs to many data points.


texts: efficient cumulative all over combinations of boolean vector elements

texts:
Problem

Given a vector of bools of length n I wish to compute the logical and over all subsets up to length k.

By logical and I mean that for a subset to give true all of its elements must be true.

Example:

With a boolean vector of 3 elements (indexes below each for reference below)

v = [true, true, false]
i =    0     1     2

The intended result for all subsets (i.e. up to k = n):

result = [true, true, false, true, false, false, false]
i.e        0     1      2     0&1   0&2    1&2   0&1&2

where the true at 01 is the result of true & true from the 0 and 1 indices in the original vector.

If we limit up to k = 2 the intended result is:

result = [true, true, false, true, false, false]
i.e        0     1      2     0&1   0&2    1&2

The order of the output need not be this one.

What I want

I want an algorithm that will not perform more operations than it needs to specify the entire result. Reducing the number of operations should lead to improved performance.

My current approach is to iterate the combinations and subset the vector with each and reduce it via logical &. But this is very wasteful as for 012 I recompute the result of 01... There must be a better algorithm but I am having no success.


texts:
I am interested in calculating the $n$'th power of a $n\times n$ matrix $A$. Suppose we have an algorithm for matrix multiplication which runs in $\mathcal{O}(M(n))$ time. Then, one can easily calculate $A^n$ in $\mathcal{O}(M(n)\log(n))$ time. Is it possible to solve this problem in lesser time complexity?

Matrix entries can, in general, be from a semiring but you can assume additional structure if it helps.

Note: I understand that in general computing $A^m$ in $o(M(n)\log(m))$ time would give a $o(\log m)$ algorithm for exponentiation. But, a number of interesting problems reduce to the special case of matrix exponentiation where m=$\mathcal O(n)$, and I was not able to prove the same about this simpler problem.


texts:
I am working on some set theory and am trying to prove how a set can have the property $A^* = A$.

For set $A=\{0^n1^n \mid n \ge0\}$, I still do not understand exactly what $A^*$ is. For example, I thought $A^*$ is the enumeration of the set $A$ so

$A^* = \{\epsilon,01,0011,000111,00001111,....\}$

Any helping in at least understanding what $A^*$ is for this problem would be much appreciated!


texts: Is there a way to access hard drives while computer sleeps?

texts:
Is there any way at all possible or possible with hardware (aside from a NAS) to access hard drives while the computer is in a low power mode such as sleep (aside from WOL)?

For example, can I log into a networked drive located on the computer and spin it up to access data without the computer coming out of low power mode?


texts: Can regular languages be Turing complete?

texts:
I was reading about Iota and Jot and found this section confusing:

  Unlike Iota, where the syntactic tree for a string can branch either on the left or on the right, Jot syntax is uniformly left-branching. As a result, Iota is strictly context-free, but Jot is a regular language.

My understanding is that both Iota and Jot are Turing complete. But apparently, one is context-free, and the other is regular! Surely regular languages can't be Turing complete?


texts: How large would a database containing perfect knowledge of chess be?

texts: Assuming that a database entry schema contains two 64-bit hash IDs generated via the algorithm explained here, in the section "Generating Hash Keys for Chess Boards", and simply a score that's a 32-bit integer, how many bytes would the database need to be to guarantee that it can store every possible game state of chess?


texts: How to minimize the average distance between pumps and cities?

texts:
There are n cities [1, 2, 3, .... n] and k available pumps. These pumps can be installed in k cities. The cities are all in a straight line.

How do I need to install these so that the average distance between the cities and the nearest pumps is minimized?

What I am thinking is that dividing is this:

Suppose there are 6 cities [C1, C2, C3, C4, C5, C6]  and 3 pumps [P1, P2, P3].

I divide the array of cities equally -> [C1, C2] , [C2, C3] .. and then each block gets one pump.

Then again break that [C1,C2] and let C2 have the pump. Same way C4 and C6.

So basically recursively calling and assigning the city a pump. Is this the right way to approach this problem?


texts: Operation of the Ford–Fulkerson algorithm given an almost maximum flow

texts:
I have been assigned the question:

Let $G$ be a flow network and $f^*$ be the maximum flow computed by the Ford-Fulkerson algorithm. Consider a new flow network $G'$ constructed by increasing the capacity of exactly one of $G$'s edges by one.
Using the maximum-flow and minimum-cut theorem, argue that if we run the Ford-Fulkerson algorithm on $G'$ with $f^*$ as the initial flow, the while-loop shall terminate in at most one iteration.

But I feel like the loop can run more than once...
Considering a base case where $G$ has one edge between the sink and source with a capacity of 1.
Then $G'$ will have one edge with a capacity of 2.
So then when we run the Ford–Fulkerson algorithm with an initial flow of $f^* = 1$, the first loop will leave a residual graph with an edge with a capacity of 1, and therefore the loop will run for a second time.


texts: How to formulate a computational problem rigorously?

texts:
I often interact with people who want to ask for an algorithm for a computational problem (or its complexity), but they don't express it in a rigorous way for us (computer scientists) to understand.
Referring them to books like CLRS is not helpful because the examples there usually have a quite straightforward way of stating rigorously, e.g. given the adjacency list of a graph and two vertices in it compute the shortest path between those vertices.

Is there any good book (or some other resource) where a person with minimal knowledge of CS can learn how one should formulate and state computational problems in a rigorous way that is understandable to computer scientists?

Preferably the book should have many examples of how to formulate computational problems rigorously from various domain and real world examples.

Clarification
To make the question more specific, let's assume that they know basic math/CS terminology like sets, functions, graphs, lists, etc. at the level of 1st/2nd year undergraduate CS student (which is the case with people who I have in mind). For example, they have read some introductory textbook like Aho and Ullman (although they might not have understood it completely).

Al Aho and Jeff Ullman, Foundations of Computer Science, 1992.


texts: How to view Graph Reduction/Graph Representation for a Haskell program?

texts:
I know that under the hood, for a Haskell program, the GHC compiler uses graph reduction for optimization. Is there any way to view this graphical representation of the program? I haven't been able to find an existing plugin that, given a Haskell program, produces its graphical representation. I am relatively new to Haskell.
Are there research tools available to study and manipulate such graphs?


texts:
We got tower $T_1$ with $n$ odd disks (1,3,5,...) and tower $T_2$ with $n$ even disks (2,4,6,...).
Now we want to move all $2n$ disks to tower $T_3$.
If $T(p,q)$ is a recurrence relation of minimum number of moves we make to move $p$ disks from $T_1$ and $q$ disks from $T_2$ to $T_3$, we must find $T(n,n)$.

If anyone has any idea, please share.


texts: Given a chordal graph $G$, what is the complexity of computing the reduced clique graph $C_r(G)$?

texts:
A graph $G$ is chordal if it doesn't have induced cycles of length $4$ or more. A clique tree $T$ of $G$ is a tree in which the vertices of the tree are the maximal cliques of $G$. An edge in $T$ corresponds to a minimal separator. The number of distinct clique trees can be exponential in the number of vertices in a chordal graph.

The reduced clique graph $C_r(G)$ is the union of all clique trees of $G$. That is, it has all the same vertices, and all possible edges. What is the complexity of computing $C_r(G)$ for a given $G$?

I think I once saw a presentation claiming $C_r(G)$ can be computed in $O(m+n)$ time without proof. This would mean it is as easy as computing a clique tree of $G$. Is there a reference that confirms this, or gives a slower algorithm for computing it?


texts: How to revert a carryless polynomial multiplication?

texts:
In the carryless multiplication of two polynomials in a 8-bit environment, is it possible to obtain the original 8-bit values from the result?

As an example:

$$\begin{align}
(x^{11} + x^{10} + x^9 ) + (x^7 + x^5 + x^4 + x^3 + x^1) &= (x^6 + x^5 + x^1) \times (x^5 + x^3 + x^2 + x^0)\\
(x^{11} + x^{10}) + (x^6 + x^4 + x^2 + x^1) &= \text?\times\text?\quad \hbox{(each value must fit in 8 bits)}
\end{align}$$

I know that I can try every possible value (it's only two 8-bit values) but that seems blunt!


texts:
I'm working in the time analysis for an algorithm with two optional optimizations variant applied and followed next approach:

Create inputs of different lengths for the algorithm
Using these inputs to execute the two algorithm variants and count the asymptopic number of operations (steps)
Graph the operations count
Graph typical time complexity curves and compare with result:

Polynomial graph graphed by using $N^6$
Quasy-Polynomial graphed by using $2^{LOG(N)^6}$ ($K=6$)
$N$ = input length

I'm a newbie on this kind of analysis and some advise on how to proceed to complete the analysis will be welcome as I feel I'm doing something wrong.

So the questions is, how is the right way/process to do a Time Analysis for an algorithm.

Just in case this helps I provide the raw data for both algorithm Optimizations

Optimization 1 (# of steps)
==========
18   168.444
19   334.625
20   671.042
21   1.869.381
22   2.664.066
23   5.318.839
24   10.656.909
25   21.008.570
26   42.226.829
27   84.365.073
28   143.803.905
29   343.807.896
30   676.068.035
31   1.372.590.031
32   2.742.788.213

Optimization 2 (# of steps)
==============

18   109.533
19   65.720
20   250.565
21   1.324.926
22   866.908
23   2.638.451
24   4.328.395
25   12.265.480
26   15.808.379
27   43.385.582
28   75.952.700
29   206.996.787
30   267.098.278
31   730.593.681
32   1.278.315.507


texts: Bit complexity of O(1) time range query in a $k$-ary array

texts:
Consider the following problem:

Let $k$ be a constant. We are given a $k$-ary array $A_{d_1\times\ldots\times d_k}$ of $0$ and $1$'s. Let $N = \prod_{i=1}^k d_i$.

We want to create a data structure by preprocessing $A$ to perform the following type of query operations:

Given the coordinates of a $k$-ary box $D$, is there a $1$ in the box?
Given the coordinates of a $k$-ary box $D$, return the position of a $1$ in the box (if there is one).

The operations must be performed in constant time $O(1)$. The time complexity is measured on a RAM machine. The preprocessing time and space for the data structure are not important for us.

The question is how much space (in bit complexity) do we need to store a datastructure allowing the above operations?

The trivial lower-bound is $N$ bits since the array can be reconstructed for these queries (so the data structure should have at least the same amount of information in it).

The trivial upper-bound is to store the answer to all of the queries. That would need $\prod_{i=1}^k {d_i \choose 2} = \Theta(N^2)$ bits. However we suspect that this can be done much more efficiently.

For example, consider the special case where $k=1$. In this case we can use a succinct RMQ data structure to solve the first problem, and the data structure takes $2N+o(N)$ bits to store.

  What is an efficient data-structure for this task?
  How low can the space complexity (the number of bits) go to support these operations (or just the first operation)?

Update (1/15):
In the special case $k=1$, using $N +o(N)$ bits is sufficient (actually better, $\log {N\choose t}+O(t)$, where $t$ is the number of $1$'s in $A$) by reducing the problem to a predecessor problem and using the reduction from predecessor problem to fully indexable dictionary (FID). See "More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries" by Grossi, Orlandi, Raman and Rao (2009).

Update (6/27):
Again by reduce the problem to RMQ. We use a $k$-dimensional RMQ by Yuan and Atallah to get a $O(n\log n)$ upper bound on the amount of space required when $k$ is fixed.


texts: What does the term "Finite" stands for in Finite State Machines?

texts:
Do we consider Pushdown Automata, Turing Machines in Finite State Machines?
If we don't, then what does the term "Finite" stands for in Finite state machines, as PDAs & TMs are also defined to have Finite Number of States?


texts: Why the 127 encodings of ASCII needed to be extended to 256?

texts:
As you all know the ASCII chart needed to be extended from 127 encoding to 256, I can't really see why. Some google expert on Coursera said "We needed that because of the foreign languages".
I still Can't understand what that has to do with the ASCII Chart.

Can anyone explain the full story?


texts: What is the standard notation for introducing syntactical formalism in a paper

texts:
Suppose you want to introduce a format for a language, commands, ... etc. (Specially in the filed of computer science) in a paper

for example something like below:

X | Y = [ Z ] <W> [ / ] $P

By this, I mean, X or Y could be at the left side of an equation, Z is an optional argument at the right side, <W> is another syntax for something and it is followed by an optional slash and $P is another argument...

What is the standard way to introduce such formalism?

For another example suppose you are

The first one who want to introduce XML synatx
Someone who want to introduce a syntax near or derived from XML

However I am the case two.


texts: Why can PDAs only write one symbol to the stack according to this definition?

texts:
This is in regards to the definition 2.13 of non-deterministic PDA given in Theory of Computation 3rd ed. by Michael Sipser.

The transition is defined as
$$
\delta: Q\times \Sigma_\varepsilon \times \Gamma_\varepsilon \to P(Q\times \Gamma_\varepsilon)
$$
where $Q$ is the set of states, $\Sigma = \Sigma_\varepsilon\cup \varepsilon$ is input alphabets, and $\Gamma_\varepsilon = \Gamma_\varepsilon\cup \varepsilon$ is the stack alphabets.

I think $\Gamma_\varepsilon$ in the co-domain of the transition should be replaced with $\Gamma_\varepsilon^*$; otherwise, I don't see how this definition can pop/push from/onto its stack.

Please help me clarify this.


texts:
Do networking ports come from "port-mapped I/O"?

I was watching a hardware basic video by Brian Will:

https://www.youtube.com/watch?v=9-KUm9YpPm0

And they brought up this concept at 18:15

Initially, I thought it makes sense that networking ports come from the implementation of port-mapped I/O, but it's strange that the video uses the term "devices" instead of "applications" when referring to doing I/O tasks with ports.


texts: Spanning tree with equally separated edge weights

texts:
I have a fully-connected graph $G=(V,E)$ with edge weights $w(v)\in\mathbb{R};v\in V$ and I need to find a spanning tree $T=(V_t\subseteq V,E_t\subseteq E)$ where the set of edge weights in the tree have as close as possible to equal separation. We quantify the notion of equal separation by minimizing the variance of difference between weights: $minimize: Var\left(\Delta(E_t)\right)$, where $Var$ is the variance function and $\Delta(E')=\{|w(e_1)-w(e_2)|, ..., |w(e_{n-1})-w(e_n)|\}$ where $e_i\in E'$ and $E'\subseteq E$ is a list of edges sorted by weight.

So an optimal solution to this problem will be an instance of $T$ such that $T$ is a spanning tree and $Var(\Delta(E_t))$ is the minimum over all possible spanning trees of $G$.

I have two ideas for this:

1) Pick a random starting node and perform a best-first spanning search, prioritizing the OPEN list for each $e'\in OPEN$ by $Var\left(\Delta(E_t \cup {e'})\right)$ where $E_t$ is the set of edges chosen so far in the search.

2) Find $n-1$ clusters of edges using a clustering algorithm such as k-means clustering based on $w(e)$ for all $e\in E$. Then (somehow) find a spanning tree that includes exactly one element from each of the $k$ cluster sets. (I think this might not work without doing something fancy to ensure that a spanning tree can actually be chosen from the sets.)

I coded up 1) and found that although it yields a fairly decent approximation it is sub-optimal, even if I take the best tree over all trees starting from each of the $n$ vertices... I have not yet tried 2).

This smells NP-hard... Is there an algorithm to compute a spanning tree with  edge weights separated as equally as possible? (aside from brute-force?)


texts:
Flynn's taxonomy contains three interesting computer architectures: SISD, SIMD, MIMD.

For the SISD architecture, we have RAM computational model that simulate real SISD systems very well;
For the MIMD architecture, there is PRAM computation model that is capable to highlight main benefits of the parallel processing units that operate on the different part of a dataset (though, this model can't cope with the complexity of the real world parallel programs).

Are there any nice computational model for SIMD architecture?


texts: on "On the cruelty of really teaching computing science"

texts:
Dijkstra, in his essay On the cruelty of really teaching computing science, makes the following proposal for an introductory programming course:

On the one hand, we teach what looks like the predicate calculus, but we do it very differently from the philosophers. In order to train the novice programmer in the manipulation of uninterpreted formulae, we teach it more as boolean algebra, familiarizing the student with all algebraic properties of the logical connectives. To further sever the links to intuition, we rename the values {true, false} of the boolean domain as {black, white}.
On the other hand, we teach a simple, clean, imperative programming language, with a skip and a multiple assignment as basic statements, with a block structure for local variables, the semicolon as operator for statement composition, a nice alternative construct, a nice repetition and, if so desired, a procedure call. To this we add a minimum of data types, say booleans, integers, characters and strings. The essential thing is that, for whatever we introduce, the corresponding semantics is defined by the proof rules that go with it.
Right from the beginning, and all through the course, we stress that the programmer's task is not just to write down a program, but that his main task is to give a formal proof that the program he proposes meets the equally formal functional specification. While designing proofs and programs hand in hand, the student gets ample opportunity to perfect his manipulative agility with the predicate calculus. Finally, in order to drive home the message that this introductory programming course is primarily a course in formal mathematics, we see to it that the programming language in question has not been implemented on campus so that students are protected from the temptation to test their programs.

He emphasises that this is a serious proposal, and outlines various possible objections, including that his idea is "utterly unrealistic" and "far too difficult."

But that kite won't fly either for the postulate has been proven wrong: since the early 80's, such an introductory programming course has successfully been given to hundreds of college freshmen each year. [Because, in my experience, saying this once does not suffice, the previous sentence should be repeated at least another two times.]

Which course is Dijkstra referring to, and is there any other literature available that discusses it?
The essay appeared in 1988 when Dijkstra was at the University of Texas at Austin, which is probably a clue -- they host the Dijkstra archive but it is huge, and I'm particularly interested in hearing from others about this course.
I don't want to discuss whether Dijkstra's idea is good or realistic here. I considered posting this on cstheory.se or cs.se but settled on here because a) a community of educators might be more likely to have someone who can answer easily, and b) Dijkstra himself emphasises that his course is "primarily a course in formal mathematics."  Feel free to flag for migration if you disagree.


texts: Why postfix arithmetic expression is not ambiguous?

texts:
A binary tree can be written as an expression, no matter prefix, postfix or infix.
But why an infix expression needs brackets, while the others don't?

Say, why postfix, prefix produce only one binary tree, while infix can produce many (and become ambiguous)?

I'm looking for a formal proof...


texts: How do I solve this graph with Dijkstra's Algorithm?

texts:
I just drew this graph completely random:

I found the shortest path (marked in red) by simply checking everything. But the reason was to use Dijkstra's algorithm. But when I try I get stuck in a loop. Lake a look at my calculations:

How to read it is:

Top Row: Wich node
Section t: Total distance traveled
From: Wich node did I come from
The 10 over S and every other section can be read like this

To come from S to node 1, the complete path takes 10 time units

So, if you try to follow Dijkstra's algorithm you will get something like this:
S->D->C->5->4->6->D->S->5->4->6->D->(and so on)

I get stuck in a loop. I understand that when I return to S I can reset the time to 0, witch make at least the first bit correct, S->5->4, but than it get stuck.

How are you supposed to solve a problem like this based on how the algorithm is formed? For me, it is obviously stupid to just go around this route, but for an algorithm it is not.

Thank you in advance!


texts: Why Cook-Levin thorem's proof can mean SAT's NP-Hardness

texts: I'm studying about Cook-Levin theorem but there is a problem I faced. Cook-Levin theorem shows that any NPTM can be encoded as a boolean formula. About given language $A$, instance $w$, and NPTM $M$ that decides $A$, I understand that when a boolean formula $φ$ is true when $M$ accepts $w$ and false when $M$ rejects $w$, decision problem $w∈A?$ will be the same problem as $φ=true?$. But I am confused that can we actually certificate existence of reduction from any other NP problem to SAT, with Cook-Levin theorem. I can't make actual Karp reduction to SAT that doesn't picky about where the reduction comes from, so I can't tell that SAT is in NP-Hard. Please help me to understand why conversion to boolean formula can mean SAT's NP-Hardness...


texts: Karp reduction from NP-hard problem to unknown problem

texts:
If I know that problem $A$ is NP-hard, but know nothing of problem $B$ and I know that the following Karp reduction is true:

$$A \to B \, .$$

Is it correct to conclude that $B$ must also be NP-hard?


texts: Unsupervised anomaly detection: assigning the clusters to normal and anomaly

texts:
Having a unsupervised algorithm done on a dataset (e.g. K-means), how can I determine which cluster is normal and which is anomalous (for 30 clusters, for example)?

If the dataset contains normal traffic much more than anomalies (99%), then the radius of clusters associate to normal traffic is bigger. Is this true? Why?

If so, then we set the clusters with greater radius to normal according to a threshold. The smaller the threshold, the more the detection rate and the more the false alarm rate. Is this true?

Could a labeled dataset help determine the normal clusters? For example, finding the closest point to the centroid of a given cluster and checking whether it is labeled anomaly or not?

[1] uses Cluto software and its mountain visualization graph that I can't understand why its 3D, having feature space of dimension 41.

Reference:
[1] Jose F. Nieves, Data Clustering for Anomaly Detection in Network Intrusion Detection


texts: I'm not too sure about how to calculate hashing probabilities, and can't find much documents online to help me with it. Am looking to solve this question "If we hash N items into M buckets using a simple uniform hash, what is the expected number of buckets that have exactly 1 item? What is the expected number of buckets with at least 2 items? What is the expected number of buckets with exactly k items?", so will appreciate any help with respect to hashing probabilities.


texts: How to prove that the time complexity of this algorithm is O($\sqrt{N}$)?

texts:
int n;
  cin >> n;
  int sum = 0;
  for (int i = 1; sum <= n; i++) {
      sum += i;
  }

If I assumed that $N = 100$, the loop will run $13$ steps, which is almost the square root of $N$, if $N = 10000$, the loop will run $141$ steps, which is almost the square root of $N$, but I don't know how to prove that, I only know it by intuition


texts:
In Introduction to Formal Languages by György E. Révész a polynomial time algorithm that can convert a left linear grammar to a right linear one is presented.

Trying to understand when it is useful I read that left linear grammars are generally harder to parse than right linear grammars.

Is this statement true?

I'm asking because I would say that there is no difference between recognizing the two in terms of hardness, but I found arguments about a difference between them.

In particular in these slides on page 8, the author argues that "left linear grammar are evil" and provides the following example:

Grammar

A → Babc

B → Cb | D

...

with $w = abbabc $.

The motivation seems to be that after checking for abbabc it is necessary to check the first part abbabc if can be derived from B that has 2 rules associated: Cb and D, while it could be done easily with a right linear grammar.


texts: How many independent yes/no questions can be asked about a point in binary space (linear vs nonlinear codes)?

texts:
This question springs from thinking about the potential benefits of using nonlinear codes instead of linear codes. Say we have a point $x \in \{0,1\}^k$ and we want to guess what it is. A naive scheme would be to ask $2^k$ questions of the form "is $x=[0100001\dots 01]$?" etc, while a refinement would be "is the $i$:th bit a one?" while linear codes generalizes this one step further to "is $x_i + x_j + \dots + x_\ell = 1$?"

With linear codes we can enumerate $k$ independent questions of this form. What I'm wondering is: can we do better?

Call $\{0,1\}^k$ our codebook with a corresponding matrix $C$ containing the coordinates of the codewords in its rows, i.e. $C_0 = [0\dots 0], C_1 = [0\dots 0 1]$ etc. Say we permute this matrix and make the permutation known to the receiver prior to transmission.

Couldn't we produce more than $k$ independent questions by asking questions of the form "is $b_i + b_j + \dots = 1$?", where $b_i$ is the $i$:th bit of the binary representation of the permuted codebook index?

It seems this could generalize into any "type division": to form a question, divide the codebook into $A_i$ and $B_i$ where $|A_i| = |B_i|$ and ask questions of the form "is $x$ of type $A_i$ or $B_i$?"

Clearly, this scheme is a strict generalization of linear coding since parity checks follow this general even division algorithm. Is it a vacuous generalization or could we in fact produce more than $k$ independent questions in this manner?

EDIT: Clarifying independence due to demand - could we by using nonlinear coding construct a list of $k+2$ or more questions such that any size $k$ subset would recover the unique answer? (I made it $k+2$ since I think we can construct a list of $k+1$ questions by using linear codes - just make the $k+1$:th question about the parity of all the rest)

EDIT: This is not a question on decoding tractability, so please refrain on commenting on that aspect.


texts: sequential consistency is not composable

texts:
I am studying for my exam in Distributed Systems course. And i have one question that i do not really understand. This is the question:

Is sequential consistency compositional? if yes explain why, if no give an example.

Now this is the only two slides that we have that explains why it is not composable.

And i am having trouble understanding why just from that example. I tried searching on the web for a better explanation but i could not find it. If you have a good example that you can describe and explain or if you have a good link or both please do provide it.


texts: Algorithm for selecting a sample that's as spread out as possible?

texts:
I have a large database of data with dates. There are large gaps and large chunks of data without gaps. I want to get a sample of this data such that the dates are as spread out as possible (i.e. as close to evenly distributed as possible).

E.g. if the dates are [1, 2, 3, 4, 100] and I want to sample 3 elements, the ideal sample would be [1, 50.5, 100] and the closest available dates are [1, 4, 100].

Is this a known problem with an existing algorithm?


texts: Several simple propositions about regular languages

texts:
(Originally posted on Math-Stackexchange)
https://math.stackexchange.com/questions/2982949/regular-languages-and-regular-expressions

Notation:
$\Sigma:=\{a_1,\cdots ,a_\Delta\}$ finite alphabet
$\Sigma^n= \underbrace{\Sigma \times \Sigma \times \cdots \times \Sigma}_{n}$ Words of length $=n$
$\Sigma^*= \bigcup \limits_{n\geq0} \Sigma^n$ Set of all finite words
$L \subseteq \Sigma^*$ Language

I'm trying to prove, that the following statements are either true or false. Unfortunately, I'm having a hard time finding formal proofs for my answers. I hope you can help me out a bit.

Let $A,B$ be two subsets of $\{0,1\}^*$

If $A$ is regular pumpable and $B \subseteq A$, then B is regular pumpable too.
If $A$ not regular pumpable and $A ⊆ B$, then $B$ is not regular pumpable too.
If $A$ is regular and $B \subseteq A$, then B is regular too.
If $A \cap B$ is regular, then $A$ and $B$ are regular too.
There is at least one finite language on the alphabet $\{0,1\}$,
that doesn't meet the pumping lemma.


texts:
I've studied something about the Kolmogorov Complexity, read some articles and books from Vitanyi and Li and used the concept of Normalized Compression Distance to verify the stilometry of authors (identify how each author writes some text and group documents by their similarity).

In that case, data compressors were used to approximate the Kolmogorov complexity, since the data compressor could be used as a Turing Machine.

Besides data compression and programming languages (in which you would write some kind of compressor), what else could be used to approximate the Kolmogorov complexity? Are there any other approaches that could be used?


texts:
I am interested in precise time complexity of distributed algorithm for finding MIS (Maximum Independent Set) of a given graph $G$.

I investigate the Slow MIS distributed algorithm (from these lecture notes, page 2).

Following is the more detailed version than in lecture notes.

Every node sends its UID to it's neighbors.
Run procedure join

on event: getting a message decide(1)  from a neighbor $w$ do

Set $b = 0$ - flag that node terminates and not participating in further phases.
Send decide(0) to all neighbors

on event: getting a message decide(0) from a neighbor $w$ do:

Invoke procedure join.

Procedure Join

if every neighbor $w$ of $v$ with a larger identifier has decided $b(w) = 0$, then do

Set $b = 1$.
Send decided(1) to all neighbors.

The question is what's time complexity of the algorithm $\Theta(n)$ or $\Theta(D)$, where $D$ is a diameter of $G$.

In the lecture notes linked above, they say that time complexity is $O(n)$. I  think that in our case it can be expressed as $\Theta(D)$ (simultaneously $O(D)$ and $\Omega(D)$) for special cases.

The problem is how to prove that that time complexity in general is $O(D)$ and there are special cases when time complexity is $\Omega(D)$ if it's right at all.

Let's take a look at the example I have in mind.

$D=1$ and $n=4$, and as I understood the algorithm every vertex will decide to join MIS on the first round.

If you have an idea how to show that, please, share it with us.


texts: what is the best way to approach the construction of nondeterministic PDA's?

texts: I'm trying to construct a PDA for $L = \{w0^i1^j \mid w\text{ ends in } 01 \wedge 2i=3j\}$. My understanding is that I have to first accept an arbitrary number of zeros and ones and then nondeterministically guess "$01$" in $w$, however I am stuck with the rest. I understand the condition $i/3=j/2$, but how do I make my PDA accept that? Does it have to be nondeterministic too? How do I approach this?


texts: In what situations should a particular sorting algorithm, such as heap sort, be chosen over others?

texts:
In my algorithm class my teacher said that we should always use counting sort when we want to sort integers. After he said this I was curious to know in which situations I should choose one sort algorithm over another.

Looking at the complexities of the worst cases of the algorithms I know (heapsort, mergesort, quicksort and countingsort), excentuating the case where I want to sort integers, I will choose mergesort when I want a stable sorting algorithm or I will choose heapsort when I want to save memory.

Searching a little I found flashsort, but I still do not understand very well when I should implement it instead of others. Since I am beginning to study algorithms, I would like to know at this initial moment when a sort algorithm is preferable over others.


texts: What are advantages / disadvantages of horizontal and vertical microprograms?

texts:
Currently I know:

About vertical micro programming: The control signals are not immediately passed to the ALU components, but are rather processed first and passed as an compressed function code.

About horizontal micro programming: There is just one wire connecting all ALU components directly. The signal contains for each component a bit indicating whether the component should be activated or not.

I guess H-$\mu$Programs generally runs faster as they have not to be processed extra. However have the disadvantage that the signals are pretty long.

Are there other advantages / disadvantages to each of these two types of micro programming?

EDIT: I saw a comment regarding the question being dated. Yes, it is. Nonetheless, examiners at university want to know such things. I had a hard time finding information, which is why I asked on this StackExchange, sort of as a last resort.


texts: Why run -time of N-Queens using backtracking algorithm fluctuates?

texts:
I have tested and measured the running time of a backtracking algorithm for solving the $N$-Queens problem. When $N=7$, the run time is $0.773$, but for $N=8$, the run time is $0.492$.

I think the run time should grow exponentially with the size of $N$.
Why is the algorithm slower for $7$ than for $8$?
This case also happens between $20$ and $21$ ,$28$ and $29$.
This is my pseudocode.

Function BACKTRACKING-SEARCH(csp)returns a solution,or failure
   return BACKTRACK({},csp)
Function BACKTRACK(assignment, csp) returns a solution, or failure
begin
if assignment is complete then return assignment
var = SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp],assignment,csp)
for each value in ORDER-DOMAIN-VALUES(var, assignment, csp) do
if value is consistent with assignment then
add {var = value} to assignment
Result ←BACKTRACK(assignment,csp)
If Result ≠ failure then
return Result
Remove {var=value} and inferences from assignment
End if
End for
Return failure
end


texts: What are the different types of databases?

texts: Is there is a study or classification available on different types of databases? (Examples include structured, unstructured, semi structured relational, object oriented, folksonomies, etc.)


texts: If P = NP, then how not cannot solve NP-hardness (the one that doesn't intersect with NP-complete) in polynomial-time?

texts:
My question is that if P = NP, then we can solve any NP-hard problems (the one which is NP-complete and the one which is not-NP-complete) by saying that since we have a polynomial time algorithm to solve the NP problems and since the reduction works in polynomial time. Therefore, polynomial to polynomial is polynomial, and so we can solve any NP-hardness problem. For example, we can solve the TSP by calling to an NP-complete problem which have polynomial time since P=NP, and since the reduction is polynomial time, therefore we can solve TSP in polynomial time.

  How could disprove this argument? What is the clue to say that NP-hardness(the one which doesn't intersect with NP-complete) can not be solved in polynomial time even if P=NP.

I know that if P = NP, then we can only solve any problem in NP (but not in NP-hard). But I want to know what it makes NP-hard (the one that have no intersection with NP-complete) is not solvable in polynomial time even if P=NP since we have polynomial time reduction and polynomial time algorithm given P=NP.

Thank you


texts: Is set of all regular languages on a specific alphabet a regular language?

texts:
so i know that the set of all strings over any finite alphabet is countable, but this question is different

so if our language is set of all regular languages(or set of all regular expressions) on a specific and finite alphabet, then is this set regular? if not then what is it? CFL?

i really can't come up with any FA that can accept this!


texts:
Show that $L=\{a^{n^2} | n \geq 0\}$ is not regular

Hey guys. I'm taking a CS class and this stuff is really new to me so bear with me.
I tried to look if I get some contradiction by using the pumping lemma for regular languages and I worked it out like this:

Suppose $L$ is regular. Then there must be a natural number $m$ for all words $z$ in $L$ with length $|z| \geq m$ and there exists a decomposition $z = uvw, |uv| \leq m, |v| > 0$, so that $u(v^i)w$ is in the language for any $i \geq 0$.
Consider the string $a^{m^2}$.
Then $uv = a^{k^2} = a^{x+y}$, for some $k \leq m$ and $x = (k-1)^2$.
Then $v = a^y = a^{2k-1}$.
Let $i = 2$. Then $u(v^2)w = a^{x+2y}$. But $\sqrt{x+2y}$ is not necessarily a natural number -> Contradiction! Hence, $L$ can not be regular.

Well, I know that this way is unnecessarily complicated and you can prove it differently (I already know the most simple solution). But my question here is: Is my proof valid as well or does it contain any flaw? Is it formally correct?
I appreciate any feedback! Thanks!


texts: Linear Discriminant Method as Pre-processing for inputs going into a Neural Network?

texts:
As the title suggests, I am curious whether Linear Discriminant Method can be performed on a dataset as pre-processing before putting the reduced-dimensional data as input for a neural network for creating the mapping function/ surrogate model.
Thanks!


texts:
The GSAT (Greedy Satisfiability) algorithm can be used to find a solution to a search problem encoded in CNF. I'm aware that since GSAT is greedy, it is incomplete (which means there would be cases where a solution might exist, but GSAT cannot find it). From the following link, I learned that this can happen when flipping variables greedily traps us in a cycle such as I → I' → I'' → I.

http://www.dis.uniroma1.it/~liberato/ar/incomplete/incomplete.html

I've been trying quite hard to come up with an actual instance that can show this, but have not been able to (and could not find examples elsewhere). Any help would be much appreciated. Thanks :)

P.S. I'm not talking about "hard" k-SAT problems in which the ratio of variables to clauses approaches 4.3. I'm just looking for a simple example, possibly involving the least number of variables and/or clauses required.


texts: Minimum capacity cut reduction from digraph with two edge weight sets

texts:
Given a digraph $G$ and $f, g : E(G) \mapsto \mathbb{R}$, how would you find a cut $(X,\bar{X})$ with $s \in X$ and $t \in \bar{X}$ such that $\sum_{e \in \delta^+(X)}{f(e)} - \sum_{e \in \delta^-(X)}{g(e)}$ is minimized?

$\delta^+(X)$ is the set of edges going out of $X$ and $\delta^-(X)$ is the set of edges going into $X$.

I can solve for the case where $f = g$, simply by constructing a network flow graph with all edges adjacent to either $s$ or $t$. Since $\sum_{e \in \delta^+(X)}{f(e)} - \sum_{e \in \delta^-(X)}{f(e)}$ can be rewritten as $\sum_{e \in \delta^+(X)}{f(e)} + \sum_{e \notin \delta^-(X)}{f(e)} + constant$ then a graph can be constructed with an edge between $s$ and all $v \notin \{s,t\}$ with capacity equal to $\sum_{e \in \delta^-(v)}{f(e)}$  and an edge between all $v \notin \{s,t\}$ and $t$ with capacity equal to $\sum_{e \in \delta^+(v)}{f(e)}$. Then dealing with negative $f$ is simply a matter of adding the capacity to the $(v,t)$ edge instead of the $(s,v)$ edge and vice versa.

However this solution does not work when $f \neq g$ and I can't come up with an answer for this case.

The solution works for the case that $f=g$ because if we have an edge $(a,b)$, in the case that $a \in X, b \in \bar{X}$ then the edge is going out of X and not going into X, the contribution to the cut capacity is $2f((a,b))$ as per the formula containing the constant above. Then if you add $b$ to $X$, $a$ no longer contributes to the sum over edges going out of $X$ and so $f((a,b))$ is removed and you are left with $f((a,b))$. If $f \neq g$, then you are instead left with $f((a,b)) − g((a,b))$ which is incorrect.

In terms of what I have tried so far for the general case, the case that $g(x) < 0$ is trivial and the edge can simply be reversed and the capacity multiplied by $-1$ so that it is positive.

In the case that both $f,g > 0$ then I consider this local portion of the graph:

Let $f = f(a,b)$ and $g = g(a,b)$ in the above graph.
I can then transform it to this network graph:

Where the capacities are given by

$(s,b) = f$
$(b,a) = f - g$
$(a,t) = f$

Clearly this is only applicable in the case where $f > g$. Then in the case that $a$ but not $b$ is added to $X$ we have a net increase of $f$. When $b$ but not $a$ is added to $X$ we have a net decrease of $g$. When both $a$ and $b$ are added to $X$ there is no net change.

However I cannot reconcile this with the case where $f < g$ or $f < 0$.


texts: Guided Backpropagation in Deep Neural Networks

texts:
I am reading about a method called guided backpropagation.
https://ramprs.github.io/2017/01/21/Grad-CAM-Making-Off-the-Shelf-Deep-Models-Transparent-through-Visual-Explanations.html#deconv-and-guided-backprop.

As shown in the figure below, you essentially compute the derivates of the output with respect to the input image while zero-ing out negative gradients along the way. The website mentions

  Negative gradients at a particular ReLU neuron, state that this neuron
  has a negative influence on the class that we are trying to visualize.

  During backpropagation there are paths that have positive influence
  and some that have negative influence, and these end up cancelling out
  in a weird interference pattern, causing gradients to seem noisy.
  Whereas in Guided Backpropagation, we only keep paths that lead to
  positive influence on the class score, and supress the ones that have
  negative influence, leading to much cleaner looking images.

My question is why does the resulting image have pixels which are negative? Don't negative pixels indicate that the gradient of the output with respect to the pixel is negative? I.e. that pixel has a negative influence on the class score?