texts: Program synthesis, decidability and the halting problem

texts:
I was reading an answer to a recent question, and sort of a strange, ephemeral thought came to mind. My asking this might betray either that my theory chops are seriously lacking (mostly true) or that it's just too early for me to read this site. Now, with the disclaimer out of the way...

It is a well-known result it computability theory that the halting problem cannot be decided for TMs. However, this doesn't exclude the possibility that there exist machines that can solve the halting problem for certain classes of machines (just not all of them).

Consider the set of all decidable problems. For each problem, there exist infinitely many TMs which decide that language. Could the following be possible

There is a TM that decides the halting problem for a subset $S$ of Turing machines; and
All decidable problems are decided by at least one Turing machine in $S$?

Of course, finding the Turing machine in $S$ may not be computable itself; but we ignore that problem.

EDIT: Based on Shaull's answer below, it seems that either (a) this idea is too ill-specified to be meaningful or (b) my previous attempt wasn't quite on the mark. As I try to elaborate in the comments to Shaull's answer, my intent isn't that we're guaranteed that the input TM is in $S$. What I really meant by my question is whether there could exist such an $S$, such that membership in $S$ is a decidable problem. The program to solve the halting problem for $S$ would, presumably, write "invalid input" on the tape or something when given an input that it recognizes as not being in $S$. When I formulate it like that, I'm not sure whether this allows us to solve the halting problem or not, or whether Rice's theorem applies (is decidability a semantic property of a language w.r.t. Rice's theorem?)


texts: RINS: start - incumbent and relaxation solution have all different values

texts:
RINS: Relaxation induced neighborhood search, firstly introduced by Danna et.al in 2004 in "Exploring relaxation induced neighborhoods to improve MIP solutions"

I wanted to design an example how the RINS algorithm works to make sure that I have it completly understood completly.

As it turns out, I do not know what happens if I am currently at a node where RINS should be applied and there are no values in the incumbent and the relaxation solution that equal to each other? How do I decide on which node to branch then?

Or can someone forward me to a very insightful example? I mean the overall procedure is clear, I am just not sure about the details. Thanks!


texts:
Given an array of $n$ elements, containing values in the range $[1, n-1] $ (assume $ n > 1 $) this implies there is at least one repeated element. The problem is to get one of the repeated values in linear time on average.
My first try was to do something with the Partition scheme from Quicksort. However, I don't know how to address the following problem:

We can divide the problem selecting a pivot, and then for each value $ <= $ than the pivot, we know that they will be in the range $0..n/2 - 1$, and the following values $>$ than the pivot, they will be in $n/2 + 1..n$.

I can't check both of those partitions, because the cost would be $O(n\log n)$ per Master Theorem.
The only way I think I can do it is only checking left or right, however, i.e., if the repeated element was in the left and I check the right, is going to be somewhat the same.
So my intuition is telling me that maybe, if I check first the left part for this condition, and after that, the right one in some recursive manner, this is going to give me a linear algorithm on average.
Am I right or is there any better way to do it?
Edit: the divide and conquer approach is mandatory


texts: Language of the graph of an affine function

texts:
Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). Let : be a symbol distinct from any digit. Let $a$ and $b$ be integers, with $a > 0$. Consider the language of solutions of the Diophantine equation $y=ax+b$:

$$L = \{ \bar{x} \mathtt: \bar{y} \mid y = a\,x + b \}$$

Is $L$ regular? context-free?

(Contrast with Language of the values of an affine function)

(Follows on How can solutions of a Diophantine equation be expressed as a language?)

 I think this would make a good homework question, so answers that start with a hint or two and explain not just how to solve the question but also how to decide what techniques to use would be appreciated.


texts: What is the most effective way to learn, understand, and utilize an algorithm?

texts:
In order to keep my interviewing skills sharp, I solve one algorithm/data-structure problem every day, from sites like Leetcode or HackerRank.

If I am not able to solve it after 45 minutes or so, I usually refer to the solution. I review it, understand it, and move on.

However, I have found that I do not really learn anything at all by looking at the solution. Even though I understand the solution at that point in time, it doesn't really stick with me. I am not able to learn the approach and trick of that solution, for purposes of retaining and utilizing it later. And, if I ran into a similar question in the future, I would not remember how to utilize the approach that I have definitely seen before.

What is your technique or suggestion in learning such approaches/techniques in solving algorithm/data-structure problems?

If this question is not in the right Stack Exchange please let me know.


texts: Algorithm for finding the set of systems of distinct representatives

texts:
Given a collection of finite sets, is there an algorithm for finding the set (unordered) of all systems of distinct representatives for the collection?

Example:

S: {{1, 2}, {1, 2, 3}}

Unordered SDRs: {{1, 2}, {1, 3}, {2, 3}}

Notice that {2, 1} is already counted by "{1, 2}" as the SDRs are unordered.

System of Distinct Representatives Definition:

Let S=(S1,S2,...,Sn) be a collection of sets. A System of Distinct Representatives (SDR) of S is a collection of elements x1,x2,...,xn such that xi∈Si and xi≠xj for all i,j∈{1,2,...,n} where i≠j

Please note that, I've asked a similar question on math exchange and am now looking to solve the problem algorithmically.

Any help would be much appreciated.


texts: Which languages are recognized by one-counter machines?

texts: Counter machines with two or more counters are typically shown to be equivalent to Turing machines in courses on the theory of computation.  However, I have not seen a formal analysis of which languages can be recognized by a one-counter machine.  Are these languages equivalent to the context-free languages (perhaps by some clever construction relating them to PDAs), or are they an entirely different class of languages?


texts: Minimum number of edges to remove to disconnect two node sets $A$ and $B$ in a directed graph

texts:
We have directed graph $G$ (not necessarily a DAG), two disjoint sets $A$, $B$, of vertices.
I need to plan an algorithm returning the minimum number of edges that need to be removed, such that there will be no path from any node in $A$, to any node in $B$ and vice versa.

I had the idea using max flow min-cut to find the minimum number of edges needing to be removed such that there won't be a path from $A$ to $B$, and then using the algorithm again on $B$ (so there won't be a path to $A$).
The problem is that the sum of these minimum number of edges isn't necessarily the "global" minimum.

Does there even exist such an algorithm running in polynomial time?


texts: Optimizing coin splitting - Is this algorithm as fast as I think?

texts:
In a recent exam, I've been asked to solve the following problem:

  The problem

  Two players play the following game:   Given a sequence of coin values
  $v_1,\ldots,v_n (n \vert 2)$ the players take turns in taking one coin
  from either "end" of the sequence. The value of that coin is added to
  their score.

  Player 1 always starts. What is the maximum score that Player 1 can
  reach if Player 2 plays optimally (always minimizing their potential
  score)? What is the time-complexity of your algorithm? Prove your result.

  Example:

  Given the coin sequence $1,1,3,1,1,2$ one of the best playing
  sequence for player 1 is (scores denoted as the second tuple):

  $$(\lbrack 1,1,3,1,1\rbrack,(2,0)) \rightarrow (\lbrack 1,1,3,1\rbrack,(2,1)) \rightarrow (\lbrack 1,3,1\rbrack,(3,1)) \rightarrow (\lbrack 3,1\rbrack, (3,2)) \rightarrow (\lbrack 1 \rbrack, (6,2)) \rightarrow (6,3)$$

  The best score player 1 can reach is 6.

My solution

I'm just going to roughly outline my proof here, the formal correctness is not the point of this question. I'm more interested in the correctness of my asserted upper bound of complexity.

For the following I will use tuples to denote ranges of values. $(i,j)$ specifies the value range $v_i,\ldots,v_j$.

We iteratively create a DAG $G = (V, E, \gamma)$ as follows:
Create a vertex $v$ named $(1,n)$. Create or refer to the previously created vertices $v_1, v_2, v_3$, named $(2,n-1), (3,n), (1,n-2)$ respectively.

Create the edges $e_1 = (v,v_1), \gamma(e_1) = v_1$ and $e_2 = (v,v_2), \gamma(e_2) = max\lbrace v_1, v_n \rbrace$ and $e_3 = (v,v_3), \gamma(e_3) = v_n$. Iterate through the vertices $v_{\lbrace 1,2,3\rbrace}$ using a queue or similar to repeat the process until the sequence of coins denoted by the $v$ we iterate over is empty.

The number of edges in the created graph is bounded as follows: $\lvert E \rvert \leq 3\lvert V \rvert$.
The number of vertices is denoted by the following sum: $1 + \sum_{i=0}^{\frac{n}{2}} 2i + 1 \leq n^2$

We can determine the maximum score for player 1 by "backpropagating" the edge weights through the graph, which takes $\lvert V \rvert * \lvert E \rvert$ steps.

This makes the overall algorithm asymptotically require $\Theta(n^2)$ steps

The problem I have with my answer is the upper bound for the number of vertices. I just pull that number out of thin air and my gut-feeling tells me that it is correct, but I might just be completely wrong.

Assuming that this is indeed a correct way to calculate the answer to the question, is my time-complexity argumentation sound?


texts: Is there a name for "density" of information?

texts: If we compare multimedia and text, if we have n bytes of text and compare it with n bytes of video, then we would be likely to think that n bytes of text is "more" information than n bytes of video data. Is there a name or measure of this difference in data? Loosely speaking it is a "density" or a "quality" of information per unit.


texts:
I tried to study the maximum matching for a line-graph , i.e , $L(G)$ of a graph , $G(V,E)$ , from here :
https://www.sciencedirect.com/science/article/pii/S0012365X97001039

But could not understand it , can anybody explain it in detail .

I understood how to  create the corresponding tree , but after that I could not understand the process of finding the maximum matching .


texts: Notations around the polynomial hierarchy

texts:
I am new to "Computational Complexity" and therefore I have enough problems with some exercises like the following one:

  Remember: $\text{PH} := \bigcup_{i} \Sigma_i$

  Show:

  $\bullet \bigcup_{i}(\Sigma_i \cup \Pi_i \cup \Delta_i) = \bigcup_{i}\Sigma_i = \bigcup_{i}\Pi_i = \bigcup_{i}\Delta_i$

  $\bullet \forall k \in \mathbb{N} (\Sigma_k = \Pi_k \Rightarrow \text{PH} = \Sigma_k)$

I have tried to make myself familiar with Polynomial hierarchy, but on the one hand I don't understand the meaning of the symbols $\Delta, \Sigma, \Pi$ and on the other hand I don't know how to solve the actual exercise.

Can somebody give me some help, please?


texts: What is MSB and LSB in significant of a floating point number? If I have a significant for example 0011010000 (half-precision) but 1. bit is implicit what is MSB: 0 or 1? In this case LSB is 0, because it is on the end of significant?


texts:
I'm talking about this one research project:

but MS closed it in 2008. I've read many articles about it, about high perfomance (30+% faster against tradinional monolithic kernels), much more secure etc. So it should be really a revolution in OS designing. Why they did it? I would be really happy if they didn't... So only one question i have: why? Was "effective managers" who destroyed it or some else? I'm thinging about it for many strenuous months...


texts: Why do we need volume as an abstraction on top of partition?

texts: I'm curious about what do we need volume as an abstraction on top of hardware partition? What problem it tries to solve? What is the limitation of this concept?


texts: Find a CFG for the language $\{ x\$y \mid x,y\in\{a,b\}^* \wedge |x| \ne |y| \}$?

texts:
Consider the language below, on the alphabet $\Sigma = \{a,b,\$\}$:
$$L = \left\{ x$y \mid x,y\in\{a,b\}^* \land \left|x\right| \ne \left|y\right| \right\}$$

I need to define a CFG for this language. I've tried couple of CFGs but they all failed in one way or another.

I'd be glad for help.


texts: Is there any algorithm for 3SAT problem that is fast and relatively easy to implement?

texts: Here is the description for 3SAT satisfiability problem. I already know about the DPLL algorithm, but it's implementation is pretty complex. I would like some algorithm that is relatively simpler but improves the performance by some extent. I would prefer something that is not Tree/Graph based instead bit-mask or multi-bit assignment based approach.


texts:
If L is regular and M is non regular; then L.M is necessarily not regular. Is this true or false? And why?

I feel its false


texts:
I am learning lambda calculus as my previous questions indicate . But in a different book , namely , The structure and interpretation of  computer program I cam across the concept of "church numerals " and the stumbled upon the following link about church numerals :

https://www.cs.rice.edu/~javaplt/311/Readings/supplemental.pdf

It goes on stating the following in the first page :

The Church numerals that follow just have additional applications of the successor function:

$$\begin{align}
C_2 &= \lambda f . \lambda x . f(fx) \\
C_3 &= \lambda f . \lambda x . f(f(fx))\\
C_4 &= \lambda f . \lambda x . f(f(f(fx)))\\
&\vdots\\
C_n &= \lambda f . \lambda x . f nx
\end{align}
$$

and then he mentions that had we been having a little more powerful language then we could define the following two functions :
$$\begin{align}
S &= \lambda r.\text{“ring the small bell (ding) and apply r”}\\
Z &= \lambda r.\text{“ring the big bell (dong)”}
\end{align}
$$
and then says that the application of

$C_4$ to  $S$ and $Z$ would yield "ding ding ding ding dong"

How to explain the above result without even knowing what "f" is ?

POST EDIT :
After I got the first answer , I tried computing the sequence by the help of clue provided .

By applying step by step I will get (lambda r.ding r)^4 (lambda r.dong) = (lambda r.ding r)^4 dong .

Now each evaluation of (lambda r.ding r) leads to "ding r " .

So the overall evaluation becomes "ding ding ding ding r dong ".

Am I doing it right ?If yes then , how to account for omission of r in the expression?

P.S :
For some trivia information , has there been any known application of this idea of church numerals to any field of mathematics ?


texts: is this an example of nominal unification?

texts:
I am thinking that is the following a problem solved by nominal unification.

$\lambda a.X = \lambda b.\lambda c.c $

where we find $X$. The answer is obvious.

The reason is that it seems in nominal unification $X$ always will be an atom, not a function such as $\lambda c.c$.
The theory seems works fine with this input, just did not saw any example similar to this one.


texts: Given n numbers How to find out a set of numbers whose sum equal to a certain given number

texts:
I am given an list of numbers and A number-s. I need to find out the collection(s) of numbers from the list of numbers whose sum corresponds to the given number s.

for example - the given set is [2,8,3] and given integer 9
Then I can tell {3,3,3} or {3,2,2,2} can be the required sets.

Unfortunately I cannot figure out the best approach (with best time complexity)..
As I tried to do it using nested loops which naturally results into huge time complexity.

Any help is appreciated.


texts: Closure properties of non-context-free languages (concatenation & complement)

texts:
I am trying to proof the properties of the complement and concatenation of two non-context-free languages $L_1$ and $L_2$.
I believe that both of these languages are closed under complement and concatenation but can't seem to find a solid proof for it. I'm leaning towards them being closed because I can't find any counter examples.
I already proved that non-context-free languages are not closed under union and intersection, so I can use those properties (if applicable).

So in short what I want to proof, given $L_1, L_2$ are non-context-free languages:
$L_1L_2 \in S_{nonContextFree}$
$\overline{L_1} \in S_{nonContextFree}$


texts:
I am working on my own personal project. I took an intro to coding class last semester so I have been exposed to coding but I am still lost with it.
Basically, for my project, I want to build a web map (I'm not even sure if that's the right word for it) using python. Here is an example.

Basically, some numbers will have arrows leading to them and others will have arrows leading out of them. I was wondering if maybe someone knew of any libraries that generated something like this. If not, I was wondering if anyone had any advice on where to start. Or at least can tell me the actual name for this type of graph because I'm not sure if it's actually called a web graph.
Thank you all :)


texts: How does 4G LTE work faster than any ordinary Internet connection

texts: How is 4G LTE faster than any ordinary internet connection? What is the mechanism behind it?


texts: Complexity of "does a directed graph have <=1 Hamiltonian cycles?"

texts:
I am studying the complexity classes and I am confused what is the complexity of the following problem: "Does a directed graph G has at most 1 Hamiltonian cycle?"
So, from my knowledge and understanding:

Existence of Hamiltonian cycle is a NP(C) problem.
Existence of exactly $k$ ($k>1$) Hamiltonian cycles in a graph belongs to PSPACE.
The stated problem would be a complement of "Does a directed graph G has at least 2 Hamiltonian cycles?"

However, I still fail to see to which class the mentioned problem belongs. Originally I though it would also belong to PSPACE, but not to any space in PSPACE. However, I have consulted my teacher and she said that, while it belongs to PSPACE, it also belongs to some subset of PSPACE. Which subset that would be? Does it belong to co-NP, and the problem from 3. then belongs to NP? If yes, how to prove it (because for now I'm just guessing it based on my teachers' hint)? If no, where does it belong?


texts:
Problem:

Consider $[k] = \{ 1, 2, \dots, k \}$ and function (of two arguments) $f: [k]^{2} \rightarrow \mathbb{N}$ that is defined for all $(n, m) \in [k]^{2}$ (all ordered pairs of numbers from $[k]$). Also, we know that for all $n, m \in [k]$ $$f(n, m) = f(m, n) .$$

Also, consider the set $S_{k}$ of all permutations on $[k]$ and function $g: S_{k} \rightarrow \mathbb{N}$ defined as follows $$ \sigma = \sigma_{1} \sigma_{2} \dots \sigma_{k} \quad \Rightarrow \quad g(\sigma) = \sum_{i = 1}^{k - 1} f(\sigma_{i}, \sigma_{i + 1}) .$$

The problem is to find at least one permutation $\sigma \in S_{k}$ such that $g(\sigma)$ is minimal.

Question:

How can we find the desired permutation faster than brute force?


texts: Why is this language *not* pumpable? (language = arbitrary word followed by exact same arbitrary word)(pumping lemma for context-free-languages)

texts:
language = arbitrary word followed by exact same arbitrary word = u * u (with u being out of non-empty words of alphabet {0, 1} )
(sorry for the formatting, see screenshot-link for conventional/clear expression)
The purpose is to prove that the given language is not a context-free-language (using the pumping lemma).
So i thought that this language should definitely be pumpable, since you can choose x and z as corresponding parts in one of the u/"halves". So if word to be pumped is "0101" then you choose e.g. x=1 (0101) and z=1 (0101) and the remaining parts that stay static are assigned with u=0 (0101), y=0(0101), and v=empty.
If pumped zero-times/i=0 word reads: 00
i=1: 0101
i=2: 011011
i=3: 01110111
(and so on)
(For more complicated words you would need to use all three (u, y, v), but the basic principle would still be that x and z are assigned corresponding parts of the word and u,y,v would be assigned the remainder. (This doesn't work for the extremely small words 00,01,10,11 that would become empty when zero-pumped, but as long as the exceptions are finite / of finite/fixed number this isn't a problem AFAIU.)
Clearly this is wrong, but can anybody explain how/why?


texts: Claimed issue with polynomial interpolation for Reed Solomon

texts:
The wiki article for Reed Solomon error correction includes the following statement near the end of this section:

https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction#Syndrome_decoding

"The advantage of looking at the syndromes ... Another possible way of calculating e(x) is using polynomial interpolation to find the only polynomial that passes through the points (α[j], S[j]) ... however, this is not used widely because polynomial interpolation is not always feasible in the fields used in Reed–Solomon error correction. For example, it is feasible over the integers (of course), but it is infeasible over the integers modulo a prime [citation needed]."

The statement is tagged as "citation needed".

However I find articles and posts at SO about polynomial interpolation in finite fields, at least for finite fields based on GF(p^n) where n is > 1. I'm wondering if n == 1, such as GF(929), used for some bar codes, can be an issue in some cases.


texts: Asymptotic expected runtime of Randomized Algorithm

texts:
I am analyzing the asymptotic runtime of a randomized algorithm in expectation. The algorithm has the following properties:

Given input size $n$, with probability $3/4$ it moves on to solve an instance of size $n-1$
With probability $1/8$ it moves on to solve an instance of size $n-2$
With probability $1/16$ it moves on to solve an instance of size $n-3$
With probability $1/2^i$ it moves on to solve an instance of size $n-i$
Each instance pays a cost of $O(n)$, where $n$ is the input size of that instance

Over expectation, the runtime can be defined recursively as follows:

$T(n) = O(n) + \sum\limits_{i=0}^{n-1} (\dfrac{1}{2^{n-i+1}} T(i)) + \frac{1}{2}T(i-1)$

$T(0) = O(1)$

I have calculated that the expected number of "jumps" at each stage is $\leq 1$. I did this by showing $\sum\limits_{i=0}^\infty \dfrac{i}{2^{i+1}}= 1$ by using telescoping and geometric series. However, since the complexity at each stage diminishes as $n$ gets smaller, although this hints the runtime is $O(n^2)$, it does not prove it. Anyone have any ideas to prove a runtime for the less relaxed version?

EDIT: Slight gap in my formulation. The "$3/4$" probability for moving onto an instance of size $n-1$ should actually be larger than $3/4$ since the probabilities $1/2, 1/4, 1/8, ...$ only go on till $1/2^{n+1}$. If no jumps were made, the algorithm deterministically moves on to an instance of size $n-1$.


texts: PSPACE completeness, with different kinds of reductions

texts:
PSPACE-complete$_{FP}$ problems are the PSPACE problems such that every other PSPACE problem can be transformed to it with a polynomial time reduction, i.e. the reduction is an algorithm $\in$ FP. This class is known as PSPACE-complete.

Similarly, we can define :

PSPACE-complete$_{FPSPACE}$ problems, the  PSPACE problems such that every other PSPACE problem can be transformed to it with a polynomial space reduction. This class is still PSPACE, minus trivial problems $\Sigma^*$ and $\emptyset$.

PSPACE-complete$_{FNP}$ problems, the  PSPACE problems such that every other PSPACE problem can be transformed to it with a FNP reduction (the function problem extension of the decision problem class NP).

PSPACE-complete$_{FPH}$ problems, the  PSPACE problems such that every other PSPACE problem can be transformed to it with a FPH reduction (the function problem extension of the decision problem class PH).

It seems to me that all these classes are well defined and that we have :

PSPACE-complete $\subset$ PSPACE-complete$_{FNP}$ $\subset$ PSPACE-complete$_{FPH}$ $\subset$ PSPACE

Additionally, if PSPACE-complete$_{FPH}$ $\neq$ PSPACE-complete then P $\neq$ NP.

Naturally, PSPACE-complete$_{FNP}$ $\neq$ PSPACE-complete works also but it's more difficult to prove.

I suspect that PSPACE-complete$_{FPH}$ is just PSPACE. What more can be found about the two last defined classes ?


texts: constructing a DFA and a regular expression for a given regular language

texts:
This is the question 1.12 from Introduction to the Theory of Computation 3rd Edition by Michael Sipser. The questions says,

  Let $D=\{w\mid w$ contains an even number of $\texttt{a}$'s and an odd
  number of $\texttt{b}$'s and does not contain the substring
  $\texttt{ab}$}. Give a DFA with five states that recognizes $D$ and a
  regular expression that generates $D$.

I was able to construct a  by using the intersection operation on the three simpler parts of $D$. I think that the regular expression that would generate $D$ is b(bb)*(aa)* but I'm not sure about it.

Is my regular expression correct? If yes, then if I apply the subset construction algorithm on  diagram (eps denotes ε) and minimize the resultant DFA, I should get the minimal DFA that I constructed through intersection, right?


texts: Finding the k-th smallest rational number efficiently

texts:
Consider the following set:

$S := \left\{\frac{a}{b} \colon a \in \{1,\ldots,A\}, b \in \{1,\ldots,B\} \right\}$

$S$ is the set of all rational numbers that can be represented by two integers $a$ and $b$ that are bounded by $A \geq 1$ and $B \geq 1$. For the sake of simplicity, we can also think of $S$ as a multiset such that the number of elements in $S$ is given by $A \cdot B$.

Do you see any possibility how to find the $k$-th smallest number in $S$ in time $\mathcal{O}(\log (A \cdot B))$ ?

Clearly, the smallest number if given by $\frac{1}{B}$ and, as long as $B \geq 2$, the second smallest number is given by $\frac{1}{B-1}$. But then things are getting interesting...


texts: Does the Kolmogorov complexity of a program $p$ generating a string $x$ equal the complexity of $x$ up to constant?

texts: If $U$ is a universal prefix Turing machine, $U(p)=x$ for some program $p$ and string $x$, is it true that $K(x)=K(p)+O(1)$, with $K$ being the prefix Kolmogorov complexity?


texts:
We consider a set of sets $S = \{S_1, S_2, \dots, S_n\}$, and we want to find a subset $I$ of $S$ that maximises the size of the union of the set $S_i$ included with a penalty for each set included. We can represent this problem as the optimisation of the following quantity:
$I = argmax_{I} |\cup_{S_i \in I} S_i| - |I|$
What would be an efficient way to solve this optimisation problem?
We know from the inclusion-exclusion principle that the union of sets can be expressed as follows:
$|S_{i_1} \cup \dots \cup S_{i_k}| = \sum_{j=1}^{k} (-1)^{j+1} \sum_{1 \leq l_1, \dots, l_j \leq k}  |S_{l_1} \cap \dots \cap S_{l_j}|$


texts:
We want to show one schedule of jobs consumes less energy than another one. For example, there are two schedules A and B. Both the schedules A and B schedule two jobs $j_1$ and $j_2$ with execution time $C_1$ and $C_2$. Schedule A schedules the two jobs with frequencies $f_1$ and $f_2$ while schedule B schedules the two jobs with frequencies $f_3$ and $f_4$. The condition is that $f_1 < f_3$ and $f_2 > f_4$ and $f_3 \ne f_4$. Now how can we show that schedule A is consuming less energy than schedule B.

Let the energy consumption function is $C_1 \cdot {f_x}^2 + C_2 \cdot {f_y}^2$.


texts: What are 'Butterfly Combinations' and why are they called this way?

texts:
In some scientific work describing Discrete Fourier Transform-algorithms, such as the well-known Cooley-Tukey algorithm, I came across the term 'Butterfly operations' and 'Butterfly combinations', which seem to refer to the fact that an algorithm takes elements that are half an array away (where the array itself is a power-of-two in size), which mean that if you want to write an iterative implementation, that you will have to bit-reverse the indices of the input (or the output).

Is this indeed what is called 'Butterfly combinations'? And why are these called 'Butterfly combinations'? What is the origin of this name?


texts: "Implied atomic propositions" in propositional boolean formula

texts:
Suppose we have a propositional boolean formula F and let M be the set of all models of that formula.

I am wondering if there is an efficient way to find all atomic propositions that are implied by the formula. Informally, this means that they can only have one specific value in all models M.

Does this problem have a specific name in literature? What is the complexity?

Examples:

Formula "(A)": the predicate A is implied by the formula, it can only ever have the truth value true in any model of the formula.

Formula "(A or B)": no predicate is implied by the formula, there are models where A is false, there are models where A is true, there are models where B is false, there are models where B is true.

Formula "A and (B or C)": in all models of this formula, A has to be true.


texts: Is DFA and Regular Expression equivalent?

texts:
The language of a DFA can be the empty set (by defining no final states), but can a Regular Expression do that?

If Regular Expression cannot do that, does it mean that DFA and Regular Expression are not equivalent (in at least some cases)?


texts: What is the best way to compress a string with only numbers and commas in it?

texts:
I have a string like this:

11,512,64,23,46,12,67,85,84

And I'm sure it's following these rules below:

Only , and 0123456789 in it.
No number will be bigger than 999, that means they are all 1,2 or 3 digits number.

Are there any simple algorithms that I can have to compress/decompress the data?

For instance, a very stupid way I can think is to convert each number into base-16 or even base base-36 numbers.


texts: Intuition for a 2-Monotone Boolean Function

texts:
I am currently studying Chapter 8 of Krama and Hammer's textbook on Boolean Functions, and having a hard time understanding what it means for a function to be "k-monotone."
I am currently working off the following definition of "K-monotone" in Chapter 8:

A Boolean function $f$ on $\mathcal{B}^n$ is $k$-monotone ($1 ≤ k \leq n$) if, for all pairs of subsets $S,T \subseteq \{1,2,...,n\}$ such that $|S \cup T| ≤ k$, $S$ and $T$ are comparable with respect to $f$

I am wondering if someone has a more intuitive definition for what it means for a function to be "2-monotone"? I am specifically interested in this "2-monotone" rather than "k-monotone" since "2-monotone" seems to be used by a number of works that study linear threshold gates.
I think that part of my confusion arises from the fact that I think about monotonicity as a property that's related to its input-output relationship rather than the "comparability" of its inputs. For example, I think about a positive Boolean function as a function $f$ that is positive in all its input variables where a function is positive in $x_1$ means that  $f(0,x_2,...,x_n) \leq f(1,x_2,...,x_n)$ for all values of $x_2,...x_n$.


texts: How does size of a number in an array affect time complexity algorithm analysis?

texts:
This question stems from this question and this answer. I also want to preface this question by stating that this question is done from the perspective of a RAM (or PRAM if it's more accurate term) model.

From the comments in the answer, it seems like when doing algorithm analysis for the solution:

  $O(n)$ solution (guaranteed): sum up the elements of the first array. Then, sum up the elements of the second array. Finally, perform the substraction.

for the problem of:

  finding the number that is different between two arrays (I'm assuming
  a fixed size structure, if it matters) of unsorted numbers (paraphrased by me)

that it isn't as black and white as just coming to the conclusion as $2n$ (1 pass for each array), because you have to take into account the size of the number too. That is the part I am confused about. I've asked one of the commenters to elaborate a bit more for me:

  My idea is that while the time to add two numbers is proportional to their length, but there are $O(\log n)$ extra bits that the partial sums have over the longest input. Now, there are two things that complicate things. First, the inputs need not have the same length, but we'd like complexity in terms of their total length. If your addition is proportional to the longer number, you might rack up $O(n^2)$ quite easily. The solution is to add in place, which means the addition is proportional to the addend length - if not for carry. Now you just need to find how many carries you can have.

Despite this pretty detailed comment, I'm still having difficulty understanding why it's different. (I suspect the reason is due to my ignorance of the lower level ongoings of a computer and numerical representations). Not wanting to test their patience, I googled it and asked here, but unable to properly articulate the question, the most I found was this answer, which seems to echo the quote above (I think), thus didn't help me further.

Is it possible to simplify the explanation by perhaps illustrating it or elaborating further? Or is this as simple as it can get (and I just need to get the prerequisite knowledge)?


texts: Minimum number of clues to fully specify any sudoku?

texts: We know from this paper that there does not exist a puzzle that can be solved starting with 16 or fewer clues, but it implies that there does exist a puzzle that can be solved from 17 clues. Can all valid sudoku puzzles be specified in 17 clues? If not, what is the minimum number of clues that can completely specify every valid puzzle? More formally, does there exist a valid sudoku puzzle (or, I guess it would be a set of puzzles) that cannot be uniquely solved from only 17 clues? If so, then what is the minimum number of clues, $C$, such that every valid sudoku puzzle can be uniquely specified in $C$ or fewer clues?


texts:
I'm reading 'Introduction to the Theory of Computation' by Michael Sipser. He gives an example of a NFA, stating that this particular automaton accepts $a$ (he lists other strings as well, I just want to focus on $a$).

But when he demonstrates how to convert the NFA to an equivalent DFA, he says:
state $1$ goes to $\emptyset$ on $a$ because no $a$ arrows exit it. [...] Note that the procedure in Theorem 1.39 [on equivalence of DFAs and NFAs] specifies that we follow the $\epsilon$ arrows after each input is read.

So, if $\epsilon$-transitions happens only after some input (as the author defines), then in the initial state $1$, when $a$ is given, the NFA should 'die' as $\delta(1, a) = \emptyset$. The transition to state $3$ never happens, the NFA doesn't accept $a$. Doesn't the author contradicts himself?

I can think of couple possible explanations: 1) the very first transition of a NFA is $\delta(1, \epsilon)$ just by definition, 2) $a\epsilon=a$, so $\delta(1, a)$ = $\hat{\delta}(1, a\epsilon)$ = $\delta(1, \epsilon)\cup\delta(1, a)$, but then again the author said state $\{1\}$ goes to $\emptyset$ on $a$, not ${3}$


texts: non-deterministic finite automaton state transition table language question

texts:
I have the nfa problem below which I dont quite understand. I have been reading many slides on this but I'm having a really hard time understanding them enough to be able to complete the question. I can see that on the $q_0 $ state when we have an $a$ it should stay in the $q_0$ state and for the $q$ state when we have an $a$ it should go to the $q_0$ state but still dont understand the other information given well enough to construct the diagram.

If anyone could help me understand the problem below it would be much appreciated.


texts:
I've recently come across the following problem.

We're given up to $10^4$ distinct positive integers $a_1,\dots , a_n$, each of them below $10^6$. Let's call a subset $S \subset \{a_1,\dots,a_n\}$ a very divisible subset if any number in this subset divides the product of other numbers in this subset.

The task is to find the largest such subset. It is guaranteed that there is at least one with at least $3$ elements. If there are several such subsets we can output any of them. For example if we're given numbers $2, 3, 4, 5, 7, 8, 9, 10$ then the algorithm might output $2, 4, 5, 8, 10$.

It's neither a homework nor an ongoing contest. I'm just curious how to solve it. Unfortunarely for now i can't see any solution better than brute force through all the subsets. And such approach is unfeasible under given limitations. Any ideas will be highly appreciated. Thanks in advance.

P.S.
Here's an original statement of this problem: https://www.e-olymp.com/en/problems/7331


texts: Algorithm to compute a recursive function on a given set

texts:
I am working on a property of a given set of natural numbers and it seems difficult to compute. There is a function 'fun' which takes two inputs, one is the cardinal value and another is the set. If the set is empty then fun should return 0 because fun depends on the product of the set and fun on all subsets of the complement set.

For clarification here is an example:

S is a set given S={1,2,3,4}. The function fun(2,S) is defined as

fun(2,S)=prod({1,2})*[fun(1,{3}) + fun(1,{4}) + fun(2,{3,4})] +
         prod({1,3})*[fun(1,{2}) + fun(1,{4}) + fun(2,{2,4})] +
         prod({1,4})*[fun(1,{3}) + fun(1,{2}) + fun(2,{2,3})] +
         prod({2,3})*[fun(1,{4}) + fun(1,{1}) + fun(2,{1,4})] +
         prod({2,4})*[fun(1,{1}) + fun(1,{3}) + fun(2,{3,1})] +
         prod({3,4})*[fun(1,{1}) + fun(1,{2}) + fun(2,{1,2})]

prod is defined as the product of all elements in a set, for example

prod({1,2})=2;
prod({3,2})=6;

I am trying to write the pseudo code  for this problem using recursive method but it's not working. The base case is the cardinal value should be more than zero that means there should be at least one element in the set other wise prod will be zero and fun will return zero.

Pseudo code:

fun(i,S)
if |S|=1 && i!=0
   return prod(S)
else if i==0
   return 0
else
  prod(subset s', s' is a subset of S and |s'|=i)*(sum over fun((for i=1 to m),{S-s'}), m=|S-s'|) //I don't know how to write code for this part and need help.
end if
end fun

prod(s)
if |s|=0
  return 1
else
  n=|s|
end if
temp=1
for i=1 to n
    temp *=s(i) //s(1) is the 1st element of set s
end for
return temp
end prod

Update:I tried to form a mathematical expression of the function fun
$fun(m,s)=\sum_{\sigma_{p}\subset s;|\sigma_p|=m}\left [\prod_{i}i\in \sigma_p \sum_{j=1}^{|s-\sigma_p|}\sum_{\gamma_p\subset (s-\sigma_p);|\gamma_p|=j}fun(j,\gamma_p)\right ]$

Where $|s|\geq 1$ and $m\geq 1$

$fun(m,s)=0$ if $s$ is a null set.


texts: How to solve the following equation: $(k-1)2^h + k(2^{h-1}+1) \leq 2^{\lfloor\lg (n)\rfloor}$?

texts:
I came with this interesting question and could understand how did we get to this equation:
$(k-1)2^h + k(2^{h-1}+1) \leq 2^{\lfloor\lg (n)\rfloor}$

But in the next step, it reached to the following step which I cannot understand. Please help me out in understanding this:

$k\leq \frac{n+2^h}{2^{h+1}+2^h+1} \leq \frac{n}{2^{h+1}}\leq \left\lceil\frac{n}{2^{h+1}}\right\rceil$
Reference: Problem 6.3.3, CLRS. Difficulty understanding the solution of heap problem in CLRS book?

Thank you.


texts: Math behind Multi-class linear discriminate analysis (LDA)

texts:
I have a question about Linear Discriminant Analysis (LDA) for the purpose of Dimensionality Reduction.

So I understand for the algorithm to calculate for $k$ projection vector(s) you need to determine the eigenvector(s) that corresponds to the top $k$ eigenvalue(s). But can anyone explain what you do with those eigenvectors after you have calculated them to get a final output?

My guess is to multiply all of the eigenvectors (projection vectors) together and then multiply that with each point, $x$, in the original dataset to produce a new corresponding point $y$. Does this sound right?


texts: Number of ways to decompose a graph into two trees

texts:
Is there an efficient algorithm to count how many ways there are to decompose a given finite simple undirected connected graph $G = (V, E)$ into the union of two trees $T_1 = (V_1, E_1)$ and $T_2 = (V_2, E_2)$ that are not necessarily edge-disjoint? By union I mean $V = V_1 \cup V_2$ and $E = E_1 \cup E_2$. My initial thoughts:

$V_1$ and $V_2$ cannot be disjoint, so $|V_1| + |V_2| > |V|$.
$|V_1| + |V_2| \geq |E| + 2$ because $E_1 \cup E_2 = E$ and $|E_i| = |V_i| - 1$.
If $G$ is a tree then we are counting the number of ways to write $V = V_1\cup V_2$ where $V_1$ and $V_2$ are not disjoint. This can be presumably calculated analytically.


texts: Planarity conditions for Planar 1-in-3 SAT

texts:
Planar 3SAT is NP-complete. A planar 3SAT instance is a 3SAT instance for which the graph built using the following rules is planar:

add a vertex for every $x_i$ and $\bar{x_i}$
add a vertex for every clause $C_j$
add an edge for every $(x_i,\bar{x_i})$ pair
add an edge from vertex $x_i$ (or $\bar{x_i}$) to each vertex that represent a clause that contains it
add edges between two consecutive variables  $(x_1,x_2),(x_2,x_3),...,(x_n,x_1)$

In particular, rule 5 builds a "backbone" that splits the clauses in two distinct regions.

Planar 1-in-3 SAT is NP-complete, too.

But for planar 1-in-3 SAT are the planarity conditions defined in the same way as in Planar 3SAT ? In particular, can we assume that there is a backbone that links the variables $(x_i,x_{i+1})$  ?


texts:
In an exam question it is asked to identify if the given language is Context-Free, Non Context Free or Regular.
This is the question :

In my opinion this language is not a CFL since w doesn't belong to L', meaning that it belongs to not(L') which is all words (a^n b^n c^n) which is not CFL.

Apparently my answer is not right and I really don't understand why... Is this question a "trap" because i,j,k > 0 and not >= ? Meaning that a word (b^n c^n) is in L ? Looks like I'm lost !

I really need your help and explantions.

Thanks in advance.


texts: Do any decision problems exist outside NP and NP-Hard?

texts:
This question asks about a corner case of NP classes. From Wikipedia, NP is defined as:

  the set of all decision problems for which the instances where the answer is "yes" have efficiently verifiable proofs of the fact that the answer is indeed "yes"

NP-Hard is defined informally as the set of problems that are

  at least as hard as the hardest problems in NP

The hardest problems in NP are NP-complete, whose best known solutions run in exponential time.

My question is, are there any decision problems that aren't as hard as NP-complete problems and do not have an efficient verifier?

I know that it cannot be any problem in P, because P is entirely contained in NP. And it probably cannot have exponential complexity, because that would likely move it to NP-complete or NP-hard. I'm thinking if such a problem exists, it would probably have to have sub-exponential complexity. Perhaps someone knows of a sub-exponential complexity problem that lacks an efficient verifiable proof. Either that or someone can tell me that it's been proven that there are no non-NP, non-NP-hard decision problems. Or that it hasn't been proven either way.

Thanks.


texts:
I have an essay question and I just want to make sure I have things right.

2 trains need to be able to communicate with eachother at any time.

Based on research i've settles on a wired network running along the tracks, with wireless access points. These converge on a central location which houses the switches/router to redirect comms.

The trains themselves have a router with WAP's so the driver can send comms from anywhere on the train.

What i'm struggling with is the idea that the train system is a LAN and so are the trains - would the onboard router connect to the trackside WAP's to send the messages?

I've seen that bridges can be used for similar but am unsure if that's what's needed in this scneario


texts: Node ordering at contraction hierarchy of biDirectional Dijkstra

texts:
I try to understand the node ordering at contraction hierarchy.

To me, ordering and contracting node looks impossible because when contracting a node, then it influence the other node. Therefore, it looks impossible to calculate the exact node order.

Let me explain the node ordering.

According to the some parameters such as edge difference, we can order the node and put the node at the prioriry queue.

After ordering, we extract the minimum priority node.

Before contracting the node, we should compare its priority with the recomputed priority of the head of the node in the priority queue, assuming the node is contracted.

It is because the contracting behavior influence the order of the nodes.

In this case, I have a question. Is it possible we cannot extract any node in the priority queue?

For example, in the queue, there are the nodes A, B, C, D, E in the order.

When we extract the node A, we found node B is actual minimum node.

Therefore, we put node A in the queue, again and extract B.

But after that, we recomputed the priority node A, we get to know A is the minimum.

Then we have to put node B.

I think it can go on and on. Therefore we cannot contract any node.

Is my think reasonable? And then how can we design the algorithm of node ordering?


texts: How to sample random game input that looks similar to human control?

texts:
What I would like to do is improve upon projects like 'RNG plays pokemon'. There, a computer produces a random sequence of inputs that are transmitted to an emulator and played in-game. Though this seems really pointless, the computer managed to beat the game that way.

However in this project, buttons are pressed at random, so the behaviour of the character is very far from what you would expect from a human player.
What I would like to do is to be able to produce a series of inputs that 'look like' one produced by a human player.

A good way to do that may be to record a sequence of inputs as played by a human player, use this data in order to produce a Markov Chain.

However I think a human player may exhibit a behaviour that is not easily taken into account by a Markov Chain. For example in order to double jump, it is generally a bad idea to have the second jump right after the first. So a typical sequence of inputs would look something like this (where f=forward and j=jump)
f-f-f-j-f-f-f-f-f-f-f-f-f-j-f-f-f

This sequence of inputs may be common when the game is played by a human, but in order to have a Markov Chain produce such a sequence of inputs, it means that the states have to correspond to sequences of inputs of length (at least) 10, hence a huge state diagram.

Is there an alternative to (or a variation of) Markov chains that can take this kind of behaviour into account?

NB: English is my 2nd language so I apologize if this question is poorly worded...


texts: Minimum amount of time for two enemies to reach their destinations?

texts:
Given an undirected, unweighted, and connected graph $G = (V, E)$, what is the minimum amount of time it takes for party $X$ to go from $s_x$ to $t_x$ and party $Y$ to go from $s_y$ to $t_y$? At each unit of time, $X$ and $Y$ can either move to a vertex adjacent to their current position or not move at all. $X$ and $Y$ are enemies with each other and if they go less than a distance of $k$ to each other they will go to war. The distance of $X$ and $Y$ is defined as the number of edges between them on the shortest path. What is an efficient algorithm to find the two optimal paths such that $X$ and $Y$ do not go to war and they both reach their destinations in the minimum amount of time? Note that the two paths can share edges as long as $X$ and $Y$ do not go less than k units of each other during their traversal. In the example below with $k$ = 1 the optimal path for $X$ is in blue and y is in red. This allows for both $X$ and $Y$ to reach their destination in two units of time Notice, if $X$ instead took the black path, this would be suboptimal as $Y$ would have to rest for one unit of time as $X$ moved out of the way. (This would take 3 units of time.)

So far I've started by computing the shortest paths between all pairs of vertices in $V$ by doing a BFS at each vertex. This will take $O(EV)$
Then, I suggest the following greedy algorithm:

At each time tick, $X$ and $Y$ should move to the vertex that is closest to their destination. If that vertex is less than k edges from the other party, choose the next closest vertex and so on. If no such vertex exists, then the current party will rest until the other party moves at least k units away from any of the adjacent vertices. Give priority to $X$ or $Y$ based on who has fewer options.

However, I don't think the greedy solution will work. Some other ideas include A* or a max flow reduction.


texts: DFA for at most two $b$'s and at least one $a$

texts:
I'm totally new to DFA's and automata in general – this is the first week or two of class that I've actually seen this – and I'm curious as to a pattern to match the following:

"Match the set of all strings on the alphabet $\{a, b\}$ that have at most two $b$'s and 1 or more $a$'s."


texts:
I am trying to understand the problem statement and the approximation algorithm for the Unique Coverage Problem from these notes. I have refined the question based on the comments provided. Thanks to D.W for pointing out Exact Cover problem.

  Given
            a universe $U = \{ e_1, e_2, \dots, e_n\}$ of n elements and
            given a collection $\mathcal{S} = \{S_1, S_2, \dots, S_m\}$ of subsets of $U$
                such that $\bigcup\limits_{S{_i}\in\mathcal{S}} S_i$, is equal to $U$.
   Exact cover is a decisional problem of finding if there exists a sub-collection of subsets $\mathcal{S^{'}} \subseteq \mathcal{S}$, which can cover the Universe $U$ and each element $e \in U$ is contained exactly in one subset $s \in \mathcal{S^{'}}$.
  Unique coverage problem is to find
            a sub-collection $\mathcal{S}^{'} \subseteq \mathcal{S}$,
            such that, pairwise intersection of $s \in \mathcal{S^{'}} = \phi$ and cardinality of  $\bigcup\limits_{S{_i}\in\mathcal{S}} S_i$ is maximum.

My questions are,

Are the definitions written above correct?
Is the Unique Cover Problem a computational version of Exact Cover? (Exact cover requires universe $U$ to be completely covered, while Unique cover problem tries to maximize the cover of universe $U$).

From this video,I got the following example and answer for this example as 6, at duration 11:46.

  $U = \{1,2,3,4,5,6,7,8\}$

  $S_1 = \{1,2,5 \}$; $S_3 = \{1,5,6,7\}$
  $S_2 = \{1,3,8 \}$; $S_4 = \{2,4,6,8\}$

It is also mentioned in the video that the answer is 6 and its when unique cover is $\{S_3, S_4\}$, but $\{S_3 \cap S_4\} = \{6\} \neq \phi$.

Isn't the answer to above example should be either $S_3$ or $S_4$, whose cardinality is 4?

The algorithm given in the notes is as following:

  Partition the elements into $\log n$ classes according to their degrees, i.e., the number of sets that cover the element. So class $i$ contains all the elements which are covered with at least $2^i$ and at most $2^{i+1}$ sets.
  Let $i$ be the class of the maximum cardinality.
  Choose any set with probability $\frac1{2^i}$

Applying the algorithm to above example, we get:

  $class_1: \{3,4,7\}$;
   $class_2: \{2,5,6,8\}$;
   $class_3: \{1\}$

As cardinality of class 2 is maximum among others, we pick $i = 2$.

What does the algorithm mean to say,

  Choose any set with probability $\frac1{2^i} = \frac1{4}$?
  (the probability of what?)

Can anyone explain how this algorithm will give a $\mathcal{O}(log \text{ }n)$ approximation of optimal solution?


texts:
I am struggling with the following problem

  Let $f:\mathbb{N} \to \mathbb{N}$ be a function on natural numbers and
  say $L$ is some language.

  Define $L_f = \left \{ x \mid \exists y \in \Sigma^*: |y| = f(|x|) , x \cdot y \in L \right \}$

  If $L$ is regular and $f$ is $x \mapsto x^2$ and $g$ is $x \mapsto 2^x$, show that $L_f$ and $L_g$ are regular.

I have solved the FirstHalf problem in which the function is $x \mapsto x$, using the technque of placing pebbles.

I understand that this problem would require some similar idea, probably keeping track of the states in two concurrent automata, using products of Boolean Transition Matrices, but I am unable to fill in the details.


texts:
According to this article,
A problem X can be proved to be NP-complete if an already existing NP-complete problem (say Y) can be polynomial-time reduced to current problem X. The problem also needs to be NP. Now my question is:

  Do we also need to prove that problem X can be reduced to at least one
  NP problem?

According to the definition of NP-completeness, each and every NP
problem must be reducible to NP-complete problem. As problem X is NP, are we not supposed to prove that this NP problem can be reduced to other NP-complete problems? Why does this reduction have to be only one way to prove a problem is NP-complete?


texts:
I am having trouble with coming up for a suitable algorithm for this question. A max-heap is essentially visualized as a binary tree not a binary search tree. Also the runtime of the algorithm must depend only on the number of elements in the output. I was thinking of doing a preorder traversal on the max heap. While doing the preorder traversal, if the value of a node is less than the given value x, we return to the previous recursive call. All child nodes in a max heap are less than the parent node. Otherwise we output current node and recur on the children.
I am not sure however if the runtime of this algorithm depends only on the number of elements in the output.
Anybody have other suggestions/thoughts? Thanks.


texts: Best way to merge 2 max heaps into a min heap

texts:
Assume we have 2 max heaps, each with n nodes. We want to merge these 2 heaps and build a min heap. What is the best way to do this?

The easiest way is to consider 2 max heaps an array with $2n$ elements and build a min heap with $O(n)$ complexity. Is there an algorithm with a complexity better than $O(n)$ ?


texts: "Natural" reductions vs "Polynomial-time many-one" reductions (Karp Reductions)

texts:
For two problems $A$ and $B$ and a Karp Reduction $R$ from $A$ to $B$, we call the reduction $R$ natural if, for any instance $I$ of problem $A$, the size of $R(I)$ (as well as the possible numerical parameters of $R(I)$ depends only on the size of $I$ and the sizes of $I$ and $R(I)$ are polynomially related.

We know that all the text-book reductions (from SAT to 3-SAT, 3-SAT to Vertex Cover, Hamiltonian Cycle etc.) are natural in the above sense. In fact, all the natural known "NP-complete" problems are complete under "Natural" reductions.

I have following two questions:

Is it possible for a Karp-reduction to be "non-natural" in the above sense?
Are "natural" reductions only a special case of "Karp" reductions or Can we generalize them for other reductions (like logspace or linear time reductions)?

To understand the context better: Kabanets-Cai[1999] in his seminal paper proved that Minimum Circuit Size Problem (popularly known as MCSP) being NP-hard under so-called "natural" reductions leads to class $E$ having superpolynomial circuit size. Then, recently Murray-Williams[2015] proved that MCSP being NP-hard under "Polynomial-Time" reductions leads to $EXP \neq NP \cap P/poly$ (This is weaker than Kabanets-Cai result). So, surely "natural" reductions are more strict than "polynomial-time" reductions. (or Am I missing something here?)


texts: Karger's min-cut (contraction): Combinatorial argument for success probability?

texts:
The contraction algorithm for min-cut is: pick an edge $(u,v)$ uniformly at random, and "contract" it by merging $u$ and $v$ into a single vertex, deleting self-loops. Continue until two vertices remain; return this cut.

The probability of finding the min cut can be shown to be at least

$$ \frac{1}{{n \choose 2}} . $$

This feels like it should have some clever combinatorial interpretation or proof. (Something that sounds like e.g. "we place the vertices in a uniformly random order and if the last pair is correct, the algorithm succeeds.") But every proof I have found involves brute-forcing the product
  $$ \frac{n-2}{n} \frac{n-3}{n-1} \cdots \frac{1}{3} = \frac{2}{n(n-1)} . $$

Is there any direct combinatorial argument that the probability exceeds ${n \choose 2}^{-1}$?


texts: Choice of algorithm for hierarchical clustering for minimizing network communication costs

texts:
Suppose I have a large distributed task running on a cluster system where part of the workload is compute bound and part depends on network performance.  Data transfer is not completely homogeneous between processes - some communication pairs are more or less sensitive to bandwidth and latency than others.

We've profiled this and have a square matrix describing how much
information is transferred between each pair of processes during the job.

We also know how the network is laid out and can approximate a scalar communication cost for each entry in that matrix.

Starting from that point, which clustering algorithms should I be looking at to permute that matrix to minimize total communication distance?  Or, I think equivalently: how can I compute a near-optimal clustering of processes so that the processes that communicate the most are closest to each other on the network?


texts: Is there a more efficient stability index algorithm?

texts:
I have this assignment for a class and we're beginning to learn time complexity. I have to find create a Java program that finds the stability indices of an array. Stability index being defined as a[0] + a[1] + ... a[i-1] = a[i+1] + a[i+2]+ ... a[n-1]. Essentially if you sum every element left of the index and every element right of the index(excluding the element at the index itself) and the two sums are equal, it is a stability index.

I believe its complexity is O(n^2) since I have nested loops both with worst case size of n. I'm having difficulty understanding how to make this more efficient. I thought perhaps there would be a way to calculate two different arrays of sequential sums. One would be increasing from index 0 and the other decreasing from the last index. Then compare the two values, but I'm not sure how to do this without nested loops.

Not looking for answers, just a push in the right direction.

EDIT: I made an improvement to O(N)


texts: Returning a random subset with length k of N strings while only storing at most k of them

texts:
Here's the problem. I've written a program that reads strings from stdin, and returns a random subset of those strings. The only other argument provided to the program is the length of the subset, $k$. The subset must contain exactly $k$ strings selected uniformly at random from the entire input set.

It's easy to do this if every single string is stored in memory. (Memory proportional to N). The question is how to only store at most $k$ strings, and still ensure that the output is perfectly random.

I've tried to work it out with the following base case. Say $k = 1$.

> Subset 1
A
B
C

A will always be added, since the queue contains less than k items.
If I only operate on what I know, which is the current number of items in the queue, the required length $k$, and the encountered strings $n$. So I've tried doing this: ($k$ - items in queue)/$n$.

Using that, the probability of A being replaced by B is $1/2$. Then the probability of B being replaced by C will be $1/3$. The problem there is that there's no way of reducing the probability of A being replaced before I've seen all of the strings.

I'm sure this question must have a clever answer. The problem of writing this Subset program to use memory $<= k$ is a bonus question on an Algs course I'm taking, and I really hope they wouldn't ask something unanswerable.


texts: Is there a way to solve coding challenges more easy?

texts:
I'm always using debugging and writing test cases to solve coding challenges. It's been very helpful so far but now that problems became very complex, its not good enough.

Is there a way to use tools like:

state machine diagrams
logic tables
regular expressions
something else

in order to create from there the pseudo code or something that provides a cognitive structure to create from there the implemented code in the technology of preference: C, C++, Javascript, etc.

In other words:

A verification process where I check my solution or part of it is going to work before typing anything in the keyboard
A scaffold to the thinking process in order to arrive at the solution faster and with better quality
A theoretical frame to make the solution faster by not testing so much.
A model from which the pseudo code can emerge easier.
A workflow that relies less in heuristics and more on some other formal method

This is the coding challenge that made me think it could be solved in a more professional way:

https://imgur.com/eW1bh5r
https://imgur.com/cTulsGL
https://imgur.com/4EeTC6Z
https://imgur.com/ewVwb8K

Maybe this question belongs to https://softwareengineering.stackexchange.com/ and not here. I'm sorry if there is a way my question doesn't meet the standards.  If so, please let me know how to perfect it. This is my first one and I have no intent in bringing trouble to the community. I know this question might be very vague but my doubt is very vague too. Because I'm not only asking for directions, I'm also asking where to go.


texts: How would I prove that nondeterministic Turing machines are undecidable?

texts:
How would I go about proving that the language:
$$A_{NTM }= \{\langle N, w\rangle | N \text{ is a nondeterministic TM and } N \text{ accepts }w\}$$
is undecidable?
I looked at the proof for $A_{TM}$ being undecidable, but am struggling to figure out how to prove the above. Any ideas?


texts: Finding top k which are the most different from each other

texts:
Assume I have a set of items $A$ and each item $a \in A$ has a score $s(a)$.
Also, each two items $a_1,a_2 \in A$ have variety score $var(a_1,a_2)$ which tells how different they are.

I want to optimize over these two values (say with equal weights) to find $k$ items that have both high scores and large variety (to avoid almost-repetitive items). That is, to solve the following optimization problem:

$$\arg\max_{a_1,...,a_k\in A}{(\sum_{i=1}^{k} s(a_i) + \sum_{1 \le i<j\le k} var(a_i, a_j)})$$

Is this problem NP-hard?
If not, can you provide a polynomial time algorithm that solves it?
If yes, can you provide a polynomial time approximation algorithm that approximately solves it?


texts:
The Monster M is the largest of the finite sporadic groups that arises in the classification of finite, simple groups in mathematics.

M can be realized as a (very large!) set of 196882 X 196882 matrices with nothing more than entries of 1's and 0's, so long as we compute arithmetic as follows:

1+1=0
1+0=1+0=1
1*1=1
0*0=0
1*0=0*1=0

I have two simple questions for the reader. What is the minimum amount of bytes needed to store a single matrix? What is the computational cost (i.e., in FLOPS) of a single matrix multiplication in the most efficient implementation?

Thanks,
Andrew.


texts: What is an algorithm that maps back and forth from (x,y) coordinates to the index of that point in a space filling curve over a rectangle?

texts:
Suppose that I have a space filling curve over a rectangle of width W and height H. For example, for the rectangle:

W = 4
H = 4

I have the following curve:

Now, given the following coordinate:

X = 1
Y = 2

We can say that its position on the space-filling curve is 7, as it takes 7 steps walking over the curve to reach that tile. Using that logic, we can build a mapping width → height → x → y → index, such as:

spaceFillingIndex(4,4,1,2) = 7

As well as its inverse, width → height → index → (x,y).

spaceFillingCoordinate(4,4,7) = (1,2)

My question is: what is an algorithm that implements spaceFillingIndex, and what is an algorithm that implements spaceFillingCoodinate?


texts: Associative mapped cache, word addressable

texts:
I have an associative mapped cache with 10 tag bits and an offset of 7bits.

What is the size of each main memory block in words(word addressable) and main memory size in words?

i worked it out as:
block size would 2^7bits.
main memory would be 2^17bits.

the issue I am facing is, how do I get them to be word addressable with this much information given. I have managed to get the above result in byte-addressable. Please correct me if i am wrong.


texts:
I'd like to expand on this question :

https://stackoverflow.com/questions/52420788/why-does-the-a-star-algorithm-need-gn

Dijkstra's algorithm uses cost function $f(n) = g(n)$
whereas A* uses cost function $f(n) = g(n) + h(n)$, with $g(n)$ being the cost of the path from the start node to node $n$, and $h(n)$ is a heuristic function that estimates the cost of the cheapest path from node $n$ to the goal.

It is clear from the linked question's answer that A* needs its $g(n)$ function in the cost function.
My question however is the following. Can one use the cost function :

$f(n) = \alpha g(n) + (1-\alpha)h(n)$

for some alpha $0<\alpha<1$ ?

I ask because in some cases I observed it can be much faster to prioritize (through a coefficient) estimated cost over already traversed cost. I am not sure however if this still results in an optimal path?

EDIT : multiplying the heuristic $h(n)$ by some alpha $0<\alpha<1$ is allowed, since this operation still underestimates if $h(n)$ already did (which is necessary to obtain the resulting optimal path). I am more concerned about the multiplying of $g(n)$.


texts: algorithm for scheduling tasks based on constraints and feedback loop if possible

texts:
I have a list of recurring tasks (1k+ tasks) and I am trying to find a optimal scheduling given a shared constrained resource.

In other respects the tasks are independent of each other

Each task is configured to run recurrently at a given interval (i.e "cron" job).
For instance a particular task could have been configured to run at 10 minute intervals while another task could be configured at 20 minutes etc.

The duration of tasks varies (disregarding the shared resource)

Tasks have priorities (importance).

The task interval is in respects to the completion time of the previous run.

Task interval is "soft" and can be offset to accommodate for higher priority jobs.

I can estimate based on historical evidence how many "shares" of the shared resource each task requires

+-----------+-------------+----------+--------------------+-------------------------+
| Task name |  Interval   | Priority | Estimated duration | Estimated resource      |
+-----------+-------------+----------+--------------------+-------------------------+
| task1     | 30 minutes  |        1 | 10 minutes         | 10                      |
| task2     | 10 minutes  |        3 | 25 minutes         | 90                      |
| task3     | 60 minutes  |        4 | 5 minutes          | 25                      |
| ...       |             |          |                    |                         |
| task 1000 | 180 minutes |        2 | 75 minutes         | 100                     |
+-----------+-------------+----------+--------------------+-------------------------+

conceptually the architecture should be:

                                                                              +------------+
  task list                                                                   |            |
+-------------+                                                               | Task x     |
|             |                       +-----------+                           |            |
|    Task1    |                       |           |      running  tasks------>+            +----------+      +-----------------+
|    Task2    |    choose tasks       |           |               |           |            |          |      |                 |
|    Task3    +----------------------->  Scheduler+---------------+           |            |          |      |                 |
|    ....     |                       |           |               |           +------------+          |      |                 |
|    Task_N   |                       |           |               |               .                   +----->+                 |
|             |                       |           |               |               .                          | constrained resource
|             |                       +-----------+               |               Many tasks                 |                 |
|             |                                                   |               .                   +------>                 |
+-------------+                                                   |               .                   |      |                 |
                                                                  |           +------------+          |      |                 |
                                                                  |           |            |          |      |                 |
                                                                  |           | Task z     |          |      +-----------------+
                                                                  +----------->            +----------+
                                                                              |            |
                                                                              |            |
                                                                              |            |
                                                                              +------------+


texts:
In CLRS , under the section "Maximum sub array problem", there is a problem to maximize the profit in the stock exchange. The problem is.. given an array A[1..n] and we have to find i and j such that i < j and A[j] - A[i] should be maximum. the solution given is O(n^2) . But I have a solution which does it in O(n) . I know it should be wrong , But I cant find a single counter example to my solution.

My solution :

(i) Find the maximun and minimum in A[1..n] . Let A[x] be the maximum and A[y] be the minimum.

(ii) And find minimum in A[1..x] . Let that be A[u].

(iii)Find maximum in A[y..n] . Let that be A[v].

(iV) Answer = Max{(A[x]-A[u]),(A[v]-A[y])}

What am I doing wrong?


texts: Unsupervised learning: necessity of labels and dependency between features and labels?

texts:
I have logs of activities without labels, which describe whether an activity is normal or not. Assuming that normal behaviors will follow a Gaussian distribution, I fit Gaussian distributions on dataset. I utilized this to generate a synthetic dataset with abnormal patterns.
Then, according to the literature review, I generate labels by confidence intervals.
After generating labels, I separated train/test dataset. I utilized pdf of gaussian distribution as a feature and learned a simple decision trees.

Depending on dataset, sometimes, this approaches produce 99.5% precision and recall, almost perfect classification.

I felt like that the approach of generating synthetic dataset, labelling, and feature extraction is related in some sense. I am not sure how much I can rely on this trained classifier.
If I did anything incorrect, could anyone suggest how to build more credibility on classifiers?


texts: Faster algorithm to search in a set of strings

texts:
Suppose that we are given a pattern $p$, which is a set of characters (order doesn't matter).  We are also given a set of strings $A$. I want to find all of the strings in $A$ whose characters are all contained in $p$ (without taking the order of these characters into consideration), i.e., to find all $s \in A$ such that every character in $s$ is also in $p$.

The algorithm that I use is to loop every string in $A$ first, and, then, loop every character in each string, so the time complexity is $O(nm)$. My question is: is there any faster algorithm? Bit operation or matrix is ok.

Here is an example:

Pattern "abcdef"

Set A  {a, b, ac, ag, bde, cbd, daf, cg, abzdef, d}

Desired results : a, b, ac, bde, cbd, daf, d

Filtered: ag, cg, abzdef (as g,z don't belong to the original string "abcdef")


texts: Average-case analysis of linear search given that the desired element appears $k$ times

texts:
The problem below is adapted from CLRS Problem 5-2 "Searching an unsorted array":

  Consider a deterministic linear search algorithm which searches an array $A$ for $x$ in order, say $A[1], A[2], \ldots, A[n]$, until either it finds $A[i] = x$ or it reaches the end of the array. Assume that all possible permutations of the input array are equally likely.

  Suppose that there are $k \ge 1$ indices $i$ such that $A[i] = x$. What is the average-time running time of this algorithm?

Let $X$ be a random variable denoting the number of comparisons.

$$
\begin{align*}
  E(X) &= \sum_{i=1}^{i=n-k+1} i \cdot \Pr(X = i) \\
       &= \sum_{i=1}^{i=n-k+1} i \cdot \left(\frac{n-k}{n} \cdot \frac{n-k-1}{n-1} \cdot \frac{n-k-2}{n-2} \cdot \cdots \cdot \frac{n-k-i+2}{n-i+2} \cdot \frac{k}{n-i+1}\right)
\end{align*}
$$

How to evaluate this summation? Or is there a simple solution to this problem?

Note that when $k=1$, $E(X)$ is $\frac{n+1}{2}$. When $k=n$, $E(X)$ is $1$.


texts: Can the concatenation of two non-regular languages be regular?

texts: Can anyone give an example of two non-regular languages $A, B \subseteq \{0, 1\}^∗$ for which the language $AB$ is regular?


texts: Should check all $2^n$ possibilities in array?

texts:
Suppose I have an array of numbers, and a function boolean isPrime(int n) that I'm allowed to use.

Boolean isPrime(int n) receives a number n and return true if the received number is a prime and false otherwise.

I need to write a function int foo(int[] a) that receives the given array and return the biggest prime number that I can "create" by adding values from the given array.

For example: for the array 8,11,8,2 the function foo should return 19

It's not a homework or something, I noticed that in a lot of job exams there is this type of question. It looks simple and naïve, but it's not.

There are a lot of possibles, for array with size $n$ the are $2^n$ possible combinations.
In the given example the possibilities are:$\{8,11,2,8+11,8+8,8+2,8+11+8,\dots\}$

What's the best way to approach this type of question? I'm sure that it's related to some smart algorithm.


texts: How can I do a subtraction with a two tape Turing machine

texts:
I have already made a Turing machine with just one tape that solves a subtraction between two numbers, but I trying to do the same but with TWO tapes.
As an example, how can I solve 4-2?
Taking account that 4 can be represented as 0000, 2 as 00 and the - as 1.
So, in this case the input will be 0000100.


texts: Check if a lambda constructor is well-typed

texts:
In basic type inference for -calculus with parametric polymorphism à la Hindley–Milner,
when can we say that we cannot give a type to a lambda constructor?
For example
$$(λx.λy.y(x\ y))(λz.z)$$


texts:
I've been reading a book about turing machines and it has a challenge about a building a Turing Machine that has as many 0s as many 1s but that can appear in any order.

I don't understand how do you set the reading to the beginning and then make a transition to the beginning.

But it deals with only 0s that shows up before 1s, how would i go about in the same instance if i find something like 100, or 100001?


texts:
I am trying to understand Church's Numerals for 4:

$$4 = \lambda f.\, \lambda x.\, f f f f x\,.$$

This will be evaluated in the following order:

$$\lambda f.\, \lambda x.\, (f (f (f (f x) ) ) )\,.$$

My question is why the function body will not evaluate left outer most, like

$$( ( ( ( (f f) f) f) f) x)\,?$$


texts: Floyd–Warshall algorithm ,Behavior with negative cycles

texts:
I am sorry my English is not very good.
my problem might look simple for everyone here.
I have read about Floyd–Warshall algorithm in wikipedia,every thing was good but when I start reading "Behavior with negative cycles" I face problem in understanding this sentence:
"There is no shortest path between any pair of vertices i, j which form part of a negative cycle, because path-lengths from i to  j can be arbitrarily small (negative)"
I don't understand what it exactly mean.
can anyone help me please.
Behavior with negative cycles


texts: Is there a sometimes-efficient algorithm to solve #SAT?

texts:
Let $B$ be a boolean formula consisting of the usual AND, OR, and NOT operators and some variables.  I would like to count the number of satisfying assignments for $B$. That is, I want to find the number of different assignments of truth values to the variables of $B$ for which $B$ assumes a true value. For example, the formula $a\lor b$ has three satisfying assignments; $(a\lor b)\land(c\lor\lnot b)$ has four. This is the #SAT problem.

Obviously an efficient solution to this problem would imply an efficient solution to SAT, which is unlikely, and in fact this problem is #P-complete, and so may well be strictly harder than SAT. So I am not expecting a guaranteed-efficient solution.

But it is well-known that there are relatively few really difficult instances of SAT itself. (See for example Cheeseman 1991, "Where the really hard problems are".) Ordinary pruned search, although exponential in the worst case, can solve many instances efficiently; resolution methods, although exponential in the worst case, are even more efficient in practice.

My question is:

  Are any algorithms known which can quickly count the number of satisfying assignments of a typical boolean formula, even if such algorithms require exponential time in the general instance? Is there anything noticeably better than enumerating every possible assignment?


texts: Region-based memory management for recursive type

texts:
In the chapter 4 of Pierce's TAPL which discusses the implementation of untyped arithmetic expressions, the author said

  The most important [for the implementation requirements] are automatic storage management... and... pattern matching over structured data types.

Indeed, which the recursive type is natural in ML, it is not allowed in Rust, e.g.

type Info = String;

enum Term {
    ...
    TmIf(Info, Term, Term, Term),
    ...
}

instead Term should be boxed as

enum Term {
    ...
    TmIf(Info, Box<Term>, Box<Term>, Box<Term>),
    ...
}

Similarly, in C/C++, we must use pointers for members in such a recursive type.

While Rust is region-based (and C/C++ is manual) memory management, I wonder whether or not automatic (garbage collection) memory management is obligatory for a language which is capable to represent naturally recursive types?


texts: LOGSPACE in different Turing Machine variants

texts:
Let's consider two-head (and two tapes) Turing machine. Let some problem $P$ be decidable in $LOGSPACE$ on that machine. What about complexity of that problem on the normal Turing machine ( one head, one tape?)

I asked that question because I am thinking of some problem- I have to be able to get value of $i$-th cell but my input is read-only.


texts: Why are threads called the unit of dispatch?

texts: Threads called the "unit of dispatch" but what does that mean? I was looking over the web and two operating systems books but I can't find the answer. It seems that processes are defined by two characteristics: resource ownership and scheduling/execution. I understand that threads are within processes, and that there must be at least one thread. Can someone explain this to me please?


texts: Can I find a clique with more than 2 nodes in a bipartite graph?

texts: As in the title, is it possible to find a clique with more than 2 nodes in a bipartite graph?


texts:
I'm new to complexity and came upon the following exercise which I'm unable to solve.

Prove that if $NP\subseteq BPP$ then $\Sigma_2^p=\Pi_4 ^p$.


texts: how to construct a formula with an opposite SAT value of another one

texts:
given a formula S (that is built of binary variables and "or", "not", "and" gates).
IS there a polynomial algorithim that builds S' that satisfies:
S' satisfied if and only if S doesn't satisfied.
which means: S' is in SAT if and only if S not in SAT


texts: How do I find the shortest representation for a subset of a powerset?

texts:
I'm looking for an efficient algorithm for the following problem or a proof of NP-hardness.

Let $\Sigma$ be a set and $A\subseteq\mathcal{P}(\Sigma)$ a set of subsets of $\Sigma$. Find a sequence $w\in \Sigma^*$ of least length such that for each $L\in A$, there is a $k\in\mathbb{N}$ such that $\{ w_{k+i} \mid 0\leq i < |L| \} = L$.

For example, for $A = \{\{a,b\},\{a,c\}\}$, the word $w = bac$ is a solution to the problem, since for $\{a,b\}$ there's $k=0$, for $\{a,c\}$ there's $k=1$.

As for my motivation, I'm trying to represent the set of edges of a finite automaton, where each edge can be labeled by a set of letters from the input alphabet. I'd like to store a single string and then keep a pair of pointers to that string in each edge. My goal is to minimize the length of that string.


texts: Why does stable matching without Gale-Shapely takes n! steps

texts: There are n men and n women. I am unable to understand how stable matching done by simply searching through all the matchings takes n! steps i.e., I cannot figure out why there are n! matchings possible.


texts: Finding a pair of non-overlapping bit vectors

texts:
I give you a list of $n$ bitvectors of width $k$. Your goal is to return two bitvectors from the list that have no 1s in common, or else to report that no such pair exists.

For example, if I give you $[00110, 01100, 11000]$ then the only solution is $\{00110, 11000\}$. Alternatively, the input $[111, 011, 110, 101]$ has no solution. And any list that contains the all-zero bitvector $000...0$ and another element $e$ has a trivial solution $\{e, 000...0\}$.

Here's a slightly harder example, with no solution (each row is a bit vector, the black squares are 1s and the white squares are 0s):

■ ■ ■ ■ □ □ □ □ □ □ □ □ □
■ □ □ □ ■ ■ ■ □ □ □ □ □ □
■ □ □ □ □ □ □ ■ ■ ■ □ □ □
■ □ □ □ □ □ □ □ □ □ ■ ■ ■
□ ■ □ □ □ ■ □ □ □ ■ ■ □ □
□ ■ □ □ ■ □ □ □ ■ □ □ □ ■
□ ■ □ □ □ □ ■ ■ □ □ □ ■ □ <-- All row pairs share a black square
□ □ ■ □ □ □ ■ □ ■ □ ■ □ □
□ □ ■ □ □ ■ □ ■ □ □ □ □ ■
□ □ ■ □ ■ □ □ □ □ ■ □ ■ □
□ □ □ ■ ■ □ □ ■ □ □ ■ □ □
□ □ □ ■ □ □ ■ □ □ ■ □ □ ■
□ □ □ ■ □ ■ □ □ ■ □ □ ■ □

How efficiently can two non-overlapping bitvectors be found, or be shown not to exist?

The naive algorithm, where you just compare every possible pair, is $O(n^2 k)$. Is it possible to do better?


texts: Can one find an algorithm whose running time is larger than Ackermann's function?

texts: Is there an example of an algorithm whose time complexity is strictly larger than Ackermann's function?


texts:
Is the Kolmogorov complexity of any piece of information with respect to a certain predefined encoding for all pieces of information, or can the encoding vary for each piece of information?

There are different encoding mechanisms for representing data, and different ways of compressing the encoded data. If Kolmogorov complexity was encoding agnostic, then wouldn't the shortest computer program to describe each information be "0" or "1" and a call to the encoding system where each encoding system maps "0" or "1" to pieces of information of arbitrary length (the number of encoding systems would be $\frac{n}{2}$, where $n$ is the umber of pieces of information being considered). We could also increase the length of the description string, and reduce the number of encoding systems, but I think my point stands. This seems like a trivial notion of Kolmogorov complexity--is there anything I'm missing?


texts: How to define the partial or total order of the segments to be inserted in a "sweep-line status" data structure?

texts:
I am interested in the details of the implementation of the "sweep-line status" data structure, which is used to implement the Bentley-Ottmann algorithm to find all intersections (and the corresponding involved segments) of a set of segments (or line-segments). The algorithm and the sweep-line status data structure is briefly described in chapter $2$ of the book "Computational Geometry: Algorithms and Applications" by de Berg, Cheong, van Kreveld, and Overmars.

In the book, the authors suggest two methods to implement the sweep line status. Both of these methods use a self-balancing BST, let's call it $T$.

One method (according to the authors the easiest one) consists in storing the segments at the leaves of the $T$ in the same order that they intersect the sweep line and use internal nodes to store the rightmost segment which is found in the left subtree of that node. For example, in the following figure, we see that the root node (an internal node) stores $s_1$, which is the rightmost leaf node (segment) in the left subtree of the root itself.

How exactly do we define the total (or partial?) order of the segments, given that we must maintain this invariant? How do we define or represent the segments? How exactly do we compare them?

If we needed to treat internal nodes in a different way (as the picture above suggests, given the different types of objects, i.e. circles and rectangles, used to represent internal and leaf nodes) than the leaf nodes (the actual segments), then it may not be an easy task to maintain a self-balancing BST (e.g. an RBT). Actually, a "plain" RBT usually treats all nodes equally, so we would need a new data structure. Nonetheless, the authors of the book claim that a self-balancing BST is enough to implement the "sweep-line status" data structure.

According to the lecture notes of D. Mount, we can store the segments (in the sweep line status) as a pair of numbers $(a, b)$, which are the numbers of the equation line which goes through the segments, i.e. $y = a*x + b$. However, he doesn't really explain how to compare segments, but only how to compare lines.

In the Bentley-Ottmann algorithm, let's suppose that we are processing segments/events from left to right. If we are processing one event point (from the event queue), this event point can either be of three cases (i.e. a left endpoint of a segment, a right endpoint of a segment, or an intersection point of two segments). Now, let's suppose it's a left endpoint of a segment. D. Mount suggests a way to compare if the line corresponding to new segment that we need to add to the sweep line status is below or above another line. I understand that and I understand his method. What I don't understand is how we go down the $T$ (from the root) to insert this new segment whose left endpoint corresponds to the current event point being processed, according to the description of the method the authors of the book regarding the storage of the segments in the tree $T$. In other words, given an event point corresponding to a left endpoint of a segment, which we want to add to $T$, how do we actual insert it into $T$ (in a self-balancing BST which needs to maintain the invariant that each internal node stores the rightmost segment or leaf of its left subtree), and maintaining the self-balancing BST $T$ as the authors of the book describe (and as I am describing above)?


texts:
For regular languages $R, S$ and $T$, which of the following are true?

$R \cup S = S \cup R$
$(R \cup S) \cdot T = RT \cup ST  $
$R^* \cdot S^* = (R \cup S)^*$


texts: Difference between consensus number n and consensus number infinite

texts:
In book Concurrent Programming: Algorithms, Principles, and Foundations of Michel Raynal, in Section 16.5.1, Theorem 75 says

  Compare&swap objects have infinite consensus number.

and in Section 16.5.2, Lemma 40 says

  The mem-to-mem-swap object type has consensus number n in a system of n processes.

Then, in Section 16.1, author puts in table both Compare&swap and men-to-mem-swap as objects with consensus number infinite.

So, what is the difference between objects with consensus number n and objects with consensus number infinite?


texts: Proving a language with equal occurences of ab, and cd is not a regular language using the Pumping Lemma

texts:
I am trying to show that $A = \{w \in \{a,b,c,d\}^{*}|w \textrm{ has equal occurences of } ab \textrm{ and } cd\}$ is not regular by using the Pumping Lemma.
My idea here was to use the string $ s = (ab)^{p}(cd)^{p} $.  Clearly, $ s \in A $, and $ |s| = 2p \geq A $.  So the the three conditions of the pumping lemma hold.
Where I am stuck is picking the correct decomposition of $ s $.  My idea was to do the following:
We can decompose $ s $ into $ xyz $ such that:

$ x = (ab)^{j}, j \geq 0 $
$ y = (ab)^{k}, k \geq 1 $
$ z = (ab)^{p-j-k}(cd)^{p} $

Now consider if we "pumped" $ y $.  Let $ i = 2 $.  Then $ xy^{2}x = (ab)^{j}(ab)^{2k}(ab)^{p-j-k}(cd)^{p} = (ab)^{p+k}(cd)^{p} \notin A $.  Therefore, we arrived at a contradiction and $ A $ is not a regular language.
But my confusion here is that the $ xyz $ I have chosen is not the only decomposition of $ s $.  For example, you could choose $ x = a $, $ y = b $, and $ z $ is the rest of the string.  Do I have to cover all possible cases?  If so, this seems like a bad choice for $ s $ -- any other ideas?
Another concern is that my chosen decomposition violates the condition $ |xy| \leq P $ of the Pumping Lemma will not hold for $ p = 1 $.


texts: Formal definition of the Dynamic Array - what is the Dynamic Array

texts:
I've researched quite a bit about this topic. Since I'm kind of a fan of Exact Sciences, I love everything to have a crystal-clear and determined definition, without any ambiguous or dubious points.

Dynamic Array, according to the Wikipedia's article, is a Data Structure. Article states, that:

  Dynamic array (also called as growable array, resizable array, dynamic
  table, or array list) is a random access, variable-size list data
  structure that allows elements to be added or removed.

This/above definition, surprisingly coincides with the definition of the Dynamic Array provided in the Data Structures and Algorithms Made Easy book (Chapter 3.5), by Narasimha Karumanchi.

However!,

We know, that the Data Structure, by its formal definition, is a specialized implementation of the Abstract Data Type (ADT), but I have never seen, in any programming language ever, any specialized Data Structure called Dynamic Array, nor can I find any ADT which is implemented by Dynamic Array.

For instance, we have several Data Structures, in Java, which implement List interface (and interface constitutes an ADT, in this case, as similarly to the concept of ADT, it declares the abstract behavioural characteristic of What must be done, and - says nothing about How), and Dynamic Array is defined (as shown above) as a Data Structure implementing a concept of the Array with the functionality of adding and removing elements in/from it. Many resources (including books provided) define the model of the Dynamic Array as implementations of List - namely ArrayList and LinkedList in the case of Java.

So,

if the Dynamic Array is a Data Structure, then what is the ADT
implemented by that Data Structure?
Maybe Dynamic Array suits more the concept of ADT where the implementations of it are provided in a different ways (example in Java is classes implementing List)?
What is the formal definition of Dynamic Array? is it ADT? is it Data Structure? as I find the definitions in the books/articles, quite contradictory and they oppose each other.

I, personally, think of defining it as a special type of Array Abstract Data Type, in which, structure is not a fixed-sized. I'd call it a special type of Array ADT, which makes it also ADT. Because, it's obvious, that if the Data Structures implementing the Dynamic Array (as said in the provided resources) are very concrete classes like LinkedList and ArrayList then the Dynamic Array itself is no longer a Data Structure, but rather it's some special kind of Array ADT.

What is the Dynamic Array? how it should be correctly and formally defined? Maybe it's just a concept of non-fixed-sized array, which is a conceptual model and has nothing to do with any ADT or DS?


texts: Explain why a language can be generated by a context free grammar

texts: I have a problem where I am asked to explain why the language that has words made of $a$ and $b$ such that the number of $a$'s is equal to the number of $b$'s, can be generated by a context free grammar. I am not sure of what is asked here, will finding such a grammar work? What should I do?


texts: How to create new language with languages $L_a = \{a\}, L_b = \{b\}$ and set operations?

texts:
I have to create new language with languages $L_a = \{a\}, L_b = \{b\}$ and with set operations which contains only words

with even length
with odd length and first letter not equal to last letter

So my solution for part 1 is this. Am I rigth?

  $L_n = \{aa, bb, ab, ba\}* = (L_a.L_a \cup L_b.L_b \cup L_a.L_b \cup L_b.L_a)*$

Regarding to part 2, I dont have any simple solution. In this language must be words like these: $abb,bba,baaaa, ababb$ etc. So before first and last word must be only word with odd length. But I dont know how to write it.


texts: Are there BBP formulas for all computable numbers?

texts:
A BBP algorithm is a formula with the following form where $b \in \mathbb Z$, $b \ge 2$, and $p(k)$ and $q(k)$ are polynomials in $k$
$$\sum_{k=0}^{\infty}\frac{1}{b^k}\frac{p(k)}{q(k)}$$
There are known BBP formulas for many computable numbers and it is easy to prove that any number with a BBP formula is computable.

Obviously all rationals have BBP formulas, let $n$ equal the length of the period in base $b$ and let $q(k)=1$ and $p(k) = \lfloor b^n\frac{p}{q}\rfloor$

I don't believe that there is a general form like that for all computable reals, i.e. you cannot given a definition of an irrational $\alpha$ derive $b$,$p(k)$,$q(k)$, but is it true that one exists for all computable numbers?


texts: How to construct the found path in bidirectional search

texts:
I am trying to implement bidirectional search in a graph. I am using two breadth first searches from the start node and the goal node. The states that have been checked are stored in two hash tables (closed lists).
How can I get the solution (path from the start to the goal), when I find that a state that is checked by one of the searches is in the closed list of the other?

EDIT

Here are the explanations from the book:
"Bidirectional search is implemented by having one or both of the searches check each
node before it is expanded to see if it is in the fringe of the other search tree; if so, a solution has been found... Checking a node for membership in the other search tree can be done in constant time with a hash table..."

Some pages before:
"A node is a boolkkeeping data structure used to represent the search tree. A state corresponds to a configuration of the world... two different nodes can contain the same world state, if that state is generated via two different search paths." So from that I conclude that if nodes are kept in the hash tables than a node from the BFS started from the start node would not match a node constructed from the other BFS started from the goal node.

And later in general Graph search algorithm the states are stored in the closed list, not the nodes, but it seems to me that even that the states are saved in the hash tables after that the nodes are retrieved from there.


texts:
Is there an algorithm that can efficiently solve the following question?

Given a directed acyclic graph G with n vertices each assigned a random color from a set of size <= n - 1 colors, a source vertex s, and two distinct vertices a and b both having the same color and reachable from s.

Determine if there exists at least one path from s to a and one path from s to b that have the same sequence of vertex colors.


texts: Given an array of sum and an array how can to find if all the sums are possible using distinct elements of array?

texts:
example:

if we have array of int as 1 2 3
and sum array is given 3,3 we can form this sum as {1,2} and {3}
if the sum array is 5 3 we can not create the sum array, we can for {2,3} but not enough items to form the sum 3.

Can someone help me to understand which algorithm can be used to solve the problem.


texts: How to explain the steps in the implementation of hashing functions like SHA1

texts:
I was reading the article about the SHA1 hashing function (I know it is not secure anymore) and I've found a pseudocode implementation on Wikipedia.

I can see that there are a lot of mathematical operations, and what I wanted to know is the justification of each step in this hashing function. I want to know, for example, how each part increases the security of the function. How do we know that these operations are gonna produce a drastic change in the output when a minimum change is made in the input?

Is there a book about the theory behind hashing function? Maybe a book that explains mathematical functions or operations that maps the input to a very large output space such that is very hard to do the inverse way.

Is there a very simple hashing function that can be studied and that are examples of attacks? Is there some paper that explains the evolution of these functions and the justification for some math operations in this?