texts: Approximate count per element in list/stream via Counting Bloom+Morris

texts:
I've a large list A of elements. Given another list B of elements, I need B to be sorted by the number of occurences in A (that is, least common to most common in A). A precise count of A would require too much extra memory/disk and an approximate count if sufficient for my needs.

I couldn't find a common solution for this problem, which I suspect is common; I'm not a CS, though.

The way I came up with is to use a counting bloom filter where I increment the counter for every seen element with a chance of 2-c
, where c is the current count, initialized to zero. When asked for the approximate count of a given element, I look it up in the bloom filter and return 2c-1 as the result, if it's there at all.

This is Morris Counting, stuck into a Bloom filter. On the plus side, the behavior and memory requirements of the Bloom filter are well known; the counter spends the same amount of storage for the ranges "between 8 and 16" and "between one or two million", which is great for my need. The false positive rate for the Bloom filter and the variance for the counter are known. On the downside: I have no idea what I'm doing. Can I do better?


texts: When was manual dynamic memory managment introduced?

texts:
Original Fortran only had static memory. Algol introduced stack allocation. Lisp had Garbage Collection. But when where manual dynamic memory management such as in C introduced.

In C memory can be manually allocated and deallocated with malloc and free. Was this the first instance of this method of memory management in a programing language?


texts: Conditional Shortest Path Through Weighted Cyclic Directed Graph

texts:
Vertices in my graph are composed of {name, category} where category is one of {red, grn, blu, ylw}. Edges in my graph are weighted and directed. In the visualization, the thick end of the edge represents the destination.

My graph has negative cycles, for example [A-red, B-red, C-blu, X-grn, D-blu, A-red] has a cost of -1, comprised of edge costs [1, 1, -1, -3, 1].

I want to find the shortest path between arbitrary {source, destination} vertices subject to the following conditions:

Each vertex may only be visited once.
The count of vertexes visited along the path must be <= m
The count of categories visited along the path must be <= n

So, for example, assuming a function shortest_path(source, dest, m, n) then:

shortest_path(('A','red'), ('D','ylw'), 100, 100) would return [A-red, B-red, C-blu, X-grn, D-ylw] which has a cost of -2. This path visits 4 vertex categories [red, blu, grn, ylw].

shortest_path(('A','red'), ('D','ylw'), 100, 3) would return [A-red, B-red, C-blu, D-ylw] for a cost of 3. This path visits 3 vertex categories [red, blu, ylw].

Any suggestions here? I believe Dijkstra's algorithm and Bellman-Ford are out here as my graph contains negative cycles. So I think i need a brute force search of edges, integrating the stopping conditions mentioned above.

Python code for initializing my graph is here:

import networkx as nx

class Vertex(object):
    def __init__(self, name, category):
        self.name = name
        self.category = category
    def __hash__(self):
        return hash((self.name, self.category))
    def __eq__(self, other):
        if isinstance(other, Vertex):
            return other.name == self.name and other.category == self.category
    def __str__(self):
        return '{}-{}'.format(self.name, self.category)
    def __repr__(self):
        return str(self)

d = {
    Vertex('A','red') : {Vertex('B','red') : {'weight':1}},
    Vertex('B','red') : {Vertex('C','blu') : {'weight':1}},
    Vertex('C','blu') : {Vertex('D','ylw') : {'weight':1}, Vertex('X','grn') : {'weight':-1}},
    Vertex('D','ylw') : {Vertex('A','red') : {'weight':1}},
    Vertex('X','grn') : {Vertex('D','ylw') : {'weight':-3}},
}
G = nx.DiGraph(d)

pos = nx.circular_layout(G)
nx.draw_networkx(G,pos, arrows=True, with_labels=True)
labels = nx.get_edge_attributes(G,'weight')
nx.draw_networkx_edge_labels(G,pos, edge_labels=labels);

Update
Here is my current traversal algorithm, its essentially a DFS but I record both the parent of each vertex I examine, and the cost of traversing from the parent to the vertex. This allows me to reconstruct a path and compute a total cost for the path. However, I'm not sure its a great solution. My aim is to get the algorithm working well then port to cython for performance (my real graph is huge).

#DFS
def calcd(parents, distances):
    d = 0
    for v in parents[1:]:
        d+=distances[v]
    return d

def backtrace(parent, start, end):
    path = [end]
    while path[-1] != start:
        path.append(parent[path[-1]])
    path.reverse()
    return path

def dfs(graph, source, target):
    visited = set()
    stack = list()
    parent = {}
    distance = {}

    stack.append(source)

    while stack:
        u = stack.pop()
        uob = graph[u] #edges outbound from u

        for v, eparams in uob.items():
            parent[v] = u
            distance[v] = eparams['weight']

            if v == target:
                path = backtrace(parent, source, target)
                print('Reached Target via {}'.format(path))
                print('calcd', calcd(path, distance))

            if v not in visited:
                visited.add(v)
                stack.append(v)

source, target = Vertex('A','red'), Vertex('D','ylw')
dfs(G, source, target)

This prints:

Reached Target via [A-red, B-red, C-blu, D-ylw] calcd 3
Reached Target via [A-red, B-red, C-blu, X-grn, D-ylw] calcd -2


texts:
I have a vey specific question regarding the pumping lemma in the context of regular languages. The theorem states that if $L$ is a regular language, then there exists a constant $n$ such that for every string $w$ in L, with $|w|\geq n$, $w$ can be broken into $w=xyz$ with the following properties:

$|y|>0$
$|xy|\leq n$
For all $k\geq 0$, $xy^kz \in L$

My question concerns the third and first properties. In the third property, does $k=0$ not imply that $|y|=0$, therefore contradicting the first property?
As far as I can tell, when $k=0 \rightarrow xy^kz=xz$ and, consequently, $y=\epsilon$. What am I missing?


texts: Here I am given 2 hash families and I need to prove the universality of the double hash, but I am stuck as to how to prove this. I know the properties of an epsilon-universal family is that the probability of collision is at most epsilon, but how could I relate this to prove the universality of the double hash?


texts: Is it possible to build a secure PRG from two functions one of them being a PRG?

texts:
Having two deterministic functions $G_1, G_2 : \left\{0,1\right\}^\lambda \rightarrow \left\{0,1\right\}^{\lambda+l}$, at least one of which is a secure PRG.

Being $\alpha$ a constant, is it possible to build a secure PRG $G' : \left\{0,1\right\}^{\alpha\lambda} \rightarrow \left\{0,1\right\}^{\alpha(\lambda+l)}$ using $G_1$ and $G_2$?

My intuition is that it can't be done, but I don't know how to prove it.


texts: I am a mathematician, and I am completely lay in the technical aspects of computer networks and computer architecture. I would like to know if there is any computer network or architecture, protocol, or whatever, which combines unidirectional links with bi-directional ones. If so, what are the practical advantages of this mixed architecture?


texts: How does RAID-5 algorithm locate the right device?

texts:
Please consider the following diagram of a RAID-5 array (Ignore the gray background):

Now, given a logical address, how can one return the device number (0-3)?

For example, DeviceByLogicalSector(50) = 0, DeviceByLogicalSector(31)=2.

I've need to implement DeviceByLogicalSector method. I can use space if that's required.

Now, I've noticed the following:
Let's observe only the first $4$ rows; If we have a sector which is above the $P$-diagonal then the formula is: $\frac{(\text{logical_addr} \mod 12)}{4}$. And if the sector is below the diagonal then we need to add $1$.

Thanks


texts: Can we find a Turing machine such that there is no Turing machine to decide whether it halts on $\epsilon$?

texts:
The halting problem states that there is no Turing machine that can determine whether an arbitrary Turing machine halts on $\epsilon$. But I try to ask something different, can we find a specific Turing machine $M$ such that $L_M=\{ 0^n : M$ halts on $\epsilon \}$ is undecidable?
Or at least can we prove there exists such $M$?

The language itself isn't the issue, it is either $L=\{0^n : n \in \mathbb{N} \}$ or $L=\phi$ and the way to distinguish the cases is only by the right side of the definition of $L$.

In other words, can we define a Turing machine such that we (or a Turing machine) can't determine whether it halts or not on $\epsilon$?


texts: How many strings are close to a given set of strings?

texts:
This question has been prompted by Efficient data structures for building a fast spell checker.
Given two strings $u,v$, we say they are $k$-close if their Damerau–Levenshtein distance¹ is small, i.e. $\operatorname{LD}(u,v) \geq k$ for a fixed $k \in \mathbb{N}$. Informally, $\operatorname{LD}(u,v)$ is the minimum number of deletion, insertion, substitution and (neighbour) swap operations needed to transform $u$ into $v$. It can be computed in $\Theta(|u|\cdot|v|)$ by dynamic programming. Note that $\operatorname{LD}$ is a metric, that is in particular symmetric.
The question of interest is:

Given a set $S$ of $n$ strings over $\Sigma$ with lengths at most $m$, what is the cardinality of
$\qquad \displaystyle S_k := \{ w \in \Sigma^* \mid \exists v \in S.\ \operatorname{LD}(v,w) \leq k \}$?

As even two strings of the same length have different numbers of $k$-close strings² a general formula/approach may be hard (impossible?) to find. Therefore, we might have to compute the number explicitly for every given $S$, leading us to the main question:

What is the (time) complexity of finding the cardinality of the set $\{w\}_k$ for (arbitrary) $w \in \Sigma^*$?

Note that the desired quantity is exponential in $|w|$, so explicit enumeration is not desirable. An efficient algorithm would be great.
If it helps, it can be assumed that we have indeed a (large) set $S$ of strings, that is we solve the first highlighted question.

Possible variants include using the Levenshtein distance instead.
Consider $aa$ and $ab$. The sets of $1$-close strings over $\{a,b\}$ are $\{ a, aa,ab,ba,aaa,baa,aba,aab \}$ (8 words) and $\{a,b,aa,bb,ab,ba,aab,bab,abb,aba\}$ (10 words), respectively .


texts:
Here's something from Slonneger's "Syntax and Semantics of Programming Languages":

  A variable may occur both bound and free in the same lambda
  expression: for example, in λx.yλy.yx the first occurrence of y is
  free and the other two are bound.

I assume the free variable is the y right after the λx. and the bound y's are the λy.y which I can sort of intuitively grasp. So ((λx.yλy.yx)a)b) would reduce to (yλy.ya)b) then to bba ? Can someone explain how this came to be? In the end it's the expression b twice. Can someone perhaps provide more examples of bound and free variables?


texts: Is this a valid proof for "Karp-polynomial reduction is not symmetric"?

texts:
Let $L = \emptyset$ and $L' = \{a\}$ be two languages over an arbitrary non-empty alphabet $\Sigma$, $a \in \Sigma$.

$L$ can be reduced to $L'$: the reduction just transforms anything it is given into the word $aa$.

There is no way to reduce $L'$ to $L$: the answer would be always negative.


texts:
I am trying to solve an exercise on set-associative cache , i struggled with it for a while but i think that i figured out the answer , would be helpful if someone could check if my solution is correct

Here is the question:

Considering a main memory with 1024 addresses , divided in blocks of 8 words each, and a set associative cache with 4 sets and 8 ways:

a) How many words can the cache memory contain?

b) in which cache position the word with address 75(octal) could be memorized?

0
1
2
3
4
5
6
7
other

c) if a cache miss occurs , how many words in cache memory will be modified?

a) We have a maain memory with 1024 locations, each location has 8 words
   1024 * 8 = 8192 words in main memory (2^13).

Then we have a set associative cache with 4 sets , 8 ways each,
 4*8 = 32 , so the cache has 32 blocks . each block  contains 8 words,
32 * 8 = 256.

So the cache can contain 256 words (2^8)

b)

We know that in set associative cache , the main memory address is divided into

tag|set|offset

n = number of bits of the main memory address
m = number of bits of the cache memory address
b = size (expressed in words) of the block

n = 13
m = 8
b = 8

offset = log2 b = 3
set = log2 (number of sets) , 4 sets , so log2 4 = 2
tag = n - offset - set (13 - 3 - 2) = 8

so the address is divided in :
8 bits|2 bits|3 bits
tag    set    offset

The address of the word is 75(octal) , convrted in binary is 111101
it is a 6 bits address , the main memory generates 13 bits addresses,
so we rewrite it as 0000000111101 , we divide the address in:

00000001|11|101

From here we can se that the word could be memorized in any of the locations of the set 3 (11)

We have a cache with 4 sets and 8 ways each set:

So we have 32 blocks in cache , assuming we start from block 0,
we can see that the blocks in set 3 (ii) are

24,25,26,27,28,29,30,31

The question is asking in which locations the word with address 75(octal) could be stored, so it could be stored in one of the blocks from 24 to 31
so the answer to the question b should be: other

I haven't still figured out point c , but would be helpful to know if my reasoning is correct , or , where i am wrong.


texts:
How does a demultiplexer ignore/discard/block the non-required outputs?
A demultiplexer channels the input to one of the outputs, but there are several outputs. When one output is selected (depending on the state of the select line(s)) then rest of the outputs are 0/low (am I right?).
Now, if the input is 0/low then the selected and non-selected outputs all becomes 0/low.
How does the demultiplexer perceive the final result in such a case??

Please explain in details (with reference to 1:2 demux if possible). Thank You!


texts: Continuation-passing style: what is meant by "CPS'ing"?

texts:
I'm reading Dijkstra Monads for Free for a presentation I'll be doing and it's pretty meaty. One of the things that I keep running into is the term "CPS'ing". I've read a little bit on continuation-passing style (i.e., I've read through most of the Wikipedia page and it didn't feel like utter nonsense...) but I'm still not clear what the phrase "CPS'ing" means.
They give an example, which I will duplicate here, after which I will present the main pattern I see:

Rather than being given manually, we show that these predicate transformers can be automatically derived by CPS'ing purely functional definitions of monadic effects (with answer type Type). For instance, rather than defining WP_ST, one can simply compute it by CPS'ing the familiar ST monad (i.e., state -> a * state), deriving
WP_ST a = ((a * state) -> Type) -> state -> Type

(For context, this can be found on page 1, first full paragraph at the top of the second column).
So there is a pretty obvious pattern here: Given some type
a1 -> a2 -> ... -> an

we can map it via the contraviariant functor F (a -> b) = (b -> a) that just reverses the arrows, yielding
an -> ... -> a2 -> a1

and then replacing each ai with (ai -> Type).
Is this a reasonable interpretation of the term "CPS'ing"? Also, it's not clear to me why this is useful - is there any motivation for what is gained by applying such a transformation?


texts:
I'm somewhat confused about IP addresses and subnet masks.
Can a same IPv4 address have two different CIDR suffixes ?
for example 95.100.252.115/28 and 95.100.252.115/26 ?

If not, how is the CIDR suffix determined by the IPv4 address?


texts: Fastest way to Add and Subtract multiple parts of a List

texts:
I am doing some research where I have a List containing numbers. For example

{5,10,98,22,13,15}

What is a fast algorithm to calculate all possible sums and differences from these? Eventually I will want to do the same thing for a list of 400+ numbers.

Some examples in the final set

index0+index1=5+10=15
index0+index3+index4=5+22+13=40
index0+index2-index5=5+98-15=88
index3-index4=22-13=9

What I am thinking now is 3 for loops. One to move through the array, one to keep track of how many numbers to skip, and one for the number of skips. But that seems slow.

Ahh I guess my answer is unsolvable bc of P=NP. I see from here: https://en.wikipedia.org/wiki/Subset_sum_problem


texts:
I am learning about regular expression, and  trying to describe a regular expression for the language L

$\qquad L = \{a^i b^j c^k \mid i+j = k\}$

What is the right approach and how to describe a regular expression like this?


texts: Are files download times actually unknowable due to the halting problem?

texts:
When downloading a file from the internet to our computer we are usually prompted with an estimate of how long it will take for the file to be downloaded.
From the Halting Problem, we know that $\mathrm{HALT}_{\mathrm{TM}}$ is undecidable, where:
$\mathrm{HALT}_{\mathrm{TM}} =\{⟨M,w⟩\mid M \text{ is a TM and }M\text{ halts on input }w \} $
Assuming that we can neglect the lack of infinite memory, we can model our computer writing on the disk as a Turing Machine $M$ and take the string encoding of the downloaded file as the input $w$. (More precisely, $w$ should be the string obtained composing the packets sent by the network)
From the Halting Problem it follows that it's not only impossible to know when the download will end, it's even impossible to know whether the download will ever end.
So, are files download times actually unknowable due to the halting problem? If not, where the above reasoning fails?


texts: Find cell neighbors of a given edge in a 2D grid

texts:
In the figure below, cells are labeled row wise, and edges are labeled counter clockwise.  That is, vertices 1' and 2' form edge #1, vertices 2' and 5' form edge #2, vertices 5' and 8' form edge #7, etc.

vertices 1' and 2' form edge #1
vertices 2' and 5' form edge #2
vertices 4' and 5' form edge #3
vertices 1' and 4' form edge #4
vertices 2' and 3' form edge #5
vertices 3' and 6' form edge #6
vertices 6' and 5' form edge #7
vertices 5' and 8' form edge #8
vertices 7' and 8' form edge #9
vertices 4' and 7' form edge #10
vertices 6' and 9' form edge #11
vertices 8' and 9' form edge #12

  Question: given an edge number (and/or the vertices that form it), is there a way to algorithmically
  compute its corresponding cell neighbors?


texts:
According to the Wikipedia page, search is "not an operation" on binary heaps (see complexity box at top-right).

Why not? Binary heaps may not be sorted, but they are ordered, and a full graph traversal can find any object in $O(n)$ time, no?

Is the page wrong or am I?


texts: Why are some programming languages Turing complete but lack some abilities of other languages?

texts:
I came across an odd problem when writing an interpreter that (should) hooks to external programs/functions: Functions in 'C' and 'C++' can't hook variadic functions, e.g. I can't make a function that calls 'printf' with the exact same arguments that it got, and instead has to call an alternate version that take a variadic object. This is very problematic since I want to be able to make an object that hold an anonymous hook.

So, I thought that this was weird since Forth, JavaScript, and perhaps a plethora of other languages can do this very easily without having to resort to assembly language/machine code. Since other languages can do this so easily, does that mean that the class of problems that each programming language can solve actually varies by language, even though these languages are all Turing complete?


texts: Can you explain this exercise solution to me?

texts:
A process running on CTSS (Compatible Time Sharing System) needs 30 quanta to complete. How
many times must it be swapped in, including the very first time (before it has run at all)?

•
Answer : The first time it gets 1 quantum. On succeeding runs it gets 2, 4, 8, and 15, so it must be swapped
in 5 times.

why does it get 2,4,8,15 on the succeeding runs?


texts:
I'm reading William Stalling's Operating System Design and internals. Talking about memory, the following tradeoff was introduced:

  As might be expected, there is a tradeoff among the three key characteristics
  of memory: namely, capacity, access time, and cost. A variety of technologies are
  used to implement memory systems, and across this spectrum of technologies, the
  following relationships hold:
  • Faster access time, greater cost per bit
  • Greater capacity, smaller cost per bit
  • Greater capacity, slower access speed

Now what exactly makes a faster memory more costly, and why does bigger memory mean slower memory?


texts: Is bounded waiting satisfied in this 2 process solution?

texts:
Two processes, P1 and P2, need to access a critical section of code. Consider the following synchronization construct used by the processes:

/*  P1   */
while (true) {
    wants1 = true;
    while (wants2 == true);
    /* Critical Section */
    wants1 = false;
}
/* Remainder section */

/*  P2   */
while (true) {
    wants2 = true;
    while (wants1 == true);
    /* Critical Section */
    wants2=false;
}
/* Remainder section */

Here, wants1 and wants2 are shared variables, which are initialized to false.

What i have tried =>

Here, mutual exclusion is satisfied and deadlock is there, so no progress .

I am only having a doubt that bounded waiting can also be satisfied here as according to the definition, bound is here 0, so waiting is bounded here ?

Is my understanding correct ?


texts:
There is a League. And there are Divisions, that are the disjoint subsets of this League. There are n teams (unique locations are given, let's assume it's x and y for simplicity reasons). Every team must belong to exactly one Division. There are min and max - minimal and maximal amount of teams per division. Every team travels once to every other team inside one division. The target is to divide the league into divisions in a way, that the total traveling distance for the whole league is minimized.

Input:
n - amount of teams
min - minimum teams per division
max - maximum teams per division
teams - array of teams (name,x,y)

Input example:
n = 10
min = 2
max = 3
teams = [{a,1,1},{b,2,1},{c,5,3},{d,9,8},{e,6,8},{f,5,1},{g,1,7},{h,6,6}{i,7,2},{j,2,7}]

Output:
League

Output example:
League = [[a,b,c],[d,e],[f,g,h],[i,j]]
One sub array stands for one division. It means that the teams a,b and c belong to one division and each of them will visit every other team from this division.
This is not the optimal solution

This is what an output of a real-world case could look like

I am struggling with selecting an algorithm for this issue. It is not a traveling salesman since we are not interested in simply visiting all of the locations. Neither the clustering approach is applicable since we need to keep the min
and max in mind and it's not what clustering does. What kind of algorithms can be used to tackle down this problem?


texts:
Disclaimer. What I'm going to ask about below may seem to be "Topological sorting". To my understanding, it is not. The latter runs in linear time, while I'm looking for a modification of the regular sort, which is at $N\log N$.

Remark. I'm doing the sort in the reverse order, to use the analogy with heights and masses.

Let us reformulate the sorting problem in the following way. Let us introduce two sets:

A set of sites (positions) $s_a,\,a=1..N$. Those are assigned certain 'heights' $h[s_a]$, which in the case of usual sorting can be simply $h[s_a]=a$.
A set of objects (numbers) $x_i,\,i=1..N$ which are assigned numerical values $m[x_i]$ (according to which the sorting will be performed). In the case of usual sorting, $m[x_i]$ are the numbers to be sorted.

The problem of sorting can be viewed as assigning to each object $x_i$ a site $s_a$ in such a way that for all assignments $\{x_i\to s_a; x_j\to s_b\}$:
$$
h[s_a] > h[s_b] \Longrightarrow m[x_i]\leq m[x_j]
$$

The physical visualization of this problem is a vertical stack of massive balls. Sorting them is equivalent to arranging them in such a way that heavier ones have lower height.

I first wanted to generalize the problem to "higher dimensions", i.e. to assume that the balls can stay in a $2$-dimensional grid, in a bucket, etc. However, I realized that from the computational point of view these settings are equivalent. In other words, whether we have a $2d$ grid with $nm$ balls in each row or a box with $n\times m$ balls in each layer makes no difference.

So, I decided to generalize the problem to an arbitrary topology (which can be reduced to the $2$-dimensional problem actually).

A set of sites (positions) $s_a,\,a=1..N$. Those are assigned certain 'heights' $h[s_a]$. Repetitions are allowed: $h[s_a]=h[s_b]$ for $a\neq b$ is OK.
A set of objects (numbers) $x_i,\,i=1..N$ which are assigned numerical values $m[x_i]$.

Again, we want to assign to each object a site in accordance with the same requirement as above.

Clearly, the brute-force solution for the most general set of 'heights' and 'masses' runs in $N \log N$. One simply sorts the objects according to their 'mass', and then fills the sites, starting from the 'highest' or the 'lowest' one.

Question. Has there been done any research for some particular cases? Clearly, if all the 'heights' are equal, the problem is trivial (which, I guess, means that it is solved in linear time). The first thing coming to my mind would be considering the case of "levels of same lengths",
$$
h[s_a]=\lceil a/r\rceil,\,r\in\mathbb{N}
$$
I would actually expect that this can be done faster than $N\log N$ (I'd assume that $r$ should enter the answer).


texts: Does exist any horn formula that is equisatisfiable to the clause that is disjunction of two literals? Does also exist equivalent?

texts: I just and simply want to know if whether or not exist any horn formula that is equisatisfiable to $(p\lor q)$. I would also be interested to know if there also exists equivalent.


texts: If I walk through list and delete every out-of-order element I come across, on average how many elements will be left?

texts:
I have a uniformly randomly permuted list of length $n$. I walk through the list element-by-element, and delete an element if it's out-of-order (compared to the previous in-order elements of the list). What I'm left with is a shorter list that's guaranteed to be in-order.

Example: The starred elements of this list would be deleted during the walk through.

[1, 4, 2*, 3*, 5, 7, 6*] -> [1, 4, 5, 7]

My question is: On average, what will be the length of the remaining list? And is there some simple/obvious form of the distribution of this?

And as one follow-up: if we used this for a sorting algorithm (called Drop Sort), what would the run-time be? To be clear, the algorithm would be something like this:
$$\textit{DropSort}(\text{list}) = \textit{Merge}(\text{Remaining list}, \textit{DropSort}(\text{Rejected list}))$$

This question was inspired by this r/ProgrammerHumor post.


texts: How to create constraints for Mixed integer linear problem?

texts:
i am a beginner to Discrete optimization domain. I am working on the real world problem, i.e., Scheduling of hybrid appliances. I have hybrid appliances which can use gas and electricity or electricity and hot water or hot water and gas for their operation. Each appliance has some set of tasks, each task use above mentioned energy carriers based on the requirement.

The question is, i want to create a constraint such that if the task of the appliance starts with electricity and hot water, it should end with using electricity and hot water. It should not alter the energy carrier to gas during the operation.

I have created some of the decision variables like this:

$x_{t,i,j}$  indicates whether task j of appliance i  at time slot k processed by electricity or not; 1 = task processed; 0 = not processed

$y_{t,i,j}$ indicates whether task j of appliance i at time slot k processed by natural gas or not; 1 = task processed; 0 = not processed

$z_{t,i,j}$ indicates whether task j of appliance i at time slot k processed by hot water or not; 1 = task processed; 0 = not processed

I tried with the following constraint it seems something missing.

$\sum_{k=t}^{t+H_{i,j}}$ $(x_{t,i,j}+y_{t,i,j}+z_{t,i,j})$ $\geq$ $H_{i,j} (x_{t,i,j}+y_{t,i,j}+z_{t,i,j})$

Where
i is index of appliance.

t is current time slot.

j is index of task.

$H_{i,j}$ is run time of tasks.


texts:
In chapter of Hardness of Approximation in V. Vazirani's book it says:

For establishing a hardness of approximation result for, say, the vertex cover problem, PCP theorem is used to show the following polynomial time reduction. It maps an instance φ of SAT to a graph G = (V,E) such that
• if φ is satisfiable, G has a vertex cover of size ≤ 2/3*|V |, and
• if φ is not satisfiable, the smallest vertex cover in G is of size >
α· 2/3*|V |,

Next line it claims:

Claim 29.1 As a consequence of the reduction stated above, there is no polynomial time algorithm for
vertex cover that achieves an approximation guarantee of α, assuming P
≠ NP. (α>1)

I couldn't understand that claim, while in previous chapters it says Vertex Cover have 2-approximation algorithm (with Maximal matching).
Could anyone explain what does it means? How it obtained 2/3*|V|? and Why it said there is no α approximation while in previous chapters it proposed ones?


texts: Why is compression ratio using bzip2 for a sequence of "a"s so jumpy?

texts:
library(ggplot2)

compress <- function(str) {
  length(memCompress(paste(rep("a", str), collapse=""), type="bzip2"))
  / nchar(paste(rep("a", str), collapse=""))
}

cr <- data.frame(i = 1:10000, r = sapply(1:10000, compress))

ggplot(cr[cr$i>=5000 & cr$i<=10000,], aes(x=i, y=r)) + geom_line()

The compression ratio starts out at 37 for "a" and hits the break-even at 39 "a"s (compression ratio = 1). The chart starts out pretty smooth and gets edgy suddenly for 98 "a"s and from there at increasingly small intervals.

The local lows and smooth sections seem also quite erratic and random. Can somebody explain to me why bzip2 shows this behaviour in this example?


texts:
Given $m$ shortest paths between any two vertices of a graph. Determining whether we can pick $k$ shortest paths such that their union covers all edges.

I am trying to reduce set cover problem to it. For a set cover problem we can convert its elements into edges and the set represent a path from the first element to the last one. This conversion of set cover into a graph gives a tree kind of structure. Since between any two nodes in a tree the path is unique so, it has to be shortest as well. I formed a counter example of my own reduction which is given here. I believe that I am making some mistake somewhere but unable to recognize it.


texts: Algorithm to find diameter of a tree using BFS/DFS. Why does it work?

texts:
This link provides an algorithm for finding the diameter of an undirected tree using BFS/DFS. Summarizing:

Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u remembering the node v discovered last. d(u,v) is the diameter of the tree.

Why does it work ?
Page 2 of this provides a reasoning, but it is confusing. I am quoting the initial portion of the proof:

Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u remembering the node v discovered last. d(u,v) is the diameter of the tree.
Correctness: Let a and b be any two nodes such that d(a,b) is the diameter of the tree. There is a unique path from a to b. Let t be the first node on that path discovered by BFS. If the paths $p_1$ from s to u and $p_2$ from a to b do not share edges, then the path from t to u includes s. So
$d(t,u) \ge d(s,u)$
$d(t,u) \ge d(s,a)$
....(more inequalities follow ..)

The inequalities do not make sense to me.


texts:
As far as I understand, Dijkstra's algorithm always picks the nearest neighbour.

But how does it work for the following graph?

    2
A-------B
 \     /
1 \   / 3
    C

var result = dijkstra(fromA, toB);

Step1: A->C is the shorter
Step2: C->B is the shorter
Answer: 1 + 3 === 4 // This is clearly wrong

What am I missing?


texts: Constructing Generalised Suffix Tree from a large set of strings

texts:
Is there a published method to construct a generalised suffix tree from a large set of strings (~ 500 000) without the need of concatenating them?

I would like to use the resulting suffix tree for a pattern search problem.


texts: Hashing using search trees instead of lists

texts:
I am struggling with hashing and binary search tree material.
And I read that instead of using lists for storing entries with the same hash values, it is also possible to use binary search trees. And I try to understand what the worst-case and average-case running time for the operations

insert,
find and
delete

is in worth- resp. average case. Do they improve with respect to lists?


texts:
Writing a proof by contradiction is fairly formulaic--first you assume the opposite, then derive a contradiction.  I would like to know the steps and conventions for writing a many-one reduction proof.  This answer was somewhat helpful, but like other explanations I've heard, it sounds too similar to a proof by contradiction for me to understand the difference.

My specific points of confusion:

The exact meaning of $A \leq _{m} B$
Do we reduce an unknown problem to a known problem, or the opposite
Does the reduction function transform a known problem into an unknown problem, or the opposite
How a many-one reduction is different from a proof by contradiction.  It seems like a simpler version of the same logic; if so, how is the simplification justified

I am only interested in many-one reductions of language/Turing machine problems (in case the term has meaning in other contexts as well).  Any help is appreciated, including links and illustrative examples.  Thanks.


texts: Generating permutations with a given bubblesort distance

texts:
I'm looking for an algorithm to randomly generate permutations on 1:n, which though have a defined bubblesort distance d from 1:n, e.g. (2,3,1) and (3,1,2) are distance 1 from (1,2,3), (2,3,1) and (3,1,2) are d=2, finally (3,2,1) is d=3.

Naive approach is to flip a random sorted pair d times, however it seems it does not produce an uniform sample... The exact approach (generate all permutations at a given d and then sample) does not scale too well.


texts: Existence of Real-Time Multiprocessor Schedule

texts:
Does an algorithm exist to check for the existence of a Real-Time Multiprocessor Schedule for aperiodic hard tasks(all of which have the same Release time)?

Assumptions:

The processors are Uniform parallel machines
Job preemption is permitted
Job migration is permitted
Job parallelism is forbidden

EDIT: Let there be $n$ jobs $J = \{j_1, j_2,\text{...}, j_n\}$ and $m$ no of processors $P = \{p_1, p_2,\text{...}, p_m\}$. Each job $j_i$ has a task time $t_i$(amount of work it would take to complete it) and due time $d_i$. Each processor has a constant speed $s_i$(amount of work it does per unit time). Each task must be completed before its due time.

I am interested to know about an algorithm with can check feasibility of a schedule in polynomial time.


texts: How to find a function in Lambda Calculus?

texts:
Yesterday I have been trying to complete this exercise. I have to find:
$$ ((map)l)t \simeq \lambda k \lambda x ((k)(t)t_1)....((k)(t)t_n)x $$

where $$l=\lambda k \lambda x ((k)t_1)....((k)t_n)x$$
And $t$ is a generic Lambda term.
I tried but without success.
Maybe it will be something like that :
 $$map=(\lambda a \lambda b (\lambda s \lambda d((b(st))d)))$$
Thank you in advance to all will answer


texts: Closure properties of linear context-free languages

texts: Under what operations are linear context-free languages closed? Suppose $L_1, L_2$ are two linear context free languages.  Are there any guarantees about $L_1 \cup L_2$, $L_1 \cap L_2$, $\overline{L_1}$, $L_1 . L_2$, etc.?


texts: Clarification of Hopcroft's proof that "deciding whether a program halts on all inputs" is not R.E

texts:
$DoesNotHaltOn\_w=\{(M, w) : M$ does not halt on input w$\}$
$AlwaysHalt =\{ M : M$ halts on all inputs x $\}$

Hopcroft gives the following proof that $AlwaysHalt$ is not R.E.

1) Given an input x of length n, $M'$ simulates $M$ on w for n steps.
2) If during that time $M$ halts then $M'$ loops and $M'$ does not halt on its own input x.
3) However if $M$ does not halt on w after n steps then $M'$ halts.
4) Thus $M'$ halts if and only if $M$ does not halt on w.
5) Since the problem of telling whether $M$ does not halt on w is not R.E., it follows that whether a given TM halts on all inputs must not be R.E. either.

I don't understand why in (1) the number of steps to simulate needs to be dependent on the length of the input x.

I don't understand how step 3 implies step 4. I don't see how knowing that $M$ does not halt on w after n steps (or less) allows us to conclude that $M$ will not halt on w after more than n steps.

Could someone clarify? Thanks.


texts: Upper-bounding the number of comparisons for Sorting to $\Theta(n)$ using a physically big number like Number of Particles in the Universe

texts:
I recently read an article Scott Aaronson - Big Numbers . That has made me think about the effective upper-bound for sorting.

According to the article, some of the big numbers like the number of particles in the universe and age of universe in milliseconds are less than $10^{100}$.

In any realistic computational device, the data to be sorted will have to be lesser than these numbers. (As otherwise, it would be impossible to store the numbers physically).

$\log_2(10^{100}) \approx 333$

Hence, if we take a number $C > 333$, we can show that number of steps required for sorting an input of size $n$ will always be lesser than $Cn$

This makes sorting an $O(n)$ time operation using algorithms like QuickSort or HeapSort.

Is there a point I've wrongly considered while making this assumption?

Should we consider physical constraints while analyzing algorithms? If not, why?


texts: What are the benefits of languages that are not Turing complete?

texts:
Unfortunately I did a degree in CS without much theoretical computer science. One thing I used to hear is that sub languages, or languages which are not Turing complete, allow for better optimization?

Why is this case? What is the thought process and what are some examples in practice? What are some good resources on the topic?


texts: Smallest possible DFA for a language over {0,1}* with third to last symbol 1 should have 4 states not 8. Where am I going wrong in my DFA?

texts:
So I was reading Micheal Sipser's Introduction to TOC and when I stumbled upon this aforementioned question , he'd the following dfa :

Now, I came up with a much better DFA with only 4 states :

I read in another thread that the minimum number of states for a DFA for this language is 8. But , I came up with 4.

Where am I going wrong ?
(I tried testing this DFA with a plethora of input strings , seems ok to me)


texts: If p(n) is a polynomial in n, then is 1/p(n) polynomially bounded?

texts:
This is part of a homework exercise. Given is an algorithm that errs with probability $\frac{1}{2}-\frac{1}{p(n)}$ for some polynomial in the input size $n$. I'm trying to prove that a polynomial number of repetitions is sufficient to reduce the error probability to $\frac{1}{2^n}$.

Using the Chernoff bound I derived that $k \geq \frac{2n \ln(2)}{\bar{p}-1+\frac{1}{4\bar{p}}}$ with $p = \frac{1}{2}+\frac{1}{p(n)}$ repetitions is sufficient. However, I'm having a difficulty in showing that this quantity is polynomially bounded. Could someone shine some light on this?


texts:
How would you algorithmically detect for any given photo whether the sun was shining when the picture was taken?

Examples

A sample from this webcam at a mountain top:

Clearly the sun is shining.

In this other sample it's far less obvious:

One could probably detect fairly easy whether it's foggy by trying to identify the tiny church spire on the chapel in the center. However, knowing very little about image processing I'd be surprised if there was a (combination of) algorithm that could reliably tell if there's sunshine or not.


texts: shortest notation for "set of all maps from $A$ to $B$"?

texts:
I usually write the following:

$$\{m| m:A\to B\}$$

Is there a more succint notation?


texts: What is the name of this sorting algorithm?

texts:
I have typeset in a Wikipedia draft this sorting algorithm. It is a comparison sort, yet can handle only numeric arrays.

Basically, it marches through the input array and for each new array component it inserts it into a sorted doubly-linked list. It has two optimizations:

each list node has a count; instead of adding a new node with the same key, existing node is reused by incrementing its counter,
the sort maintains a reference to the most recently accessed list node. This allows faster search for the next list node in case the two relevant keys are "close" to each other.

My question is: what is the name of that sort? (I believe I am not the first one to conceive it.)


texts: How to store large graphs, when adjacency lists/matrices don't cut the mustard?

texts:
If space is of primary concern, how could we improve on adjacency matrices and adjacency lists for representing a graph of nodes and undirected edges in memory?

Throughout academia we learn adjacency matrices and lists but in the real world we encounter graphs of sizes that exceed the capabilities of these representations.

Are there known techniques to achieve significantly smaller memory usage while maintaining the representation of the graph?


texts:
In learning about proof theory, I am interested to know how to go about "proving properties of a program". I don't exactly see yet what needs to be proven, nor how to prove it, which leads to this brief discussion followed by some questions.

In some languages (such as TLA+), the program is the specification (I think). If not TLA+, maybe you can do that in Coq, but I've heard of it. So that means roughly that what you write is automatically proven. But if that is the case, how do you prove that it's proven. It seems that at some point you have to actually test both the code and the proofs and see that it does what the specification says. Some basic TDD.

In reviewing the Curry-Howard correspondence, programs are proofs, or at least lambda/functional/logic style programs. Not really sure what this means in practice. If simply writing a new function that implements a specification means we have a proof, or what.

So the questions are:

What exactly we are proving.
How do we prove that the system meets the specification (if the language is or is not the actual specification). If I write code that says "I will always handle this HTTP request error by tracing its output to the console", and that is "specified" in the specification, then how does it get proven. Not sure what I do to say "guaranteed, this behavior will happen". In my head the only way this can be proven is by actually doing tests on the code (i.e. model testing or just brute force simulation testing like you would see in TDD).
When writing tests (as in TDD) comes into play when creating these proofs. Wondering if proofs need tests, sorta thing, or at what point you are done with your proof being proven.

So it seems that what we want to prove is that the system behaves as expected. And given we have defined how we want the system to work, the question is how to prove it matches the specification, at a high level. How much do we prove, how do we know the proofs actually prove what we want and the behavior will be what we want (and proven).


texts: Complexity of shortest paths if paths have to use edges from different partitions

texts:
We are given a simple, undirected, weighted, incomplete graph $G=(V,E)$, where $V$ is the set of vertices, and $E$ is the set of edges. In addition, a collection of sets $S$ is given, which fully partitions $E$.

For any two vertices in $V$, I need to find the shortest path between them.
The additional caveat is that no two edges which belong to the same partition may be in the path.

This has totally thwarted any polynomial algorithm I can think of. It confounds algorithms like Djikstra, because at any step during the process, it may be best to forgo the best available edge in favor of having a better choice still open in the future.

I've tried reducing it to the traveling salesman problem, and several others, but I can't quite get there. Proof-writing is not really my strongest suit. Any point towards proving this would be much appreciated.

EDIT: Yes, $S$ is a partitioning of $E$. This does seem to be perfectly analogous to rainbow graphs. Is it known that finding rainbow paths on an unweighted graph is NP-Hard?


texts:
Consider the following 2-3-4 tree.

Does this have a height of 3 or 2 ?
Code for searching a min heap

If I count from the external nodes ie. the ones with the square boxes then height should be 3.
Not sure if they are to be included in the height as they are represented as NIL.
If they are not to be included then the height of the tree = 2
Any clarification on this.
Also looking to understand the following algorithm for searching in heaps -

https://tinyurl.com/w9yzwx9w


texts: Pumping Lemma for $L = \{a^n b^{2n} \mid n \ge 0 \}$

texts:
One of my CS course assignment problems was finding whether $L = \{a^n b^{2n} \mid n \ge 0 \}$ was regular or not. Now, I'm struggling quite a bit getting my head around this as it just seems like an overly complicated pigeonhole problem.
Regardless, I have written my solution and would like to know if it makes sense or is right?

Suppose $L$ is regular. We then have some $p > 0$ and some $|m| > p$.
$a^pb^{2p}$
$m = uvw$ and $|uv| \leq p$ and $uv^iw \in L$ for all $i > 0$
As $|uv| \leq p$ then it follows that $v = a^l$. However, as $uv^iw \equiv a^{p+l}b^{2p}$ it shows that as $p + l \ne 2p$ therefore $L$ is not regular.

As I said, I have no idea whether this is right and I've spent countless hours trying to understand it.


texts: Why is the assignment rule the way it is in Hoare Logic?

texts:
Why is the assignment rule the way it is in Hoare Logic/Axiomatic Semantics?
I can't wrap my head around why the assignment rule is backwards from what I expected.

I understand Hoare logic is use to prove formal propositions of the state of a program as commands are executed. Thus, if we execute the command $$x:=e$$ I would have expected that the next state has such substitution...but it seems the substitution happens before we execute the assignment which I find bizzare. I would have expected:

$$ \{ P \} x:= e \{P[e/x]\}$$

Given that $P$ are statements about the program state.

I'm sure there is a good explanation for this and sorry if this is a basic question, I know it must be. But can someone explain it to me?

Bonus Question:

Why don't we write the assignment rule as:

$$ \{ Q \} x:= e \{Q[x/e]\}$$

note its NOT the same as my original suggestion because we have the $x$ and $e$ swapped around. i.e. in the post condition wherever we have an $e$ we place an $x$ (which is fine because the statement we just execute is that $x$ holds the value of $e$, so we should be able to replace $e$ for $x$ in the post condition if the pre condition help.

Related posts that I've read that have not helped:

Hoare triple for assignment P{x/E} x:=E {P}
Wikipedia Hoare logic
https://www.quora.com/unanswered/Why-is-the-assignment-rule-the-way-it-is-in-Hoare-Logic
https://www.reddit.com/r/ProgrammingLanguages/comments/e8suhh/why_is_the_assignment_rule_the_way_it_is_in_hoare/

Appendix:

For us dyslexics, in this question this is what the substitution notation means:

$$ P[e/x] = P[e \to x] $$

i.e. replace every free occurrence of $x$ with expression/term/thingie $e$.


texts: a jigsaw problem: recreating a subgraph from a limited number of fragments on an original graph

texts:
Suppose I have a set of small subgraphs $A=\{G_i\}$ of an original directed acyclic graph $G$, typically $|G_i| \ll |G|$, which together span the original graph

$$
G= \bigcup_i G_i
$$
My question is if I take a arbitrary subset of these graphs $A′ \subset A$, and a single subgraph from this graph, $ a \in A′$, is there a simple way (or known algorithm) of reassembling the subgraph $G′ \subset G$ given by that portion of the union of $A′$ connected to $a$?

In words, this is rather like a jigsaw problem where $A$ is the total collection of pieces that originally came in the box, $A′$ is the subset left after half of them got lost and $a \in A′$ the random selected piece you put down the start the puzzle off. The question is then what is the largest connected graph (connected subset of pieces $x \in A'$) that you can lay down all on the board.

The actual application arises where each subgraph $G_i$ of A represents a rule and (e.g. $x \wedge y \Rightarrow z$) and the objective is to find the largest rule implied transitively from an initial seed rule $a \in A′$ and the remaining rules contained in thinned out subset $A′ \subset A$.

I suspect I maybe able to do something by brute force here but would be most interested in knowing if there is any area or known application of this problem elsewhere.
 I think similar things are possible in declarative language such as Prolog but I suspect that Prolog can actually do any more. Any good up-to-date reference on declarative programming languages would also be very useful.

I originally posted a version of this question on the Computational Science site but was advised that this forum could be better.


texts: Relative succinctness of NFAs and regular expressions

texts:
What is known about the succintness of NFAs, relative to regular expressions?

In order to clarify the question, let me explain what I know. The regular languages can be characterized by any of the following:

A language is regular iff it can be recognized by an NFA.
A language is regular iff it can be recognized by a DFA.
A language is regular iff it can be defined by an MSO formula.
A language is regular iff it can be described by a regular expression.

The family of languages $(\{w\in\{0,1\}^* \mid |w|>n, w_{|w|-1-n}=0\})_{n\in\omega}$ has NFAs with $n+1$ states. For DFAs, there is a lower bound of $2^n$ states. This family exemplifies that the translation from NFAs to DFAs necessarily incurs a worst-case exponential explosion of size.

In the other direction, there is no explosion, because each DFA is an NFA. Together, we can say that NFAs are exponentially more succinct than DFAs.

A similar result holds for the comparison of automata (either NFAs or DFAs) to MSO formulae: The formulae are non-elementarily more succinct.

I am aware that the translation from regular expressions to NFAs is linear and that there is an exponential translation in the other direction. Now to the actual question: Is it known that an exponential blowup cannot be avoided? What NFAs (or even DFAs) witness this? What techniques are used to prove non-existence of short regular expressions?

This question leads me to assume that divisibility languages are witnesses. That was what prompted the present question.


texts: Relation between “formal verification”, “formal proof”, and “type systems” for software verification?

texts:
I have a vague understanding what formal verification is about, a vague understanding of what the cutting edge is of type theory for programming languages, and a better understanding of formal proofs.

So far as I understand, the purpose of formal verification is to (1) specify a set of “desired properties” in the form of logical propositions about a system/program, and (2) use some kind of logic to check those propositions.

Similarly, using type theory (especially with the curry-howard isomorphism) we can also to (1) specify a set of “desired properties” of a program, and (2) by type-checking ensure that those properties hold.

Formal proof seems to underly both.

What is the relation between these three things?

What kind of properties of programs/systems can we check with modern state-of-the-art type systems?
is type theory an example of “formal verification” or does the latter term not include it?
What are the advantages and disadvantages of (classical?) formal verification versus type theory-based checking of program properties?


texts: Generate triangular surface mesh of convex hull spanned by 8 points in 3D-Space

texts:
I am looking for a numerically efficient algorithm to get a triangular surface mesh of the convex hull given by 8 points in three-dimensional space.

For context, the use case is the following:

I have a numerical Simulation calculating the time evolution of a field with three components on a lattice. Say we have lattice coordinates $(i,j,k)$, then every lattice point $(i,j,k)$ has a field vector $(\phi_1, \phi_2 , \phi_3)$ attached.

For relevant physics, I need to now take unit cells on my lattice, so the 8 corners of a little cube of my lattice. I take the field vectors  $(\phi_1, \phi_2 , \phi_3)$ of every corner of my unit cell and then interpret their convex hull as a closed volume in $\phi$-space, with $\phi$-space being the 3D space given by the $(\phi_1,\phi_2,\phi_3)$ coordinates.

I am now interested if the volume spanned by these 8 points in $\phi$-space does the following things:

If it contains the origin, $(0 ,0 ,0 )$
If a Ray traveling from the origin in $(-1,0,0)$-direction pierces my given volume

The idea to evaluate both 1.) and 2.) at the same time is to decompose the surface of the convex hull into triangles. For a triangle in 3-Dimensional space, it is easy to evaluate whether it is pierced by my given Ray in $(-1,0,0)$ direction. I can then count how many triangles are pierced. If exactly two triangles are pierced (because of convexity), I know the cell satisfies condition 2.). If exactly one triangle is pierced, I know the origin has to lie inside my volume, that is condition 1.) is satisfied. Lastly, when no triangles are pierced, none of the above apply.

I think this approach is probably relatively fast. Speed is critical, because I have approximately $10^6 ... 10^9$ cells to evaluate per sweep across my lattice.

I'd be interested in any other approaches as well, though.

Update:
So, I think possibly a 3D-Gift-Wrapping algorithm would atleast produce the required result, because it creates the convex hull by consecutively finding triangles on the surface? I will have to try that out tomorrow.

Can I do better than that in terms of efficiency?


texts: Number of special paths between two nodes

texts:
Consider a directed graph. Each node in this graph has an integer label. We want to count the number of special paths between source and sink. Let's define a variable named value. Every path starts with value = label[source]. When we move from node A to B value changes like this: value = lcm( label[B], value ) where lcm is lowest common multiplier. A speical path has two condition:
1- During the move from source to sink value should always change. It means when moving from node A to B, if value before and after the move remains unchanged, that path is not special.

2- value should become some predetermined integer k at the end of the path.

How many ways we can go from source to sink while not contradicting above conditions.

I think we can remove every node that lcm(label[node], k) != k because this node could not be on any special path. Also condition one removes every loop from the graph.

Now the only algorithm I know about counting all the paths between two nodes is to use Dynamic Programming but I can't reduce this problem to that.

Also I can compute the result using backtrack but as there could be exponentially large number of such paths, it's not efficient enough.

original problem statement


texts: Characterization of NFA whose equivalent (minimal) DFA has exponential number of states

texts:
(I don't know if there are standard names for this, so) Let's say that a Nondeterministic Finite Automaton (NFA) is $n$-expansive if it has $n$ states and any Deterministic Finite Automaton (DFA) recognizing the same language has at least $2^{n/2}$ states.

Let $E_n$ be the set of all $n$-expansive NFAs.

Is there a characterization to $E_n$?

Given any NFA $A$, is there a way to test if $A \in E_n$ in polynomial time in $n$ (therefore, without constructing the minimal DFA of $A$)?

The lower bound $2^{n/2}$ is arbitrary. If you know a characterization for other similar exponential bounds (e.g. $2^{n-1}$ or $2^{n/10}$), it will be very helpful.


texts: Is there any good way to judge whether the rectangle is inside the point cloud?

texts: How to judge whether a rectangle in the figure is inside the given point cloud? For example, in this figure, the red rectangle is outside the point cloud and the green rectangle is outside the point cloud.


texts:
I'm trying to understand the contrast between run-time for this function

public static String f(int N) {
    if (N == 0) return "";
    String s = f(N / 2);
    if (N % 2 == 0) return s + s;
    else            return s + s + "x";
}

and this function

public static String f(int N) {
    if (N == 0) return "";
    if (N == 1) return "x";
    return f(N/2) + f(N - N/2);
}

where string concatenation takes time proportional to the size of the strings.

So far, I believe that the first function is called log(N) times for input N and the second 2log(N) times.  Is that right?  Beyond that, I'm not sure how to think about how many operations happen in each of those calls.  I know that for the first function, in the base case there are 0 operations (no concatenation), then 1 operation (concatenation of two null strings with a string of length 1?), then 2 operations.  In general I believe the string produced by a call with N is of length N?  But I just don't know where to start thinking about how it all adds up.

For the second one likewise I'm a little lost.  I just need a way to approach the analysis.  Keep in mind I'm not great with symbols, so if you're going to show off with symbols, I'd appreciate an explanation that will help me follow the symbols as well.


texts: Scalable byzantine consensus protocol for a boolean variable

texts:
Consider the following problem:

We have an extremely large set of nodes, $\pi_0, \ldots, \pi_{N - 1}$ with $N$, e.g., in the order of millions. Each node has a boolean variable $b_0, \ldots, b_{N - 1}$. Some of the nodes will have $b_i = \top$, others will have $b_i = \bot$.

Now, I need a procedure that can scale to that extremely large amount of nodes, that is guaranteed to rapidly converge to a situation where either $b_0 = \ldots = b_{N - 1} = \top$ or $b_0, \ldots, b_{N - 1} = \bot$. It is not absolutely fundamental that, if at the beginning the majority of the boolean values is $\top$, we converge to $\top$, and vice versa.

In the set of nodes, there is a fraction of malicious nodes whose purpose is to make the consensus protocol to never converge.

What solutions are there to achieve this? What is the fastest algorithm that achieves consensus? What is the maximum fraction allowed of malicious nodes for that algorithm?


texts: PSPACE languages reducible to other PSPACE languages in polynomial space

texts: Intuitively it makes sense that all PSPACE languages are reducible to other PSPACE languages in polynomial space. But how would I go about actually showing this?


texts:
I think this is again an easy one:

  $DTIME(f(n)) \subset DSPACE(f(n))$

They say its trivial but I dont see it, why?

And would

  $DTIME(f(n^2)) \subset DSPACE(f(n^2))$

also be true? if yes why or why not?


texts: If set $C$ is recursively enumerable and $B$ is Recursive, and if $B-C$ is recursively enumerable then is $C$ recursive or not?

texts:
So this is how i solve it but someone told me its wrong:

$B-C = B\cap \overline C $ and since $B\cap \overline C $ is r.e and B is recursive recursive sets are closed under intersection then $\overline C $ is not Recursive(because if both of them were recursive then the intersection would be recursive), also since r.e sets are closed under intersection then $\overline C $ must be r.e

and since $\overline C $ and $C$ are r.e then C is recursive

so am i wrong? is C recursive or not and why?


texts: Computing the running time of a divide-by-4-and-conquer algorithm

texts:
I write this code in python:

def sub(ma):
    n = len(ma); m = len(ma[0])
    if n != m : return
    n2 = int(ceil(n/2))
    a = []; b = []; c = []; d = []
    for i in range(n2):
        a.append(ma[i][0:n2])
        b.append(ma[i][n2:n])
        c.append(ma[n2+i][0:n2])
        d.append(ma[n2+i][n2:n])
    return [a,b,c,d]

def sum(ma):
        if len(ma) == 1 : return ma[0][0]
        div = sub(ma)
        return sum(div[0])+sum(div[1])+sum(div[2])+sum(div[3])

Do you know what is a possibly recurrence equation $T(n)$ to the 'sum' method?
I suppose that is like that
$$T(n) = 4T(n/2) + f(n)$$
what it is $f(n)$ ?
Thanks,


texts:
the exact complexity for hypergraph transversal problem is yet unknown and is an open research problem.

However, I would need a fast way to compute, on paper, the minimal transversal of a hypergraph. A transversal intersects all hyperedges of the graph.

A transversal is minimal if it does not contain any transversal as a proper subset.

Let us look at this example, where V = {a,b,c,d,e}

Hyperedge 1: de
Hyperedge 2: abce
Hyperedge 3: bd

How can I compute, on paper, the minimal transversal of this hypergraph? Computing the minimal transversal with only 2 hyperedges is trivial, but in the 3 hyperedges case, the complexity increases.

Looking forward to your input.


texts: Trivial clarification with the analysis of the Dijkstra Algorithm as dealt with in Keneth Rosen's "Discrete Mathematics and its Application"

texts:
I was going through the text, "Discrete Mathematics and its Application" by Kenneth Rosen where I came across the analysis of the Dijkstra Algorithm and felt that the values at some places of the analysis are not quite appropriate. The main motive of my question is not the analysis of the Dijkstra Algorithm in general( a better version and more clearer version exists in the CLRS text) but my main motive is analysis of the algorithm acurately as far as the mathematics is concerned, considering the below algorithm as just an unknown algorithm whose analysis is required to be done. I just want to check my progress by the fact that whether the thing which I pointed out as being weird, is actually weird or not.
Lets move on to the question. Below is the algorithm in the text.
ALGORITHM: Dijkstra's Algorithm.
procedure Dijkstra(G: weighted connected simple graph, with all weights positive)

    {G has vertices a = v[1], ... ,v[n] = z and weights w(v[j], v[j])
    where w(v[j], v[j]) = ∞ if {v[i],v[j]) is not an edge in G}

    for i: = 1 to n
        L(v[i]) := ∞
    L(a) := 0
    S:=∅
    {the labels are now initialized so that the label of a is 0 and all
        other labels are ∞, and S is the empty set}

    while z ∉ S
        u := a vertex not in S with L(u) minimal
        S:= S ∪ {u}
        for all vertices v not in S
            if L(u) + w(u, v) < L(v) then
                L(v) := L(u) + w(u, v)
            {this adds a vertex to S with minimal label and updates the labels of vertices not in S}            return L(z)
{L(z) = length of a shortest path from a to z}

The following is the analysis which they used:
We can now estimate the computational complexity of Dijkstra’s algorithm (in terms of additions and comparisons). The algorithm uses no more than $n − 1$ iterations where $n$ is the number of vertices in the graph, because one vertex is added to the distinguished set at each iteration. We are done if we can estimate the number of operations used for each iteration. We can identify the vertex not in S in the $k$th iteration with the smallest label using no more than $n − 1$ comparisons. Then we use an addition and a comparison to update the label of each vertex not in S in the $k$th iteration . It follows that no more than $2(n − 1)$ operations are used at each iteration, because there are no more than $n − 1$ labels to update at each iteration.

The algorithm uses no more than $n − 1$ iterations where $n$ is the number of vertices in the graph, because one vertex is added to the distinguished set at each iteration., What I feel is that it shall be $n$ iterations and not $n$ as in the very first iteration the vertex $a$ is included in the set $S$ and the process continues till $z$ is inserted into the set $S$ and $z$ may be the last vertex in the ordering i.e.$v_n$.
The rest statements are fine I hope.


texts: Generating integer vectors sorted by total weight

texts:
I am trying to implement an algorithm that finds the key of the RC4 cipher from the inner permutation. For each key byte I have several options, each with different weight. Is there any way, to test first the possibilities with highest weight, than with second highest, and so on?

Basically what I need is to generate vectors like this (for 3 byte key):

[0,0,0]
[1,0,0]
[0,1,0]
[0,0,1]
[1,1,0]
[1,0,1]
[0,1,1]
[1,1,1]
[2,1,1]
...

So it is sorted by sum.

(I have the bytes stored in a table sorted by weight, highest weight on the top.)

A similar problem is solved here: application of Dijkstra's algorithm, but I don't know how to apply it to my problem.

The paper only mentions that they do it in iterative depth manner.

Is there any algorithm which solves this problem?


texts: Is proof of totality of a semantic function for binary numbers cicular?

texts:
I think the following proof found in a textbook is circular, since the proof for case n=n'0 assumes the case n=n'1 and vice versa. Am I missing something?

Proof that the semantic function N is a total function from binary strings into the integers:

  Let N be defined thusly:

  N(0) = 0;
  N(1) = 1;
  N(n0) = 2*N(n);
  N(n1) = 2*N(n) + 1;

  For any n, there is one and only on integer mapped to by N(n), that is to say, N is a total function from binary strings into the integers. (A)

  In the case n = 0, there is only one way to evaluate N(n) and that is with N(n) = N(0) = 0; hence (A) clearly holds. The proof for the case n = 1 is similar.

  In the case n = n'0, we have only one way to evaluate N(n) and that is with N(n) = N(n'0) = 2*N(n'). Assuming by induction that (A) holds for N(n'), (A) clearly holds for N(n). The proof for n = n'1 is similar.

  QED

In the second part of the proof, for the case n = n'0 you have to assume for induction that * holds for n = n'1, and vice versa. Does this not lead to a circular dependency in the proof?


texts: Asymptotics of the number of words in a regular language of given length

texts:
For a regular language $L$, let $c_n(L)$ be the number of words in $L$ of length $n$. Using Jordan canonical form (applied to the unannotated transition matrix of some DFA for $L$), one can show that for large enough $n$,
$$ c_n(L) = \sum_{i=1}^k P_i(n) \lambda_i^n, $$
where $P_i$ are complex polynomials and $\lambda_i$ are complex "eigenvalues". (For small $n$, we may have additional terms of the form $C_k[n=k]$, where $[n=k]$ is $1$ if $n=k$ and $0$ otherwise. These correspond to Jordan blocks of size at least $k+1$ with eigenvalue $0$.)

This representation seems to imply that if $L$ is infinite then asymptotically, $c_n(L) \sim C n^k \lambda^n$ for some $C,\lambda>0$. However, this is patently false: for the language $L$ over $\{0,1\}$ of all words of even length, $c_{2n}(L) = 2^{2n}$ but $c_{2n+1}(L) = 0$. This suggests that for some $d$ and for all $a \in \{0,\ldots,d-1\}$, either $c_{dm+a}(L) = 0$ for large enough $m$ or $c_{dm+a} \sim C_a (dm+a)^{k_a} \lambda_a^{dm+a}$. This is proved in Flajolet & Sedgewick (Theorem V.3), who attribute the proof to Berstel.

The proof provided by Flajolet and Sedgewick is somewhat technical; so technical, in fact, that they only sketch it. I attempted a more elementary proof using Perron-Frobenius theory. We can regard the transition graph of the DFA as a digraph. If the digraph is primitive then the result follows almost directly from the Perron-Frobenius theorem. If the digraph is irreducible but imprimitive with index $r$, then by considering the "$r$th power" of the DFA (each transition corresponds to $r$ symbols), we get the same result. The difficult case is when the digraph is reducible. We can reduce to the case of a path of strongly connected components, and then we get the result by estimating sums of the form
$$ \sum_{m_1+\cdots+m_k=m} \prod_{i=1}^k \lambda_i^{m_i}. $$
(Each such sum corresponds to a particular way of accepting a word, going through the different components in a certain way.) This sum, in turn, can be estimated by pinpointing the largest term, which corresponds to $m_i \propto \log \lambda_i$. For every eigenvalue which is repeated $r$ times, we get an extra factor of $\Theta(m^{r-1})$.

The proof has its rough edges: in the reducible case, we need to pass from terms asymptotic to $C \lambda_i^m$ to the sum mentioned above, and then we need to estimate the sum.

The proof by Flajolet and Sedgewick is perhaps simpler, but less elementary. Its starting point is the rational generating function of $c_n(L)$, and it involves induction on the number of pole magnitudes (!). The basic idea is that all eigenvalues of maximal modulus are roots of unity (if normalized by their modulus), due to a (moderately easy) theorem of Berstel. Choosing an appropriate $d$ and looking at words of length $dm+a$, all these eigenvalues become real. Considering the partial fraction expansion, we get that if the eigenvalue of maximal modulus "survives", then it determines the asymptotics, which are of the form $Cn^k\lambda^n$. Otherwise, we find a new rational generating function which corresponds just to words of this length (using an Hadamard product), and repeat the argument. The aforementioned quantity keeps decreasing, and so eventually we find the desired asymptotics; $d$ might have to grow in the process, to reflect everything that happens in the inductive steps.

  Is there a simple and elementary proof for the asymptotic property of $c_n(L)$?


texts: Minimize sum of $w_i(y_i-y)$ given $|y_i-y| \leq 4w_i$

texts:
Given numbers $y_1,\ldots,y_n$ and $w_1,\ldots,w_n > 0$, find $y_c$ which minimizes $$ L = \sum_{i=1}^n w_i (y_i - y) $$
under the constraint $|y_i - y| \leq 4w_i$.

How to proceed?


texts: Are there 3-colorable maps that can never be colored?

texts:
I just watched this explanation of zero-knowledge proofs with Avi Wigderson: https://www.youtube.com/watch?v=5ovdoxnfFV
Key claims from the video:

Every formal statement can be translated into a map in a way that preserves truth. If a statement is true, its map will be 3-colorable. If not, it isn't 3-colorable https://youtu.be/5ovdoxnfFVc?t=1721

If every formal statement can be translated to a map, and suppose there's a true statement that can't be proven true by Gödel's incompleteness theorems, then doesn't that mean that no algorithm whether P, NP, or worse can exist to color it? Does that mean that there are some 3-colorable maps that can never be colored?
This seems wildly counterintuitive (which maybe is just the nature of Gödels' incompleteness theorems, which I haven't tried to understand the proof of). Or maybe I don't understand Gödel's incompleteness theorems (also likely). If I'm misunderstanding something though, it'd be helpful to know what to look into more.


texts: Probability lower bound on a double cycle on two vertices in random cuckoo graph

texts:
I have read Chater 17. Balanced Allocations and
Cuckoo Hashing in Mitzenmacher. Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis and got stuck with a problem.

We have $m$ elements and $n$ buckets. Each element is hashed into two random buckets (we assume that two our hash functions are completely random).
If each bucket corresponds to a vertex and each element corresponds to an
edge. Then we have a random graph with $n$ vertices and $m$ edges.
Loops and multi-edges are allowed.

What I don't understand is how to get the lower bound on probability
to have a double cycle on two vertices (without self-loops).
To estimate it, the authors first calculate the expected number of double cycles on two vertices.
It is ${m}\choose{3}$ $(1 - \frac{1}{n}) (\frac{2}{n^2})^2$.
Here $(1 - \frac{1}{n})$ is probability that the first edge doesn't form a self-loop. And $(\frac{2}{n^2})^2$ is probability that two remaining edges
are between the same two vertices as the first one.
Next the authors write:

  We easily observe that when $m = \Omega(n)$ this expectation is
  $\Omega(1/n)$. A calculation of the variance readily yields the
  probability that there
  is such a triple is also $\Omega(1/n)$, using the second moment method.

As I understood the authors mean that using the second moment method ($P(X = 0) \le \frac{Var[X]}{(E[X])^2}$), we can get that $P(X \ge 1) = 1 - P(X = 0) \ge 1 - \frac{Var[X]}{(E[X])^2} \ge 1 - n^2 Var[X] = \Omega(1/n)$.
Here $X$ is a random variable that equals to the number of triples of edges
that form double cycle on two vertices.
So this means that Var[X] should be $\frac{1}{n^2} - \Theta(\frac{1}{n^3})$. I tried to calculate variance using the formula
$Var[\sum_i X] = \sum_i Var[X_i] + \sum_{i \not=j} Cov(X_i, X_j)$ since
$X_i$ and $X_j$ aren't independent.
Here $X_i$ is an indicator random variable that equals one when $i$-th
triple of edges form a double cycle on two vertices.
But I always receive a complicated formula that looks like $c_1 \cdot \frac{1}{n} + c_2 \cdot \frac{1}{n^2} + c_3 \frac{1}{n^3}$.
Here $c_1 \cdot \frac{1}{n}$ appears due to term $\sum_i Var[X_i]$ and since $Var[X_i] = \Theta(1/n^2)$.
Is there a simpler way to calculate variance and show that $P(X \ge 1) = \Omega(1/n)$ or I have a mistake somewhere?

Thank you!


texts: Why multiplying float number by multiple of 10 seems to preserve better precision?

texts:
It is famous that for float numbers:

.1 + .2 != .3

but

1+2=3

It seems that multiplying floats by 10 allows you to preserve more precision. To further illustrate the case, we can do this in python:

sum([3000000000.001]*300)
#900000000000.2957

sum([3000000000.001 * 1000]*300) / 1000
#900000000000.3

By multiplying each element in the list by 1000 and divide the sum of the list by 1000, I can get the "correct" answer.
I am wondering:
1) why it's the case.
2) Will this always work, and
3) At what magnitude, will this method backfire, if it will.


texts: LP realaxation for multicut problem with polynomial number of constraints

texts:
The integer linear programming formulation for the multicut problem for the given graph $G = (V,E)$ and distinguished source-sink pairs of vertices $(s_1,t_1),...,(s_k,t_k)$ is:

\begin{alignat}{3}
\text{minimize} & \quad  \sum_{e \in E} c_ex_e \\
\text{subject to} &\quad  \sum_{e\in P} x_e  \geq 1, & \quad  \forall P \in \mathcal{P}_i , 1 \leq i \leq k \\
& \quad   x_e \in \{0,1\}, & \quad  \forall e \in E
\end{alignat}

where $c_e$ is the cost of edge $e$ and $\mathcal{P}_i$ is the set of all paths $P$ joining $s_i$ and $t_i$. The number of paths in the graph may be exponential in the the size of the input so the number of constraint in this formulation may be exponential. In the book The Design of Approximation Algorithms they provided a separation oracle for the LP relaxation of this ILP by allowing $x_e$ to be a positive real number. But it is also stated in the book that it is possible to give a LP with polynomial number of constraints, equivalent to the LP relaxation stated above i.e. any optimal solution to either one can be transformed in polynomial time to an optimal solution to the other one. What is the main idea to reduce the number of constraints?

EDIT: It seems to me that this question is quite relevant to the following post but I can't understand it clearly:
Use complementary slackness to prove the LP formulation of max-flow only need polynomial number of path constraints


texts:
I am trying to design a context-free grammar for the language $L = \{a^ib^jc^k \mid i\neq j+k\}$ over the alphabet $\Sigma = \{a,b,c\}$.

I know that I can split this up into the union of two cfg's $S_1$ and $S_2$,
where $S_1$ is the case where $\#_a \lt \#_b + \#_c$,
and $S_2$ is the case where $\#_a \gt \#_b + \#_c$.

I keep producing the grammar that generates this language but not in the correct order, that is I am having a hard time keeping the $a$'s on the left, $b$'s in the middle, and $c$'s to the right. Is this even context free?


texts: What are the examples of scalable and non-scalable data structures?

texts:
Big data era, people say the big data systems must use the scalable data structures and store.

I didn't get the point here. I need some examples.

What are the good examples of (1) scalable and (2) non-scalable data structure respectively?

Can any one give me an idea on it?


texts:
This might not be a computer science specific question and apologies if that is the case but it does come from material related to working out access control lists and I cannot understand the notation and I wonder if someone could break it down for me?
$$A’[s_i,o_j]=A[s_i,o_j] \; ∀(s_i,o_j)≄(s,o)$$
I understand that $A’[s_i,o_j]$ is the new resulting matrix after some operation and I think $s_i$ and $o_j$ are the matrix pairs that are not being amended although I do not know exactly that this is the case or how adding the $i$ and $j$ denotes this.
This might be way off the mark but is it saying that the new matrix is equal to the old matrix where none of the pairs are equal to the pair being deleted?
I am also looking at a list of set symbols and I cannot find this $≄$ listed.


texts:
Recently, I encountered terminologies such as primitive recursion and recursion combinator. One of the sources is here link

I googled and read some, but missing the points of them. I know that recursion occurs when a function appears within its definition. While $\lambda$-calculus cannot express such recursive definitions directly, it can use combinators to implement recursion.

So, what are Structural recursion, primitive recursion, recursion combinator and recursion principles? how each related to others?

Hoping someone could explain these clearly, so I can go in the right direction. now I am struggling to figure out their "points".

Thanks in advance!


texts: Thompson's construction, transforming a regular expression into an equivalent NFA

texts:
There is this case of concatenation that says (from wikipedia):

  The initial state of N(s) is the initial state of the whole NFA. The final state of N(s) becomes the initial state of N(t). The final state of N(t) is the final state of the whole NFA.

My question is, does this mean that the final state of N(s) is linked to the initial state of N(t) with an edge labeled ε ?


texts:
$$\begin{align*}
  T[1] &= 1 \\
  T[2] &= 2 \\
  T[i] &= T[i-1] + T[i-3] + T[i-4] & \text{for \(i \gt 2\)} \\
\end{align*}$$

I have to calculate $T[N]$, but $N$ is too big ($\approx 10^9$), how can I optimize it?


texts: Finding bicliques in a bipartite graph of minimum size

texts:
Let $G=(U \cup V, E)$ denotes a bipartite graph. A biclique $C = (U, V)$ is a subgraph of $G$ induced by a pair of two disjoint subsets $U' \subseteq U$, $V' \subseteq V$, such that $\forall u \in U', v \in V':  (u, v) \in E$.

Given $\delta$, I'd like to identify bicliques $(U',V')$ such that $|V'| \ge \delta$.  Since the number of all bicliques in a bipartite graph w.r.t its size can be exponential, I'm looking for an approximate algorithm (desirably with guarantees), that can find bicliques such that $|V'| \ge \delta$. For example, find $k$ bicliques where $|V'| \geq \delta$, in time polynomial w.r.t. $k$ and $G$.  Can anyone suggest such an algorithm?

One naive solution is to enumerate bicliques using an enumeration-based algorithm and keep the bicliques that satisfy the last condition until the selection of "k" bicliques.


texts: LCA from children using bottom up approach?

texts:
I'm interested in finding the LCA of two distinct Nodes in a (not necessarily binary) tree from the bottom up without using depth.

How would I go about traversing the tree, starting from any 2 arbitrary nodes, each of which points to a previous node as shown without a depth variable?


texts: Hierarchial clustering cannonnical representation?

texts:
I have to handle large binary dataset. That is one of the reasons I have to build my own Hierarchical Clustering. As I digged into the algorithms I was surprised and not ;) to find that it is possible to have multiple (not just two) vectors that have the same distance (hamming,overlap,...), so you can pair them differently in a 'correct' way.
F.e. using overlap as similarity mesaure ... the following 3 vectors have overlap of 2 and there are 2 different correct pairing.
 sequence : 110,101,111

what this means is that there is multiple ways to cluster those :
 ((110,111),101)  vs (110,(111,101))

 sequence : 110,101,111,011

 (110,((111,011),101))  vs ((110,(111,011)),101)

Let me illustrate it with integers  :
 2,6,8,4
 (2,((4,6),8))  vs ((2,(4,6)),8) vs ....

What this means is that there are no canonical way of clustering/dendogram .
How do you handle that ?
Is there a different type of clustering that can have canonical/single representation ?


texts: Smallest string length to contain all types of beads

texts:
I read this question somewhere, and could not come up with an efficient answer.

A string of some length has beads fixed on it at some given arbitrary distances from each other. There are $k$ different types of beads and $n$ beads in total on the string, and each bead is present atleast once. We need to find one consecutive section of the string, such that:

that section contains all of the $k$ different types of beads atleast once.
the length of this section is as small as possible, provided the first condition is met.

We are given the positions of each bead on the string, or alternatively, the distances between each pair of consecutive beads.

Of course, a simple brute force method would be to start from every bead (assume that the section starts from this bead), and go on till atleast on instance of all beads are found while keeping track of the length. Repeat for every starting position, and find the minimum among them. This will give a $O(n^2)$ solution, where $n$ is the number of beads on the string. I think a dynamic programming approach would also probably be $O(n^2)$, but I may be wrong. Is there a faster algorithm? Space complexity has to be sub-quadratic. Thanks!

Edit: $k$ can be $O(n)$.


texts: Type-checking function calls with functional subtyping

texts:
I'm relatively new to the topic. Suppose that you want to type-check an expression of the form f(a), i.e. a function call. Assuming that all the declarations are provided explicit types, I believe that a simple type-checker would behave as follows:

Given the environment, compute the types of a and f;
Check that the type of f be of the form $T\to U$;
Check that the type of a be a subtype of $T$;
Return $U$ if needed.

But now suppose that, for all $U$, the following subtyping relation holds:
$$
[U]<:\text{Int}\to U
$$
where $[\thinspace\cdot\thinspace]$ denotes the array-type, and that computation (1) finds the types of a and f to be resp. $T$ and $[U]$ for some $T$, $U$. Now, $[U]$ is not a function-type, so check (2) fails. I'm assuming that the definition of $<:$ is completely independent of the type-checker, so we can't just hard-code a check (2.1) for array-types, too. We could instead check that $[U]$ be a subtype of a least acceptable function-type $T\to\top$, where $\top$ denotes the universe-type, but what if function-types are invariant according to $<:$?
I suspect that what I really need is a form of type-inference, rather than type-checking, even though the types of f and a are completely determined, which doesn't make sense to me. What would be the correct approach, here?


texts: Polynomial time verifier for $\overline { EQ_{CFG}}$

texts:
How to find, or prove impossible, apolynomial time verifier for $\overline { EQ_{CFG}}$?

$\overline { EQ_{CFG}}$ means all pairs G and H, which are CFGs such that L(G) is not equal to L(H)


texts:
I'm stuck on this question, a BST is slightly broken only if there is a node with value x in which :

there is at least one value less than x on its right branch or atleast one value greater than x on its left branch.

for example :

                3
               / \
             10   5
             /\   /\
            8 15 4  7

suggest an algorithm which will fix the tree also it should keep its original shape and same values, at worst case $O(n)$, where $n$ is the number of values.

I know it is possible to fix it and keep same shape but I can't seem to find the an algorithm that is at worst case $O(n)$.


texts: Relating memory complexity and decidablity

texts:
Given a language $L_u$, about which we know that there exists a non-deterministic turing machine which accepts it (as in, implying $L_u \in RE$) with memory complexity of $c^{p(n)}$, where $c$ is a constant and $p(n)$ a polynomial, can we decide whether $L_u \in R$ or not?

Memory complexity represents the largest difference of indices of used slots of the tape. So I believe $L_u \in EXPSPACE$, although here it is defined using a constant, whereas most articles use a 2 to the power of some polynomial. This is why I'm not sure about that fact.

Basically, what I'm asking is:

Is $L_u \in EXPSPACE$?

If it is, can this fact be used to derive whether $L_u \in R$, and how?

If not, how can the fact that $L_u \in RE$ and that the turing machine has a memory complexity of $c^{p(n)}$ be used to determine whether $L_u \in R$, and how?


texts: Dijkstra's algorithm: why are distances initialized to infinity and not some negative number?

texts:
I'm a high schooler who has been self-learning graph algorithms for a month or two now.

I was wondering why the distance array in Dijkstra's algorithm is initialized to infinity (INT_MAX in C++) when it could just be set to a negative number? Since Dijkstra's isn't even used for negative numbers, why isn't the distance array set to some arbitrary negative number (say, -1) and instead a very large number which takes up far more space? It's possible that I'm overestimating the space occupied in memory by a very large INT value.

I'd appreciate any constructive feedback.


texts: Complexity of deciding the satisfiability of a quasi-monotone CNF formula

texts:
A quasi-monotone CNF formula is a formula where each variable appears at most once as a positive literal (and any number of times as a negative literal).

What is the complexity of deciding its satisfiability?


texts: Is it legal to draw an NFA with fewer nodes than what I normally see?

texts: Is it Ok to express an NFA accepting 1*0 like the one above? All examples in books are represented like the bottom one. I'd like to know is that only a convention or it must have two extra nodes?


texts: Beam size is a parameter in some RNNs like TensorFlow's Magenta. What is beam size?

texts: Magenta's melody_rnn_generate method includes a parameter beam_size. What is it and how does affect the melody?


texts: What will happen to NP-Hard problems if P=NP

texts:
I was going through the lecture of  prof. Erik Demaine and he said that a problem X is NP-Hard if it is at-least as hard as every problem Y that belongs to NP class.

He further said that if we can prove that there exists a problem that belongs to NP but not to P, then we can absolutely be sure that NP hard problems don't belong to P class.

Here is my question... What happens if P=NP. Thus it mean that all NP-hard problems become polynomially solvable? Will all NP hard problems reduce to polynomial order if P=NP?


texts: Can't understand this division algorithm in Computer Architecture

texts:
So, I'm preparing for an exam where I have solve divisions using this division algorithm:

While I understand the theory (image above), I couldn't understand this example below:

My problem is with the "First Step", apparently you place the dividend in the "Remainder" box but I don't undetrsand how did they come up with the divisor (10 000), where did this number come from?


texts: Reducing CLIQUE to Super Connector problem

texts:
I am trying to show that our problem is NP-Complete by reducing the known problem CLIQUE to our problem.
Regular CLIQUE problem:

Input: An undirected graph $G$ and a positive integer $K$.
Goal: Does $G$ have a clique of size at least $K$?

Our problem:

Input: An undirected graph $G$ and a positive integer $K$.
Goal: Is there a group of size $K$ of super connectors in $G$?

A super connector is a node with at least $C$ (i.e., a fixed number of) edges. A group $S$ of super connectors is a set of super connectors all connected to each other.
A group of super connectors is thereby a clique and a return value of TRUE from our problem will result in TRUE in the CLIQUE problem as well.
My idea to solve this is that I modify the graph by removing all nodes that aren't super connectors. We are then left with a graph where every node is super connectors and can then input the graph in the CLIQUE problem to see if there exists a clique and thereby get a solution for our problem. By modifying the graph like this both of the problems will give the same outputs with the same inputs. Am I on the right path or completely wrong?


texts:
I have to write an algorithm for a following problem. I have a function that has 2 parameters: an array of 32 bit unsigned whole numbers - bit vectors [ARR] and distance[dist]. We need to find how many 32 bit numbers x there are such that they are differing from each of the bit vector for the most dist bits.

Example: We have vectors: 0011, 0101 and 0101. When dist=3 then for 0000..1111 there are 13 such numbers. If dist=4 then the result is 16.

My idea is to do it with Levenshtein algorithm ( example on this website), so that I would convert the array into string.

But it would be too slow. I have a hint that we should look at the ARR and find those bits that are same in every number and therefore we need not compare them.

  "For example, we have specified bit vectors with 18 fixed bits (ie we
  will test a total of 2 on (32-18) values) and we have given dist =
  6. If you calculate for a value of x, which varies from the modified bit vectors in 6 bits, you will count just one. If it differs in less
  bits, for example in 5 bits, then you count 19 times (4 differences -
  172x, 3 differences - 988x, ...). Think about the combinatorial
  problem here."

I have trouble understanding that part. Can someone please explain this to me and give me a suggestion in which direction to go?


texts:
I have a directed acyclic graph where the nodes are tasks and the edges are dependency relations between tasks - the edges go from the dependency to the task that depends on it.
It is possible that multiple tasks depend on the same parent task and that a task depends on multiple other tasks, so it can be any DAG.

I need to transform this DAG to satisfy the following constraint:

Forks (nodes that have multiple children) and joins (nodes that have multiple parents) must come in pairs - all paths coming from a fork must eventually converge to the same join.

To me it seems that there are DAGs that cannot be transformed without adding new dependencies, which may reduce the parallelism (and thereby execution speed). I'm looking for an algorithm that transforms the DAG in a way that:

No dependencies are deleted - this is an absolute requirement, since a task cannot run until all of its dependencies have completed. This means that if there is a path from node A to node B in the original DAG (respecting the direction of the edges), there must be a path in the transformed DAG, too.
New dependencies are only added when necessary - if the original DAG can be transformed to fork-join format without adding dependencies, we should not add any.
If it is necessary to add new dependencies, we should add as few as possible.

Of course 3. is not an absolute requirement (nor is 2., but I'd like to have that one if possible).

Thanks in advance,

Daniel


texts:
So I've been looking into lambda calculus on and off for months simply trying to understand the numerical system and the successor function.  I understand that it's basically just argument evaluation, but the syntax confused me for the longest time.  Finally, I found this:

S0 = (λ abc.b(abc)) (λ sz.z)
     = λ bc.b((λ sz.z) bc)
     = λ bc.b((λ z.z) c)
     = λ bc.b(c)

from this URL: http://palmstroem.blogspot.com/2012/05/lambda-calculus-for-absolute-dummies.html

and realized that I didn't understand how this worked because there seems to be no delimiter indicating the start of argument space.  My question is: Is there an acceptable delimiter for this in lambda calculus, and, if not, how can I verbalize this when writing or viewing  it?

EDIT: Some people seem to have misunderstood this, so let me explain better.  How do I indicate that a function is being called on a specific set of arguments?  For example, in most programming languages the indicator is just parenthesis

function(arg0,arg1,arg3...)

Is there an equivalent to this in untyped lambda calculus?

ANOTHER EDIT: Okay, it's still misunderstood as to what I mean.  Let's talk about the successor function again.  The wikipedia pages shows something like the following:

Succ=La.Lb.Lc.b (a b c)
               ^

The marked whitespace is annoying since It's not clear that the part in parenthesis is still part of the function itself, and instead looks like an argument is being passed to the function.  Is there a delimiting character that separates the body of the function from the  arguments on which it is to be called?  Example:

Succ=((La.(Lb.(Lc.(b,((a,b),c))))),),,

The problem that I think I'm having is that since functions can be returned as primary values, the syntax doesn't express that very clearly.  However, in the example that I gave, we can see that there are three commas without trailing inputs, indicating that the function takes 3 values (the function to find the successor of and the successor's potential arguments).  Is there a good convention to express the point where a function's body ends and the values that it needs to be evaluated begin?

*A VERY IMPORTANT EDIT: * This is not about currying.


texts: Minimizing a multivariate polynomial over the hyper-cube is NP-Hard

texts:
In an exercise I have to show that minimizing a multivariate polynomial with $n$ variables over the hyper-cube $H = \{ (x_1, \ldots, x_n) : 0 \leq x_i \leq 1 \}$ is NP-Hard. Formally, given $p(x_1, \ldots, x_n)$ and $\alpha$, does $\min_{0 \leq x_i \leq 1} p(x_1, \ldots, x_n) \leq \alpha$?

My idea is to reduce it to MAX-SAT as follows. Suppose I am given the formula:

$(x_1 \vee \overline{x_2} \vee x_3) \wedge (\overline{x_1} \vee \overline{x_3}) \wedge (\overline{x_1} \vee x_2 \vee \overline{x_3})$

Then I consider:

$p(y_1, y_2, y_3) = y_1 (1 - y_2) y_3 + (1 - y_1) (1 - y_3) + (1 - y_1) y_2 (1 - y_3)$

If $p$ reaches a minimum at a corner of $H$ then the assignment:
$$x_i = \textit{true} \ \text{if} \ y_i = 0 \ \text{and} \ x_i = \textit{false} \ \text{if} \ y_i = 1$$
is a solution for MAX-SAT value for the corresponding formula and since MAX-SAT is NP-Hard we are done. However, how do I proceed if $p$ reaches its minimum at an interior point? Or is it the case that it will always be a corner?


texts: Is generating MIN-3-UNSAT $\mathsf{NP}$-hard?

texts:
Input: amount of variables (with minimum of $10$ since otherwise problem is unsolvable).

Output: unsatisfiable formula.

Restrictions:

Every clause contains exactly 3 variables.
Every clause differs by at least one variable.  For example, a pair of clauses $(x\lor y\lor z)\land(x\lor \overline y\lor\overline z)$ is forbidden.
Every variable must be involved.
Removing any clause makes the formula satisfiable.

No set of clauses is given as input. Is this problem in $\mathsf{FP}$ or is it $\mathsf{NP}$-hard?


texts:
I'm doing some research on the CRCs, but i can't find informations about the use of two (or more) short CRCs compared to the use of a longer CRC:

Suppose that i have a dataword A of some length and 3 different generator polynomials, 2 of degree 8 and one of degree 16. These polynomials are used respectively by CRC1, CRC2 and CRC3 algorithms, where CRC1 and CRC2 generate 8-bit codes while CRC3 generates 16-bit codes.

Suppose also that the three CRC have the same Hamming Distance for datawords of the same size.

now consider these 2 options:

Compute CRC1(A)=x1 and CRC2(A)=x2 and use codeword A|x1|x2 (where '|' means concatenation);
Compute CRC3(A)=y and use codeword A|y;

what are the eventual advantages and disadvantages of the first approach in respect to the second considering error detection capabilities?

Please provide also some references if you have them!


texts: Dijkstra single-source shortest path $\Omega(n\log n)$?

texts:
If I have a directed graph with $n$ weighted edges, is it possible to prove that Dijkstra's single-source shortest path algorithm takes $\Omega(n\log n)$ in the worst case?

I know heaps reduce Dijkstra's algorithm to $Ο(m \log n)$ and can be stored in an array.
Rooted, binary, as complete as possible tree with all nodes satisfy Heap property:
    node <= all children of node.. Is this the right direction?

**I have an implementation that runs $O( (n + m)\log n)$, could it work?


texts: Proving that a Turing machine decides a language in NP

texts: Suppose a deterministic Turing machine T decides language L and L is in NP. Then must it be provable in ZF that T decides L?