texts:
I have the following Bayesian Network.

I have worked out the following:
P(H) = P(H|D) + P(H|¬D) = 0.5 + 0.1 = 0.6
P(D|H) = (D)∗(P(H|D) +P(H|¬D)) = 0.3∗(0.5 + 0.1) = 0.18
How do I compute the probability of D, given that C and F are true, and also the probability of F given that C and H are true? Can you explain to me the reasoning behind this?


texts: Solving $$f(x, k) = f(x, k-1) + f(x-1, k-1) + \dots + f(1, k-1)$$ in terms of $x$

texts:
I'm having trouble determining the complexity of an algorithm.
Let's say the number of operations of my algorithm is described by
$$f(x, k) = f(x, k-1) + f(x-1, k-1) + f(x-2, k-1) + \dots + f(1, k-1)$$
where $f(x, 1) = x$

How can I describe the growth of $f(x)$ in terms of

$x$
$k$
$x$ when $k=x-1$

For 1), I believe $f(x, k)$ would be exponential in $x$ as $k$ can be taken to be a constant which would reduce the above equation to being similar to

$$f(x) = f(x-1) + f(x-2) + \dots + f(1) $$

Similarly, for 2), I believe $f(x, k)$ would be exponential in $k$ as I would need to take $x$ as a constant which would lead to the below equation

$$f(k) = xf(k-1) $$

Need help with 3) and also validating my thinking for 1) and 2)


texts: Is there a theory/abstraction behind OOP?

texts: Functional programming has the very elegant Lambda Calculus and its variants as a backup theory. Is there such a thing for OOP? What is an abstraction for the object oriented model?


texts: Solving for the minimum cost, colored, set cover

texts:
Formulation
This problem has four entities:

A universe: $U = \{1, 2, ..., n\} $ of $n$ elements, indexed with $u$
A set of available colors: $C \in \{1, 2, ..., m\} $ with $m$ colors, indexed with $c$
A collection of sets: $S = \{s_1, s_2, ..., s_k\}$ where there are $k$ sets, indexed with $i$. These sets contain elements of the Universe. $\bigcup S = U$.
A cost function: $cost(u, c)$ where $u$ is the element, $1 \le u \le n$, and $c$ is the color of that element $1 \le c \le m$

We must assign a single color to each element such that the overall cost of the color assignment is minimized AND such that a valid set cover exists such that all elements in each set of the set cover have the same color. That is:
$$min \sum\limits_u cost(u, c) x_{u,c}$$
subject to

$0 \le x \le 1$. That is, $x_{u,c}$ is a binary decision variable which indicates that a particular element ($u$) is a particular color ($c$).
$\sum \limits_c x_{u,c} = 1 \quad \forall u \in U$. That is, an element may only have one color.
$\sum \limits_{s:u\in S} y_s \ge 1 \quad \forall u \in U$. That is, every element must be in the set cover.
$0 \le y \le 1$. That is, $y_{s}$ is a binary decision variable which indicates that a particular set ($s$) is included in the set cover.
$ x_{s_{i_1},c} = x_{s_{i_2}, c} = ... = x_{s_{i_l},c} \quad \forall s_i \in S \bigm| y_s = 1$. That is, given that a set is included in the set cover, everything in that set must be the same color.

Example
$U = \{1, 2, 3, 4, 5, 6, 7, 8\}$
$C = \{r, g\}$
$S = \{\{1, 2\}, \{1, 2, 3\}, \{2, 3, 4\}, \{3, 4, 5\}, \{4, 5, 6\}, \{5, 6, 7\}, \{6, 7, 8\}, \{7, 8\}\}$
$cost_{r} = \{0, 0, 2, 1, 2, 1, 1, 0\}$
$cost_{g} = \{1, 0, 1, 2, 0, 0, 0, 3\}$
Optimal solution:
$= \{r, r, g, g, g, g, r, r\}, \quad cost=4$
That is, the set cover is $\{\{1, 2\}, \{3, 4, 5\}, \{4, 5, 6\}, \{7, 8\}\}$.
Typically, $U$ consists of 100-2000 elements, $C$ consists of 3 - 10 colors, $S$ consists of 200-4000 sets of 5-25 elements.
Context
Perhaps one way to think about this, is that you have a paint brush of a certain size that is larger than an element - that is it can only paint a collection of elements in one stroke. The allowed places to 'stroke' are overlapping - they are the sets in S. When you paint a particular set a particular color there is a cost associated with it that you would like to minimize. When you paint an area, you can paint the overlapping areas the same color only paying for the 'difference' in cost (kinda).
Questions

Is the formulation above well formed, and understandable? Is there a better formulation more related to an already existing problem?
Can this be expressed as an integer linear programming problem?
How would you solve this problem?

I have constructed an algorithm to solve this problem that first tries to use branch and bound to construct the optimal solution - it does quite well, but as the problem gets larger it slows down. If it starts to take too long I stop the branch and bound and use a random search to improve a solution. I think that having a better mathematical understanding of the problem will help me solve it better - I would also like to prove that this is NP-Hard.
One idea I have toyed with is to construct a new collection of sets $S'$ which consists not only of all the original sets but all of their combinations / unions (I understand this will be a lot, $2^k - 1$ right, but for at least proving the complexity of the problem it should be ok..) and then duplicating those sets once for each color, and then solving for the weighted exact set cover. Does that 'reduction' prove that this is NP-Hard? Is that even a reduction?
I've also thought about thinking about the problem the other way around, that is thinking about it in terms of the sets being assigned a certain color - but then I don't know exactly how to account for the overlapping of the sets in the minimization, also there will be some sets that do not have a single color so long as the sets that do have a single cover form a covering of the universe.
Thanks in advance.


texts: Most scalable distributed consensus mechanism based on message complexity?

texts:
One of the most challenges in distributed consensus mechanisms is both time complexity and message complexity.
For example, PBFT message complexity is O(n^2) that means that it is only scalable to tens of nodes. Thus, classical BFT (Byzantine Fault Tolerant) consensus mechanisms are not scalable to the large networks.
Nevertheless, I am looking for the most scalable BFT consensus  among all.
In other words, is there a distributed BFT consensus with less than O(n^2) message complexity?
P.S. I brought up this question before in scicomp.stackexchange.com, but they suggested me to bring up it here. (https://scicomp.stackexchange.com/q/36087/37225)


texts: Is it possible for a graph to have two different minimum spanning tree

texts:
I am suppose to create a minimum spanning tree from this graph below

I got this answer

However this is my textbook answer

Based on what i have learnt , I think my answer and the textbook answer would both be acceptable however I would like assurance from the community that both the answers are acceptable and I did not miss anything out

Thanks


texts: An approximation variant of the halting problem

texts:
It always has been bugging me that we (humans) know pretty easily when most programs we write halt or not, but the halting problem is still undecidable.
I have just thought of a variant approximation-like extension to this problem, that tries to "maximize" the correct answers an algorithm can make on this problem.
Formally speaking, let us say that a turing machine $A$ that always halts, is $r$-solving the halting problem, for $r\colon \mathbb{N}\rightarrow\mathbb{N}$, if $$r(n)\le |\{x\in \Sigma^*\mid x\text{ is a TM}\space\land\space|x|\le n\space \land\space A(x) \text{ is correct}\}|$$ where $A(x)$ is said to be correct $\iff$ $A(x)$ outputs true for $x\in HALT$ and outputs false otherwise.
Equivalently, we can define $r$ to be a function $r\colon \mathbb{N}\rightarrow [0,1]$ and then the requirement will change to $t(n)\cdot r(n) \le \cdots$, where $t(n)$ is the number of Turing machines that are encoded into strings no longer than $n$.
My question is: What is the largest $r$ function that we have an $r$-solving algorithm for? Or, what is the highest $r$ function that we can have an $r$-solving efficient (e.g. polynomial) algorithm for? Or are there other known things about the behavior of $r$-solving algorithms?

This can be easily adapted to any other problem, so I would be glad for any answer that explains this on any interesting language, and not necessarily the halting problem


texts:
I'm wondering where the GUI terminology like modal dialogue comes from.

Who first used these terms? Is there a paper or a book, or was it just sw?


texts: Computational complexity of counting symbols

texts:
Consider the counting function $\{x\}^* \rightarrow \mathbb N$ that counts the number of occurrences of the symbol $x$.

I am confused about the (asymptotic) complexity of computing this function, where the output should be represented in a non-unary system (e.g., binary). My intuition strongly suggests that this should be linear, i.e., $O(n)$ where $n$ is the number of occurrences of the symbol $x$ in the input.

As far as my understanding goes there are multiple interpretations of computation - e.g.,

single-band Turing machines, for which my best idea has run time $\Omega(n^2 \log n)$ I think (the $\log n$ comes from the assumption that the binary successor function has $\Omega(n)$ run time, where $n$ is the length of a binary representation of a natural number, and the $n^2$ comes from the assumption that the Turing machine has to travel over all the $x$'s to reach its current count),
multi-band Turing machines, for which I think I have an idea of run time $\Omega(n \log n)$,
random-access machines, which I don't know at all.

So my question is the following.

What is the computational complexity of the counting function in the various models of computation? Is it linear in any of them?

If at all relevant, I ask from the point of view of abstract algebra, where I am trying to assess the computational complexity of the word problem in some specific group.


texts:
I have to prove the following problem is in NP (and define verifier as well as the certificate/witness):

The input is a set of $n$ boxes with weights $w_{1},\ldots,w_{n}$ and two numbers $s$ and $t$ (all natural numbers).
Can the boxes be loaded onto $s$ trucks if each truck can only carry a total weight of $t$?

Apparently this is supposed to be easy, but I'm stuck.


texts: Implementing Queue operations in $\Theta(1)$

texts:
We want to implement a Queue which has two special operations besides the regular Queue operations: $getMiddle$(returns the element from the middle of the Queue, for example, if the Queue has 7 elements, it returns the 4th element, if the Queue has 6 elements, it returns the 3rd or the 4th) and $popMiddle$(removes the middle element). We want both of these operations and all the other Queue operations to run in $\theta(1)$. Pick a suitable data structure for representing the Queue, implement the $popMiddle$, pop and push operations and explain in short how the other operations would be implemented.

I was thinking that the linked list would be a good pick if we keep in mind also the tail. But there is a problem when popping the middle because we have to iterate until there. An array would not be good because when erasnig we have to move all the elements to the left, if not there is no suitable formula to find the middle. Does somebody have better ideas?


texts: Finding the maximum s-t flow of a graph $G$ in $O(n+m)$ time when $G-t$ is an arborescence

texts:
You are given an directed graph $G = (V , E)$ with positive edge capacities, a source vertex $s \in V$, and a target vertex $t \in V \setminus \{s\}$. $G$ is guaranteed to have the following additional property: The graph obtained by deleting $t$ from $G$ has exactly one path from $s$ to each other vertex in $V \setminus \{t\}$.
How can we compute the maximum flow from $s$ to $t$ in $G$ in time $O(|V|+|E|)$?

First, I read this post, and i think start from $s$ then run BFS, when we visit each node then set it to minimum flow that we find from $s$ to that vertex. Do this until we achieve vertices that have edges to $t$ and push each flow inside that vertices to $t$ this way we have an algorithm with linear time. Is argument correct?


texts: Question regarding Hoare's partitioning scheme and a slight modification to it

texts:
This is the pseudocode on wikipedia for Hoare's partitioning scheme:

algorithm partition(A, lo, hi) is
    pivot := A[lo]
    i := lo - 1
    j := hi + 1
    loop forever
        do
            i := i + 1
        while A[i] < pivot   //Question here

        do
            j := j - 1
        while A[j] > pivot

        if i >= j then
            return j

        swap A[i] with A[j]

This code finds an inversion and swaps it. Now, the problem of partitioning about a pivot is to divide an array such that all elements <= pivot fall in one partition, and all elements > pivot fall in the other.

My question is simple: why not use while a[i] <= pivot ?

As far as I can tell, it will work correctly, infact it would align better with the previous definition of partitioning.

If it does work, the big question is why wasn't it used in the original paper? It makes more sense and seems to be slightly faster as well (less number of swaps required).

Infact, while we're on the subject: would it be incorrect to also use while A[j] >= pivot that could further reduce the number of swaps.

I know that if I'm too worried about multiple elements repeating I should use 3 way partitioning, but I'm curious about how this algorithm would work nonetheless.


texts: Is arithmetic coding slightly more efficient than rANS?

texts:
I'm extending a framework for lossy compression of multidimensional floating-point data. At some point in the pipeline, sequences of symbols from a non-uniform distribution are losslessly compressed using entropy coding. The existing software used an implementation of arithmetic coding based on this post. As an extension, I implemented a second option, rANS.
However, analyzing the results, it seems that rANS needs around 1-2% more bits to encode the same data and this pattern is consistent among many different sequences of symbols of different lengths. Yet, as far as I understand, they should both be extremely close to the entropy limit. Indeed, looking at empirical results the arithmetic coder seems to only have a constant overhead of around 32 bits (the size of its normalized state) compared to the entropy limit.
So, my question is: Is there a known phenomenon that consistently makes certain variants of rANS slightly less efficient than arithmetic coding?
Some more information that might be useful:

I write/read from the compressed bit stream bit by bit, which should normally lead to optimal compression.
I have tried using various values of l (the lower bound on the valid state interval), such as  2^20 and 2^32, but this doesn't seem to have any effect.

If this is caused by a basic error in my implementation, I apologize and will take this question elsewhere (which is also why I didn't post the relevant code here).
Update: I have now also made b a variable (the ratio in between the upper and lower bound of the valid state interval, previously hard-coded to 2). Strangely enough, increasing b from 2 to higher powers of 2 seems to have mostly removed the overhead. With b = 256 I now get ~0.25% overhead typically. However, this doesn't really make much sense to me either, since I thought increasing b improved speed (by allowing the encoder to work with bytes or groups of bytes) while decreasing efficiency.


texts:
Given functions $f, p, c$, a matrix $X$, and vectors $C,D,E$.

I want to maximize the multivariable function $f(X)$, where $X$ is a $p \times q$ binary matrix ($X_{ij}$ is 0 or 1). So, $p\cdot q$ variables. The function $f(X)$ is given by
$$ f(X) = \sum_j \sum_i C_{ij} X_{ij} - \sum_j p(X,j), $$
where $C$ is a matrix of constants and $p$ is a penalty function (basically could be rewritten as a loose constraint as far as I can tell):
$$p(X,j) = \max(0, \sum_i X_{ij} - D_j)^2,$$
where $D$ is a vector of constants.

As hard constraints we got that $X_{ij}$ is binary, and
$$c_i(X) = \sum_j X_{ij} \leq E_i,$$
where $E$ is a vector of constants

I found linear programming is a topic that solves problems like this, and then found constrained optimization which would be more or less what I want, although I don't know how to write max() into inequalities. I suppose I could try to split the solution if the conditional branch was enforced on a single variable, but there are several conditionals at the same time anyway. Out of my searches the penalty method looks extremely similar to my equations, but there's the hard constraints that haven't been merged into the main function.

I request the exact topic I can research, I'm a bit confused as all of this is new to me and I'm not sure I'm studying the right topics.


texts: Recursive relation help for dynamic programming 2D plane algorithm

texts:
Consider a straight highway in the plane which can be modelled by a horizontal strip in the plane. A finite set T of targets are located on the highway, and a finite set S of wireless sensors are located outside of the highway. A sensor s can monitor a target t if and only if the Euclidean distance between s and t is at most one. Suppose that each sensor s is an element of S has a positive cost c (s) and each target t is an element of T can be monitored by at least one sensor in S. Consider a subset S' of sensors in S. S' is said to be a cover if each target in T is covered by at least one sensor in S'. The cost of S' is the total costs of the sensors in S'. The objective is to compute a cover S' of minimum cost. This is a polynomial time algorithm

Consider a 2D plane. There are targets that are randomly distributed between a $y$ upper bound and lower bound. This set is $T$. $T_1$ is marked with coordinates $(X,Y)$. There is a set $S$ of sensors that are guaranteed to cover every target. Each sensor has a radius $1$ and an $(X,Y)$ coordinate. Each target has a cost $c$ that is a weight. So my task is to find a minimum weight or cost for a set $S'$ that covers each sensor.

So I know that there is a recursive relation between the disks that "dominate" or "control" other disks but I'm having trouble seeing a property that shows how to utilize the dominance of the disks. I got this far:

Let $D^+$ be the set of disks whose center lies above the strip (upper disks).

Let $D^-$ be the set of disks whose center lies below the strip (lower disks).

Consider an upper disk $d$, and $d$ intersects a vertical line $L$. Another upper disk $d'$ is said to be controlled or dominated by $d$, if one of the following holds:

$d'$ does not intersect $L$,
the lower intersection endpoint of $d'$ and $L$ is higher than the lower intersection endpoint of $d$ and $L$, and
the lower intersection endpoint of $d'$ and $L$ is identical to the lower intersection endpoint of $d$ and $L$, but the center of $d'$ is on the right of the center of $d$.

Similarly, for a lower disk $d$, and $d$ intersects a vertical line $L$. Another lower disk $d'$ is said to be controlled or dominated by $d$, if one of the following holds:

$d'$ does not intersect $L$,
the upper intersection endpoint of $d'$ and $L$ is lower than the upper intersection endpoint of $d$ and $L$, and
the upper intersection endpoint of $d'$ and $L$ is identical to the upper intersection endpoint of $d$ and $L$, but the center of $d'$ is on the right of the center of $d$.

Howevern, I'm having trouble finalizing the algorithm. Any help? Is that clear?


texts:
We can associate a one counter finite automaton with a function $f:\Sigma^* \to \mathbb{N} \times \{0,1\}$, where $f(x)=(n,b)$ describes the state where the automaton terminates when fed an input word $x \in \Sigma^*$: $n$ holds the number inside the counter, and $b=1$ iff the state is an accepting state.

Is it decidable to determine whether two of these automata are associated with the same function?

I looked at posts like this one and this one too but I can't find the answer.

Furthermore, since these machines are always aimed to accept/reject a string, is there any natural way to expand them to represent a function?
As an example, think of a machine that simply counts the number of times it visited a specific node in the DFA, or even simpler: counts the length of its input word.


texts: Subset minimizing the cost of a one-sided matching, involving preference orders

texts:
We're given a set of items $A=\{1,\dots,m\}$ and a set of people $B=\{1,\dots,n\}$.  Each person has a preference ordering for the items in $A$.  Each item in $A$ has a specific positive cost for each specific person in $B$: item $i$'s cost to person $j$ is $c_{ij}$.

For any non-empty subset $T \subseteq A$ of items, we can imagine each person in $B$ choosing exactly one item in $T$: their top preference out of all the items in $T$ according to their preference ordering.  (Different people can choose the same item.)  Let $c(T)$ be the total cost of the items selected in this way.

Given the costs $c_{ij}$, I'd like to find a non-empty subset $T \subseteq A$ that makes $c(T)$ as small as possible.  What is the complexity of this task?

It looks like a NP-Complete problem to me.  It seems quite similar to a subset-sum or travel salesman problem, but I'm not sure. Do you have any suggestion for a reduction or a polynomial-time algorithm?


texts: A doubt on best media for a time capsule

texts:
So, I have some data to a time capsule project of mine. But the thing is, I need to know the best media on long-time scale to use as storage unity. The time range is 120 years. Now, I've been thinking about two medias: the average CD-ROM/DVD-ROM and a outdated Vinyl/LP. On the one hand the CD/DVD is a good one, due to its dimensions and information space, but the question remains about the difficulties to read a CD/DVD in 2141. A vinyl LP could be more simple.
So my question is: what is the best media for a time capsule?


texts: Why is randomness a problem? (i.e. why do we care about derandomization?)

texts: I'm reading Aaronson's survey on P vs. NP, and I've come to understand that in CS theory, people really care about derandomization results like P vs. BPP etc. My question is, what's the problem with randomness? If your algorithm is known to only require a polynomial number of random bits, then simply go ask a physicist to get the bits for you, which isn't a problem since you only need a tractable number of them, and then write them on the Turing machine tape and you're good! The goal of complexity theory is to figure out what we can compute in this universe, right? Well, this universe has randomness, right? So why do we care about derandomization? Theoretical and practical answers are both welcome.


texts: Distribution of resources from providers to maximum number of receivers

texts:
Consider there is a city with $n$ residents who are in need of internet and there are $m$ internet providers in the city. Here in the city every resident needs internet and every resident knows what providers are available to him. Formally let resident $i$ has list of providers $a_i$. Also each provider has a maximum number of connections he can give, that is, provider $i$ can have at max $k_i$ connections. Find the optimal way of providing internet so that the number of residents having internet is maximum.
My thoughts on the question is that this question looks like a derivative of knack-pack problem with constraints, which suggests dynamic programing but i am unable to find the states. Could anyone help me?


texts: Can someone give me the definition of #Monotone-2SAT?

texts:
In the decision problem, I set all variables to true and see if the formula is satisfiable.

My question is because I do not understand how there can be multiple solutions, though all variables are true.


texts: List the properties of $S \subseteq V(G)$ such that if we flip $\forall v \in S$ then all the nodes in $G$ will have the same value

texts:
We have a graph $G$ with binary values on it's vertices. If we flip
  the value of an vertex $v$ $ \forall v \in V(G)$  (that is, from $o_v$
  in $\neg o_v$, where $o$ is the value of the vertex $v$). And the
  values of it's neighbors will flip as well, so the value of $w$,
  $\forall w \in N_G(v)$ will flip from $o_w$ in $\neg o_w$.

  The interesting property to this type of graph is that if all the
  vertices have the same value $o$, then there exists a set $S$ that if
  the flip the vertices in $S$, one at a time (no matter the order),
  then all the vertices in the graph will have the same value $\neg o$.

  By $m(v, X)$ we denote the number of edges from the vertex $v \in V(G)$ to > the subset $X \subseteq V(G)$

List the proprietes of $m(v, S)$ and $S$ ($\forall v \in V(G)$).

My try:

There are 2 cases for this problem. If the graph $G$ is a connected graph then we need to flip only one node to get from $o$ to $\neg o$. And $|S| = 1$ and $S$ can be made from any node in the graph. Also, because of this $m(v, S) \in \{0, 1\}$.

If the graph is not connected, it will be partitioned in $k$ connected partitions. This means that $|S| = k$, $S$ will have only one node from each partition.

How will you approach this problem?


texts:
Recently it occurred to me that one could potentially design an interactive "compression" scheme which seems to allow for arbitrarily high compression ratios, at the sole expense of time. This already sounds pretty cranky, I realize that, but here is a formal description of the protocol which I hope makes sense:

Define a data store as a tuple $(\mathcal{O}, n, \delta)$ with $\mathcal{O} : \mathbb{N} \to \{ 0, 1\}^n$ a random oracle. We say that the data store "contains" the value $x$ at a (real) time $t \geq 0$ if $\mathcal{O}(\lfloor t \delta^{-1} \rfloor) = x$, such that the contents of the data store randomly change every $\delta$ units of time. A data store could be realized in software using the current time in some agreed-upon representation and any cryptographic hash function.
Alice wants to sends a message to Bob encoded as a bit string as part of an interactive protocol (Alice and Bob are both present and active during the transmission). First they both agree on a suitable $\delta$ such that they can both resolve the current time to within $\delta$ units of time. Then, Alice chooses an integer $n \geq 2$, instantiates a data store $(\mathcal{O}, n, \delta)$, and sends these parameters to Bob, and then breaks up the message into $n$-bit blocks. For each block, Alice then monitors the data store until its contents equal the block, at which point Alice sends a single bit "1" to Bob. When Bob receives this signal, he looks up the contents of the data store and retrieves the corresponding $n$-bit block (possibly rewinding as needed to account for any transmission delay, this is feasible as long as the transmission delay is fairly constant and known to within $\delta$ units of time). When the last block is sent, Alice sends the bit "0", Bob computes a checksum of the message and sends it to Alice for verification.
If the message contained $m$ $n$-bit blocks, the total amount of data actually sent (outside of protocol overhead) was $m$ bits, achieving a compression ratio of $1 - 1/n$, and it would take an expected $m \delta 2^{n}$ time to successfully send it (that is, $\delta 2^{n} / n$ time per bit). Also note that since this scheme doesn't actually use any structure in the message, it can be given already compressed data to compound any already attained compression ratios: the two are not mutually exclusive.
Clearly this doesn't allow for amazingly high transmission rates in general. A realistic usecase could be communication with a space probe, where the light-time transmission delay may be accurately computed allowing for a very low $\delta$, say, $\delta = 10 ~ \text{ns}$. Then we can achieve decent compression ratio/transmission rate tradeoffs, e.g. 94% at 3 KB/s ($n = 16$) or 90% at 122 KB/s ($n = 10$).
It gets exponentially more time-consuming to send data as $n$ increases, so  95% compression ratio is probably about the best one can practically achieve in reasonable time in the general case.

Obviously this only works as an interactive protocol, not as an offline protocol. Also, it doesn't really work "as-is" in real life because you can't just send 1 bit on most channels, as each communication entails a nontrivial amount of overhead (TCP/IP packet, etc..) but in principle I don't see why it couldn't work.
So, does anyone know if this kind of "temporal communication" has been studied before, and can point out any fundamental or practical problems or errors I overlooked that might explain why it isn't used?


texts: Log-Space Reduction $USTCON\le_L CO-2Col$

texts:
I want to show that $USTCON\le_L CO-2Col$ (Log-Space reduction)

$USTCON$
The $s-t$ connectivity problem for undirected graphs is
called $USTCON$.

Input: An undirected graph $G=(V,E)$, $s,t \in V$. Output: 1 iff $s$ is connected to $t$ in $G$.

$CO-2Col$
A graph is $2$-colorable if there is a way to color the vertices
of $G$ with $2$ colors, such that for every edge the two vertices
on the edge are colored differently. $CO-2Col$ is the following
problem:

Input: An undirected graph $G$. Output: 1 iff $G$ is NOT $2$-colorable.

I know this can be solved by simply using the $USTCON$ decision algorithm and then output a bipartite or non-bipartite graph accordingly. But is there any other reduction that actually changes the input graph?


texts: Subgraph of an interprocedural control flow graph

texts:
Say I have the interprocedural control flow graph (ICFG) of a program.

Now I am only interested in the control flow between two functions f1 and f2.

What is the most straight-forward way to remove the non-relevant part
of the ICFG?
Is there a standard performance-optimized algorithm for this task?
Does the result, that is, the interprocedural control flow "subgraph", have a special name?

I guess it would not be appropriate to call this a "slice" because its creation is based on the control flow graph reachability but not on data dependency relations. But I am not 100% sure.

EDIT:

I have to clarify: I am interested in the control flow starting at function f1, optionally passing via other functions, but eventually ending at function f2. In other words, the subgraph that contains all paths in the ICFG whose start node is f1 and whose end node is f2. This also includes paths with other nodes in between f1 and f2. Sorry in case my first explanation was not clear enough.


texts: Iterative Fibonacci algorithm correctness proof, finding loop invariants

texts:
The algorithm take in an integer $n$ and outputs the $n$th number in the Fibonacci sequence ($F_n$). The sequence starts with $F_0$. I am trying to prove the correctness assuming valid input:

int Fib(int n) {
    int i = 0;
    int j = 1;
    int k = 1;
    int m = n;
    while(m >= 3){
        m = m-3;
        i = j +k;
        j = i+k;
        k = i + j;
    }
    if(m == 0 ){
        return i;
    }
    else{
        if(m == 1){
            return j;
        }
        else{
            return k;
        }
    }
}

For a reminder, a loop invariant is a claim which holds every time just before the loop condition is checked. It holds even when the loop condition is false. I've established and proven one loop invariant that $m \geq 0$. This helps me show that the algorithm terminates since when the loop exits since $m$ is either 0, 1, or 2. However, I'm stuck on finding another loop invariant that would help me show that the algorithm produces the correct Fibonacci number.

One pattern I found is that the result of returning i, j, or k is due to the result of the initial value of $m$ $\% 3$. Depending on the remainder, either i, j, or k is returned. I tried expanding this idea further but led myself to a dead end. I'm thinking I need to find some way to express $F_n = F_{n-1} + F_{n-2}$ in terms of i, j and k in order to prove that the program outputs correctly. Am I on the right track with remainders or is there something I'm missing?


texts: How to Show Subset Sum $\le_p$ 3-Partition

texts:
Given a set of integers S (positive and negative, may contain duplicates) can S be divided into three disjoint subsets that all sum to the same value? Prove this problem is NP-complete.

Is it possible to show directly that Subset Sum $\le_p$ 3-Partition, or would I have to do
Subset Sum $\le_p$ Partition $\le_p$ 3-Partition?


texts:
I know how to use the pumping lemma to do so, but I don't think that can be used for this language:

$$L = \{x \in \{0,1\}^* : \text{no prefix of $x$ has more $1$'s than $0$'s}\}. $$

What other method can I use to prove this?


texts: How the concept of computer change over time?

texts:
There was a time when a "computer" was a person who worked on accounts. However, machines were introduced and this profession eventually died out over time. The definition below was taken from pag 750 of volume C of the year 1893 of the OED dictionary:

Computer [...] one who computer; a calculator, reckoner a person employ to make calculations in a observatory [...]
Oxford English Dictionary. Year: 1893; Volume C. Entry computer, pag 750.

People today attribute the concept of a computer to a machine. Some even think it is wrong to say that human beings "compute", because in their head computers are only "machines". Historically we know that this is not true and commenting on this mistake is the same thing as: finding that humans are not animals, because humans are not chimpanzees.
An oberservation that I believe to be unnecessary, but it may prevent some people from making some mistakes. Human beings are not machines. I say this not because humans have feelings and machines do not, people think that way are thinking wrong. Because machines are physical objects designed by some intelligent being as a means to achieve some purpose. If you stop to think, all machines are like that and in principle nothing prevents us from having a machine that has feelings since they can be made of the same atoms as us and have structures as sophisticated as ours. Perhaps in the future, with genetic engineering, the distinction between machines and living things does not make any difference. But, that's not what I'm discussing here.
My question is this: Why do many people today only assign computing to machines only? Why is it not commonly accepted today that human beings are also computers? Since the first computers were human?


texts: What is the time complexity of this method?

texts:
On CodingBat.com there's a problem that asks for the length of the longest sequence of repeating characters within a string:

(https://codingbat.com/prob/p179479)

Given a string, return the length of the largest "block" in the string. A block is a run of adjacent chars that are the same.

maxBlock("hoopla") → 2

maxBlock("abbCCCddBBBxx") → 3

maxBlock("") → 0

This is the solution I wrote:

public int maxBlock(String str) {

  int max = 0;

  for(int i = 0; i < str.length(); i++)
  {
    char c = str.charAt(i);
    int j = i + 1;
    int possibleMax = 1;

    // iterate through a "block"
    while(j < str.length() && str.charAt(j) == c)
    {
      possibleMax++;
      j++;
    }

    // if the block's length is greater than any found, save it
    if(possibleMax > max)
      max = possibleMax;
  }

  return max;
}

The time complexity is at least O(N) but I'm not sure if the while loop inside makes it O(N^2).


texts:
Right now I am working on my implementation of Knuth's DLX algorithm.

I did understand the exact cover problem. But I didn't fully understand how Dancing links works. Here is Knuth's paper.
The question is about the solutions presented in the paper. I don't understand how these solutions make sense taking into account the matrix that he uses.

Matrix for the exact cover problem

     A B C D E F G
  1  0 0 1 0 1 1 0
  2  1 0 0 1 0 0 1
  3  0 1 1 0 0 1 0
  4  1 0 0 1 0 0 0
  5  0 1 0 0 0 0 1
  6  0 0 0 1 1 0 1

And solutions are:

A D
B G
C E F

But how come these solutions are valid? Isn't it supposed to be answered like A B E? Where in each row there is only one 1.


texts: Equivalence between alternative definitions of NP

texts:
I'm having some problems in understanding the two alternative definitions of NP. They're presented as equivalent, but to me they seem to define different class of problems. Intuitively, we can think of a non-deterministic TM as branching at every step to check all possible alternatives in parallel. Also, we can see it as guessing the right next state at every stage of the computation. In both cases, if there is a computation path which terminates in an accepting state, the TM is said to accept its input, otherwise it rejects it. On an informal level, we can define NP in two ways.

The class of problems solvable in polynomial time by a NTM. That is, given an instance $x$ of the problem, there is a NTM $M$ which accepts $x$.
The class of problems which can be verified in polynomial time by a TM. In this case, together with the input we get a certificate which provides a proof that $x$ is a solution. We can then check if this is the case by some polynomial time procedure.

Now, what baffles me is that taking the first definition, it would seem as if a NTM would always find the accepting computation path and will thus always be able to accept its input (provided this is in the language recognized by the TM). On the other hand, by the second definition, since we're given only one certificate, $x$ could actually be in the language recognized by $M$, but we cannot tell because we've been given the wrong certificate.

On a second thought, the problem here could be that I'm thinking as a NTM as actually performing a computation, while it is just a theoretical construct. That is, even if we allow the TM to accept if at least one computation path accepts, no one guarantees that a concrete run of the algorithm will "follow" this computation path. So, in this sense we could see the equivalence by stating that, in the case of a verifier, the TM accept if there is at least one certificate which proves that the input is in the language recognized by the TM; this parallels the way in which a NTM needs only to have at least one computation path which accepts the input.

Any deeper insight or also formal derivations would be very appreciated.


texts: finding the combinatorial solutions of series and parallel nodes

texts:
I have n nodes, and I want to find the (non duplicate) number of possible ways in which these nodes can be combined in series and parallel, and also enumerate all the solutions. For example, for n=3, there are 19 possible combinations.
 0 (0, 1, 2)
 1 (0, 2, 1)
 2 (1, 2, 0)
 3 (1, 0, 2)
 4 (2, 0, 1)
 5 (2, 1, 0)
 6 [0, 1, 2]
 7 [0, (1, 2)]
 8 [0, (2, 1)]
 9 (0, [1, 2])
10 ([1, 2], 0)
11 [1, (0, 2)]
12 [1, (2, 0)]
13 (1, [0, 2])
14 ([0, 2], 1)
15 [2, (0, 1)]
16 [2, (1, 0)]
17 (2, [0, 1])
18 ([0, 1], 2)

In the notation above, a series combination is denoted by (..) and a parallel combination is denoted by [..]. Duplicates are removed, for example [0,1,2] is the same as [1,2,0] since all of them are happening in parallel so the order does not matter here.
Can you give me an algorithm for this, or if any such algorithm already exists, then point me to it?
(I tried googling for a solution, but did not hit any relevant answer, maybe I was entering the wrong keywords.)
Note: for a sequential-only solution, the answer is easy, it is n!, and the enumeration of the solutions is also easy. But when parallelism (especially non duplicates) is added to the problem, it gets very complex.


texts: Is there any K-means analog for regression, not culstering?

texts:
Good day
Is there any regression Machine learning model, based on k-means?
Example (Zillow's Zestimate):
I have a lot of houses(with features like sq.feet and location) and prices. I want to estimate price for a new house by averaging k neighbors.


texts:
I'm trying to find an efficient algorithm (running time of O(|V|*|E|)) that finds for any graph an order of the edges that allows Bellman-Ford algorithm to run in a single sweep (iteration).
I was thinking of running some known algorithm that will find the shortest path tree of the given graph and then running Bellman-Ford algorithm on that tree, but I'm not sure if it works.


texts: State of the Art in linear-time DFA minimization

texts:
What is the most complicated kind of deterministic finite-state automaton that can be minimized in $O(n)$ time?

Here’s what I’ve been able to find so far:

The acyclic case has been solved. So any acyclic DFA can be minimized in $O(n)$ time by the Revuz algorithm [2].
As for cyclic automata, an automaton that is a simple cycle can be minimized in $O(n)$ time. A simple cyclic automaton has an underlying graph which is a cycle, and in particular, has states that can be named $1,2,3,…n$ and the only transitions allowed are $1 \rightarrow 2, 2 \rightarrow 3, 3 \rightarrow 4, …, i \rightarrow i+1,…, n \rightarrow 1$.  This is from Almeida and Zeitoun [1], who reference a result in Lemma 4.2 of their paper saying that the primitive root of a string can be found in $O(n)$ time.

Is this the state of the art, or can more complicated automata be minimized in $O(n)$ time?

[1] J. Almeida and M. Zeitoun. Description and analysis of a bottom-up DFA minimization algorithm. Inform. Process. Lett., 107(2):52–59, 2008.

[2] D. Revuz. Minimisation of acyclic deterministic automata in linear time. Theoret. Comput. Sci., 92:181–189, 1992.


texts: Turing machine that can move right only $O(1)$ steps beyond input

texts:
I need to prove that a Turing machine that can move only $k$ steps on the tape after the last latter of the input word is not equal to a normal Turning machine.

My idea is that given a finite input with a finite alphabet the limited machine can write only a finite number of "outputs" on the tape while a normal Turing machine has infinite tape so it can write infinite "outputs" but I have no idea how to make it into a formal proof.


texts: Running Time of naive implementation of Dijkstra's Algorithm

texts:
Here is the "naive" implementation of Dijkstra's algorithm that the professor uses:

For a directed graph $G = (V,E)$ as input
Initialize:

$X = \{s\}$   (the vertices processed so far)

$A[s] = 0$   (computed shortest path distance)

$B[s] = empty path$  (computed shortest path)

Main Loop:
While $X \neq V$:

Among all edges $(v,w) ∈ E$ with $v ∈ X$, $w \notin X$, pick the one that minimizes $A[v] + \ell_{vw}$, where $\ell_{vw}$ is the length of the edge between $v$ and $w$. Call this edge $(v^*,w^*)$ .

Add $w^*$ to $X$.

Set $A[w^*] = A[v^*] + \ell_{u^*w^*}$.

Set $B[w^*] = B[v^*] \cup \{(v^*w^*)\}$.

The running time for this is given as $O(nm)$, where $n = |V|$ and $m = |E|$. I don't fully understand why. He says $n$ is the number of loop iterations, which I understand, but that $m$ is the work per iteration (a linear scan through edges to compute the minimum). But if it's doing $m$ work per iteration, that would imply that it's looking at every single edge in the graph, when it should only be looking at edges that cross the "frontier" between $X$ and $V - X$. Can someone clear up my confusion?


texts: Error correction codes - with strong noise

texts:
I was reading this answer on how error-correction works on magnetic tape recorders for the Voyager space probes.
After watching one or two youtube videos I understand the principle of Hamming-coding and that some sort of this is probably used in encoding the Voyager data.

Also it is known that simple Hamming-encoding can't handle large numbers of errors, particularly when nasty combinations of wrong data and parity appear.

Now if we transmit a Hamming-code, which is essentially 50% error-correction bits, through the solar system in the presence of strong noise sources, this becomes relevant.

Maybe we could think of adding more layers of parity bits that check parity bits, or 'outer codes' to correct those. But then, the stronger the noise source gets, the more encoding we need and so the percentage of actual data transmitted decreases more and more.

I'm by far not an expert in this field, so here's my question:

What kind of smart encoding can we use, when we expect a high percentage of all transmitted bits (including a large percentage of parity bits, which could make a large percentage of the total message) to be corrupted? I guess I'd be satisfied with just the keywords or a good youtube video, then I can google the rest, but ofc a short answer outlining the ideas would be nice!


texts: Numerical Boardgame -- Help with with a pruning method (alpha-beta : minimax)

texts:
I'm developing a simple AI to play a boardgame which consists of N x N squares, each with a predefined value.

44 33 75 12 99 23
53 89 14 01 32 98
34 98 67 45 02 38
89 87 54 21 34 87
65 84 99 72 95 17

Each player can either (a) instant claim an unclaimed cell anywhere on the board, or (b) rush an unclaimed cell from a cell already owned. In the case of (b), any enemy cells that are touching the newly claimed cell are converted to your side.

Example:

Player 1:  (1,1) -- {89}
Player 2:  (3,1) -- {87}
Player 1:  rush->(2,1) -- {98}

In the scenario above, after the rush move, Player 1 now owns all three cells (since (3,1) was an adjacent cell to (2,1)).

I have the MiniMax algorithm working great for this. It's actually quite fun to watch the AI compete against each other. My problem is determining an effective way to prune moves from the tree. I attempted a trivial pruning method of:

 - - If the cell we're claiming is empty
 - - - If the neighbors of the cell we're claiming is empty
 - - - - If the neighbor's-neighbor is an enemy-owned cell
 - - - - - Prune this move

The idea above being, we don't want to claim a cell that could immediately result in the opponent rushing towards us, claiming for themselves the cell we just claimed.

This didn't go well.

I'm a bit at a loss for a decent heuristic for pruning moves at this point. Move ordering is a bit difficult because I can't just choose the highest remaining cell (can I?), since there are plenty of opportunities for the opponent to right-out rush that cell as soon as it's claimed. That is to say, if our opponent owns cell (4,4), it wouldn't be ideal for us to choose (4,2) since it could wind up being immediately rushed. But maybe it wouldn't hurt to start at the largest values and just test them out? I don't know.

Any help here is greatly appreciated.


texts: Scheduling of process manufacturing with setup times

texts:
Overview

The process manufacturing is (in contrast to discrete manufacturing) focused on the production of continuous goods such as oil. The planning is typically solvable by means of Linear Programming, come constraints can be introduced for MILP.

Problem Formulation

The problem consists of

Sequence of consecutive time intervals $t\in\{1,\dots,n_t\}$, each with start and end $(s_t,e_t)$ and length $l_t=e_t-s_t$. Consecutive means $e_{t}=s_{t+1}$ for all $t\in\{1,\dots,n_t-1\}$.
List of type of goods that are being produced: $j\in \{1,...,n_j\}$
Demand of each type of good per time interval $d_{j,t}$.
List of production lines $i\in{1,\dots,n_i}$
Availability of production lines per time interval $a_{i,t}$. $a_{i,t}$ is binary - whether available or not.
Manufacturing speed per production line per type goods $v_{i,j}$.
Setup time from one type of goods to another one $u_{j,j'}$.
Price for using a production line (leasing based), counted per minute $c_{i}$

The goal is to plan the production lines so the demand is covered and the price for leasing is minimal.

Notes:

The setup time can be shorter or longer or equal to the length of the intervals
It is acceptable that the production line will not work the whole time interval if the supply has been completed sooner
The setup to the production of another good can start any time, not necessarily at the beginning of an interval.

Example

There are two production lines, i.e., $n_i = 2$ and there are two types of goods, i.e. $n_j=2$.

We have two intervals, i.e. $n_t=2$, each has a leght of 1 hour. Say one starts at 1 pm, the second at 2 pm.

The demand is:

$d_{1,1}=1.1$
$d_{1,2}=1$
$d_{2,1}=1$
$d_{2,2}=0.5$

The of running the production lines are:

$c_{1} =c_{2} = 1$ USD/minute

All possible setup times are 30 minutes, i.e.:

$u_{j,j'}=0.5$ for all $j,j'$ where $j\neq j'$.

The speeds are:

$v_{1,1}=1.1$
$v_{1,2}=1.5$
$v_{2,1}=1$
$v_{2,2}=1$

Obviously, the demand is met if the first line is producing the first type of goods at both intervals and the second line is producing the second type. The cost is 204.55. See the solution here:

However, it might be tempting to switch them. Line 1 is much more efficient for the second type of goods (1.5). If there would be no setup time, we would have the cost 180 USD. However, this is not possible.

Question

What is the algorithm to schedule this manufacturing process optimally?

An answer is welcome even if it would outline the way and approach (MILP, SAT, CSP,...).

Ideas fo far

If the length of intervals would be fixed, say 1 hour and the setup time would be defined in terms of these units, say 2 hours. Then, it might be solvable by SAT/CSP.
An idea is to use an evolutionary algorithm that would: consist of a sequence of activities with mutations (add an activity, delete activity, prolong activity) and crossover (mix two plans in a random way).


texts:
I am working with some research problem connected loosely to TSP which requires to find the Minimum Spanning Tree of a fully connected, weighted graph, where all the weights are positive and the graph is undirected (just like in Christofides algorithm). The point is, the problem I am working on requires me to find the MST with possibly lowest diameter (the number of nodes on the longest path between any two leaf nodes, equivalently, for the purpose of measuring the diameter one can treat all the edges of the MST as if they had the weight equal to 1).

I know that Boruvka's, Prim's and Kruskal's algorithm can be used to find some MST, but can I influence them somehow to prefer the shortest (in the terms of the diameter) trees possible?

If the answer to the question above is negative, are there any algorithms or methods which either yield MST with some bounds on the tree diameter or, at least, are there any known methods of obtaining a bound on MST diameter for a given graph?


texts: Why cannot match $ Bool \equiv Bool $ with $ refl $ while $1 \equiv 1$ can?

texts:
This code depends on agda-stdlib:

{-# OPTIONS --without-K #-}
open import Data.Nat
open import Data.Bool

open import Relation.Binary.PropositionalEquality

-- this code doesn't check, cannot match e with refl
why : (e : Bool ≡ Bool) -> ℕ
why refl = zero

but-why : (e : 1 ≡ 1) -> ℕ
but-why refl = zero

I know K-rule means I cannot match $ \forall a.a \equiv a $ with $ refl $, but if $a$ is a concrete value, it can (i.e. $1 \equiv 1$ can be matched with $refl$).
But why I cannot match $Bool \equiv Bool$ with $refl$? Why is type and value treated differently in a dependently-typed programming language?

(Maybe related: What does it mean if we disable K-rule in Agda?)


texts: Myhill-Nerode style characterization of CFL?

texts:
Define the Nerode equivalence over a language $L \subseteq \Sigma^{*}$ as $u \sim_L v$ iff $uw \in L \Leftrightarrow vw \in L$ for every $w \in \Sigma^{*}$.

The Nerode equivalence ${\sim}_L$ has finitely many equivalence classes precisely when $L$ can be recognized by a finite-state automaton.  This is the Myhill-Nerode theorem.

  Is there a similar characterization of context-free languages?

Motivation:

The Nerode equivalence classes each correspond to a distinct state in any automaton that recognizes $L$.  Each CFL can be recognized by an NPDA, which has a finite number of states but also a potentially unbounded stack of alphabet symbols.  The stack keeps track of one possible way that a string can be parsed.  The number of equivalence classes may be infinite since the stack can store an unbounded number of symbols.

I am asking: is there always a way to clump together equivalence classes so that each clump represents one state of the PDA, with each class within the clump representing equivalent states of the stack for that PDA state?

For instance, the language of properly nested parentheses only needs states to handle pop and push, as the stack will keep track of the current nesting depth.  If such clumping can always be done, then whether the number of clumps is finite determines whether the language is context-free.

As pointed out by @sdcvvc in a comment, a form of this question was asked as https://math.stackexchange.com/questions/118362 although Yuval Filmus's answer to the related question at Example of a non-context free language that nonetheless CAN be pumped? is more relevant.


texts: polynomial time reducibility - $L_{2} \notin \textbf{P}$ and $L_{1} \leq_{p} L_{2} \implies L_{1} \notin \textbf{P}$

texts:
If we have two languages $L_{1} \subseteq \Sigma^{\ast}_{1}$ and $L_{2} \subseteq \Sigma^{\ast}_{2}$

I proved that when $L_{2} \in \textbf{P}$ and $L_{1}  \leq_{p} L_{2}$ then $L_{1} \in \textbf{P}$

Is it also true that when $L_{2} \notin \textbf{P}$ and $L_{1}  \leq_{p} L_{2}$ then $L_{1} \notin \textbf{P}$? I don't think it's, but I can't find a counter-example.


texts: Simplify logical expression represented as binary tree

texts:
I implemented logical expressions using a binary tree in C++. Now I want to be able to simplify such an expression using rules like e.g.

but have issues with the commutativity. Assuming the expression is

then the tree would look like this:
       xor
       /\
     xor b
     /\
   xor true
   /\
true a

The expression can be simplified:

but I don't know how to apply the above rule to this tree since it is never directly applicable to one of the subtrees. Is there a better way than having to rotate the tree in all possible orders?


texts: What is the complexity of the algorithm to calculate power set of a set?

texts:
Below is an algorithm to compute the power set of a set. To my understanding, for a set with cardinality n, there is a for loop iterating 2^(n-1) times. Hence the time complexity has to be O(2^n).

However, the time complexity as per the solution, is O(n*2^(n-1)). What mistake am I making?

Arraylist < Arraylist < Integer >> getSubsets(Arraylist < Integer > set, int index) {
    Arraylist < Arraylist < Integer >> allsubsets;
    if (set.size() == index) { //Base case - add empty set
        allsubsets = new Arraylist < Arraylist < Integer >> ();
        allsubsets.add(new Arraylist < Integer > ()); // Empty set
    } else {
        allsubsets = getSubsets(set, index + 1);
        int item = set.get(index);
        Arraylist < Arraylist < Integer >> moresubsets
        new Arraylist < Arraylist < Integer >> ();
        for (Arraylist < Integer > subset: allsubsets) {
            Arraylist < Integer > newsubset = new Arraylist < Integer > ();
            newsubset.addAll(subset); //
            newsubset.add(item);
            moresubsets.add(newsubset);
        }
        allsubsets.addAll(moresubsets);
    }
    return allsubsets;
}

The pseudocode looks like:

// set: The set[0:n-1] which the power set has to be computed for
set getSubset(set):
    1. set_size = size(set)
    2. set_size == 1:
        2.1 return [{}, set]
    3. power_set_of_subset = getSubset(set[0:set_size-2])
    4. last_element = set[set_size-1]
    5. power_set_of_set = power_sets_of_subset
    6. for subset_of_subset in power_set_of_subset:
        6.1 subset_of_subset.add(last_element)
        6.2 power_set_of_set.add(subset_of_subset)
    7. return power_set_of_set


texts: Canonical infinitely ambiguous languages

texts:
In an article I am currently reading the grammar

S → SS | a | ε

is being described as canonical infinitely ambiguous. The infinitely ambiguous part I have no problem recognizing, but does "canonical" mean? Does it mean "typical", "standard example" etc.?


texts: Did anyone successfully implemented Gödel machine? Is it practically possible to implement?

texts:
For reference - Gödel machine is a hypothetical self-improving computer program that solves problems. It uses a recursive self-improvement protocol in which it rewrites its own code when it can prove the new code provides a better strategy. So let's say you have a program which solves TSP using Simulated Annealing, you leave it running through the night and in the morning it rewrote itself so now it uses Genetic Algorithm. A self modifying code. Did anyone ever implemented something like that? According to linked book I found there are some implementations but I've never seen any project actually working. If any actual implementation doesn't exist is it possible to implement it in practice?

Link: https://link.springer.com/chapter/10.1007/978-3-642-22887-2_29


texts:
In the bin packing problem, there are some $m$ items of size less than $1$, and they have to be packed into as few as possible bins of size $1$. The problem is NP-hard, but if we are allowed to break some items then it becomes easy, since each bin can be filled completely.
What if we are allowed to break (to as many pieces as we like) only $k$ items of our choice, where $k$ is a fixed constant - is the problem still NP-hard?


texts: Maximum number of multiples of an array element preceding it

texts:
Given an array of size $n$, we have to find the maximum number of multiples of $A[i]$ in the array, where the indexes of the multiples should be less than $i$.

For example, given the array

  36 40 16 24 27 12 9 4

We see that element 4 has the highest number of multiples (5) as per the given conditions, so the answer is 5.

My approach: I used brute force to solve this. I used nested loops to solve this. The first loop from the last element and the second loop from the first element to the second to last element.

Can you help me improve the running time?


texts: A fast algorithm for a simple multi-objective minimization?

texts: I have a set $S$ of $n$ (arbitrary) integers which I want to partition into subsets $S_1, \dots, S_k$, each of size $n/k$ (you can assume that $k$ divides $n$). Let $A$ be the arithmetic mean of elements of the set $S$. I am looking for the fastest algorithm that fills each $S_i$ with elements of $S$ such that sum of the elements of each $S_i$ is as close as possible to $A$. Essentially, this is a multi-objective minimization problem and I am looking for Pareto-minimal solutions. The complexity of the brute-force algorithm is $O(n!)$. I am wondering if there exists a faster algorithm.


texts: Does the undecidability of the halting problem require Turing Machines to be enumerable?

texts:
I (think I) understand the enumeration and then diagonalization proof of the undecidability of the halting problem, but I came cross this proof in SICP below, which does not seem to require the enumeration. Did I miss anything?

(define (run-forever) (run-forever))

(define (try p)
  (if (halts? p p)
      (run-forever)
      'halted))

I suspect this has to do with how a TM is encoded, i.e. the parameter for try. Being able to encode a TM might require enumeration? But I'm still very confused.


texts: What is the largest number of Byzantine failures that can be tolerated in an $m$-dimensional hypercube for the consensus problem?

texts:
We are given a system with $n$ nodes which have been arranged into the topology of a hypercube of $m$ dimensions. I would like to derive a tight bound on the maximum number of Byzantine failures that can be tolerated in this system.

One upper-bound that I have derived on the number of failures $f$ is from the fact that consensus cannot be solved in a system if

connectivity of the graph $G$ i.e. $conn(G) > 2f$
$n > 3f$

Since the connectivity of an m-dimensional hypercube is $m$, this gives us that $$f < \min\left(\frac{2^m}{3}, \frac{m}2\right)$$

But I am unable to show that this upper-bound is tight. This bound is tight for $m = 2$ since then the topology is a ring and $0$ failures can be tolerated in a ring topology.

I need pointers to show that this bound is tight (I think that too show this we need to give an algorithm that solves consensus under these conditions) or show some tighter upper bound (probably by reduction?)

Also why are conditions 1 and 2 necessary and sufficient only for the weak Byzantine consensus as proved in Nancy Lynch's Distributed Algorithms Theorem 6.30? My intuition is that if the connectivity of the graph is $\ge 2f+1$ then we have $2f+1$ disjoint paths between any two pair of nodes due to Menger's Theorem. Since there are only $f$ Byzantine nodes, they can corrupt at most $f$ paths and thus the majority of the paths should communicate reliably and we can solve consensus as if it were for a complete subgraph consisting of only the non-faulty processors.


texts: Formula to see where a memory address can be depicted in cache?

texts:
I've been trying to find a formula that helps us identify where an address can be depicted in cache. I remember my  professor talking about some kind of division but I can't find it in my textbook nor internet (maybe I am not searching the right words). For example:
I have a cache that has $2^{14}$ blocks, each 32 bytes, and it is 8-way associative with $2^{11}$ sets and each address is 64 bits. So we have 48 bits for the tag, 11 for the index, and 5 for the offset. I would like to answer the following question:

Where can we find in cache, the addresses 300A21 (hex)?

My obvious answer is to convert it into a binary address: 0011 0000 0000 1010 0010 0001, and now, we know that index is  0000 1010 001, so it has to be into the set with this index (it is the 81st), and since
0 0001 is the offset, I guess that since we count from 0, it is the second word on the block (?).
Is there anything else I can say? Something that involves a division or modulo of the address?


texts: Is function with finite amount of $\Phi_x(x+1)$ occurrences Turing computable?

texts:
I'm studying for my exam from Logic and Computability and we have to face following kind of examples:

$$f(x) = \begin{cases}
         \ 1 &\text{if }\Phi_x(x+1)\!\downarrow\text{ and }x\leq50\\
         \ 0 &\text{otherwise.}
\end{cases}$$

Unfortunatelly I'm not really clear on how to tackle those. $\Phi_x$ is the $x$-th computable function, thus it's also Turing computable. This implies, there exists a TM (we have $N$ of them) which halts and returns the output.

The task is to determine whether it's computable. In order to prove it we either provide an informal algorithm to show it's computable or a formal proof that it's not. Can any of you solve this example?

If $f(x)$ is computable, then $\Phi_x$ needs to halt for every $x \in\{1, \dots, 51\}$. However $\Phi_x$ could be undefined on one of the elements from $\{1, \dots, 51\}$ and keep looping forever.

At the other hand, there is an upper bound on $x$, which indicates its computability.

Please, can you show me the right direction?

Thanks!


texts: Why can L3 caches hold only shared blocks?

texts:
In a recent CACM article [1], the authors present a way to improve scalability of shared  and coherent caches. The core ingredient is assuming the caches are inclusive, that is higher-level caches (e.g. L3, one global cache) contain all blocks which are stored in their descendant lower-level caches (e.g. L1, one cache per core).

Typically, higher-level caches are larger than their respective descendant caches together. For instance, some models of the Intel Core i7 series with four cores have an 8MB shared cache (L3) and 256KB private caches (L2), that is the shared cache can hold eight times as many blocks as the private caches in total.

This seems to suggest that whenever the shared cache has to evict a block (in order to load a new block) it can find a block that is shared with none of the private caches² (pigeon-hole principle). However, the authors write:

  [We] can potentially eliminate all recalls, but only if the associativity, or number of places in which a specific block may be cached, of the shared cache exceeds the aggregate associativity of the private caches. With sufficient associativity, [the shared cache] is guaranteed to find a nonshared block [...]. Without this worst-case associativity, a pathological cluster of misses could lead to a situation in which all blocks in a set of the shared cache are truly shared.

How is this possible, that is how can, say, 1MB cover 8MB? Clearly I miss some detail of how such cache hierarchies work. What does "associativity" mean here? "number of places in which a specific block may be cached" is not clear; I can only come up with the interpretation that a block can be stored multiple times in each cache, but that would make no sense at all. What would such a "pathological cluster of misses" look like?

Why On-Chip Cache Coherence is Here to Stay by M. M. K. Martin, M. D. Hill, D. J. Sorin  (2012)
Assuming the shared caches knows which blocks are shared where. This can be achieved by explicit eviction notifications and tracking bit, which is also discussed in [1].


texts: Data structure for interval subset queries

texts:
I have a set $S$ of intervals.  I'd like to store them in a data structure, so that I can handle the following query efficiently: given a query interval $q$, count the number of intervals $s \in S$ that contain $q$, i.e., count the number of intervals $s \in S$ such that $q \subseteq s$.
(This is like a stabbing query, but now the query is an interval, not a single point.)
Is there an efficient data structure for this?  Ideally, one that can be constructed in $O(n \log n)$ time and where each query can be answered in $O(\log n)$ time, where $n$ denotes the number of intervals in $S$?


texts: Given a set C of set P of sets R, find the smallest set S such that at least one subset R from each P is a subset of S

texts:
Given a universal set of elements $\mathbf{U} = \{a_1, a_2, .., a_n\}$, a set $\mathbf{R} = \{a_i\} \subset \mathbf{U}$ where $i ϵ \{1, .., n\}$, a set $\mathbf{P} = \{R_1, .., R_m\}$ and a set $\mathbf{C} = \{P_1, P_2, .., P_l\}$, how do I go about finding a set $\mathbf{S} = \{a_1, .., a_n\} \subset \mathbf{U}$ such that at least one set $\mathbf{R}$ from each  $\mathbf{P}$  is satisfied and such that the size of $\mathbf{S}$ minimal?  I consider the set $\mathbf{R}$ to be satisfied by $\mathbf{S}$ if $\mathbf{R} \subseteq \mathbf{S}$.

This seems similar to set cover problem, but I am not sure how I can approach this.


texts: What is a disequality path in the context of equality graphs?

texts:
A path consisting of a number of disequality edges and a single equality edge

A path consisting of equality edges

A path consisting of a number of equality edges and a single disequality edge

A path consisting of disequality edges

The answer is number three, right? Who has any reasonable doubts or general short references?


texts: Applicative-order languages don't support constant time array writes? If not, why not?

texts:
I'm reading Steven Skiena's "The Algorithm Design Manual", and in one of his War Stories on page 155 he states:

  Efficiency is a great challenge in Mathematica, due to its applicative
  model of computation (it does not support constant-time write
  operations to arrays) and the overhead of interpretation (as opposed to compilation).

I've already read SICP so I'm familiar with the difference between applicative and normal-order languages (i.e. that normal-order languages delay evaluation of procedure arguments until they're needed, whereas applicative-order languages evaluate them as soon as the procedure is called).  But Skiena's sentence above appears to link the idea of applicative-order languages with the idea of worse-than-constant-time array writes.  I don't remember Abelson and Sussman mentioning this in their text, so this came as a surprise.

If true, what are the under-the-hood reasons for why applicative-order languages don't write to arrays in constant time?  Why would the order of evaluation matter in determining array write time?

I'm also curious what the Big-O write performance is in this case, but I imagine that depends on the language implementation, so I'll skip that question unless there's a definitive answer.


texts: Binary Floating Point Range/Precision for 4-bit Mantissa and 4-bit Exponent

texts:
I'm trying to understand binary floating point and using just a 4-bit mantissa and a 4-bit exponent (both 2s compliment) to keep things simple.

As far as I can tell, the largest denary number I can represent is 112: 0111 0111

So why do I have trouble representing denary 11 (eleven) in this system? I get that the largest (positive) mantissa is 7 in denary (0111). So I'm inferring that I can't represent consecutive positive integers between 0 and the maximum value of 112.

Is that correct? If so, can someone help me to see why please? Which numbers in this range can I represent?


texts: Sifting algorithm for group generated by a set

texts:
On page 38 of  "Lecture Notes in Computer Science" by Christoph M. Hoffmann, there is an algorithm (ALGORITHM 2).

I have some confusions.

Why it is written that an entry $M_{i,j}, j < i$, cannot be referenced? what is the meaning  of "reference" here?

Thanks.


texts: Restricted traversal on an undirected graph

texts:
Given a undirected graph $G=(V,E)$.

Imagine traversing the Graph was restricted; following an edge $a$ over a node $v$ to an edge $b$ is allowed if and only if a function $w: ( a, v, b ) \rightarrow \{0,1\}$ returns $1$.

Is there a effective solution to find the shortest path between two nodes without trying every possible path on the graph? (Since without visiting every node from every possible direction it is not guaranteed to follow every edge that might exist. Also, just remembering if a node has been already visited nor not does not fit anymore since there might be other leaving edges allowed to take - depending on the incoming edge that had been taken. )

Also, is there a more common formulation of this problem (e.g. “restricted traversal”) ?


texts:
I need to choose the highest value combination of items given a specific set of constraints. These constraints are:

Exactly 6 items from group A and 2 items from group B must be selected.
Items in group A and group B count towards the same maximum weight.
No item can be selected more than once.
No more than 2 items of the same 'color' can be selected (there is always exactly 2 of each color in group A and 1 of each color in group B).

Example data set:

Group A
Item  -  Weight  -  Value  -  Color
A01  -  32  -  59  -  Teal
A02  -  31  -  65  -  Teal
A03  -  29  -  57  -  Red
A04  -  27  -  16  -  Red
A05  -  25  -  07  -  Orange
A06  -  25  -  20  -  Purple
A07  -  24  -  06  -  Orange
A08  -  23  -  39  -  White
A09  -  22  -  20  -  White
A10  -  21  -  23  -  Purple
A11  -  21  -  31  -  Blue
A12  -  20  -  16  -  Green
A13  -  20  -  17  -  Blue
A14  -  19  -  45  -  Green
A15  -  18  -  22  -  Black
A16  -  18  -  14  -  Yellow
A17  -  17  -  08  -  Yellow
A18  -  17  -  22  -  Gray
A19  -  16  -  13  -  Black
A20  -  16  -  26  -  Gray

Group B
Item  -  Weight  -  Value  -  Color
B01  -  36  -  85  -  Teal
B02  -  33  -  39  -  Red
B03  -  31  -  48  -  Purple
B04  -  30  -  28  -  Orange
B05  -  29  -  71  -  White
B06  -  24  -  65  -  Blue
B07  -  23  -  64  -  Green
B08  -  22  -  61  -  Yellow
B09  -  21  -  36  -  Black
B10  -  20  -  27  -  Gray

Max weight = 200

I'm not necessarily looking for a solution to this problem. I have found all sorts of ways to solve many variations of problems that seem very similar to this, but none seem quite right. If I just knew what to look for, I'm sure I'd be able to find an example and figure out the rest from there.

The closest I've been able to get is an 0/1 multi-knapsack (or maybe multi-dimensional knapsack?) problem. Does anyone have a better description of this problem? Thanks in advance!

Edit: Oh, bonus question, if anyone has any recommendations for languages which are particularly well suited to this type of problem (I was thinking python for itertools), I'd greatly appreciate it.


texts: General Understanding of SMT Solving Across Multiple Theories

texts:
My first question was a little too simplified in that it turned out to be an integer linear programming problem solvable with the Simplex Method. However, what I think I am wondering about is how to solve constraints across multiple theories, as with SMT solvers. To demonstrate, I have created a set of constraints using (I think) the theories of strings, arrays, integers, real numbers, bit vectors, and (I just made it up) files. Here are the variables:

x: a string variable
y: a string variable
a: an array variable
b: an array variable
i: an integer variable
j: an integer variable
m: a real number variable
n: a real number variable
v: a bitvector variable
w: a bitvector variable
p: a file variable
q: a file variable
r: a boolean variable
s: a boolean variable

And here are the constraints:

exists(x) && exists(y)      // String theory + Existence theory?.
  && length(v) > length(w)  // Bitvector theory.
  && length(x) != length(y) // String theory.
  && i > j                  // Integer theory.
  && m > n                  // Real number theory.
  && r || s                 // Boolean theory.
  && read(p) != read(q)     // File theory.
  && a[i] != a[j]           // Array theory.
  && a[i] != i              // Array theory mixed with integer theory.
  && m != i                 // Real number theory mixed with integer theory.
  && j > length(x)          // Integer theory mixed with string theory.
  && match(read(p), y)      // String theory mixed with file theory.
  ...

First question is if I am conceptualizing this correctly. I don't know if I am using the word "theory" in the list of constraints properly. For example, "Array theory mixed with integer theory", wondering if that example is correct.

The main question is the general way to go about solving this problem. I assume this is an SMT problem, since it involves more than just Boolean variables. Wondering if I somehow break this apart, normalize it into CNF, or otherwise divide it into pieces that can be solved independently. And then how to integrate the solutions. The reason I ask this part of the question is because I have seen the Nelson Oppen method suggesting how to combine theories (but I am not that far in my understanding yet). I am still trying to get a grasp of how to translate common programming constraints (like what I demonstrated above) into something acceptable to an SMT solver.

I am not asking about how to actually solve this problem, because from my understanding so far, each theory would require its own complex set of decision procedures (algorithms). I am just wondering what the general steps are for solving this problem of:

  How to find values for $x$, $y$, $a$, $b$, $i$, $j$, $m$, $n$, $v$, $w$, $p$, $q$, $r$, $s$ such that the constraint system is satisfied.

I sort of understand how the DPLL algorithm works, but this implies I have all my variables ready for a SAT solver (i.e. in Boolean form), which these variables clearly aren't. So I'm not sure if I should do some preprocessing step to get them into boolean form, or something entirely different.

I am basically looking for a set of steps outlining the process for solving the problem, so I know where to direct where I look. Something like:

Divide the variables into disjoint sets by theory.
Solve each theory independently. The goal is to output a boolean variable for each chunk in the theory.
Combine the theories into a single set of Boolean clauses.
Apply a SAT solver algorithm such as DPLL or CDCL to the Boolean clauses to get the variable valuations that satisfy the constraints.

(That is basically what my understanding is, which is clearly missing some pieces and is misdirected in other parts). But a list of some sort like that is all I am looking for to help guide search.


texts: I've read this which describes how to do do integer arithmetic in circuits. The one thing that it does not describe is how to do these operations with a modulus. How can modular arithmetic be done in circuits? Can someone point me to a resource or describe the modular step here?


texts: Optimal Selection of Non-Overlapping Jobs

texts:
I'm trying to find what the family of problem is - as well as an approach - for the following:
I have a set of tasks T = [t1, ..., tn] to do, each of which has a corresponding reward ri.
Each task takes place during a fixed interval - ie: task 1 is from times 1-4, task 2 from 2-5, and task 3 from 9-15.
This means that I would have to pick either task 1 or 2 depending on which is more valuable, and then task 3 which does not conflict with either of the previous.
I'd like for this to scale to n tasks, and also to m "CPU's" - where more than one task can be executed in parallel.
This reminds me of the knapsack problem, but maybe an interval graph would provide a better approach?
Any suggestions on how to approach this problem, or any relevant references?


texts: Has anyone found polynomial algorithm on Hamiltonian cycle isomorphism?

texts: As the title says, has anyone found a polynomial time algorithm for checking whether two graphs having a Hamiltonian cycle are isomorphic? Is this problem NP-complete?


texts:
How can one show that the counting problem:
Given a  graph, output the number of perfect matchings
Is self reducible?
I found a hint in Moore's Chapter on Counting, Sampling and Statistical Physics:

Let G be a graph and e one of its edges. Show that we can modify G to
produce two graphs, G0 and G1, such that the number of perfect matchings
of G that include and exclude e is the number of perfect matchings of
G1 and G0 respectively.

But I could not come up with a proof. The main question here is: How can we proof self-reducability of #perfectMatchings?
Aside: I don't know of a formal definition of self-reduciability. I just know the intuitive phrasing "partially solving the problem results in a smaller problem of the same kind". But is there a formal definition?


texts: Loop variant for a while loop that occasionally doesn't decrease?

texts:
I'm working on practice problems for a test I have, and every example of loop variant decreased with every iteration of the loop. On this one, the values remain the same when a < b. My attempts also got me a loop variant that has a chance of a negative since occasionally a becomes larger than b and vice versa. Any advice on attempting to find and prove the loop variant for this question?

def mystery(a,b):
# Precondition: a >= 0 and b >= 0
while a >= 0 and b >= 0:
    if a < b:
        a, b = b, a
    else:
        a = a - 1
return a

EDIT: For anyone who is interested in this question, my best solution is as follows.

$$f_{1} = a + 2b + 1$$


texts: Intuitive explanation of neutral / normal form in lambda calculus

texts:
It is possible to distinguish Normal terms which don't contain beta redex as a sub-expression, from others like so

data WithBound a = Var | Other a

data Normal a
  = Neutral (Neutral a)
  | Abstract (Normal (WithBound a))

data Neutral a
  = Variable a
  | Apply (Neutral a) (Normal a)

Is there any intuitive explanation as to why this property would hold ?
It might be entirely self-evident somehow after you look at it long enough but it does not prompt straight out to me as of now.


texts: Does DFS have better constants/complexity than Backtracking on a Graph?

texts:
I came to know through some examples that DFS and Backtracking aren't exactly the same ( A misconception I had since a long time). So now my question is, since Backtracking visits nodes backwards step by step while DFS on a graph may directly jump some nodes backwards, is DFS a faster algorithm? If so, only in terms of constants or complexity wise?
Edit:
Maybe the original writeup was a bit confusing. What I mean specifically is this.
DFS:

A normal implemetation of DFS should traverse the following tree in this manner A->B->C->D. This implies that the implementation for what we normally refer to as DFS visits each node exactly once, giving it a time complexity O(V) where V is the number of vertices.
By Backtracking, what I have in mind is this:

This I feel is a more bare bones approach where one step of backtracking actually goes to a parent node and explores its other children, instead of skipping over some parent nodes which had only one child (node B here) to begin with. This results in a traversal sequence of A->B->C->B->A->D. This particular example shows that this is always going to require more nodes to be visited than the standard DFS and hence the question.


texts:
Will the Traveling Salesman Problem (TSP) become easier if the simple path constraint is omitted?
That is, each node in the topological graph should be visited once at least (instead of exactly).

Is it still NP-complete or reduced to a P problem?
How would this modification affect classical methods for solving the original TSP such as dynamic programming, mixed integer programming, meta-heuristics and maybe branch-and-cut/bound/price?

What I have tried:

I believe this variant might be easier to solve, but after a sketchy thought about the MIP model, I found it is hard to write the sub-tour elimination constraints.

I have checked TSP Where Vertices Can be Visited Multiple Times but it is asking for a working solution which could be a heuristic that does not guarantee the optimality and computational time. This is not what I want.


texts: Can x86 Instruction Set be changed with microcode update?

texts:
How I understand microcode translate an instruction to microinstructions. And CPU has a unit that stores all possible of microinstructions. These microinstructions can be changed, because it load every time after boot from motherboard. Can instruction set be changed?
I am sorry if i ask strange question, if I misunderstood , please correct , thanks
and again I am sorry if my English grammar is bad. (google translate)


texts: Show that $x^3 = O(x^4)$ and $x^4 \neq O(x^3)$


texts: Software code generation from the (operational) semantics - reference request for automatic programming

texts:
Are there research trends that try to research code generation directly from the (operational or some other kind of) semantics? One can imagine cognitive architecture that discovers and reasons about the tasks that the software should do and constructs the operational semantics of some program. And later there should be only one additional small system that generates software code from the semantics for the execution on well established platforms.

In such a way one can avoid the uncertain and rigorous path that goes through discovery and generation of formal specification that requires rigorous reasoning (sometimes undecidable, sometimes exponentially hard). Use of cognitive architecture and generation of the operational semantics (or some other semantics) allow one to do approximate, uncertain reasoning which cancels undecidability or exponentiality by discovery of additional axioms or shortcuts.

This is reference request question. Of course, I can use Google, but my experience is that computer science often names the research themes and terms differently than I have them imagined firstly and there is no reliable semantic search. So - reference request is necessary.


texts:
Give two Prolog implementations to calculate the sum of first N numbers divisible by 3. For example: N=4 -> 30 (3+6+9+12).
sum(N,I,C,C):-!.
sum(N,I,C,R):-
    I mod 3 =:= 0,
    C1 is C+I,
    I1 is I+1,
    sum(N,I1,C1,R).
sum(N,I,C,R):-
    not(I mod 3 =:= 0),
    I1 is I+1,
    sum(N,I1,C,R).

I tried like this, but it's not a good way of thinking. Can somebody help me, please?


texts: CFG for $L=\{ \omega \in \{ a,b,c,d \}^* : |\omega|_a = |\omega|_b \}$

texts:
Given the language:

  $$ L=\{ \omega \in \{ a,b,c,d \}^* : |\omega|_a = |\omega|_b \} $$

I propose the following grammar:
$$ \begin{align*}
S &\to \varepsilon \mid aSbS \mid bSaS \\
S &\to cS \mid dS \mid Sc \mid Sd
\end{align*} $$

I want to know if this is correct or if there exists a smarter grammar (a shorter grammar).


texts: $T(n)=2T(n/2)+n\log n$ and the Master theorem

texts:
According to  Introduction to algorithms by Cormen et al,
$$T(n)=2T(n/2)+n\log n$$ is not case 3 of Master Theorem. Can someone explain me why?

And which case of master theorem is it?


texts:
So, in the book I'm studying from it says :

  The statement “f(n) is O(g(n))” means that the growth rate of f(n) is no more than the growth rate of g(n).

What I understood from this statement is that since 9n is O(n), the growth rate of the functions 9n and n have the same growth rate, which does not make sense. I know that growth rate is the increase of a certain quantity over time. So, obviously the function 9n will grow way faster towards infinity, than the function n.

Did I understand the sentence given in the book incorrectly or is the statement incorrect?


texts:
Let $C $ be a self-dual binary $[n,k,d]$ code.

I want to show that if $ c=(c_1, \dots, c_n) \in C $ then $ \sum_{i=1}^n c_i=0$ and that all the words of the code have an even weight.

We know that $ x \in C^{\perp} \Leftrightarrow Gx=0$ where $ G $ is the generator matrix.

Since $ C=C^{\perp}$ we have that  $ G=H $ where $ H$ is the parity matrix of the code.

So we have that $ c=(c_1, \dots, c_n) \in C \Rightarrow c \in C^{\perp} \Rightarrow Gx=0 \Rightarrow Hx=0 $

Do we get from that,  that $ \sum_{i=1}^n c_i=0$?

If so how?


texts: Arranging Colors in a Grid; Two Dimensional TSP?

texts:
I am working on an interesting problem, which I believe can be solved algorithmically. I have a 6x8 on which I am attempting to arrange 48 color swatches, such that the transition from each swatch to its neighbor is as smooth as possible.

I can compute perceptual color differences using LAB-space encoding, so it is simple to generate a matrix of color differences. If I were attempting to simply order these colors, it would essentially be the traveling salesman problem; and I could use some heuristic solutions to get a near optimal result.

However, arranging the colors into a grid introduces a new dimension. In the interest of symmetry, we can wrap the edges of the grid so that each swatch has exactly 4 neighbors.

I have a hunch that this problem reduces to the following graph problem: Given a fully connected weighted graph of 48 nodes, find a subset of this graph such that the resulting graph is fully connected, each node has exactly 4 edges, and the sum of edge weights is minimized.

Any ideas on existing algorithms that might be helpful in solving this problem? Approximate solutions and heuristic solutions are acceptable as I imagine this problem is in EXP.


texts: Asymptotic analysis with factorial and exponential

texts:
I'm solving a complexity question where I have:

$$ n!/2^n $$

The goal is to find an upper bound for this.

My idea is using the fact that:
$$ n! = O(n^n)$$
$$ n!/2^n = O((n/2)^n) = O(n^n)$$

But is a correct upper bound, and if so is it the tightest upper bound that can be found? I know that n! is asymptotically larger than 2^n, but I'm struggling to do a tighter analysis.


texts: Given a bitonic sequence $a_1, a_2, \ldots, a_n$ , calculate the median in $O(\log n)$

texts:
This is a question in my textbook, it requires me to write an algorithm to find the median of a bitonic sequence in $O(\log n)$, where $n$ is the number of elements (a bitonic sequence is a sequence that is non-increasing first, and then it's non-decreasing after some point). How do I approach this? I feel like it has something to do with the medians of the 2 parts (the non-increasing and non-decreasing parts of the sequence), but I couldn't find a way to solve it from there.
Any help would be much appreciated. Thank you.


texts:
This is a very elegant implementation of prefix-span algorithm by the maintainer of the prefixspan pip package. However, I am having a hard time understanding the reason behind the implementation. The result by localOccurs doesn't really make any sense to me. Can I get a overview of what each part of this implementation achieve? particularly what mine_rec and localOccurs do. Thanks!
#! /usr/bin/env python3

from collections import defaultdict

db = [
    [0, 1, 2, 3, 4],
    [7, 6, 5, 3, 4],
]

minsup = 2

results = []

def mine_rec(patt, mdb):
    def localOccurs(mdb):
        occurs = defaultdict(list)

        for (i, stoppos) in mdb:
            seq = db[i]
            for j in range(stoppos, len(seq)):
                l = occurs[seq[j]]
                if len(l) == 0 or l[-1][0] != i:
                    l.append((i, j + 1))

        return occurs

    for (c, newmdb) in localOccurs(mdb).items():
        newsup = len(newmdb)

        if newsup >= minsup:
            newpatt = patt + [c]

            results.append((newpatt, [i for (i, stoppos) in newmdb]))
            mine_rec(newpatt, newmdb)

mine_rec([], [(i, 0) for i in range(len(db))])

print(results)


texts: Minimal regular expression that matches a given set of words

texts:
I have a dictionary-like regular expression, an "or chain" of words,

word1|word2|word3|...

Unfortunately, the chain is too large.  I'd like to find the minimal regular expression that is equivalent.  How can do I do that?

You should think of this as a regex like /^(word1|word2|word3)$/.  I have a dictionary of words, and I want a minimal regex that will match if and only if the input string is a word in that dictionary.  By minimal, I want the shortest regex that matches all words in the dictionary (and nothing else).  I need a regex, not some other representation.

The words come from SQL SELECT DISTINCT word FROM t ORDER BY length DESC, word so I'm hoping for a solution that is optimized to practical use.

I was able to identify some heuristics that work for some special cases, but not a general algorithm:

It's easy to deal with accented variations: mãe|mae becomes ma[ãe]e).  This works fine.
Also, ABCCC|ABCC|ABC|DF can be automatically reduced to (output) ABC{1,3}|DF or AB(?:C|CC|CCC)|DF

As @Raphael noted, "minimizing regular expressions is hard", so it is important the focus on non-generic solutions.

I found a web page that describes how  to convert a regex to NFA or DFA, but that doesn't help me get back a minimal regular expression.  I'm willing to use an existing library, such as this PHP one, but how do I use the library for this purpose?


texts: Maximizing the minimum of $k$ submodular functions

texts:
Let $f(X)$ be a monotone submodular function from $2^{\{1, \ldots, n\}}$ to $\mathbb{N}$ and consider the problem of maximizing it subject to a cardinality constraint $|X| \leq m$. By using the greedy algorithm, it is possible to obtain a $1-1/e$ approximation (see, for example, these lecture notes).

But now suppose $f_1(X), \ldots, f_k(X)$ are monotone submodular functions and we want to maximize $\min(f_1(X), \ldots, f_k(X))$ subject to the same cardinality constraint. Is it still possible to obtain a constant factor approximation?


texts: Are too many function calls bad(as in slows speed performance) for programs written using interpretor-based scripting language(JavaScript, Perl)?

texts:
The interpreters used for running scripting language (i.e., JavaScript, Perl, PHP, etc. ) programs go line-by-line.  Isn't it better to Avoid too many function invocations for programs written in said scripting languages?  However, Avoiding writing functions would be really a pain because you would have huge blocks of code that go continuously (basically No modularity)

@d-w Sorry, I should have mentioned that since interpreters for scripting languages go line-by-line, I thought it would be slower with more function calls. In compiler-based languages, it would be faster because the compiler's optimizing features could substitute the actual code within the function where the function is actually invoked. Basically, I thought compilers are more sophisticated, while interpreters just go line-by-line.  Is the aforementioned belief correct?


texts: Proving that $\{0^i10^i : i \ge 1\}$ is non-regular, using only closure results

texts:
I have been stumped on the following question for a few hours now, I feel like I am missing some "aha" moment.

  $\text{Suppose that } \{ a^nb^n : n \ge 1 \} \text{ is non-regular.}$
  $\text{Prove using closure results that } \{ 0^i10^i : i \ge 1 \} \text{ is non-regular.}$

Starting off I assumed for contradiction that the language is regular. Then I took countlessly many compliments and intersections and homomorphisms, none leading me anywhere close.

I understand using Pumping Lemma would quickly solve this problem, but the question restricts the proof technique to not using Pumping Lemma.

How would one go about solving such a question with the given restraints? Is there a methodology as to find the correct closure results to use or is it mostly intuition and luck?


texts: A multidimensional "moving van problem": a mix of a knapsack and a bin-packing problem

texts:
This problem is a mix of the bin-packing and the knapsack problems. I call it "the moving van problem": there is a moving van with a limit on the weight it can transport, and a set of boxes that you want to fill with valuable objects to be transported in the van. Both the boxes and the objects that are available can be choosen repeatedly and have weights. Also, the size of each box is bounded by above and below (their size limits), so you cannot put empty boxes in the van. Also, the value of each object doesn't depend on itself but on the box you save it.  The problem is maximizing the transported value while respecting all of the above restrictions. Ah... almost forgot, the weights are multidimensional.
Formally, given the following entities, where all vectors are column vectors, each element of every vector/matrix is a natural number $\geq 0$, and all weights are $q$-dimensional vectors:

$W$: the weight of the moving van.
$n$ and $m$: the amount of available objects and boxes respectively.
$V$: a $n\times m$ matrix where each element is the value of saving each object in each box.
$w_o$: a $n$-dimensional vector with the weights of each object.
$w_B$: a $m$-dimensional vector with the weights of each box.
$l$ and $u$: two $m$-dimensional vectors that, together, forms the size limits of each box (lower and upper bounds per box respectively).

The problem consists of finding:

$X$: a $n\times m$ matrix with the amount of times each object has been choosen to be saved in each box, and
$y$: a $m$-dimensional vector with the amount of times each box has been choosen,

in order to achieve: $$
\begin{align}
\max\quad & \sum_{i=1}^n\sum_{j=1}^mv_{ij}x_{ij}\\
\text{s.t.}\quad & w_B\cdot y + w_o\cdot\texttt{columnsum(X)}\leq W\\
&y\cdot l\leq \texttt{rowsum(X)}\leq y\cdot u\\
&X\geq 0\\
&y\geq 0
\end{align}
$$
where $\texttt{columnsum}(X)$ is a vector with how many times each object has been choosen in total (sum of columns), and $\texttt{rowsum}(X)$ is a (column) vector with how many objects have been saved in each box in total (sum of rows and then transposed).
I want to know if there's any formal name for this problem, to search algorithms for it in the bibliography. What I have tried is to see it as an instance of an integer programming problem, but I'm not able to adapt its mathematical formulation to match the canonical form of ILPs, so I don't know if I'm in the right path or have to look somewhere else.


texts: Implications of the $\Omega(\frac{2^n}{n})$ circuit lower bound being tight

texts:
There is a basic result in circuit complexity that says:

  There exists a language that cannot be solved with circuits of size $o(\frac{2^n}{n})$.

The argument is a simple counting argument on the number of boolean functions and the number of distinct circuits.  See, for example, these lecture notes.

I believe it is unknown whether or not this bound is tight.  That is, we don't know if the following statement is true:

  Every language can be solved with circuits of size $O(\frac{2^n}{n})$.

If this statement were true, would it have any interesting implications for complexity theory?


texts:
All the consensus algorithms that I've seen always depend on having a leader elected with all queries directed at the leader (assuming that we're not OK with getting back stale data). Are there any efficient algorithms that are completely symmetric, i.e. which do not elect a leader and therefore allows querying any server in the cluster?

Since a given server doesn't crash very often, from an engineering perspective it would seem like electing a leader is simpler because you can worry separately about what to do when the leader goes down, which would seem to allow for more modular protocol design. On the other hand, if all the queries are directed at one sever, then this server will get hammered, since in addition to all queries, it will have to send updates to all other servers in the cluster.

My questions can be phrased as follows: is dependence on a leader seen as a problem? Are there some fundamental issues with this approach in addition to problems with load? Do we have some fundamental problems when running a leaderless protocol? Do we know if there exists efficient leaderless protocols?


texts:
Given: $N$ segments (arrays) of ordered integers, integers could be from $-K$ to $K$.

Example:

Segment 1: [-2,-1,0,1,2,3]
Segment 2: [1,2,3,4,5]
Segment 3: [-3,-2,-1,0,1]

You can represent them as [min, max]---it is equivalent:

Segment 1: [-2,3]
Segment 2: [1,5]
Segment 3: [-3,1]

How can I find an integer that belongs to the maximum amount of segments? For the given example, it is 1.

I look for the most efficient algorithm.


texts: Is parameter tying more common in RNNs than in regular NNs?

texts:
From what I can see it seems like RNNs favour using a backprop through time method which I haven't seen really applied to other neural networks.

Can someone explain the significance of tying the weights and why it is necessary to be done for backprop  through time?


texts:
I have a binary tree, the node has two subtrees, every node except the the leaves, has 2 children and all the leaves are at the same level.

I want to know the worst and best case complexities when I applied centralized ranking to this type of tree. (defined above)

For the worst case, O(n^2) happens when the tree is chain. But what about this kind of tree? What is the best and worst case complexities of this kind of tree?