texts: Time complexity and upper and lower bounds

texts:
Consider the following algorithm:
(the print operation prints a single asterisk; the operation x = 2x doubles the value of the variable x).
for k = 1 to n:
   x = k
   while (x < n):
      print ’*’
      x = 2x

Let f (n) be the time complexity of this algorithm (or equivalently the number
of times * is printed). Provide correct bounds for O(f (n)) and Ω(f (n)), ideally
converging on Θ(f (n)).
This question is one of practices in The Algorithm Design Manuel.
I found the time complexity to be $\sum\limits_{k=1}^{n}\lceil\lg(\frac n k)\rceil$
My question is, could this (or any function) be its own upper and lower bound?
Also is there a way to simplify this function (like writing the sums using some formula like $\frac{n(n+1)}2$)?
Thanks in advance.


texts: λ -calculus : What is the most efficient in memory representation of functions?

texts:
I would like to compare performance of function encoded (Church's / Scott's) vs classically encoded (assembler / C) data structures.

But before I do that I need to know how efficient is / can be function representation in memory. The function can be of course partially applied (aka closure).

I am interested in both the current encoding algorithm popular functional languages (Haskell, ML) use and also in the most efficient one that can be achieved.

Bonus point : Is there such encoding that maps function encoded integers to native integers (short, int etc in C). Is it even possible?

I value efficiency based on performance. In other words the more efficient the encoding is the less it influences performance of computation with functional data structures.


texts:
I have very little experience with graph DBs but i imagine this problem suits one

Assume a dataset with two entities , Users and Foods. A user can have a relationship with a Food, specifically they can score it from 0 to 100.

What i'd like to achieve is, for every user, find all the other users that are similar to them. By similar i mean find the Users that have also liked similar Foods and get a match so essentially im trying to build a a matchmaking system.

Algorithms such as finding friend's of friends are relatively easy to wrap my head around however im unsure as to how to approach this one and wether describing my data as a graph is even the right way to go about it.

I originally made a thought experiment to see how this would look on a relational database and its clearly quite hard to achieve as for every insert of a new Food or User, recalibration would need to happen for the entire database ( which sounds unavoidable in the first place )

I dont know what i dont know so if you could give me some pointers from here i'd be happy to follow your leads. Thanks so much.


texts: Finding a graph-theoretic representation of expressions in Boole's algebra

texts:
I just read "Boole's Algebra Isn't Boolean Algebra" by Theodore Halperin (behind a paywall here). I don't have a strong background in abstract algebra, so, frankly, the paper is a bit over my head but the gist of it is as follows: the algebra developed by Boole in the 19th century has some strange properties. Boole interprets every term in an expression as representing a set and restricts the domain of valid expressions on the basis of relationships between the underlying sets. In particular, he asserts that the expression $x + y$ is valid iff $x$ and $y$ represent disjoint sets, and $x - y$ is valid iff the intersection of $x$ and $y$ is nonempty. He also defines an operation $w = \frac x y$ such that $w$ has many solutions. Halperin goes to great lengths to construct a commutative ring that satisfies Boole's constraints.

I think that there might be a nice, intuitive, graph-theoretic interpretation of Boole's algebra where we can say something like "Given a complex expression in Boole's algebra, $\Phi = \{\phi_1, \phi_2\, \dots, \phi_n\}$, we can construct a (di)graph $G$ such that $\Phi$ is valid if and only if $G$ has some property $P$."

For example, to test if $X + Y$ is valid, we could do something like the following:

Let $G$ be a graph. Let $V(G) = X \cup Y \cup \{v_X, v_Y\}$, i.e. make a vertex for every element of the underlying set, plus a vertex for each term in the expression. Then define

$$E(G) = \{uv_X \mid u \in X \} \cup \{uv_Y \mid u \in Y \}$$

and let $\partial(G)$ be the set of all valid bonds formed by subsets of $V(G)$. It follows that $X + Y$ is valid if and only if $|\partial(G)| = 2$.

From there, I'm not sure how to go about forming graphs for complex expressions like $\frac {y(x + z)} {z^2 + 1}$ by composing simpler graphs. I imagine that there is literature about representing Boolean algebra on graphs, but I haven't been able to find it.

Does anyone have an elegant interpretation? Or a pointer to relevant literature that might get me started?

EDIT: I can't find the article for free anywhere, but wikipedia touches on the issues:

  In places, Boole talks of terms being interpreted by sets, but he also
  recognises terms that cannot always be so interpreted, such as the
  term 2AB...Such terms he classes uninterpretable
  terms...uninterpretable terms cannot be the ultimate result of
  equational manipulations from meaningful starting formulae.

Halperin's paper shows that his algebra is isomorphic to "a commutative ring with unit having no additive or multiplicative nilpotents." I think, for that reason, that it will require heavier machinery to represent than normal Boolean logic operations.


texts: NLP - Deep belief neural networks or logic?

texts:
The NLP progresses seems to me that has split in two big group of thoughts:

Deep learning have a neural network with multiple layers that has been trained and learned to represent knowledge and understand the meaning of sentences. However, such system would be difficult to debug and correct
Logic and inference, label parts of speech and learn by inference and using tools such as Natural logic.

Can someone point out if anything is wrong in these conclusions? Is there any other stream of thoughts that I should be taking into consideration?


texts: right and left derivatives of a cfg from parse tree?

texts:
i just want to double check with what i concluded from this parse trees.

       A
      / \
     /   \
    B      C
   / \    / \
  0   D  D   E
         |   |
         0   1

from the above tree i get right derivation to be

  A -> C

  C -> D|E

  E -> 1

  D -> 0

and the left derivation as

  A -> B

  B -> 0|D

  D -> 0

i just want someone to proof check for me. and tell me if am wrong somewhere. Thanks!


texts: Why is $AF \phi \lor \varphi$ not equivalent to $AF \phi \lor AF \varphi$?

texts:
Can someone explain to me (perhaps with an example) why $AF (\phi \lor \varphi)$ is not equivalent to $AF \phi \lor AF \varphi$. This seems counter-intuitive, because in any path where $\phi$ (or $\varphi$) is true, $\phi \lor \varphi$ is true as well. Or is my reasoning wrong?

Thanks


texts: Combinatorics: how many ways can we mark nodes in a DAG as black or white, if every node downstream of a black node is also black?

texts:
We are assigning the colours white/black to the vertices of a DAG, under the condition that if $V$ is black and there is a path $V \to W$ for some vertex $W$, then $W$ is black.

Examples:

In the case of a linear chain of $N$ nodes, the answer is $N+1$ - either all the nodes are white, or one of the N nodes is black meaning all subsequent nodes in the chain are black.
In the case of $N$ nodes and zero edges, the answer is $2^N$.

A trivial solution is to generate all valid of the graph colourings, and then count the number of them. This can be done recursively in exponential time.

I'm looking for an efficient solution to the above problem. There is a seemingly O(n) dynamic programming algorithm that solves this for trees; I wasn't able to generalise it for the arbitrary DAG case.


texts: Clarification regarding definition: Two way non deterministic finite state Automata

texts:
In two way non-deterministic finite state automata there is the concept of reject state.

Since an input is accepted if any one of the parallel branches in the Non Deterministic FSA reaches an accept state and the rest of the branches are then immaterial.

On a given Input even if one of the branches reaches the 'reject' state and the other reaches the accept state (after processing the last input symbol) what do we do ?
If one of the branch reaches the reject state before processing the complete input what do we do? Continue processing the other branches that might lead to accepting the input and terminate only the local branch? Or the input is rejected (similar to accept state)?


texts: How attributes helps us to allow column interchange in a relational database?

texts:
A relation on two sets $A$ and $B$ is defined as the subset of the cartesian product $$A\times B = \{(a,b),\ a \in A, b \in B\}$$
A database is also a relation and each entry is an ordered tuple respecting the cartesian product.
Now, interchanging the rows and the columns of a database does not change it. I can understand that a relation is just a set of tuples (called as row) so the order of elements in a set does not matter and hence row interchange will not pose a problem. But column interchange conflicts with the idea that a particular entry of the database is an ordered tuple.
So, attributes are used to tackle this problem. This is what I was told (verbatim):
Example table:
$$
\begin{array}{|r|r|}\hline
\text{Name}&\text{Roll No.}\\\hline
\text{Alex}&\text{2}\\\hline
\text{Fred}&5\\\hline
\text{Nate}&7\\\hline
\end{array}
$$
$\Rightarrow$ Fix a set $C$ also called the index set (here it can be $\{1,2\}$ or $\{\text{Name},\text{Roll No.}\}$)
$\Rightarrow$ Consider::$\{A_i|\ i\in C\}$, $A_i$ is the type of the attribute $i$ (here that is $A_1=\text{String}$ and $A_2=\text{Integer}$).
$\Rightarrow$  The cartesian product: $\prod_i A_i$ is seen as the collection of functions $$f : C \to \cup_i A_i$$ such that $f(i)\in A_i$
I was told that this definition of the cartesian product will allow us not to worry about the position of the column 'Name', etc. But I did not understand why. I would appreciate any kind of help and I apologize in advance for bad/incorrect formatting.


texts: (reference) Where can I learn more about I/O operations in OS?

texts:
I have basic understanding of file I/O. I know how to operate the read and write system calls in Linux. I know that there is blocking and non-blocking I/O. I want to know more about the underlying mechanism in OS for I/O. How is blocking and non-blocking I/O implemented? How do the kernel I/O buffers work? How big are they and when are they "erased"? For example if there is an open socket how much data will be kept in the kernel buffer before the data is overwritten?
I prefer a book of some kind. And please don't tell me to go and read the source. I konw that if I REALLY want to know how those things work that is the best I can do, but I simply am unable to dedicate so much time to this subject.


texts: Is there a grammar (not necessarily context-free) that generates $n^2$ zeroes?

texts:
My Introduction to Computation Theory professor talked about how we can write more general grammars (called unrestricted grammars) for languages that are not context-free. For example, the language: $\{0^{2^n} : n\geq0\}$ is not context-free, so it cannot be generated by a context-free grammar.

I am wondering if the language: $\{0^{n^2} : n\ge0\}$ is also not context-free, and what could be the grammar for it?

For this language, we would have to generate $n^2$ zeroes, which seems awkward and difficult to put into grammar form.


texts: Counting the number of N-dimensional coprime integer vectors

texts:
I am looking for an efficient way to count the number of coprime vectors in a finite and bounded set of integer vectors.

The vectors in my set are $N$-dimensional integer vectors whose components are bounded on the top and bottom by an arbitrary value $K$. Let $x = [x_1,x_2,\ldots,x_N]$ denote a vector from this set. Then $x$ is coprime if the greatest common denominator of all its elements is 1. That is, $\gcd(x_1,x_2,...,x_N)=1$.

Some 3-dimensional coprime vectors include: $x = [1,2, 3] , [6, 10, 15] ,[0, 1, 1]$
Some 3-dimensional non-coprime vectors include: $x = [2,4,6] ,[0, 10, 15] ,[0, 12, 12]$

For fixed $N$ and $K$, my set contains a total of $(2K+1)^N$ distinct integer vectors as each of the $N$ elements can take on integer values from $-K,\ldots,0,\ldots,K$.
A brute-force approach for counting the number of coprime vectors consists of iterating over each of the $(2K+1)^N$ possible vectors and checking to see whether they are coprime (using, for instance, this function). Unfortunately, this approach quickly runs into time and memory issues for large values of $N$ and $K$.

I am wondering if anyone can think of a way to smart algorithm to do this. Ideally, I am looking to implement this algorithm as a MATLAB function that can number of coprime pairs given $N$ and $K$ as its input.


texts: Parallelization of priority queue-based algorithms

texts:
There's a number of algorithms that operate by maintaining and consuming a priority queue of "events". I'm thinking primarily of geometric algorithms, particularly sweep-line algorithms like Bentley-Ottmann and Fortune's algorithm, but also things like Dijkstra's algorithm and Prim's algorithm.

There's no trivial way to parallelize these algorithms: In non-degenerate cases there's exactly one event which is legal to process. One could speculatively distribute the next n events to n processors, but (a) handling them in any interleaved order would generally violate the algorithm's invariants, and (b) would often add new events to the priority queue which should have been handled earlier.

Nevertheless, for things like sweep-line algorithms, there's a natural locality to exploit. Handling two events which are close to each other along the sweep axis but far away on the perpendicular axis would probably be okay as long as the underlying state structure could be concurrently updated, and one could imagine either speculatively handling those events and rolling back only when interactions were detected, and/or partitioning a prefix of the queue into mutually independent workloads.

Are there any articles which explore this sort of approach, either for specific problems or for paradigms like sweep-line algorithms?


texts: How to handle missing attribute's value with ID3 algorithm?

texts: i am working with ID3 algorithm, and i know that classic ID3 basically can handle missing data. But i am trying to code this algorithm, so what should i do if there is missing attribute's value in training dataset? How can i classify the data point that has missing attribute's value?


texts: Why do we do topological sorting to find shortest or longest path in weighted DAG?

texts:
I was wondering why do we need to do the topological sort before performing relaxing of edges.

Wouldn't it'd be better if we do :
if starting vertex is "s"

queue.add(s)
while(the queue is not empty)
 for every adjacent vertex v of u
   if( dist[v] > dist[u] + weight(u,v) )
       dist[v] = dist[u] + weight(u,v)
       add v to the queue

I had intentionally left out visited[] array


texts: If each pixel contains the channels for the 3 primary colours, why can a 1-bit picture only be presented in white and black?

texts:
I'm an igsce student. I'm taking computer science as an OL subject this year.
Pixels are the small squares which make an image. Inside each pixel there are 3 channels: one for blue, one for green, one for red. The three primary colours from which any other colour can be made. And that's how I imagine it:
When we say an image is 8-bits we actually mean that for each channel (in one pixel) of green, blue or red there are 8 bits. So green can have 255 shades/intensities/brightness and so on for the rest of the colours.
So even for a 1-bit image, each pixel contains 3 channels one for each of the primary colours. The only difference is that there's only 1 intensity/brightness/quantity for each colour.
So even in 1-bit image the three primary colours still exist so more colours other than black and white can be made by mixing the three colours together, 8 colours to be exact. Why is it said then that a 1-bit image is only black and white?


texts: What are the popular approaches to inexact attributed-subgraph matching?

texts:
Given two graphs $G_{1}(E_{G1},V_{G1})$ and $G_{2}(E_{G2},V_{G2})$, with scalar weights on the vertices, I would like to find a subgraph $H_{1}$ of $G_{1}$ that best matches some subgraph $H_{2}$ of $G_{2}$.  However, in most papers I've seen the weights are usually on the edges, $H_{1}$ is pre-specified and the matching being attempted was exact. I would be grateful if somebody could point me in the right direction.

Clarification edit: I'm looking for $H_1(E_{H1},V_{H1})\subset G1(E_{G1},V_{G1})$ and an injective function $f:V_{H1}\rightarrow V_{G2}$ so that $|\{(f(u),f(v))$ $\in$ $E_{G2}$ | $(u,v) \in E_{H1}\}| / |E_{H1}|$ is maximized while the sum of the node weight differences - $\sum_{v \in V_{H1}} |w(f(v))-w(v)|$ is minimized.


texts: What is the importance of disjoint edges in k-opt algorithms?

texts:
I'm trying to implement a k-opt algorithm and I'm bogged down on a detail: the importance of choosing disjoint edges.

My question: Is there any benefit to considering adjacent edges, or is the full power of the heuristic achieved when only disjoint edges are considered?

Wikipedia seems confused on this question. Its description of k-opt explicitly says "k mutually disjoint edges", but then it describes 2-opt and 2.5-opt as special cases of k-opt, and describes both those algorithms as processing adjacent edges. Is there something I'm not understanding here?


texts: How to avoid division by zero in UCT formula in Monte Carlo tree search?

texts: In step 2 (expansion) of the Monte Carlo tree search algorithm, one or more child nodes are created, and one node named C is chosen among them. The simulation step is applied to C giving it a score of 0/1 or 1/1. What happens to the other newly created leaf nodes? I assume they get a score of 0/0, which will not work very well with the UCT formula that decides which nodes to explore by maximizing wins / total simulations + some other stuff which will cause a division by zero when evaluating this expression. How is this reconciled?


texts: Given L1 and L2 in NP, if L1 transforms L2 and L2 transforms HC then L1 NP complete?

texts:
Why this Question is False ?

NP-complete problems are the hardest problems in NP.
if L is in NP-complete then [L must be in NP, all problems in NP can be transformed to L].

Does this mean that L2 is also NP-complete ?
and if so does this also mean that L1 is NP-complete by transitivity ?


texts: Common name for a group of commands which break the linear structure of the program

texts:
I'm looking for a name of a group of all commands which are break the linear structure of the program.

In C PL, they are: goto,return,break,continue. C++ also contains throw.

Perl has last,next,return.

Is there a common name for those groups of commands? Where can I read about those kind of commands?


texts:
I've been tasked with building a library of books on algorithms for our small company (about 15 people). The budget is more than 5k, but certainly less than 10k, so I can buy a fair number of books. All people here have at least a Bachelor's degree in CS or a closely related field, so while I will get some basic textbook like Cormen, I'm more interested in good books on advanced topics. (I will get Knuth's 4 volumes, BTW.)

Some list of topics would be:

Sorting algorithms
Graph algorithms
String algorithms
Randomized algorithms
Distributed algorithms
Combinatorial algorithms
etc.

Essentially I'm looking for good recommendations on books about major topics within CS related to algorithms and data structures. Especially stuff that goes beyond what's typically covered in algorithm and data structure classes as part of a Bachelor's degree at a good school. I know the question is quite fuzzy, since I'm looking for generically useful material. The software we develop is mostly system level stuff handling large amounts of data.

The ideal would also be to find anything that would cover fairly recent cool data structures and algorithms, which most people might not have heard about.

EDIT: Here are some preliminary books that I think I should get:

Introduction to Algorithms by Cormen et al.
Algorithm Design by Kleinberg, Tardos
The Art of Computer Programming Vol 1-4 by Knuth
Approximation Algorithms by Vazirani
The Design of Approximation Algorithms by Williamson, Shmoys
Randomized Algorithms by Motwani, Raghavan
Introduction to the Theory of Computation by Sipser
Computational Complexity by Arora, Barak
Computers and Intractability by Garey and Johnson
Combinatorial Optimization by Schrijver

A few other books my colleagues wanted that deal with techniques and algorithms for language design, compilers and formal methods are:

Types and Programming Languages by Pierce
Principles of Model Checking by Baier, Katoen
Compilers: Principles, Techniques, and Tools by Aho, Lam, Sethi, Ullman
The Compiler Design Handbook: Optimizations and Machine Code Generation, Second Edition by Srikant, Shankar
The Garbage Collection Handbook: The Art of Automatic Memory Management by Jones, Hosking, Moss


texts: Can I prove that $\sqrt n\log{\sqrt n}=\Theta(n)$?

texts:
I'd like to  prove that $\sqrt n\log{\sqrt n}=\Theta(n)$ but I'm not sure how to do it.

This is my attempt:
$$
\lim_{n \to \infty}\frac{\log{\sqrt n}}{\sqrt n}=0 \Rightarrow \log{\sqrt n}=o(\sqrt n) \text{(Little o)}
$$

Therefore:
$$
\sqrt n\log{\sqrt n}=o(\sqrt n\cdot \sqrt n)=o(n)
$$
But this is too much as I need theta.


texts: Concentration inequality of sum of geometric random variables taken to a power

texts:
Let $X_1, \cdots, X_n$ be $n$ independent geometric random variables with success probability parameter $p = 1/2$, where $X_i = j$ means it took $j$ trials to get the first success. Let $S_d = \sum_{i=1}^n X_i^d$ and $\mu_d = \mathbb{E}\left( S_d \right)$. Given $\delta > 0$, I am interested in finding an inequality of the form
$$\text{Pr} \left \lbrace S_d \geq (1 + \delta) \mu_d \right \rbrace \leq c \exp\left(-f(\delta) n^\alpha\right)$$
for some function $f$, some positive constant $c$, and $0 < \alpha \leq 1$, where I would like $\alpha$ to be as large as possible. In the case of $d = 1$, one can use a Chernoff-like approach to get a result with $\alpha = 1$. However, interestingly, the Chernoff-like approach does not appear to work for $d > 1$ because the moment generating function $M_{X_i^d}(s) = \exp(s X_i^d)$ does not appear to be finite.
In my approach for this problem, I let $\mathcal{E}$ be the event that $\forall i: X_i \leq b$ for some positive $b$ that has yet to be determined. Then we find that
\begin{align}
\text{Pr} \left \lbrace S_d \geq (1 + \delta) \mu_d \right\rbrace &= \text{Pr} \left \lbrace S_d \geq (1 + \delta) \mu_d | \mathcal{E}\right\rbrace  \underbrace{\text{Pr} \left \lbrace \mathcal{E}\right\rbrace}_{\leq 1}  + \underbrace{\text{Pr} \left \lbrace S_d \geq (1 + \delta) \mu_d | \mathcal{E}^c\right\rbrace}_{\leq 1}  \text{Pr} \left \lbrace \mathcal{E}^c \right\rbrace \\
&\leq \text{Pr} \left \lbrace S_d \geq (1 + \delta) \mu_d | \mathcal{E}\right\rbrace + \text{Pr} \left \lbrace \mathcal{E}^c \right\rbrace
\end{align}
I believe one can use Hoeffding to bound $\text{Pr} \left \lbrace S_d \geq (1 + \delta) \mu_d | \mathcal{E}\right\rbrace$ since the conditioning implies that each $X_i$ is a bounded random variable that takes values in $[1, b]$. $\text{Pr} \left \lbrace \mathcal{E}^c \right\rbrace$ can be found readily. With some work shown in a previous post here, we can choose $b$ such that we obtain a result with the desired form that has $\alpha = 1/(2d+1)$.
Unfortunately, this bound is loose in the sense that when $d = 1$, this approach obtains $\alpha = 1/3$ while the Chernoff-like approach gives $\alpha = 1$ in this case. Does anyone have any idea how to improve the concentration result for $d > 1$? Note that apparently for $d = 2$, the optimal result is $\alpha = 1/2$, though I do not know where to look to find the proof.
This problem has been on and off in the back of my mind for some time, so any insights would be great.


texts:
I have started learning lambda calculus from the book by Hindley and Seldin.

It brought up the concept with the function $x-y$, first as a function of $x$ and then as a function of $y$. In a way, it emphasized the difference between treating the expression as a function of $x$ and function of $y$, giving separate names to the functions.

$$f(x,y) =  x-y \qquad\text{and}\qquad g(y,x) = x -y$$
and, in $\lambda$ notion,
$$h = \lambda xy.x-y \qquad\text{and}\qquad g = \lambda yx. x-y\,.$$

If I am not wrong then it can be inferred that $f =\lambda x .(x-y)$ means that while computing the value of the expression the expression will vary only with  $x$ and similarly when $\lambda$ is placed with $x$ the other variable $y$ will be kept as a constant.

But then it said that this can be denoted as, with $h$ being the common name of the function
$$h = \lambda xy.(x-y)\qquad\text{and}\qquad h = \lambda yx.(x-y)\,.$$
Is it so that in the above expression the variable which is adjacent to $\lambda$ receives the value and the other one is constant?
The above function is called a two-place function; what does that mean?

Then he introduces the following function in $\lambda$ notation calling it a one-point function:
$$h^\star = \lambda x .(\lambda y . x−y)$$
and says that, for each number $a$, we have $h^\star(a)=\lambda y . a−y$.
Here $a$ is being provided as an argument but $\lambda$ is placed near $y$. Why is this?

And then it deduces that $(h^\star(a))(b)=(\lambda y . a−y)(b) = a−b = h(a,b)$ and says $h^\star$ can be viewed as "representing" $h$. Is "representing" a technical term? How was  $(\lambda y . a−y)(b) = a−b$ concluded?


texts: Finding a Good Estimate for Amount of Time Computers Spend Sorting Lists of What Lengths?

texts:
I have an assignment to envision and calculate the possible effects the implementation of a general sorting algorithm that is O(n) time and O(1) space ( assuming general case ) would have on computation and society.
In order to do that, I am trying to estimate how much computation time computers in server farms spend on sorting, and what general orders of magnitude the lengths of lists being sorted fall in.  Server farms seem to be the most impactful area to analyze for pertinent effects, but if there are some other areas that people would expect to see an outsize effect, I would appreciate them being called out.
I can then present sets of assumptions with the "new" algorithm being faster at sorting lists at such a length and larger and how much faster than the current state of the art.  eg. "If the new algorithm is even with the state of the art for lists of 500 billion items, and increases in time with "n" while the soa increases in time with "log n", and 1/2 trillion item and larger sorts take X% of server-farm computation, you could expect to see computation time for the same tasks reduced by order of magnitude Y%".  Once I can get some firm numbers ( not the question here ) on how much electricity server farms use, then I can also electricity usage cost comparisons.
When I researched on the web, I found that an O(n)/O(1) sorting algorithm is considered theoretically possible, but undiscovered to this point.  I suspect that there might not be much impact on computation, because there seems to be no incentives put out for someone to come up with such an algorithm ( or a proof that it cannot exist ).
What is a the fastest sorting algorithm for an array of integers?
https://en.wikipedia.org/wiki/Sorting_algorithm
http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap09.htm#:~:text=We%20have%20now%20introduced%20several,quicksort%20achieves%20it%20on%20average
I have presumed that sorting algorithms in general use, at least for large lists like web search results, are O(n log n) time and O(1) space as a general matter of course.  If this is in error, please point it out!
My apologies if this forum is not appropriate for this kind of question.  In that case, I would ask for pointers on where I should go with this question.
Thank you.


texts: How many "compressible" strings are there?

texts:
Let's say that a string of length $N$ is "compressible" iff its Kolmogorov complexity is less than $N$. To keep it simple, we can assume binary strings for this.

It is easy to see that almost all binary strings of length $N$ are incompressible by using the pigeonhole principle.

So my question is, how many strings of length $N$ are compressible?

In particular, let's assume that $K(S)$ is the Kolmogorov complexity of binary string $S$, which is of length $N$. Then I have the following three questions:

Of the $2^N$ binary strings $S$ of length $N$, how many have $K(S) \leq N-1$?
Of the $2^N$ binary strings $S$ of length $N$, how many have $K(S) \leq N/2$?
Of the $2^N$ binary strings $S$ of length $N$, how many have $K(S) \leq \log N$?

All of the above are for sufficiently large $N$.


texts: What is the implication of NP-completeness if P=NP?

texts:
If a certain problem $X$ is NP-complete and $P\neq NP$, then $X$ is not polynomial. But we still don't know that $P\neq NP$, so in theory $X$ may be polynomial. Does the fact that $X$ is NP-complete say anything about it being more difficult than other polynomial problems? In particular:

Does it mean that $X$ cannot be solved in linear time? (alternatively, are there NP-complete problems that can be solved in linear time if $P=NP$)?
Does it mean that $X$ cannot be solved in quadratic time? (alternatively, are there NP-complete problems that can be solved in quadratic time if $P=NP$)?
If $X$ is NP-complete, and I prove a lower bound of $\Omega(n^2)$ on the run time of $X$ (a lower bound that does not depend on whether $P=NP$), did I prove anything new?


texts: Complexity Theory - Why can't you use diagonalization to seperate classes A and B when an orcale O exists under which A=B?

texts:
In a recent lecture the professor stated that given two complexity classes A and B, and given the existance of an oracle O such that $$A^o=B^o$$
(As I understand, meaning that a problem in A with can be reduced to a problem in B with the oracle O), It can be shown that classes A and B can not be seperated using a diagonilization argument.

Unfortunately he did not explain much further... Can someone give the outline\thought process of the general proof (informally)? I think I understand why diagonalization fails in specific time hirearchy proof constructions (due to the existence of a cook reduction) but I can not see how to generlize this in a satisfactory way.

Thank you.


texts: Determinant computation is equivalent to matrix powering

texts:
It has been claimed in this paper (page 2 last paragraph) that Matrix powering is equivalent to determinant computation.

https://www.cse.iitk.ac.in/users/manindra/algebra/depth-four.pdf

Does anybody why is this the case?


texts: Can bottom-up architectures be effectively programmed in top-down paradigms?

texts:
The subsumption architecture, proposed by Rodney Brooks in 1986, is a "bottom-up" approach, in which robots are designed using simple hierarchical models.  These models build upon and subsume the lower modules to form a final product.  For example, a robot can be given a "find opening" module which is subsumed by a more abstract "find doorway" module, which is then itself subsumed by an "exit the playing field" module.

Now, obviously, in a more "object-oriented" design, we could have started the design with the "exit the playing field module", but for sake of argument, assume some of the more primitive components (as "functions") will likely get reused in other higher concepts.

Realizing that implementing this robot in a procedural language (or a functional one, for that matter) could be the simplest, but is it counterproductive to try to conceive of a subsumption architecture-based robot in an object-oriented programming paradigm? (realizing also that it's perhaps difficult to weigh a software engineering paradigm against a robotics one)  To obtain a solution, is there some form of "adapter" that can be implemented for increasing the effectiveness of using what may be two conflicting paradigms?


texts:
I am studying the maximum/minimum flow question, and was given the following problem:

  A traveling agency has $n$ destinations on their service map, and it intends to maintain them with minimum amount of vehicles. Say a transit $i$ starts at ${s_{i}}$ and ends at $e_i$, and then for that transit, it needs another $ret_{ij}$ to return back to $j$ from destination $i$.

How can this transit schedule problem solved by using flow networks?


texts: Find maximum distance between elements given constraints on some

texts:
I have a list of numbered elements 1 to N that fit into positions on a number line starting with 1. I also have constraints for these elements:

The element 1 is in position 1, and element N must be at a position >= the position of element N-1. (i.e. element 2 could be at position 1, element 3 at position 7, and element 4 at position 8 (but not position 5))
Some elements must be within a certain distance from each other on the line.
Some elements must be at least a certain distance from other on the line.

My objective is to return an integer that represents the maximum span between element 1 and element N. If no lineup is possible, return -1, and if the elements can be any distance apart, return -2.

I am given:

The number of elements
A withinArray[][] where withinArray[x][y] = the distance elements x and y must be within on the line. Any zero values represent no constraints.
An atLeastArray[][] where atLeastArray[x][y] = the distance elements x and y must be apart on the line. Any zero values represent no constraints.

An example input would be: 4 elements, withinArray1[3] = 10, withinArray[2][4] = 20, and atLeastArray[2][3] = 3. (all other array values are zero).

The return value for this input would be 27. (element 1 at position 1, element 2 at position 8, element 3 at position 11, and element 4 at position 28)

The problem was first posted here by someone else. I'd like to figure out an elegant solution to it programmatically. Though I've been working on it for a whole day, I still have no luck coming up with a good solution. I feel that I need to use dynamic programming techniques, but have a hard time finding a good substructure.

I am not able to locate the same example on the web. Any pointer to such materials online would be appreciated. It's even better if you are an expert for such kind of question and can outline the solution in detail. Executable code is a plus.


texts: What's flawed about the "save-the-input" method of reversible computing?

texts:
I'm an undergraduate just beginning to read about reversible computing. I know that, because of Landauer's principle, irreversible computations dissipate heat (and reversible ones do not). I brought it up with my professor, who had never heard of reversible computing before, and he was having difficulty understanding why the theory of reversible computing was not trivial.

His point was just that you can always save the input, i.e. for any function $f: \{ 0, 1 \}^n \rightarrow \{ 0, 1 \}^n$ that you wish to make reversible, define a new function $f_{reversible}: \{ 0, 1 \}^n \rightarrow \{0, 1 \}^{2n}$ (or $\{ 0, 1 \}^{2n} \rightarrow \{0, 1 \}^{2n}$ and you just put $0$s in for the last $n$ bits of the input) which returns the output in the first $n$ bits and the input in the other $n$ bits. Then in order to invert $f_{reversible}$ you just discard the output and return the input that you saved.

My immediate objection was that this takes more memory than the original function did -- though only by a constant factor. Constraining the output to $n$ bits would seem to restore the interesting-ness of the problem, though. Is this what is usually meant by reversible computing?

Another objection seemed to be that when we discard the output, we're doing something irreversible which is going to dissipate heat. But we correctly recovered the initial state, so how could it be irreversible? I don't know enough physics to understand whether the important thing w/r/t heat is just for the entire computation to be reversible, or whether every step needs to be reversible as well, or if this idea is just up the wrong tree.


texts: Are Context Sensitive Languages Turing Complete?

texts:
Related questions:

Can regular languages be Turing complete?
Why are Linearly Bounded Turing Machines more powerful than Finite State Automata?
https://stackoverflow.com/questions/14589346/is-c-context-free-or-context-sensitive
https://softwareengineering.stackexchange.com/questions/132385/what-makes-a-language-turing-complete


texts:
Suppose a language $L$ has a non-adaptive PCP verifier which uses at most $r(n)$ random coins, and queries at most $q(n)$ locations of the proof, on inputs of length $n$. How can we show that there is a PCP verifier $V'$ for $L$ that uses proofs of length at most $2^{r(n)}q(n)$?
I understand that the verifier can query at most $2^{r(n)}q(n)$ locations of the proof. How does the verifier 'know' a map from these queried locations to $\{1, 2, \dots, 2^{r(n)}q(n)\}$? For example, I think an interesting case is when $r(n)=n, q(n) = O(1)$.


texts: How to prove this language is not regular (via Fooling Set)

texts:
By using this fooling set, I am able to prove that the concatenation of bz is in the language L, but I still need to prove that az is not in the language to complete the proof.

This is also the point that the ceiling function is very tricky to deal with. It is also where I am lost.

Any hints and suggestions will be appreciated!


texts: Why is And-Or-Graph-Search called a search algorithm?

texts:
An algorithm in Artificial Intelligence: A Modern Approach for planning in stochastic, fully observable environments is called And-Or-Graph-Search, implying that it's a search algorithm. However, I don't see how it is one. Wikipedia defines search algorithms as, "an algorithm for finding an item with specified properties among a collection of items," but And-Or-Graph-Search doesn't do that. It instead finds multiple items (goals states) in order to guarantee it will reach a goal state no matter what the results of its stochastic actions are.

So, why is it a search algorithm?

Here's its pseudo-code:

function AndOrGraphSearch(problem) returns a conditional plan, or failure
    OrSearch(problem.initialState, problem, [])
function OrSearch(state, problem, path) returns a conditional plan, or failure
    if problem.GoalTest(state) then return the empty plan
    if state is on path then return failure
    for each action in problem.Actions(state) do
        plan = AndSearch(Results(state, action), problem, [state | path])
        if plan does not = failure then return [action | plan]
    return failure

function AndSearch(states, problem, path) return a conditional plan, or failure
    for each si in states do
        plani = OrSearch(si, problem, path)
        if plan = failure then return failure
    return [if si then plani else if s2 then plan2 else . . . if sn-1 then plann-1 else plann]

AndOrSearch is an algorithm for searching And-Or graphs generated by nondeterministic environments. It returns a conditional plan that reaches a goal state in all circumstances. (The notation [x|l] refers to the list formed by adding the object x to the front of list l.)

The function is from the book Artificial Intelligence: A Modern Approach.


texts: Unrolling closures into SAT boolean formula

texts:
I need to verify some assertions about the minimalist Turing-complete language Jot.

Many of the assertions I want to investigate are semi-deciable (co-recursively enumerable). So far it's been fairly straightforward to literally enumerate every Jot program via its Goedel number and testing the assertion's complement by running a Jot program with a given space/time bound.

This works great for small programs (< ~40 bits) and has allowed me to find the shortest known representations of several standard simple functions from lambda calculus.

SUCC = J(18400)
CHURCH_0 = J(154)
CHURCH_1 = J(0)
CHURCH_2 = J(588826)
IS_ZERO = J(5)
MUL = J(280)
EXP = J(18108)
S = J(8)
K = J(4)
AND_2 = J(16)
AND_3 = J(139248)
OR_2 = J(9050)

However, this is particularly inefficient for larger functions and I'd like to speed up searches using a SAT solver. To do this requires unrolling the recursion of a Jot program J(n) to a predefined hard cut-off depth as a boolean formula.

Technically the formula isn't of polynomial length, but is still practically useful due to the small constants in program length and an already known existing polynomial number of beta reductions in an equivalent (but verbose) implementation of the target J(n).

I'm used to encoding problems in SAT formulae, however the new issue for me is understanding how to encode closures (nested functions) in an efficient manner.

None of the standard tools for bounded model checking that I know of allow nested anonymous functions, so I haven't been able to study any existing encoding methods. I would greatly appreciate any hints about how to encode these closures.

Here's the Jot interpreter written in Python which I'm trying to unroll into a boolean formula:

def S(x): return lambda y: lambda z: x(z)(y(z))
def K(x): return lambda y: x
def X(x): return x(S)(K)
def B(x): return lambda y: lambda z: x(y(z))
def I(x): return x
def J(n): return (B if n & 1 else X)(J(n >> 1)) if n else I


texts: Does "in-place" for $n$ items imply space dominated by $n$?

texts:
Does the characterisation of an algorithm for $n$ items as in-place imply space ∊ $ο(n)$

formally
informally ("among coders")?


texts:
I am studying the proof of the following theorem:

Given the language

$\mathit{REGULAR}_\mathit{TM} = \{\langle M \rangle | M $ is a turing machine and $\mathit{Accept}(M)$ is regular$\}$

$\mathit{REGULAR}_\mathit{TM}$ is undecidable.

The proof given in Sipser shows that if we already have a machine $R$ that decides $\mathit{REGULAR}_\mathit{TM}$ then we can make a machine $S$ that decides the halting problem:

$$\mathit{Accept}_\mathit{TM} = \{\langle M, w \rangle | M \mbox{ is a turing machine and }w \in \mathit{Accept}(M) \}$$

I am having trouble understanding the proof. Here's how I understand it:

When $M$ (any turing machine) and $w$ (any string) is fed to the machine $S$, we construct a machine $M_2$ that takes a string $x$ as input, but first runs machine $M$ on $w$. First case, if $w$ $\in $$\mathit{Accept}(M)$, then $M_2$ simply accepts x. That is $\mathit{Accept}(M_2) = \sum^*$ in this case - i.e a regular language. Otherwise, second case, $M$ rejects $w$, then $M_2$ checks if the input $x$ is of the form $0^n1^n$, and accepts if it is so - i.e $ \mathit{Accept}(M_2) $ is not a regular language. Inside $S$, for both these cases if we run $R$ on $M_2$ returns the appropriate result which $S$ can directly return.

The case I am confused about, the third case, is when $M$ does not halt on $w$. Then $\mathit{Accept}(M_2) = \{\}$, which is a regular language, and $R$ will therefore return ACCEPT, which $S$ cannot directly return as $w \notin \mathit{Accept}(M)$. But the description of the solution sounds to me like $S$ returns ACCEPT even in this case(pseudocode below). So what am I doing wrong? There's probably a very basic idea I am missing. Here's the pseudo-code for the machine $S$, and inside $S$, as you can see, there's the machine $M_2$ that $S$ creates.

machine S(M, w):
    // Construct an instance of machine M2 which uses M and w
    machine M2(x):
        r := M(w)  // Might hang here
        if r == ACCEPT:
            return ACCEPT
        else:
            if x is of form 0^n.1^n:
                return ACCEPT
            else:
                return REJECT

    // Run R on M2 (always returns, never hangs)
    r1 = R(M2)
    if r1 == ACCEPT:
        return ACCEPT
    else:
        return REJECT


texts: What is the expressive power of finite-state transducers and pushdown transducers?

texts:
One would assume that a finite state transducer can perform any translation such that the resulting string is from a regular grammar. Similarly, that a pushdown transducer can generate strings from CFG grammars.

I am, however, unsure about this because we can construct a finite state transducer which translates a string of the form $ab$ to $\{ a^n b^n : n \ge 1 \}$, which is irregular.

Is this the case? If so, can anyone provide the relevant literature?


texts: What are the treatises on how to build mechanical computers?

texts:
I've just watched this replica of the Antikythera mechanism. I've heard also about Babagge's analytical machine and the Curta calculator. I got curious: What did they use to build computers made of gears? We have nowadays some treatises to make logic gates with transistors, how did they manage to build logic gates or to do whatever was needed for building their computers?

I'm not sure if this question really fits this forum, but it was the nearest one I could think about.


texts: TM recognizing $0^n1^n$ requires Ω(log n) space

texts:
I am trying to prove that any deterministic 1-tape Turing Machine which recognizes the language $L = \lbrace{0^n1^n | n \geq 0 \rbrace}$ requires
$\Omega(\text{log }n)$ space.

I believe this can be done using a crossing sequence argument.
I have been trying to imitate the $DSPACE(O(1)) = REG$ proof from wikipedia.

What I have tried is:

Suppose $L \in DSPACE(S(n))$, for some $S(n) = o(\text{log } n)$ and let $M$ be an $S(n)$ space bounded TM recognizing $L$.
Since $L$ is not regular, $L \notin DSPACE(O(1))$. Therefore, given $k \in \mathbb{N}$, let $x \in L$ be a string of minimal length that requires more than $k$ worktape cells.

Let $C$ be the set of configurations of  $M$ on $x$. That is, $C$ is the set of tuples of the form

(state, work tape head position, work tape contents).

Then $|C| \leq |Q_M| \times S(n) \times 2^{S(n)} \leq 2^{cS(n)} = o(n)$, where $c$ is some suitable constant.

The crossing sequence at $i^{\text{th}}$ cell boundary is the sequence of such configurations  occurring as the input head moves across that boundary.
Each term of a crossing sequence can be any of the $|C|$ elements from $C$.

Also, length of any crossing sequence cannot be more than $|C|$; for otherwise, some configuration will repeat and $M$ will enter into an infinte loop.

Therefore,
number of crossing sequences of $M$ on $x$ $\leq |C|^{|C|} \leq 2^{cS(n)2^{cS(n)}} $.

The problem is that this doesn't give the required bound. So, a cleverer argumet is needed.


texts: Equivalent definition of minimal spanning tree

texts:
Prove that $T$ is MST $\Leftrightarrow$  for any edge $uv \notin T$, $uv$ has the maximal weight on the cycle created by adding $uv$ to $T$.

It's my attempt to prove $\Rightarrow$:
Consider the cycle $path(v, u) \in T \cup E(v, u)$. If $(v, u)$ is not maximal, replace the maximal edge on the path by $(v, u)$. T is still connected, and we got spanning tree which weight is less than $w(T)$.

But I am stuck with the direction of "$\Leftarrow$".


texts:
I got a problem related to graph theory -

Consider an undirected graph ܩ where self-loops are not allowed. The vertex set of G is
{(i,j):1<=i,j <=12}. There is an edge between (a, b) and (c, d) if |a-c|<=1 and |b-d|<=1
The number of edges in this graph is

Answer is given as 506
but I am calculating it as 600, please see attachment.

I am unable to get why it is coming as 506 instead of 600.

Thanks


texts: Looking for references for real-world scenarios of data-poisoning attack on labels while doing supervised learning

texts:
Consider the following mathematical model of training a neural net : Suppose $f_{w} : \mathbb{R}^n \rightarrow \mathbb{R}$ is a neural net whose weights are $w$. Suppose during the training the adversary is sampling $x \sim {\cal D}$ from some distribution ${\cal D}$ on $\mathbb{R}^n$ and sending in training data of the form $(x, \theta(x) + f_{w^*}(x))$ i.e the adversary is corrupting the true labels generated by $f_{w^*}$ (for some fixed $w^*$) by adding a real number to it.
Now suppose we want to have an algorithm which will use such corrupted training data as above and try to get as close to $w*$ as possible i.e  despite getting data corrupted the above way the algorithm is trying to minimize (over $w$) the "original risk" $\mathbb{E}_{x \sim {\cal D}} \left [ \frac{1}{2} \left ( f_w (x) - f_{w*}(x) \right )^2 \right ]$ as best as possible.

Is there a real life deep-learning application which comes close to the above framework or can motivate the above algorithmic aim?


texts: To build a special unary regular expression

texts:
Say that there's a prime number P,
And we can easily build an unary regular expression [E0]for every number that is divisible by P:
E0::= (aaaa...a)*,with p "a",

The question is, how do we build the opposite unary regular expression [E1], for every number that isn't divisible by P?

Do I need to build the E1 by listing all the number mod p=1,2, to p-1, or there can be a easier way to build it ?


texts: Advantages and disadvantages of microcoded vs hardcoded architectures

texts:
Preamble
I can't understand what are the advantages and disadvantages of microcoded processor architecture and hardcoded one.
Basically what I understood is that a microcode architecture divides an istruction in more microinstructions. I didn't found much documentation written in a simple way (too much complicated) so I'm asking you: what are the advantages and disadvantages of each one?
Due to the large amount of aspect of this "subject", I'll recap the question into three main aspects:
Question (architectural point of view)
A microcoded architecture should semplify the design of each instruction, it means that it's do much more difficoult to design a full hard coded processor?
Or maybe hardcoded archtecture is suitable for microcontrollers or smaller design?
Question (performance point of view)
Wikipedia (not the most reliable source, I know) says that a microcoded architecture is a little slower than an hardcoded one. It also says that microinstruction are used to build complex instruction, but these are not commonly used because programmers prefer high level languages, and compilers prefer using simpler but faster instruction.
From this point of view, is still necessary to design microcoded processor?
Question (functional point of view)
If microcoded archtectures help the creation of complex instruction (= easier assembly development?), hardcoded ones help programmers in any way during their work? This seems a stupid question but I think it's not.
Looking at this site of assembly game programmers (I hope I can post that link, FAQ says to share your research), one guy says that HuC6280 processor has the best instruction set because:

Fav[ourite]: HuC6280.  Basically a 65CS02 set (Rockwell's added instructions). Optimizing is soo much fun. There are some super crazy optimizations for this style chip out there. I know people will fight to the death (or possibly argue) that it's not RISC, but it definitely had some precusor ideas of RISC. A very small, simple, but fast instruction set (hard coded, not microcoded), a large set of 128 16bit address registers (also halved as 256 8bit data registers). The immediate operand instructions are very fast and lend themselves perfectly for self modifying code. The downside is the small logical address range of the PC. All optimizations have to be made local and very specific. Look up tables (LUTs) need to be organized accordingly (and interleaved for 16bit and wider data elements).  One thing I never understood is why they never implemented immediate operand opcodes as 1 cycle instead of 2, since the chip would perform a fetch cycle while operating an ALU operation on other opcodes. Same for implied instructions (flag changing).

He seems to be very excited about that architecture. One point to hardcoded design?
However, I found that HuC6280 is an 8bit processor, it is much much simplier than modern ones. It means that hardcoded would be preferrable if its design wasn't so hard? EDIT: He also quote self modifying code, which is not commonly used today (due to high level programming maybe) but for assembly programmer is quite an important feature.
Examples
I know that this is an hard question, explanation might be long. If you (guy with much more experience than me) want to answer, may you add some example of hardcoded architecture? It would be much appreciated. Both modern and deprecated are ok
And thanks for reading all this poem


texts: What is the difference between a TM accepting and deciding a language?

texts:
Frankly I'm very uncomfortable with the material right now. There are some things I can understand, but many I still do not.

My first assignment is asking me in one question (which I do know how to do) to give a full description of a TM that accepts a language $L = \{ x \in \{0,1\}^* \mid x \text{ is divisible by } 4 \}$.  I know that any binary string ending with $00$ is divisible by 4, so $\{00,100,1100,1000,11100,11000,10100,10000,\dots\}$ is the language that this TM accepts.

But on the topic of (un)decidability:  I know that a language is decidable if there exists a TM that accepts all strings in, and only strings from that language — and that same TM rejects all strings and only strings not in that language.

Which leads to the question:  What is the difference between a Turing machine accepting and deciding a language?


texts: I have the language $L = \{ \langle M_1, M_2 \rangle : L(M_1) \subset L(M_2)\}$ and I'd like to prove that it is not Semidecidable. To do so, I need to use a reduction from $\neg H$. I cannot use Rice's theorem. I'm having a hard time with this, and would appreciate a walkthrough.


texts: Can the difference of a non-regular and a regular language be regular?

texts:
I have some trouble understanding some exercises related to operations on regular languages.I tried to apply their closure properties, but I am not sure how to do the following exercises:

If $L_2,L_3$ are regular and $L_1 \setminus L_2 = L_3$, is $L_1$ also regular?
If $L_2,L_3$ are regular and $L_1 \cap \overline{L_2} = L_3$, is $L_1$ also regular?


texts: When is splitting a collection coins two ways NP-complete?

texts:
Suppose we have a set $D$ of denominations of coins and a our input is a "tip jar" containing some finite number of these coins (e.g., five nickels, a dime and three quarters).  In the first two problems, we want to know whether it is possible to divide the money in the jar equally between two people; in the third one, we're satisfied if the money can be divided almost equally.  What is the complexity of these problems?

$D = \{1, 2, 4, 8, \dots\}$.
$D = \{1, 2, 3, 4, \dots\}$.
$D = \{1, 2, 3, 4, \dots\}$ but we only require the two people to be given amounts $x$ and $y$, respectively, satisfying $|x-y|< 10$.

My main question is what sets $D$ lead to the problem being in P and what makes it NP-complete.


texts: Prove that $L^{\nsubseteq}_{M'}=\{ \langle M \rangle \ | \ L(M) \nsubseteq L(M')\}$ with $M'$ a TM that always halt is undecidable

texts: I've done some other problems by reduction, but I'm quite stuck here. I'm not really sure what to do with $M'$. I know that because $L(M) \nsubseteq L(M')$ there exists $w \in L(M)$ and $w \notin L(M')$ and I'm trying to create the  machine that ignores the input and accepts only when M accepts $w$, but I'm kinda stuck on what to do next. Any suggestions?


texts: $\text{MOD}_{2017}(x_1, \ldots, x_k)$ computable by bounded depth polynomial size circuit in basis $\{\neg, \text{MAJ}\}$?

texts:
Now, I have the following conjecture.

  $\text{MOD}_{2017}(x_1, \ldots, x_k)$ is computable by a bounded depth polynomial size circuit in the basis $\{\neg, \text{MAJ}\}$.

However, I am at a loss at how to realize/see this. Could anybody help me out?


texts: For AVL trees, how do we know if a RL or a LR rotation is needed?

texts:
Suppose I am trying to construct a simple AVL tree:

Upon inserting 'B' the tree becomes imbalanced. How do I exactly know that I need a LR or RL rotation without making any guesses?

From what I heard is that if you insert at right side of tree and it becomes imbalanced then you need a LR rotation and vice-versa. I want to make sure that it is true.


texts:
How to construct a single-tape Turing Machine which writes the number 7 in UNARY number system, leaving the tape with a delimiter symbol followed by 7 1s?

So outout would be a tape contains #111111 and blank symbols afterward.


texts: What are some good hints for proving non-regularity with the pumping lemma?

texts:
My CS Theory Professor said that when proving that a language is not regular by the Pumping Lemma, that there are some 'tricks' for solving languages more complicated that something like $L = \{a^{n} b^{n}\mid n \in\mathbb{N}\}$. Although I know that these come with practice, I wondered if this community would have some input on the matter?

If you don't quite know what I am asking, think to calculus, when your professor used something that HE knew would get you from point a to point b that if YOU don't know, you cannot solve the problem.


texts: Is there any base representation that produces a non-regular language for set S?

texts:
To clarify, by base representation I mean binary representation (ie. 101 = 5), ternary representation, etc.

Given the set $S$ of natural numbers such that $S = \{2^i| i \in \mathbb{N}\}$ prove that for some base representation of set $S$, the resulting language is not regular.

I have tried but I can't seem to figure out how to prove this. I figure that base 3 would probably result in a nonregular language, but then how would I prove it?


texts: Neighbourhood in local search metaheuristic

texts:
I cannot seem to find an answer to this question with Google, so I am  going to ask here: is it required for a good neighbourhood function that it in principle (i. e. by recursively considering all neighbours of a certain solution - which is not practical) can reach all possible solutions?

My question is whether there are references in literature that explicitely state it's a requirement - I can see that it is a good property of a neighbourhood.


texts: If XOR of n distinct numbers is ANDed over one of the number, the result would be zero

texts:
Say we Have n distinct numbers

x1,x2,....xn

And we xor the result

xoredResult = x1^x2...^xn

And if we AND(&) with one of the number say x2
We get Zero

xoredResult & x2 = 0

Can we always claim that if the ANDed result is zero that the number is repeated ?
Can this be used to find the first repeated element in a stream of numbers ?


texts: Is a computer equivalent to a Turing machine or linear bounded automata?

texts:
Till date I have read that a Turing machine can do whatever a computer can.

Wikipedia Turing machine

mentions that since a real machine can have only a finite number of configurations it is equivalent to linear bounded automata.

Is this true?


texts:
Can we construct reduction from $k$-sum to $l$-clique or vice versa where $k$ and $l$ are some fixed integers?

That is given two parametrized problems whose unparametrized version is $NP$-complete when can we construct reductions between them?

In general NP complete problems the reductions are polynomial time.

What is the corresponding analogue in parametrized problems?


texts: How to sort a large list of elements where everything is sorted but k elements?

texts: Assuming the list is very large, and $k$ is very small, what's the fastest algorithm to sort this list?


texts: How can one measure the time dependency of an RNN?

texts:
Most of the discussion about RNN and LSTM alludes to the varying ability of different RNNs to capture "long term dependency". However, most demonstrations use generated text to show the absence of long term dependency for vanilla RNN.
Is there any way to explicitly measure the time dependency of a given trained RNN, much like ACF and PACF of a given ARMA time series?
I am currently trying to look at the (Frobenius norm of) gradients of memories $s_k$ against input $x_l$, where $l\le k$, summed over training examples $\{x^i\}_{i=1}^N$ - $$\text{Dep}(k,l):=\sum_{i=1}^N \big\|\frac{\partial s_k}{\partial x_l}(x^i)\big\|_F$$ I would like to know if there are more refined or widely-used alternatives to this prototype.
I am working with time series so I treat the inputs $\{x_t\}$ as realization of a random process $\{X_t\}$, thus by "current" I mean $x_i,s_i$ for some fixed $i$, "the past" I mean $\{x_j\}_{j=1}^{i-1},\{s_j\}_{j=1}^{i-1}$ and "time" I mean the index $t$.
I guess that the "long-term dependency" in literature refers to the sensitivity of the current memory $s_k$ w.r.t. past inputs $\{x_j\}_{j=1}^{k-1}$, hence the prototype I formulated.


texts: How do I use message passing to find the maximum of all values in a grid?

texts:
I am working on a problem. I have been tracing much more simple problems by hand, but I got this one and I am truly at a loss. I do not know how to research this to help me figure it out. I am truly at a loss as to how to begin writing the message passing code to solve this. Any help on knowing how to break this problem down would be greatly appreciated.

The question is as follows:

  Suppose $N^2$ processes are arranged in an $N$ by $N$ square grid. $P_{i j}$ refers to at the grid position (row $i$, column $j$). A process can communicate, using message passing, only with its neighbors to the left and right, and above and below. (Processes on the corners have only two neighbors; others on the edges of the grid have three neighbors.) Every process has a local integer value $v_{i j}$.
  Show an efficient computation scheme at each of the nodes that will eventually result in every process knowing the maximum of all values in the grid.


texts:
As an example of languages that are in P/poly is the UHALT Problem :

  UHALT = { 1^n: n's binary expansion encodes a pair  such that M halts on input x}

We can create a boolean circuit of just AND gates.
However, we can create it only for a fixed 'n', not for all n's ...

My question is : when we consider a language like the UHALD problem, do we consider all of the 'n' possible values ,ie for every 'n' we have a different language? or for every n we have a different language ?

In Turing-machines, i think we can loop, but in boolean circuits.. i dont think we can, thus the impossibility (in my point of view) of making, for example, a circuit for the UHALT problem for every n there is.


texts: Column Generation - Worst dual bound when adding various columns per iteration

texts:
I'm implementing a Column Generation algorithm. The pricing problem, in general, find more than one column with negative reduced costs(the master is a min problem). If i add only the most negative reduced cost column per iteration, at the end i have a linear relaxation with $Z = 8240.3$. When i tried adding all the columns found in the pricing problem, in the end i have found a linear relaxation with $Z = 8166.668$.

That doesn't seem possible. Anyone have any clues on why this is happening?

Thanks in advance


texts: Looking for an algorithm to iterate over essentially different solutions

texts:
I'll explain my problem with an analogy to Sudoku-grids.

Consider a filled Sudoku-grid. If you exchange labels or rearrange rows/columns within a block, you have another valid Sudoku-grid. However the new grid is essentially equivalent, if that makes sense. One might say, under the operations "swap rows", "exchange labels" etc., both grids are in the same orbit. (https://en.wikipedia.org/wiki/Mathematics_of_Sudoku#Enumerating_essentially_different_Sudoku_solutions)

I want to iterate over all grids, but in a way that the algorithm ignores other solutions in the same orbit. However, this question is not about Sudoku grids! My grids have a different structure, which is a bit simpler:

I want to fill a 4x6 table with the integers 1 to 8 (each three times) such that each row contains each integer at most once. There are a few other more complex conditions, but I think it's easier to check them later after a solution has been generated.

Just like in the Sudoku analogy, there are a few operations that generate other essentially equivalent solutions:

1) Rearranging rows: if one row is

1 3 5 6 2 8

the solution with that row replaced by

1 2 3 5 6 8

is of course also valid and consindered essentially equivalent.

2) Swapping rows.

3) Exchanging labels.

E.g. these solutions are essentially equivalent

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

First row rearranged:
1 2 3 5 6 8
4 1 5 7 8 2
4 7 6 1 2 3
3 4 5 6 8 7

First two rows swapped:
4 1 5 7 8 2
1 3 5 6 2 8
4 7 6 1 2 3
3 4 5 6 8 7

All 1's and 2's exchanged
2 3 5 6 1 8
4 2 5 7 8 1
4 7 6 2 1 3
3 4 5 6 8 7

My question is what an efficient (both runtime and memory) algorithm to generate these solutions might be.

The naive approach would be to store all previous solutions and check whether an equivalent solution has already been found. However, this is expensive in both runtime and memory!

I managed to improve this by calculating a hash of each solution in such a way that equivalent solutions generate the same hash. Then we can store the solutions in a map, so that we need to check fewer solutions and thus reduce the runtime. However, the memory cost is still huge.

If the hash has the property that different solutions yield different hashes, then I would only need to store the hashes and reduce the required memory by a large factor.

Can you think of a more elegant algorithm that does not store hashes nor previous solutions?

EDIT:

I simplified my problem too much without realising that I reduced the number of orbits to 1. (Thanks @Klaus Draeger). In fact the numbers 4,6,8 and 3 were made up as an example. I thought I could adapt the algorithm to the more general case later.
Actually, my problem is a bit more complex: The number of rows is variable and rows need not have the same length, so rule 2) only applies to rows of equal length. Also the frequency of the numbers is not necessarily constant (e.g numbers 1,2,3,4 might appear four times and 5,6,7,8 three times or whatever), so rule 3) only applies to labels with the same frequency.

EDIT2:

And this is the more complex condition, that I thought doesn't matter for now. Maybe I'm wrong again...

If, in one row, y appears directly to the right of x (or y is in the first column and x in the last), then in a (unique) different row there must be an x to the right of y (above example does not satisfy this). This means that rule 1) only applies to rotations of rows and not any permutation.

I think this can be dealt with at a later point.


texts: Can a second-order busy beaver function/turing machine be programmed?

texts: I have seen a computer program at https://github.com/pkrumins/busy-beaver/blob/master/busy-beaver.py that computes Busy Beaver numbers (well, pretends to). It has busy beaver numbers up to 4, and I am wondering if it is possible (reasonably) for a programmer to add a second-order, n-state, 2-symbol Turing machine.


texts:
Time and Space are two commons parameters (and also natural parameters) to measure the complexity of the problem. I am not able to understand the motivation behind defining " Descriptive Complexity". I search on the internet and find out that it is the complexity of expressing some property of the input. Take the example of the sorting problem. Time and Space seems to be a natural choice. I am unable to come up with an example or a problem which immediately implies the importance of defining the  " Descriptive Complexity ".

Question :  What is the motivation behind " Descriptive Complexity "?


texts: How the SIFT results vary by changing some parameters

texts:
I'm studying the SIFT algorithm and I have some problem understanding its operation, in particular I don't understand how the results vary according to the parameters: number of octaves, number of levels and sigma0.

I've read Lowe's original paper and I've done searches online but I still have doubts, I hope you can solve them.

I'm currently using this MatLab library.

This is what I get by editing the number of octave, layers, and window size (called also sigma0, if I have correctly understood the APIs).

What I see is that by increasing the number of octaves, it increases the number of features and adds larger features.

By increasing the number of levels, it seems to me the same thing happens when the octaves increase, ie the number of features increases and these are larger.

What should happen to the increasing number of octaves? Does it mean that increasing the series of halved images and hence?
While increasing the number of levels means increasing the number of DoGs and hence in practice?

Instead, the features don't change varying sigma0, why? As the sigma0 increases, it should increase the degree of blur of the image and hence I should get fewer features, right?
I have tried with many values and with different images and I always get the same features.

I don't understand how the results vary based on the variation of these parameters. Can anyone help me?

Thank you very much


texts: Minimize longest continuous streak of $1$s after flipping $m$ $-1$s to $1$s

texts:
Given an array a of length n of $-1$s and $1$s, and another input $m$, I was supposed to minimize the longest continuous streak of $1$s or $-1$s after flipping $m$ $-1$s to $1$s or vice versa.

I know how to maximize it but can't figure out how to minimize it. I maximize the number of $1's$ by sliding window method.
Take a window ($wleft$ , $wright$).It covers given array from index $wleft$ to $wright$.
I represent $-1$ with $0$ for ease.Suppose number of zeros in window in $wzeros$.

Algorithm :

while wright < length of array {

     wzeros <= m: increment wright

     wzeros>m: increment wleft

  // Update the max window size during this whole process.

        int temp = wright-wleft;
        if(temp > mx_length){
          mx_length = temp;
          solution_window = wleft;
        }
    }

This code maximizes the number of consecutive $1$s whereas I want to minimize the number of consecutive $1$s and $-1($or $0)$s. How do I modify the algorithm/code to achieve so ?


texts: How many vertices should be disconnected to make a graph acyclic?

texts:
Given an undirected graph with some cycles:

we can "disconnect" the red vertex by adding a separate vertex to each of the edges adjacent to it:

In this case, disconnecting a single vertex makes the graph acyclic.
My questions:

What is a term for the smallest number of vertices that must be "disconnected" like this, to make the graph acyclic?
What is an algorithm for finding a smallest such set of vertices?

(I found some related concepts, but they are different:

The circuit rank is the number of edges that have to be removed to make the graph acyclic; it always equals the number of edges minus the number of vertices plus the number of components.
The vertex connectivity is the number of vertices that have to be removed to make the graph disconnected.)


texts: How to parallelize a summation efficiently

texts:
Say I have an array a[1..n], and I want to output an array s[1..n] with s[i] = a[1]+...+a[i]. What is the best (or at least standard) way to do so in parallel?
The way I can think of doing it, given m processors, is to split the array a into m blocks of equal size M, compute b[j] = a[floor((j-1)/M)*M+1]+...+a[j-1]+a[j] (in parallel), then compute s[iM] for 1<=i<=m by summing values of b[jM] (serially), and then, lastly, compute s[jM+i] = s[jM]+b[jM+i] for all 0<i<M, 0<=j<m (in parallel). That feels a little wasteful, though the time complexity is right - is there a better way?


texts: Kernelization algorithm for the following problem

texts:
We are given an undirected graph $ G $ and a positive parameter
$ k \geq 0 $. The problem is to decide if there exists a set $ S \subseteq V(G) $ of size at most $ k $ such that $ G − S $ does not have any path on three vertices.
Is there any deterministic kernel algorithm for this problem with $ \Theta (k^2) $ vertices?
Kernelization algorithm definition: Given $ (G,k) $, output an equivalent instance $ (G’,k’) $ of the same problem in polynomial time, such that $ |G’| \leq f(k) $ and $ k’ \leq k $.


texts: Query complexity of exact learning and combinatorial parameter

texts:
When defining the query complexity of exact learning for a concept $c$ (considered as a function from $\{0,1\}^n \mapsto \{0,1\}$) in a concept class $\mathcal{C}$, we often come across the following definitions leading to query complexity theorems (see R.Servedio and S.Gortler, Equivalences and Separations between Quantum and Classical Learnabbility for instance).

Let $\mathcal{C'} \in \mathcal{C}$. For $a \in \{0,1\}^n$ and $b \in \{0,1\}$, let $\mathcal{C'}_{<a,b>} = \{ c \in \mathcal{C'} : c(a) = b \}$. Then define:
$$\gamma^{\mathcal{C'}}_{<a,b>} = \frac{\lvert \mathcal{C'}_{<a,b>} \rvert}{\lvert \mathcal{C'} \rvert}$$
$$ \gamma^{\mathcal{C'}}_a = min(\gamma^{\mathcal{C'}}_{<a,0>},\gamma^{\mathcal{C'}}_{<a,1>})$$
$$ \gamma^{\mathcal{C'}} = max\{ \gamma^{\mathcal{C'}}_a : a \in \{0,1\}^n \} $$
And finally let:
$$ \hat{\gamma}^{\mathcal{C}} = \underset{\mathcal{C'} \subseteq \mathcal{C}, \lvert \mathcal{C'} \rvert \geq 2}{min} \gamma^{\mathcal{C'}} $$
i.e. :
$$ \hat{\gamma}^{\mathcal{C}} = \underset{\mathcal{C'} \subseteq \mathcal{C}, \lvert \mathcal{C'} \rvert \geq 2}{min} \ \ \ \underset{a \in \{0,1\}^n}{max} \ \ \ \ \underset{b \in \{0,1\}}{min} \frac{\lvert \mathcal{C'}_{<a,b>} \rvert}{\lvert \mathcal{C'} \rvert}$$

I'm not sure to totally understand why using these definitions. Say we want to learn $c \in \mathcal{C}$. If we identify an $a$ such that $c(a) = 0$ whereas for most of $\tilde{c} \in \mathcal{C}$ , $ \tilde{c}(a) = 1$ then it's great for the learning algorithm because we can discard a lot of concepts that does not match $\tilde{c}(a) = 1$. However these above definitions have an inner min ($min$ on $b \in \{0,1\}$) which would give us a poor bound on the number of concepts we can discard in the case I mention in the paragraph.

Is this because we have to give a query bound independent of which concept we want to learn in the class? And thus we cannot use the membership query for a specific concept. I still think it would not be equivalent to specifying a concept and taking the maximum query complexity (which is what I would have done intuitively).


texts:
In the highlighted part below how is Weiss concluding that the array starting at an arbitrary index "p" and ending at "j" can never be larger than the array starting at "i" and ending at "p-1"?

By his own example (the inner loop of algorithm 2 shown below) this is demonstrably false.

Let i = 0, and j = 3.

Let a[ 0 ] = -14, a[ 1 ] = -4, a[ 2 ] = -2, a[ 3 ] = -1.

If p = 2, the subsequence sum from "p" to "j" is clearly bigger than "i" to "p-1".

Even more concerning is Mr. Weiss seems to pull an assumption out of thin air ("j is the first index that causes the subsequence starting at index i to become negative") when nothing in the above could possibly imply that! Indeed, Weiss only mentions "detection" of the subsequence sum being negative between index "i" and "j", but never where the source of this could only occur. Where is this coming from?

Thanks for any help!


texts: Convert C language code to problem specification by computing the invariant of a program

texts:
Suppose that you need to give a problem specification of some problem P and you have an implementation of P, in C.

I have 2 questions:

Can you obtain the formal specification of the problem if you compute the invariant of the external for cycle?
What is the relation between the specification and the C code invariant?


texts: Do the minimum spanning trees of a graph have the same number of edges with a given weight?

texts:
I'm asking about the answer here:

Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?

I didn't understand the best answer here

  Choose edge $e \in T_1 \mathop{\Delta} T_2$ with $w(e) = \min W$, that is $e$ is an edge that occurs in only one of the trees and has minimum disagreeing weight. Such an edge, that is in particular $e \in T_1 \mathop{\Delta} T_2$, always exists: clearly, not all edges of weight $\min W$ can be in both trees, otherwise $\min W \notin W$. W.l.o.g. let $e \in T_1$ and assume $T_1$ has more edges of weight $\min W$ than $T_2$.

First of all, what does minimum disagreeing weight mean?

  assume $T_1$ has more edges of weight $\min W$ than $T_2$.

Does the above line mean, $T_1$ has multiple edges with weight $\min W$

  Now consider all edges in $T_2$ that are also in the cut $C_{T_1}(e)$ that is induced by $e$ in $T_1$. If there is an edge $e'$ in there that has the same weight as $e$, update $T_1$ by using $e'$ instead of $e$; note that the new tree is still a minimal spanning tree with the same edge-weight multiset as $T_1$. We iterate this argument, shrinking $W$ by two elements and thereby removing one edge from the set of candidates for $e$ in every step. Therefore, we get after finitely many steps to a setting where all edges in $T_2 \cap C_{T_1}(e)$ (where $T_1$ is the updated version) have weights other than $g(e)$.

This paragraph seems to be a problem for me. So, we remove edges with weight $e$ which is also $\min W$ and replace it with $e'$. So we do that for all edge weight $e$ present in $T_1$

  Therefore, we get after finitely many steps to a setting where all edges in $T_2 \cap C_{T_1}(e)$ (where $T_1$ is the updated version) have weights other than $g(e)$.

I didn't understand this line at all. What is supposed to be $g(e)$?

  Now we can always choose $e' \in C_{T_1}(e) \cap T_2$ such that we can swap $e$ and $e'$¹, that is we can create a new spanning tree

  $\qquad \displaystyle T_3 = \begin{cases}
  (T_1 \setminus \{e\}) \cup \{e'\}  &, w(e') \lt w(e) \\[.5em]
  (T_2 \setminus \{e'\}) \cup \{e\}  &, w(e') \gt w(e)
\end{cases}$

  which has smaller weight than $T_1$ and $T_2$; this contradicts the choice of $T_1,T_2$ as minimal spanning trees. Therefore, $W_1 = W_2$.

Why is $w(e') \lt w(e)$ here? isnt $e'$ same as $e$ ? and why does  $T_1,T_2$ contradict as minimal spanning trees?


texts: Why any problem can be reduced to SAT is NP-Complete?

texts: I have a book statement says the title, I don't understand it. From my current understanding if a problem A can be reduced to a problem B then it only means B is at least as difficult as A.


texts:
I've been searching for a specific case of the four color map theorem all over the internet, but can't seem to find a reliable explanation.

Does anyone know one or two "cases" of maps as applied to the four color map theorem, including how it could be proved by hand?

The only explanation given on the web is Appel & Haken's computer-based proof, which is not helpful in the sense that the code used in their programs is not available to the public, nor do I understand it completely.

Also, can someone please explain (in depth) what Kempe's chains are and how they work? (maybe also provide an example?)

I am writing a paper for my math class about the four color map theorem, and so far the internet has not been very promising.


texts:
Consider the following problem. Given a set of $n$ items having weight $w_i$ and value $v_i$ and a maximum capacity $W$, maximize $\sum\limits_{i=1}^n a _i v_i$ under $\sum\limits_{i=1}^n a_i w_i \leq W$ where $a_i \in \{0,1\}$. That is, choose a subset of items giving the maximum total value while still fitting into the capacity. I am wondering what the time complexity of this problem is and I think that I found that it is not in NP. The reason is that there can be no certificate of correctness for any one particular choice of items. When someone gives me a set I cannot simply check to see that it indeed gives maximum value.

It seems that this problem is at least as hard to check as it is to solve, so it cannot be in NP.

Another line of reasoning leads me to the following: The decision problem can a value of at least $V$ be achieved can be checked in polynomial (actually linear) time by a certificate giving a list of the items. Now a machine can first add up all the values to get $V_{\max}$, and then perform the decision problem for $V = 1, \ldots, V_{\max}$ until the answer is no, having then maximized the sum. This would I guess be an NP computation as we run $V_{\max}$ NP computations and $V_{\max}$ grows linearly with the input.

Hmm, help would be appreciated.


texts: Using A* path finding is giving me inaccurate results

texts:
So i am using A* path finding to find a path from a person, to a node on a graph. This person has a few 'must pass' nodes that they must go through. So my solution was to run the algorithm for each of the must pass nodes, to make sure they always go to each of these. My method for deciding which order nodes come in for their individual run through the algorithm is to use a distance between the person on the graph and the remaining nodes, the smallest distance will be put through the algorithm first.
Here is a diagram of what this looks like:

The person must visit the blue node last, which is why the  distance hasn't been included for that node.
As you can see, the bottom right pink node is the first node to go through the algorithm since they have the smallest distance.
Here is where i come across a problem:
If the algorithm tries to find a path to this node on the bottom right, the person will actually travel across the edge with weight 1, since the distance between the node on the other side of the edge with the weight of 1, to the end node, is 6.25 (using a ruler by hand and making sure the diagram stays the same size on my screen at all times for all distances measured).
Would this not mean the person ends up travelling through all of the other must pass nodes on the graph before they even reach the first must pass node?
Is my criteria for picking the next node for the algorithm wrong?
What am i doing here that is wrong? Or is this a fault with A*?
Note: The weights on each edge are measured fairly accurately by hand with a ruler, so i doubt that is the issue.
EDIT:
The one question i need answered is this. What is the best way to decide which node to path find for first? I'm starting to doubt if Euclidean distance is the best choice here.


texts: How can I determine if two vertices on a polygon are consecutive?

texts:
Suppose I have a set of points that construct a convex polygon in the Cartesian plane with the points as its vertices. I randomly choose two vertices and want to know if they are consecutive vertices on the polygon. Does anyone know of an algorithm that would do this, as in you would input the array of points and the two vertices as parameters and it would return a boolean?

It's given that the polygon exists and is unique.


texts:
What does it mean exactly a "uniform shuffle" algorithm ?

Is this method considered a uniform shuffle ?

public void shuffle(Comparable[] a) {
    int n = a.length;
    int k, j;
    for (int i = 0; i < n; i++) {
        k = StdRandom.uniform(n); // k in [0, n-1]
        j = StdRandom.uniform(n); // j in [0, n-1]
        exch(a, j, k);
    }
}


texts: Algorithm To Compute The Gaps Between A Set of Intervals

texts:
Problem
Given a set of intervals with possibly non-distinct start and end points, find all maximal gaps. A gap is defined as an interval that does not overlap with any given interval. All endpoints are integers and inclusive.
For example, given the following set of intervals:
$\{[2,6], [1,9], [12,19]\}$
The set of all maximal gaps is:
$\{[10,11]\}$
For the following set of intervals:
$\{[2,6], [1,9], [3,12], [18,20]\}$
The set of all maximal gaps is:
$\{[13,17]\}$
because that produces the maximal gap.
Proposed Algorithm
My proposed algorithm (modified approach taken by John L.) to compute these gaps is:

Order the intervals by ascending start date.
Initialise an empty list gaps that will store gaps
Initialise a variable, last_covered_point, to the end point of the first interval.
Iterate through all intervals in the sorted order. For each interval [start, end], do the following.

If start > last_covered_point + 1, add the gap, [last_covered_point + 1, start - 1] to gaps.
Assign max(last_covered_point, end) to last_covered_point.

Return gaps

I have tested my algorithm on a few cases and it produces the correct results. But I cannot say with 100% guarantee that it works for every interval permutation and combination. Is there a way to prove this handles every permutation and combination?


texts: Is it possble to store a counter that could reach $\lfloor \frac{N}{x}\rfloor$ using $\lceil\log_2(N+1)\rceil$ - $\lfloor\log_2 x\rfloor$ bits?

texts:
Let $x,N$ be positive integers.

I'd like to store a counter which could reach value of $\left\lfloor \frac{N}{x}\right\rfloor$ (i.e. could take any value in $0,1,\ldots,\frac{N}{x}$) using  $$\lceil\log_2(N+1)\rceil - \lfloor\log_2 x\rfloor$$

bits.

Equivalently, does the following hold:
$$\log\left\lfloor \frac{N}{x} + 1\right\rfloor \leq \lceil\log_2(N+1)\rceil - \lfloor\log_2 x\rfloor$$

Obviously, this holds for $x=1$, what about general $x$?


texts: Derivation tree and Productions from left most derivation of string

texts:
How can one find Derivation tree and Productions of a Grammar from left-most derivation and string used?
I was given input string x = abaccacaa , left most derivation lder(x)=(1,2,1,3,4,1,3,5) and two rules :

Length of RHS of each production is 2
Each production's RHS starts with a terminal symbol

How should I go about solving this?


texts: Parallel colouring to minimize collisions?

texts:
I have a graph in which there is a set of leader vertices $L$. There is no edge between any pair of leader vertices. Each leader vertex $u$ has a common set of colours $C$ and a set of neighbour vertices $N(u)$. A leader vertex is oblivious of the decisions of other leader vertices. Each leader vertex picks a colour for each of its neighbours. A leader knows its neighbours, the available colours, and the number of leaders.

Let $w$ be a common neighbour for leader vertices $u$ and $v$, i.e., $w \in N(u)\cap N(v)$. If the leader vertices $u$ and $v$ assign the same colour for $w$, a collision occurs.

I would like to find an algorithm that is executed at each leader vertex independently and assigns a unique colour to each one of its neighbours such that the number of collisions is as small as possible.

The context of this problem is from frequency assignments in a distributed wireless sensor network, where each node that can communicate (it is a neighbour) with more than one leader cannot do so using the same frequency.

This problem is probably studied before. Because I have little graph-theory backgrounds, I hope some help from graph-theory specialists? At least, can you point me to any reference I should read?

For now, I am looking for "Parallel graph colouring", "Leader colouring", but I am a little lost.


texts:
This question might be redundant but I want to verify my understanding further. Suppose I have this linear directed graph:

$$S \overset{2}{\to} A \overset{1}{\to} B \overset{3}{\to} E \overset{1}\to D.$$

Here, $S$ is the source, $D$ is the target, and numbers indicate to edge weight:

When taking about shortest path, do we only count the number of edges? So in this example, shortest paths from $S$ to $D$ is 4.
Thus, when taking about shortest distance, we find the sum of the edges weights. So in this example, shortest distance from $S$ to $D$ is 7.

The reason why I elaborate this question using example is that I've seen plently of answers when I google this question but it seems they treat the work path and distance in similar way which is counting the number of edges (hops).


texts: How to find the minimum number of states required by a DFA

texts:
Given a language $L = \left\{ a^{nk+1} | n > 0 \right\}$ and $k$ is an integer constant.

How to show that a DFA for this language must have $k+2$ states or more states using minimum state lemma.

By minimum state lemma I mean the number of minimum state a DFA has is the number of pairewise distinguishable states. I have constructed a set of pairewise distinguishable string ${a, aa, aaa, ... a^{k+2}}$ with respect to L and found that I can not add anymore strings to it. But I don't know how to prove this string has the maximum number of pairewise distinguishable strings.


texts:
Turing Test definition taken from wikipedia:

  The Turing test is a test of a machine's ability to exhibit
  intelligent behavior equivalent to, or indistinguishable from, that of
  a human. In the original illustrative example, a human judge engages
  in natural language conversations with a human and a machine designed
  to generate performance indistinguishable from that of a human being.
  All participants are separated from one another. If the judge cannot
  reliably tell the machine from the human, the machine is said to have
  passed the test. The test does not check the ability to give the
  correct answer to questions; it checks how closely the answer
  resembles typical human answers. The conversation is limited to a
  text-only channel such as a computer keyboard and screen so that the
  result is not dependent on the machine's ability to render words into
  audio

But how is a Turing Test defined?

What type of questions are considered to be so good that trick the human judge?

What and who defines a human judge suitable to be a judge? (for example if the judge is 5 year old wouldn't he be more easily tricked than a 50 year old computer scientist?)

All those chatbots are considered to pass the Turing Test? Most people are not sure if the chat bot is an actual bot or not.


texts: Path with least max-weight, in an undirected connected graph

texts:
The problem we were given, states that we have graph, where vertices are cities, and edges are roads. Each edge has a weight equal to the kilometers of the corresponding road. We want to get from city $A$ to city $B$, with a car that can last up to $M$ kilometers in one go, but we can refuel, every time we go to a city. It isn't mentioned, but i guess we can't suppose that the graph is acyclic, since it represents a country's map.

We need to find two algorithms that give as the least $M$ our car needs to have to get from a city $A$ to city $B$. One should have time complexity $m\log m$, and the other one linear (where $m$ is the number of edges).

I thought that we could use BFS/DFS for that, but they aren't what we are looking for, because of the complexity. The only other thing I came up with is using Kruskal algorithm somehow, because it has the complexity we want, and also the graph is connected, so maybe we have less things to worry about. As for the linear one, I can't find anything.


texts: How do you find an infinite regular language that is a subset of a non-regular language?

texts: In order to do this, we would probably need the non-regular language to be infinite as well, then find some definition for the non-regular language in order to fulfill the requirement, but I don't know how to construct one.


texts:
For the following code fragment:

i = 1;
s = 1;

while(s <= n) {
    i++;
    s = s+i;
    printf("x");
}

How can we go about proving the time complexity of this code is $\Theta(\sqrt{n}))$?

Usually, I use sigma series analysis to figure the time complexity but I am having trouble turning this code into series notation and then using the series to find out the time complexity.


texts:
I am looking over the classic  Reader and Writer Problem
Just to give a quick overview:

Many readers can be in CS (as long as no writers are)
Only one writer can be in the CS (with no combination of other readers/writers)

So the solution is:

binary semaphore wrt, mutex = 1;
int No_of_Readers = 0;

Writer Process
wait(wrt);
write
signal(wrt);

Reader Process
wait(mutex);
No_of_Readers ++;
if (No_of_Readers == 1)
   wait(wrt);
signal(mutex);

Read
wait(mutex);
No_of_Readers --;
if (No_of_Readers == 0)
   signal(wrt);
signal(mutex);

My question is simple but I just don't understand it, what is the use of the binary semaphore mutex? why do we have to wait(mutex) when we enter Reader Process and then also wait(mutex) after we Read ?
If someone can give a clear explanation that would help me completely understand this algorithm I am just getting tripped up on that little part.


texts: Shortest paths when edge weight depends on previous edge

texts:
I have a directed graph with non-negative weights on the edges.
I can divide the nodes in two "classes", X (roughly 1700 nodes) and Y (~300).
I want to collect all the shortest paths from x in X to y in Y.

The weight of the edges depend on the previous edge in the path I am currently on.

Testing the possible paths between x1 and y1, e4 has same attribute "B" as the preceding edge e3, so its weight will be reduced (I want to favour paths with same properties).

How do I actually find the shortest among the paths among x1 and y1 in this scenario?


texts: Can the formalisms of category theory replace those of type theory?

texts:
The subtleties of the correspondence between type theory and category theory are outside my ken. However, by my naive understanding of the relationship between the two historically convergent disciplines, the latter entirely subsumes the former. If this is so, can the language and formal/graphical descriptions used by category theorists replace those of type theorists? And should they (e.g., in pedagogy and academic publishing)?

Different formalisms can inspire novel perspectives and lay bare conceptual connections that might otherwise be obscure. However, a multiplicity of dialects probably also limits the size of a receptive audience, and, should a polyglot approach be taken, the length and complexity of exposition is compounded.

If category theory does subsume type theory, should the dialectical differences of the two disciplines be retained, and if so, why? For the sake of historical or cultural value? To retain different but salient differences of instructional or theoretical emphasis? What might these be?


texts:
$L=\{$$($$m$,$w$,$n$$)$| $m$ is an encoding of a non-deterministic Turing machine, $w$ is any word/string in the closure of alphabet, i.e. $w\in\Sigma^*$, $n$ is any positive integer, i.e. $n\in\Bbb{Z}$ and $n>0$, and $m$ accepts $w$ for a maximum of $n$ moves/steps/operations $\}$

Alphabet is $\Sigma=\{0,1\}$

If this language is NP Hard then what reduction proves it?

My effort to answer this question myself is:

If $L$ is NP Hard then every NP language reduces to $L$ in polynomial time deterministically.

More formally $L\in\Bbb{NPH}\implies\forall L'\in\Bbb{NP}:\;L'\le_PL$

Let $L'$ be any arbitrary NP language.

According to the assumption that $L'\in\Bbb{NP}$ by definition of the complexity class $\Bbb{NP}$ exists non-deterministic Turing machine $m$ that decides $L'$ in polynomial time.

This means that for every word/string $w\in\Sigma^*$:

If $w\in L'$ then $m$ accepts $w$ for a maximum of $c\cdot N^k$ moves/steps/operations

AND

If $w\notin L'$ then $m$ rejects $w$ for a maximum of $c\cdot N^k$ moves/steps/operations

Where $c$ and $k$ are constant non-negative integers and $N$ is the length of $w$.

If $L'\le_PL$ then exists deterministic Turing machine $m'$ that computes function $f:\Sigma^*\rightarrow\Sigma^*$ in polynomial time so that for every word/string $w\in\Sigma^*$:

$w\in L'\iff f(w)\in L$

Let $m'$ be deterministic Turing machine that in the beginning $m'$ inserts the encoding of $m$ before input word/string $w$, which takes constant time $\mathcal{O}(1)$, because the encoding of $m$ is constant word/string and thus the length of the encoding of $m$ is constant non-negative integer, then $m'$ computes the length of the input word/string $w$ by counting all symbols of $w$, which suppose to take linear time $\mathcal{O}(N)$ where $N$ is the length of the input word/string $w$, then compute the power of the computed length by the constant non-negative integer $k$, which takes polynomial time, then multiply the result by the constant non-negative integer $c$, which also takes polynomial time, and at last append the result after $mw$ and the content of the tape of $m'$ will be $(m,w,c\cdot N^k)$ where $n=c\cdot N^k$

After doing all these actions $m'$ halts.

$m'$ is indeed deterministic Turing machine and runs in polynomial time and $w\in L'\iff (m,w,c\cdot N^k)\in L$ followed by the definitions of complexity class $\Bbb{NP}$ and non-deterministic Turing machines.

Hence by definition $L'\le_PL$ because of $m'$

Conclusion: For arbitrary language $L'$ I showed that $L'\le_PL$ holds.

Therefore every NP language reduces to $L$ in polynomial time deterministically and by definition $L$ is NP Hard.

What I wrote above suppose to be a proof that $L$ is NP Hard, but the proof doesn't reduce already proven NP Hard language to $L$, so I think that I did some mistake.


texts:
Suppose a pair of random variables $(X,Y)\in\mathcal{X}\times \mathcal{Y}$ with joint distribution $P_{XY}$ is given. I am interested in a deterministic mapping
$f:\mathcal{Y}\to \{0, 1\}^k,$ for some integer $k>0$ such that
$$f(Y)\perp X, \qquad \text{i.e.}, \quad f(Y)\text{ is independent of } X,$$ and
$$H(f(Y))>0.$$ The second condition is just to rule out the degenerate functions $f$.

For example if $X\sim\mathsf{Bernoulli}(p)$ and $P_{Y|X}$ is an erasure channel* with erasure probability $\delta>0$, then $f:\{0,\text{e},1\}\to \{0,1\}$ where $\text{e}$ is the erasure, defined as
$$f(1)=f(0)=1,\qquad f(\text{e})=0,$$ satisfies the above condition.

What is a necessary and sufficient condition on $P_{XY}$ for the existence of such deterministic map?

*By erasure channel, I mean the following conditional distribution:
$$P_{Y|X}(y|x)=(1-\delta)1_{\{y=x\}},$$ and
$$P_{Y|X}(\text{e}|x)=\delta, ~~~~\text{for}~~~~x=0,1.$$


texts: Are there any problems that require exponential time in quantum computing?

texts:
Given the fact that the qbits have superpositions, and have more representational power compared to circuits, are there any problems that require at least exponential time to guarantee a solution with a quantum computer?

I've checked the Complexity Zoo and couldn't find any complexity class mentioned there that fits this description.


texts: Relation between number of edges and vertices in a DAG

texts: I conjecture that, in a Directed Acyclic Graph, $O(|V|) = O(|E|)$. Is this statement correct, can it be refined? This is probably standard material; is there a simple reference about this?