texts: Is the complexity of problems in NP exponential at most?

texts:
I read on Wikipedia the following:

  Since NP-complete problems are in NP, their running time is at most exponential.

Is that correct? I thought a problem is in NP-complete if:

the problem is also in NP (i.e. accept verification in polynomial time)
Every problem in NP can be reduced to it in polynomial time.

These two conditions don't necessarily limit (to our knowledge) how hard a problem in NP Complete can be, right? (other than bounding the complexity of verification to polynomial time).

What am I missing?


texts: Why the Smallest Operable Data Type in Most Programming Languages Is One-Byte Sized?

texts: Why the smallest operable data type in most programming languages is one-byte sized? Is it possible that to operate with a single bit? If it is possible, how to do it in practical?


texts: Wikipedia says this grammar is LR(0), but Grammophone says it is not; is it?

texts:
E -> E * B .
  E -> E + B .
  E -> B .
  B -> 0 .
  B -> 1 .

I am confused because Wikipedia cites this grammar as an example of an LR(0) grammar and constructs an LR(0) parsing table for this grammar, while Grammophone reports shift-reduce conflicts and marks some cells in the grammar's LR(0) parsing table red. (The dots are not terminals; rather, they denote end of production; Grammophone requires this.)
What's going on here?


texts: How do you translate these 2 regular languages in words correctly?

texts:
Given are 2 different languages and I'd like to know if I understand them correctly.

L ⊆ ∑* is a regular language.

cycle(L) = {vu ∈ ∑* | uv ∈ L}
L/2 = {x ∈ ∑* | ∃y ∈ ∑* : xy ∈ L, |x| = |y|}

I need to know that because the actual task is to show that these languages are regular by either describing how you build a DFA or NFA for them.

But I just like to know if I understood them correctly.

So 1. means that every word has an existing reverse.

As example we have word aaa and bab, if we concatenate them, we have aaabab. Now the language says that there is also a word babaaa

Means that we have two words of same length and we concatenate them?


texts:
Here's a problem that came up when organizing a party:

You need to place $n$ guests in tables of size 10. Each guest has a list of $m$ other guests they'd like to have in their table. Find a seating arrangement so that the number of granted wishes is maximized.

As many tables as possible should be full, i.e. at most one table can have less than 10 guests.

We tried to formulate it as a directed graph problem where for each guest there's a corresponding vertex in $V$. The edges represent wishes of the guests, i.e. there's an edge $(u, v) \in E$ if guest $u$ wishes to sit next to guest $v$. Note that this does not imply $(v, u) \in E$ because the wish might not be mutual.

Now finding the seating arrangement could be thought of as finding $m/10$ sets of 10 vertices where each set is as close to a fully connected clique as possible. This way we maximize the happiness of the guests. Another way of looking at it would be minimizing the number of outgoing arcs from each set.

To me this sounds very difficult, but I couldn't find a satisfying problem which I could use in a NP-hardness reduction proof. I noticed that this is pretty close to a K-clique densest subgraph problem, but that is also only about undirected graphs.

Is there a way to formulate this as a problem with an undirected graph, or some other problem related to cliques I am missing?


texts: Is there a way to solve the optimal branching / arborescence problem with path-dependent weights?

texts:
The optimal branching problem (solved by Edmond's algo or Tarjan's algo) finds the spanning arborescence for a particular graph. [0]
I'm looking for a formulation of the problem that allows for path-dependent weights.
i.e. if I have a path from ROOT to A, B, C, with weights 2 for each of the edges:
ROOT =[2]> A =[2]> B =[2]> C
The overall cost of the path is 8, not 6.
Is such a formulation possible?
[0] https://en.wikipedia.org/wiki/Edmonds%27_algorithm


texts:
what are the language that the DFA accept ?

so my approach for the first one is : a needs to be 4n+1 for all n>=0, #b%2=0
also i found out there some loops inside the DFA and a:b ratio is 3:1

but how do i write it formally ?  L = {W |.... } ?

second DFA is that the word must end with letter b, there also few loops, so a* can be accepted and folloing with b... so... (a)* b but whats next ?

ty


texts:
What is the recurrence equation for this function?
i <- n
while ( i > 1){
   j <- i
   while ( j < n){
      k <- 0
      while (k < n){
         k = k +2;
      }
      j <- j * 2;
   }
   i <- i / 2;
}

I guess, T(n) =T(n^2/4) + 2/n. or  T(n) = M*T(n^2/4) + 2/n
Am I right to guess?
I think something's gonna have to come to M, but I'm not sure.


texts: Where to find published research papers?

texts:
Coming from the POV of someone who is thinking about pursuing a PhD in Computer science.

I am having trouble deciding what I would focus my research on when I go for my PhD. See also this question on academia.SE.

So I am thinking that reading/keeping current on what research is being done and what research papers are being released is a good source of....inspiration?  Plus good knowledge to know.

Is there central place/database of/good starting place to see recently published CS research papers, or are they all hidden deep within the websites of the University they were written at?


texts: Augmenting a tree such that we preserve the insertion operation optimal runtime

texts:
Suppose we are given a red-black tree with $n$ vertices with distinct keys and we want to store, as addition information in each vertex $v$, the biggest key out of the keys that are smaller than $v$ (or nothing if it doesn't exist). Can we insert a new element in this tree in $O(\log n)$ time?

I think that we can. My idea is that while traversing the tree in order to determine where to insert the new element, we could just update this additional information for every vertex that we encounter. The problem with this is that we may not update all the required vertices, for instance:

        (80)
      /      \
    (1)      (81)
   /   \     /   \
  (0) (79) (77)  (82)

Here, if we would try to insert $76$, we would not update the additional information in the vertex with value $77$ if we use the method I described above.

I would like strongly appreciate hints to improve my solution (mostly I would want only hints).


texts: How to color sudoku with this added constraint?

texts:
I couldn't figure out an algorithm for following graph coloring problem:

Output color of each vertex for this graph:
Given  a solved 9*9 sudoku board that is a 9-colored board, applied first three rules below( a 4*4 one is in the picture as example),
Output a new k-coloring(k > 9) for the graph made from the input when we also applied rule number four.
Edge incidence rules:
 1. There exists an edge between every pair of cells that are in the same row.

There exists an edge between every pair of cells that are in the same column.
There exists an edge between every pair of cells that are in the same 3*3 square.
There exists an edge between every pair of cells that have the same label in the input board, that is an edge connects every cell labeled with number 1 to every other cell with the label 1, and every 2 is connected to any other 2s, and ...

Edit:
I wondered whether there is an algorithm with tighter upper bound on k than the usual greed algorithm or not.(The greedy algorithm's upper bound on k is maximum of degrees of vertices of the graph plus one)
Till now I just figured out that the subgraph that contains each color in the input is a clique when the rule four applied, That is there is a clique with vertices labeled 1, a clique with vertices all labeled 2, and so on.Since there is an edge between every pair of vertices with the same label so they are all connected, thus we have a complete subgraph, i.e. clique.


texts:
I am trying to find the total number of distinct minimum weight spanning trees(MWST) in a simple, undirected, unlabeled and weighted graph but I am confused whether should I have to consider Isomorphic trees(if it is present) as a single minimum weight spanning tree or not while counting the distinct MWSTs because graph is unlabeled.

For example, If I have a graph as :

Now, I have to find the Total number of distinct minimum weight spanning trees(MWST) in the above weighted graph.

I got total $3\times2 =6 $ possibilities of MWSTs but I also found the possibility of Isomorphic trees in these total $6$ MWSTs because graph is unlabeled. For example,the below $2$ MWSTs are Isomorphic in nature for the above given graph.

Similarly , If I have a simple, weighted, undirected and unlabeled graph as :

Now, I got total $2^{2} \times 2^{4} = 64$ MWSTs but If I consider Isomorphism property in a graph then I am getting 2 Isomorphic Trees as :

So, If I consider the possibility of many Isomorphic trees like above in the given graph then total number of distinct MWSTs will be less than $6$ and $64$ in the above 2 cases respectively. But I am not sure whether it is correct or not.

So, My doubt is :- While counting the total number of distinct MWSTs in an unlabeled weighted graph, Should I have to consider Isomorphic MWSTs as a single minimum weight spanning tree  or not ?


texts: What is the accepted term for the "stale-while-revalidate" cache strategy?

texts:
I was trying to look for docs and libraries about a cache akin to RFC 5861 where objects can be in three age states, fresh and expired (as usual), and a third where it can be returned immediately (as though fresh), but asynchronously checked (as though expired).

Is this a named pattern? What should be searching for to find literature on this outside of the HTTP realm?

  3.1.  Example

  A response containing:

Cache-Control: max-age=600, stale-while-revalidate=30

  indicates that it is fresh for 600 seconds, and it may continue to be served stale for up to an additional 30 seconds while an asynchronous validation is attempted.  If validation is inconclusive, or if there is not traffic that triggers it, after 30 seconds the stale-while-revalidate function will cease to operate, and the cached response will be "truly" stale (i.e., the next request will block and be handled normally).


texts: Algorithm for arranging elements into different sized buckets

texts:
I have a set of items. For each item, there is a list of buyers I can sell it to and a corresponding price they will pay me. For example:

item1:        item2:       item3:       item4:
  john: 17      john: 19     bob:  42        ...
  bob:  23      mick: 22     mick: 44
  sue:  19      liz:  24     sue:  38
  liz:  20                   joe:  45

I need to assign each item to one buyer so as to maximise the amount of money I make. If it were as simple as this, the assignments would go

item1: bob
item2: liz
item3: joe
          ...

However, I also need to try to meet quotas of items for the buyers.

So these quotas might be:

bob:  99
sue:  30
john: 45
        ...

i.e. I need to sell a total of 99 items to Bob, 30 to Sue etc.

The quotas will not cover all items, so it could be that of a total of 1000 items, only 800 are forced to follow the quotas and the remainder can go to whichever buyer pays the highest amount.

The problem then, is to assign the items in such a way as to maximise revenue while still filling the quotas.

In some cases it will not be possible to meet the quotas because not every item can be assigned to every buyer - for example, if there were only the 3 items above and Joe had a quota of 2, I wouldn't be able to meet it as only item3 can be sold to him. It seems to me two types of solution are available in this case, either of which I'm open to.

Find a solution that minimises the number of unfilled quota positions and maximises revenue.
Run a preliminary algorithm that checks if the quotas are fillable. If they aren't, simply fail at that point (under the assumption that some user will then manually tweak the quotas and run the process again). If they are, then find a solution that fills them and maximises revenue.

I've thought of a few strategies, but none that has the mathematical rigour I'd like.

Also, I'm not really sure what flavour of problem this is, so if anyone can suggest a better title for this question, feel free to edit :)

For context, this is a work-related requirement for an energy broker that wants to assign customers (the 'items' in my example) across its pool of energy suppliers.

Edit: If this can be thought of as a form of the Generalized Assignment Problem (as per @fade2black's) answer, it may be helpful to tweak things in this way: items that can't be sold to a particular buyer are assigned a revenue of 0 with respect to that buyer.

So in other words, every item can be sold to every buyer, but some have a revenue of 0. Presumably any optimisation algorithm will then tend to filter these 0-revenue combinations out.


texts: Choice of algorithm to use to produce an optimal solution based on a growing number of constraints

texts:
Background Information
I am currently doing research for my final year project in college. I am planning on building an ambulance booking system that will ease the process of booking an ambulance for patient transfer - that is to transfer a patient from one hospital to another.
A subsystem of the overall booking system will be a broker system. This will select the optimal ambulance company of n number of companies based on a number of hard constraints:

Price
Capacity
Average time to transfer a patient (this will be calculated over time)
Is it active at this current time (some companies only run during the day)
Type of ambulance (normal or cardiac)

Edit: This list of constraints is expected to grow as I further my research on the problem. For example since I first this question I have added a new constraint:

Urgency (Is the situation urgent or can we be lenient with time)

Choice of Algorithm
The problem I am having is that I do not know what type of algorithm to use. I was just going to use a brute force search but my supervisor said the performance of that algorithm will decrease exponentially as the number of companies and hard constraints grow.
I have been searching Google and Google Scholar to find possible algorithms to use but so far I have had little luck. Can anybody suggest some algorithms to look up? Relevant links/resources would also be appreciated.


texts:
I'm learning about NEAT from the following paper: http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf

I'm having trouble understanding how adjusted fitness penalizes large species and prevents them from dominating the population, I'll demonstrate my current understanding through an example and hopefully some one will correct my understanding.

let's say we have two species, A and B, species A did really well last generation and were given more children, this generation they have 4 children and thier fitnesses are [8,10,10,12] while B has 2 and thier fitnesses are [9,9] so now thier adjusted fitnesses will be A[2,2.5,2.5,3] and B[4.5,4.5].

now onto distributing children, the paper states :"Every species is
assigned a potentially different number of offspring in proportion to the sum of adjusted fitnesses f'i of its member organisms"

So the sum of adjusted fitnesses is 10 for A and 9 for B thus A gets more children and keeps growing, so how does this process penalizes large species and prevent them from dominating the population?


texts: About the complexity of deciding if the closed world assumption for renamable Horn CNF is consistent

texts:
Let $T$ be a theory that only contains renamable horn formulas. What is the complexity of deciding if the closed world assumption $CWA(T)$ is consistent?

The closed world assumption is defined as follows:
$CWA(T):=T\cup \{\neg p : p\text{ is atom } T \not\models p\}$
Renamable horn formulas are CNF formulas that can be renamed to horn formulas by negating a variable in the formula for example
$(x_1\vee x_2 \vee x_3)\wedge (\neg x_3 \vee\neg x_4)$
is not a horn formula but can be renamed by the renaming $R=\{x_2,x_3\}$ to get the equally satisfiable formula
$(x_1\vee \neg x_2 \vee \neg x_3)\wedge (x_3 \vee\neg x_4)$

My findings so far:

We call a theory $\Phi$ of first order logic inconsistent if $\exists \phi \in \Phi$ such that $\Phi\models \phi$ and $\Phi\not\models \phi$. Otherwise $\Phi$ is consistent.
To check whether $CWA(T)$ is consistent it is sufficient to check if $\Phi=\bigwedge_{\phi\in CWA(T)}\phi$ is satisfiable.

Algorithm to construct CWA:

To compute $CWA(T)$ we need to know if $T\models x_i$ for all variables in $T$. This can be done by considering $\Psi=\bigwedge_{\psi\in T}\psi$ and then checking if $\Psi \rightarrow x_i$ or equivalently $\neg x_i \rightarrow \neg\Psi$. Therefore if we set $x_i=0$ in $\Psi$ and $\Psi$ is not satisfiable it follows $T\models x_i$, otherwise $T\not\models x_i$.
First create an set $I=\{\emptyset\}$
For all variables defined by the index $i=0,...,n$ we do the following calculation:
1.] set $x_i=0$ in  $\Psi=\bigwedge_{\psi\in T}\psi$
2.] if $\Psi$ is not satisfiable $I=I\cup\{x_i\}$
By considering the elements of $I$ we can conclude $CWA(T)=T\cup\{\neg x_i:x_i\not\in I\}$.

Deciding if CWA(T) is consistent is at least NP-hard:

let $C_1,...,C_m$ be clauses of an arbitrary 3-SAT instance and $C_{m+1}=(u\vee v)$ such that $u,v$ are fresh atoms. Then $T=\{C_1,...,C_m,C_{m+1}\}$ contains only renamable Horn clauses.
To decide if $CWA(T)$ is consistent we need to decide if $u$ is free for negation. This follows by checking if $T\models u$. Therefore we assume $u=0$ and check if $C_1\wedge C_2 \wedge ... \wedge v$ is not satisfiable. Since v occurs in no other clause, the formula is not satisfiable if $C_1\wedge ... \wedge C_m$ is not satisfiable, but $C_1\wedge ... \wedge C_m$ is an arbitrary 3-SAT instance and so checking if $CWA(T)$ is consistent is at least NP-hard.


texts: Why to implement Open list in Heuristic search with priority queue

texts:
I don't understand why do we need to implement Open list using priority queue? There could be other data structure.

I understand the usage of priority queues from this example clearly. The newly discovered node would always be inserted at the head of the Open List. Then why do we need priority queue?

This article has mentioned everything about open list.

Usually Open Set contains the states. Its more convenient to assume Open Set as a list. However, the when we were to implement it in some programming language, we use priority queue as data structure.

By states, I mean assume rubix cube of 6 faces. When  we rotate it we could have 3 possibilities: 90, 180, 270 degree rotations.

Total states 6x3 = 18


texts: Find All permutation of String using Iteration

texts:
How to find all permutation of a String in Iterative way ?

Code (Recursion) :

private void permute(String str, int l, int r)
{
    if (l == r)
        System.out.println(str);
    else
    {
        for (int i = l; i <= r; i++)
        {
            str = swap(str,l,i);
            permute(str, l+1, r);
            str = swap(str,l,i);
        }
    }
}

public String swap(String a, int i, int j)
{
    char temp;
    char[] charArray = a.toCharArray();
    temp = charArray[i] ;
    charArray[i] = charArray[j];
    charArray[j] = temp;
    return String.valueOf(charArray);
}


texts:
I am trying to analyse a weighted multi-graph which represents a snapshot of a rail network for a particular day. As such, the vertices of the graph can be considered stations and the weighted edges represent the time taken to travel from one station to another.

For any particular vertex, there might be multiple edges going from that vertex to another (as there could be, for example, a scheduled service that departs from A to B hourly each day - meaning 24 journies in a day and 24 edges between the two vertices for this one journey).

In terms of my analysis, I want to be able to find the shortest path from all stations to all other stations. I can then use algorithms such as BetweennessCentrality on the resultant data to find the most "important" vertices. This type of analysis obviously lends itself to using Dijkstra’s algorithm to find the shortest paths.

However, using Dijkstra’s algorithm will mean that real-life constraints are ignored. For example, Dijkstra’s algorithm won’t take into consideration you can’t set off from station A at 10:00, arrive at B at 10:30 and then take a train from B to C at 8:00 (you are not a time traveller!).

Dijkstra's algorithm also won't take into account time spent waiting in a station for a train to arrive in a situation where a passenger would have to change trains.

I have looked into modifying Dijkstra's algorithm to take these factors into account but as these factors change on a case by case basis you are unable to apply them to the network as a whole.

The ConnectionScanAlgorithm does take real-life constraints into account and scans through a network’s nodes and edges with a given start and end node in mind (I believe this is how train ticket websites find a quickest route).

However, since I need the routes from all stations to all other stations, to make use of the ConnectionScanAlgorithm I have to pass through every combination of station pairings (for me, this is some 36 million combinations) which is far too time expensive.

Are there any algorithms out there which are applicable to this problem?

If not, what is the best way to go about forming a solution?


texts: Can the Same Function Have Different Asymptotic?

texts:
Say we had a function $4^k$.

The asymptotic of this function would be $\Theta(4^k)$, and thus we would say the function has exponential run-time.

But what if $k = \log{n}$? Then our same function would be $4^k = 4^{\log{n}} = n^{\log{4}} \in \Theta(n^{\log{4}})$.

(Step 2 to 3 is accomplished via a change of logarithm base).

Would we now say the function runs in polynomial time?

Or something more nuanced, like

“The function is exponential in respect to k, and polynomial in respect to n”?


texts: A procedure for Topological sort, proof for its correctness

texts:
Definition: A preserved invariant of a state machine is a predicate, $P$, on
states, such that whenever $P(q)$ is true of a state, $q$, and $q  \rightarrow r$ for some state, $r$,
then $P(r)$ holds.

Definition: A line graph is a graph whose edges are all on one path.

Definition: Formally, a state machine is nothing more than a binary relation on a set, except
that the elements of the set are called “states,” the relation is called the transition
relation, and an arrow in the graph of the transition relation is called a transition.
A transition from state $q$ to state $r$ will be written $q \rightarrow r$.

DAG: Directed Acylic Graph

  The following procedure can be applied to any directed graph, $G$:

  Delete an edge that is in a cycle.
  Delete edge $<u \rightarrow v>$ if there is a path from vertex $u$ to vertex $v$ that does not
  include $<u \rightarrow v>$.
  Add edge $<u \rightarrow v>$ if there is no path in either direction between vertex $u$ and
  vertex $v$.

  Repeat these operations until none of them are applicable.

This procedure can be modeled as a state machine. The start state is $G$, and the
states are all possible digraphs with the same vertices as $G$.

(b) Prove that if the procedure terminates with a digraph, $H$, then $H$ is a line
graph with the same vertices as $G$.

Hint: Show that if $H$ is not a line graph, then some operation must be applicable.

(c) Prove that being a DAG is a preserved invariant of the procedure.

(d) Prove that if $G$ is a DAG and the procedure terminates, then the walk relation
of the final line graph is a topological sort of $G$.

Hint: Verify that the predicate
$P(u,v)$:: there is a directed path from $u$ to $v$
is a preserved invariant of the procedure, for any two vertices $u, \ v$ of a DAG.

(e) Prove that if $G$ is finite, then the procedure terminates.

Hint: Let $s$ be the number of cycles, $e$ be the number of edges, and $p$ be the number
of pairs of vertices with a directed path (in either direction) between them. Note
that $p \leq n^2$ where $n$ is the number of vertices of $G$. Find coefficients $a,b,c$ such
that as+bp+e+c is nonnegative integer valued and decreases at each transition.

  My Problems:

  I got stuck with problems $d$ and $e$ but solutions to other problems are welcome too.

  At problem  $d$, I could not understand the hint and why it is given, how it helps.

In my way for proving $d$, I am trying to show that given procedure always preserves the order of vertices, which are associated with edges, on the start graph $G$. So a line graph is automatically a topological sort since the "precedence order" of the vertices are preserved.

  But procedure number $3$ is problematic, how to show it preserves precedence ?


texts: If micro-kernels were parents, how exactly do they just receive messages from their kids (software) and pass it to a webcam?

texts:
I don't understand the last para., but I edited its typos. Please explain like I'm 5. Picture.

What does "they know how to do it and those parents do everything for the children" mean?

"So when your children want to use the camera, you'll just take a message and pass it on the webcam and continue doing this back and forth." What does this mean? How does a micro-kernel receive messages from the programs (kids) and act as the interface?

Well that difference is simpler. Monolithic parents (kernels) prefer to do more things themselves, like serving other useful things and helping the kids play with the toys, like the webcam (drivers and also the filesystem). They're kinda overprotective: when Chrome wants to use the webcam, they know how to do it and those parents do everything for the children. You the Microkernel are more laid back. You prefer treating the webcam just like you do your children. So when your children want to use the camera, you'll just take a message and pass it on the webcam and continue doing this back and forth. Now since you're a laid back parent, if the toy is terrible, you won't care, the children will continue to at least get their essentials, and if the webcam is becoming annoying, it's the only thing that'll stop working. But the crazy monolithic parents go crazy and have a meltdown as soon as the webcam is annoying! Of course your children need to be more patient, it takes a while to send messages back and forth, but at least they know they have a dependable parent.


texts: Sorting an "almost sorted" array in sub linear time

texts:
I am given an "almost sorted" array with the condition that each element is no more than $k$ places away from its position in the sorted array. I need to show that it is impossible to sort this array in sublinear time asymptotically.

My proof is to suppose a sorted array of length $n$.
Now assume that every second element is swapped with the element on its left.
The new array is almost sorted. To sort it would require a minimum of $n/2$ swaps - asymptotically linear amount of operations. Therefore, no sublinear sorting algorithm exists.

Is this proof correct?


texts: If A and B are NP-complete, then A ∪ B need not be NP-complete

texts:
I am studying the proof of this exercise (link)

  There exist N P-complete languages A and B such that A ∪ B is not N P-complete. Example:

  $A = \{1x : x ∈ SAT\} ∪ \{0x : x ∈ \{0, 1\}^∗\};$
  $B = \{0x : x ∈ SAT\} ∪ \{1x : x ∈ \{0, 1\}^∗\};$.

  The languages A and B are N P-complete (prove it). On the other hand, A ∪ B contains allbinary strings (i.e. A ∪ B = {0, 1}∗); and thus it is not N P-complete.

I know the Union (L1 ∪ L2) of two NP language L1,L2 ∈ NP is NP. I can describe a TM not-deterministic for $\{1x : x ∈ SAT\}$ (and for $\{0x : x ∈ SAT\}$) and therefore $\{1x : x ∈ SAT\}$ is NP (note, I know SAT is NP). I have a problem to understand why $\{0x : x ∈ \{0, 1\}\}^∗$ is NP? I remember $\{0, 1\}^∗$ is in P, and I cannot describe a TM not-deterministic for $\{0x : x ∈ \{0, 1\}\}^∗$


texts:
This paper says pebble games have super linear lower bound for every fixed $k$ https://dl.acm.org/citation.cfm?doid=62.322433.

Why is it not considered proof of constructive example for a function in $NP$ which requires superlinear runtime?


texts: Is there an existing protocol where a sender does not know who he is sending data to?

texts: I was thinking about how the BitTorrent protocol automatically gives every peer a list of IPs of every other user who is currently seeding / leeching off the torrent in question. Is there an existing protocol where, somehow, the destination address is vague enough or unknown to the sender (and perhaps becomes more known as the packet is sent through the routers ?) Or is there research in implementing something like this that could be interesting to read ?


texts: reducing the halting problem to the blank tape problem

texts:
I have checked many discussions for understanding this problem.

I understand the reasoning , unfortunately there are some drawback in my understanding.

The Blank-tape halting Problem

Input: Turing Machine M

Question : Does M halt when started with a blank tape?

So this is the reduction :

The construction of Mw is as follows :

When started on blank tape, writes w
Then continues execution like M

What i don't undesstand is the step 2 , in my opinion if we execute M on w maybe M will loop !!!

My second question : what the blank-tape do when executed?even if the blanktape machine halt on blank tape , how can we be sure that M halt on w .i miss something here.

Thank you in advance.


texts: How to implement two stacks in one array?

texts:
I want to begin by saying that this is NOT a homework question. I am reading Introduction to Algorithms - the famous CLRS text to become a better programmer. I am trying to solve the problems and exercises given in the book by myself.

I am trying to solve Excercise 10.1-2 from Chapter 10 Elementary Data Structures from CLRS Second Edition. Here is what its states:

  Explain how to implement two stacks in one array A[1..n] in such a way that neither stack overflows unless the total number of elements in both stacks together is n. The PUSH and POP operations should run in O(1) time.

The solution that I have come up with so far is:

  Let array A[1..n] implement two stacks: S1[1..i] and S2[i..n].

  For the PUSH-S1 and PUSH-S2 operations, if the stack is 'full' then start pushing elements into the other stack (eg. if stack S1 is full when a new element is trying to be pushed in, then push that element into stack S2 and vice versa).

The problem with this approach is I will not be able to POP-S1 or POP-S2 reliably as there is no way of 'remembering' which element belongs to which stack. If the elements of the stack are (key,value) pairs, the key being the stack number, then to pop an element I would have to search, in the worst case, i or (n-i) times - which will be O(n) (feel free to correct me if I am wrong here), which would not be O(1).

I have been banging my head on the question for quite a while now. Am I on the right track? Can someone give my possible pointers for solving this problem?

In general, how should I 'think' about these problems? Or can only really intelligent people solve these types of problems? Will tackling/solving problems like these (i.e. gaining experience) help me become better at this?

I await enlightenment.


texts: Proving closure under reversal of languages accepted by min-heap automata

texts:
This is a follow-up question of this one.

In a previous question about exotic state machines, Alex ten Brink and Raphael addressed the computational capabilities of a peculiar kind of state machine: min-heap automata. They were able to show that the set of languages accepted by such machines ($HAL$) is neither a subset nor a superset of the set of context-free languages. Given the successful resolution of and apparent interest in that question, I proceed to ask several follow-up questions.

It is known that the regular languages are closed under a variety of operations (we may limit ourselves to basic operations such as union, intersection, complement, difference, concatenation, Kleene star, and reversal), whereas the context-free languages have different closure properties (these are closed under union, concatenation, Kleene star, and reversal).

  Is HAL closed under reversal?


texts: Boruvka MST algorithm using doubly linked lists

texts:
I'm reading Sedgewick & Wayne's Algorithms book, and one of the questions in one of the chapters is the following:

  Develop an implementation of Boruvka's algorithm that uses doubly-linked circular lists to represent MST subtrees so that subtrees can be merged and renamed in time bounded by E during each stage (and the union-find data type is therefore not needed).

I'm aware of the standard version of Boruvka's algorithm that uses a union-find data structure to do the merges and check subtree identifiers (there is also an implementation on the book's official website )

But I'm not being able to figure out how to improve the performance of the algorithm by replacing the union-find data structure for subtrees represented by doubly-linked circular lists.

Any ideas? Thanks!


texts: Big O relation between $2^n$ and $2^{2n}$

texts:
I know that:

If $f(n) = O(g(n))$ , then there are constants $M$ and $x_0$ , such that

$f(n) <= M*g(n), \forall n > n_0$

The other, plain English way of defining it is,

If $f(n)=O(g(n))$ then for large $n$ , $f(n)$ would grow as fast as $g(n)$.

I got confused when comparing $2^n$ with $2^{2n}$. Here , $f(n) = 2^n$ and $g(n) = 2^{2n}$. Clearly , $f(n)$ is smaller than $g(n)$ by a factor of $2^n$. So there will be constants $A$ and $x_0$ such that the first definition above is met.

However, for large $n$ , $2^{2n}$ would grow much faster than $2^n$, leaving $2^n$ far behind. That is $2^{2n}$  won't be an asymptotic/tight bound for $2^n$ .

So, is $2^n = O(2^{2n})$ or not? (or did I just create a confusing situation out of nothing)


texts:
I am having some confusion in understanding RICE's theorem.

It says every non trivial property of RE in undecidable.

I need to understand when to apply RICE's theorem and when to not.

Questions like:- Turing machine makes at least five moves,It  accepts a string input of length atleast five ,TM halts for every input on length <50 are all decidable.

But  these  are  NON TRIVIAL properties?Some TM will make 5 moves and some will not,Some will halt on every input <50 and some will not?So if this is Non trivial property then why cant we apply RICE's theorem?

On other side questions like:- TM accepts at least 10 strings is undecidable because some TM will say yes and some will say NO.Then why can't we use same concept on above mentioned questions?

Please help me in understanding how to identify whether question is based on Rice's theorem or not?


texts: Borrowing bioinformatic methods in other fields

texts: Have the bioinformatic methods like sequence analysis, genome annotation, comparative genomics (and many others), been applied to solve problems outside the field of bioinformatics?


texts: A simple clarification on $\#P$ closure properties

texts:
What does $\#P$ closure under addition and multiplication mean?

Does it mean given $NTM$s $N_1$ and $N_2$ we can create in deterministic polynomial time an $NTM$ $N_\times$ and $N_+$ such that for every input $x$ we have $$\#N_\times(x)=\#N_1(x)\#N_2(x)$$ $$\#N_+(x)=\#N_1(x)+\#N_2(x)$$ accepting paths?


texts: Is every reduction function $f \in O(n)$?

texts:
I have no detailed questions actually. My question is about a (maybe possible) generalization for reductions.

We defined reduction as following (If I translate a term false please correct me.):

$ L_1, L_2 \in \{0,1\}^* $ two languages.

One may reduce the language $L_1$ to $L_2$, if there is a total function:

$f: \{0,1\}^* \rightarrow \{0,1\}^* $ with the following properties:

$ \forall w\in \{0,1\}^* :w\in L_1 \Leftrightarrow f(w) \in L_2 $
The function is via a Turing Machine $M_f$ computable.

My question is the following:

If one may can reduce a language to another, then one may can construct a function from a language to another. It means intuitively for me that the reduction function has to go over $|L_1| = n$ operations. Which means that the reduction function is computable in $O(n)$. But I am not sure about any generalization. I mean does it imply that:

$f$ is a reduction function $\Rightarrow f\in O(n)$


texts:
What is the  difference between multilayer perceptron and linear regression classifier.
I am trying to learn a model with numerical attributes, and predict a numerical value.

Thanks


texts: Subset sum problem, given that a valid subset exists

texts: I have a problem at work.  I need to find a subset of a set of positive integers that sums to a certain value.  I know there is a subset but I need to find it.  Is this new problem the same as the subset sum problem?


texts: How to prove QUADPROG is NP-hard using 3COLOR?

texts: I am given a task to prove using 3COLOR that Quadratic Programming is NP-hard. Does anyone have a clue on how this is meant to be done?


texts: How does a turing machine with doubly infinite tape simulate a normal-taped turing machine?

texts: The intuition is that on any input, we can write a symbol like $\#$ on the left that tells the machine to not move past this symbol. However, I'm running into problems trying to show this using the formal definition of a turing machine. It's not simple using the usual 7-tuple definition. Any help would be appreciated.


texts: Decidability of $SEQ_{CFG} = \{⟨G,H⟩ \mid \text{$G,H$ are CFGs and $L(G) ⊆ L(H)$}\}$

texts:
How can I prove that $SEQ_{CFG} = \{⟨G,H⟩ \mid \text{$G,H$ are CFGs and $L(G) ⊆ L(H)$}\}$ is decidable ?

I know that $EQ_{CFG} = \{⟨G, H⟩ \mid \text{$G,H$ are CFGs and $L(G) = L(H)$}\}$ is not.


texts:
Hiring problem is discussed in section 5.1 and 5.2 of the CLRS and I'm referring this for exercise solutions.

However, for Exercise question 5.2-2 my solution deviates from the one given in the reference and mine seems be correct. I am still not satisfied with the reasoning of my solution though. Here it goes.

The Question: In HIRE-ASSISTANT, assuming that the candidates are presented in a random order,
what is the probability that you hire exactly twice?

My solution: 1. First candidate is always going to be hired so all we have to do is to calculate the probability that only one candidate is hired from the remaining n - 1 candidates. So I divided it into n - 1 cases where like

case 1: If the second candidate is hired. (other than the first one only)

case 2: If the third candidate is hired.

and so on..

Now the probability of case 1:

1(anyone will be hired) * 1/2(the probability of this being more than the first) * 2/3(probability of this not being the highest till now) * 3/4 * 4/5 * 5/6.... * (n-1)/n = 1/n

Similarly for case 2: 1 * 1/2 * 1/3(must be highest till now) *1/4... * (n - 1)/n = 1/2n

case 3: 1/3n
and n-1 th case : 1/(n-1)*n

so my answer is

1/n * (1 + 1/2 + 1/3 + 1/4... 1/(n-1))

but the solutions pdf mentions

(2^n - n - 1)/n!

My solution seems correct for n == 3 where the answer should be 3/6. So can anyone please validate this approach and guide me if this is wrong.


texts:
I am studying game theory and I am wondering how many winning combinations are possible for Nim game? Suppose, stones = 500 and piles = 5. With these number, there are many initial game positions are possible. like [1, 2, 4, 3, 490], [100, 100, 100, 100, 100], [100, 200, 100, 100], [0, 200, 200, 50, 50] and so on. So basically there are stones^piles combinations possible. Among these, some will yield Xor > 0 and considered as winning possible.

My question is - how many winning initial positions are possible for given stones and piles? Instead of checking all possible combinations(which is impossible for larger inputs), is there any smart way to solve this?

This is not a homework or programming contest problem.


texts: Examples of context-free grammars whose ambiguity is unknown

texts:
Are there any examples of context-free grammars for which we simply do not know whether they are ambiguous? By examples I mean an actual specification for the grammar, not some kind of non-constructive existence proof with a counting argument or whatnot. To make things more clear, I should be able to write a parser for this grammar from the specification (this should exclude grammars that are somehow defined via constructions involving other undecidable problems).

I am not a specialist so I hope the previous paragraph makes what I mean clear enough. Otherwise please do let me know if you think I am not being clear enough.

Another point: coming up with a random grammar specification on the spot and claiming its ambiguity is unknown because no one has tried to figure it out does not count. I guess I am really looking for known open problems in this area.


texts: How to generate all $n$-bit numbers with certain bits fixed?

texts:
Consider the example where $n = 4$, bit 0 is fixed at 1, and bit 2 is fixed at 0. I would like to generate all $n$-bit numbers with those bits fixed. Essentially, everything I generate would have the form:

$$1*0*$$

where $*$ represents a bit that can vary. The fixed bits can be in arbitrary positions, and there can be arbitrarily-many of them (anywhere from 1 bit fixed to $n-1$ bits fixed). Ideally, I would prefer these to be generated in lex order; what I'm looking to generate for the example case would be:

$$1000, 1001, 1100, 1101$$

I've only found solutions for doing something like this when specific bits are set to 1 - my question is more general, as it allows bits to be set to 0 or 1. What is a good algorithm (in terms of simplicity and efficiency) to do this for arbitrary $n$?


texts:
I have problems understanding Lamport's bakery algorithm. The thing I do understand is that each thread ask all other threads what number they have.Then the thread takes the maximum number and add 1 to that and give that number to itself. The thread with the lowest number can enter the critical zone and if two or more threads have the lowest number then the thread with the lowest process id will be allowed to enter the critical area. When a thread exits the critical area then it put it's number to 0, meaning it's not interested in going inside the critical area. First when it picks a number higher than 0 it is interested going inside the critical area.

Now here is what I don't understand:

If a thread wants to get into the critical area it picks a number, but what if it changes its mind while it's waiting in line? does it then change its number to 0 or does it go through the critical area anyway when it is its turn?
In Lamport's bakery algorithm there is a Boolean value of "true" or "false". If a thread wants to enter it sets the Boolean value to true, but what is that Boolean value used for in the code? Because when a thread has been inside the critical area it changes its number to 0, so other threads in that way can see it's not interested in going inside the critical area, and if it decides it wants inside the critical area again, then it has to ask all the other threads what their number is and then add 1 to the maximum value which will be its number. So the true and false Boolean seems useless to me. Anybody understand why they are there?


texts:
I am trying to calculate a signal to noise ratio to achieve a rate of 300Mbps on a bandwidth of 3Mhz.

The shannon capacity formula C = B*Log(x,(1+SNR)) should be my friend on this one, but this is my first time doing this calculation.

Currently I am at 300Mbps == 3000000 * Log(2,(1+SNR)) From this point I would just get SNR by its self, but I am not sure how to do it.

My question is: How do I calculate the signal to noise ratio given the speed and bandwidth? I am not sure if the setup of my equation above is correct.


texts: CFGs: detecting infinitely many derivations of a single string

texts:
Some particularly degenerate CFGs can produce a single string in infinitely many ways: for a dumb example, $S \to SS \mid \epsilon$ can produce the empty string as $S \to \epsilon$ or $S \to SS \to S \to \epsilon$, etc.

I'm writing a general CFG parser which can produce all the different parses for a given string, but obviously it chokes on examples like the above. I'd like to be able to detect when there may be infinitely many parses for a string, rather than just looping forever. Can I, and, if so, how?

My intuition is that a grammar has this property if and only if there is some non-useless nonterminal A (ie, A is used in the production of some string in the language of the CFG) which can produce itself via some chain of productions such that all of the other symbols produced by following that chain are nullable nonterminals of A itself. But I don't know if this is correct, and I'm not sure how to detect it.

(A nonterminal B is nullable if $B \to^* \epsilon$, ie, some series of productions replaces the symbol with the empty string.)


texts: Calculating the process time for a synchronous network system

texts:
Okay I am trying to understand why asynchronous systems are better that synchronous systems in terms of throughput.

Relating to the calculation done in this answer. Can someone tell if my reasoning is correct ?

Lets say I have a system that has 1000 live connections and each connection takes 5 packets to complete and a packet is received every millisecond. Processing time is 0.001 ms(1 micro second). The system can only process 1 packet at a given time, if there are multiple packets then remaining packets must wait until the processing is complete for the present packet.

My reasoning and calculation-:

So in the 1st millisecond the system receives 1000 packets, all 1st packets of the 5 packets from each of the 1000 connections. Am I right ?

If I am correct then the process time should be calculated in the following fashion-:

1st packet of 1st connection

Waiting Time for first packet-: 0ms

Process Time-: 0.001ms

Time taken to completion of this packet-: 0.001 (wait time + process time)

1st packet of 2nd connection

Waiting Time : time taken for completion of previous packet = 0.001ms

Process time = constant = 0.001ms

Time taken to completion of this packet = (wait time + process time) = 0.001+0.001 ms = 2*0.001 = 0.002ms

So in the same way processing all 1st packets of the 1000 connections would take = 1000*0.001 = 1ms

So in a total I will be receiving 5*1000 packets = 5000 packets, so processing them will take 5000*0.001 = 5ms

Am I correct in my above reasoning and calculation ? If not please correct me where I am going wrong.


texts: Which law is this expression X+ X’.Y=X+Y

texts:
Question. Name the law given and verify it using a truth table. X+ X’.Y=X+Y

My Answer.
X   Y   X’  X’.Y    X+X’.Y  X+Y
0   0   1   0       0       0
0   1   1   1       1       1
1   0   0   0       1       1
1   1   0   0       1       1

Prove algebraically that X + X’Y = X + Y.
L.H.S. = X + X’Y
           = X.1 + X’Y        (X . 1 = X property of 0 and 1)
           = X(1 + Y) + X’Y   (1 + Y = 1 property of 0 and 1)
           = X + XY +  X’Y
           = X + Y(X + X’)
           = X + Y.1          (X + X’ =1 complementarity law)
           = X + Y            (Y . 1 = Y property of 0 and 1)
           = R.H.S.      Hence proved.

My teacher marked my answer wrong. And told me to find the correct answer. Friends tell me is it a complementary law or distributive law or Absorption law? If it is absorption kindly tell me how to prove RHS and LHS algebraically.


texts: ZigZag sequence without dynamic programming

texts:
I just came across the maximum zigzag sequence problem, defined as follows:

  A zigzag sequence is defined as a sequence of numbers such that the difference between two consecutive numbers alternates between positive and negative.

  Given a an array of N integer number, find the length of the longest zigzag subsequence. A subsequence is formed by deleting zero or more elements of the original sequence, but preserving the order in the original sequence.

  For example given the array {1, 2, 4, 2, 3, 5, 1} the subsequence {1, 4, 2, 5, 1} is the longest zigzag.

  A sequence of one element is a trivial zigzag of length 1.

I've found several references to a dynamic programming formulation of the solution which is O(N^2) and very complex. See for example this.

However, I've come with a much simpler solution with O(N) and based on finding all the local maximum and minimum of the original sequence, that is, the elements of which the sign of the difference between consecutive elements change. Here is the code in Java:

public static int zigZagLength_pablochacin(int[] sequence) {

    if (sequence.length == 0)
        return 0;

    int lastDiff = 0;
    int length = 1;

    for (int i = 1; i < sequence.length; i++) {
        int diff = Integer.signum(sequence[i] - sequence[i - 1]);
        if ((diff != 0) && (diff != lastDiff)) {
            lastDiff = diff;
            length++;
        }
    }

    return length;
}

Apparently,this approach has also been proposed elsewhere.

My question is, am I missing something that makes this simple solution wrong?

Note: I originally asked this question in Code review Stack, but was considered off-topic, as it doesn't relate to code style but to the solution.


texts: Polytime and polyspace algorithm for determining the leading intersection of n discrete monotonic functions

texts:
Some frontmatter: I'm a recreational computer scientist and employed software engineer. So, pardon if this prompt seems somewhat out of left field -- I routinely play with mathematical simulcra and open problems when I have nothing better to do.

While playing with the Riemann hypothesis, I determined that the prime gap can be reduced to a recurrence relation based on the intersection of all $n-1$ complementary functions formed by the multiples of each previous prime number (keen observers will note this is a generalization of the Sieve of Eratosthenes). If this makes absolutely no sense to you, don't worry -- it's still frontmatter.

Seeing how these functions related, I realized that the next instance of each prime can be reduced to the first intersection of these functions, recurring forward infinitely. However, I could not determine if this is tractable in polytime and polyspace. Thus: what I'm looking for is an algorithm that can determine the first intersection of $n$ discrete (and, if applicable, monotonic) functions in polynomial time and space. If no such algorithm currently exists or can exist, a terse proof or reference stating so is sufficient.

The closest I can find so far is Dykstra's projection algorithm (yes, that's R. L. Dykstra, not Edsger Dijkstra), which I believe reduces itself to a problem of integer programming and is, therefore, NP-hard. Similarly, if one performs a transitive set intersection of all of the applicable points (as they're currently understood to be bounded), we must still constrain ourselves to exponential space for our recurrence due to the current weak bound of $\ln(m)$ primes for any real $m$ (and therefore, $e^n$ space for each prime $n$).

Globally, I'm wondering if my understanding of the reduction of the problem is wrong. I don't expect to solve the Riemann hypothesis (or any deep, open problem in this space) any time soon. Rather, I'm seeking to learn more about it by playing with the problem, and I've hit a snag in my research.


texts: Proof: Kolmogorov complexity of string concatenation

texts:
Does there exist a universal constant $c$ such that for any strings $x, y$, we have: $$K(xy)\leq K(x) + K(y) + c$$
where $K(\cdot)$ denotes the Kolmogorov Complexity of a binary string and $xy$ means the concatenation of $x$ and $y$? I know the answer to this problem is no but I am seeking a proof for this, any hint?

Update: for reference, this is stated at the top of page 266 in Sipser's famous book "Introduction to the Theory of Computation", third edition, and is listed as Problem 6.19 in the book. I've tried to prove it but didn't succeed, just curious to know what proof technique should be used in order to prove it.


texts:
For school I have a big assignment on hashtables etc. One of the functions is a size_t function where we calculate the hash value. (Keep in mind the structure of every function is given so we are not allowed to change input variables/function types). However, the hash calculator function does need to handle errors, but I am stuck on what value to return when encountering errors. In my head: all positive numbers are also possible hash values, and all negative numbers can not be returned in a size_t function.

Thanks in advance


texts: Turing machine which diverges on its own code

texts:
Show that the set $K^{c}$ = $\lbrace M \mid M(M) \text{ diverges} \rbrace$ is not recursively enumerable.

This question is essentially asking to show that the set of turing machines which diverge when run on their own code is not RE.

My idea is to attempt to reduce this problem to something which is the complement of the halting problem.  Thus, the idea is to take a machine M and a word w, and construct a new machine which diverges on it's own code when M diverges on w, but haven't had much luck with that.

This is from a practise exam, but please treat it as a homework question so I can attempt to work through a solution.


texts: Versions of NP with different logical unifiers

texts:
One formulation of NP is this: a language is in NP if it can be solved in polynomial time by an algorithm that has access to a special "Nondeterministic Bit" function, which branches the world into two alternate universes, writes a $1$ on the worktape in the first universe and a $0$ in the second, finishes the computation in each universe, and then returns the OR of the computation value of each universe.

If we replace the OR in this formulation with an AND, we get coNP.

I'm wondering what complexity class is described if we use the other nontrivial symmetric binary logical operators.

$\text{OR} \to NP$

$\text{AND} \to coNP$

$\text{XOR} \to \,?$

$\text{NAND} \to \, ?$

$\text{NOR} \to \,?$

$\text{EQUALS} \to \, ?$


texts: maximal subset such as $A[i].X \lt A[j].Y$ for each $j \lt i$?

texts:
I need to find the maximal subset $S$ of an array $A$ of length $N$ ,where each element of $A$ contains $X$ and $Y$, such that for each $0 \leq i \lt N$ , $j \lt i$ the rule is $S[i].X \lt S[j].Y$ , What would be the best approach for finding such subset of $A$ (in terms of time, knowing that $N \leq 100,000$) ?

EDIT:
An example to that is $A = \{(2, 15), (6, 3), (6, 11), (4, 7), (8, 5)\}$

$S$ can be $\{(6,11),(2,15),(4,7),(6,3)\}$
where each $X$ of $S$ is smaller than each $Y$ before it


texts: Why is Brent's Cycle Detection method faster at finding a Linked List cycle than Floyd's Cycle Detection method?

texts: I understand in Floyd’s cycle, you are finding a cycle in a linked list by moving two counters- one by a factor of 2, other by a factor of 1. In Brent’s you are basically doing the same but the one factor moves by multiplying 2 instead by merely adding 2. Is there any math explanation behind why Brent’s is faster than Floyd’s?


texts: Proving NP-hardness of Hamiltonian Cycle problem variant

texts:
I need to prove that determining whether a graph has a  relaxed-Hamiltonian cycle (definition given ahead) is NP-hard.

A relaxed-Hamiltonian cycle in $G$ is a closed walk $C$ that visits every vertex of $G$ exactly once, except for at most one vertex that $C$ visits more than once (i.e. that vertex may repeated twice or even more times).
Note: In a closed walk we can visit a vertex or edge multiple times, but first and last vertex are same. In the relaxed-Hamiltonian cycle this first and last vertex being the same is not counted as repetition.

I am thinking reducing to relaxed-Hamiltonian cycle from Hamiltonian Cycle.
Claim: Construct graph $G'$ given $G$ such that $G$ has Hamiltonian cycle iff $G'$ had relaxed-Hamiltonian cycle.
My idea is that if a graph $G$ has one or more articulation points then it cannot have a Hamiltonian Cycle so simply give a $G'$ which does not have a relaxed-Hamiltonian cycle.
The problem is when graph $G$ does not have any articulation points. In this case the graph $G$ may or may not have an Hamiltonian Cycle. I cannot think of a construction for this case such that my claim holds.
Is my approach correct? If yes please suggest how I could take care of the mentioned case? Otherwise, please hint me towards the correct direction of thinking to get the right construction.


texts: Why is $((aa)^*bb(aa)^*bb(aa)^*)^*$ of star-height 1

texts:
A generalized regular expression is like a regular expression but with one more operation allowed: complementation. The (generalized) star-height of a generalized regular expression is the maximal number of nested Kleene stars. The star-height of a language is the minimal star-height of a regular expression describing it. It is not known if there is even a language of star-height 2.
So I imagine the langage $((aa)^*bb(aa)^*bb(aa)^*)^*(aa)^*$ of words consisting of concatenations of $aa$ and $bb$, with an even number of $bb$, is of generalized star-height $1$. But I couldn't prove it. In the paper Some results on the generalized star-height problem (Pin, Straubing, Thérien), lemma 6.1 (the transfer lemma) cannot be applied because both $(bb)^*$ and $(aa)^*$ are of star-height 1.
I saw elsewhere some languages which were conjectured to be of star-height 2 and they were more complex than the one I give, so it is very probably of star-height 1. Is it the case?


texts: Mathematical model for a webpage layout?

texts:
Getting layout right (even if only a structure is considered) with HTML5/CSS3 is still more like an art or black magic.

On the other hand, there are other GUI systems (like wxWindows and Tcl/Tk) and some GUI research (like The Auckland Layout Model, ALM, and other methods), which hint at the possibility of formalization for the layout managers (geometry managers).

Are there any comprehensible formal models for HTML5/CSS, which provide ultracompact (abstract) way to describe structure, "physics" and "geometry" of resizeable webpages, using language of blocks? Also html/css can be generated from it, which works more or less as described in standard browsers. Also, a model can be derived given HTML/CSS (browsers do it by their algorithms, so this seems to be theoretically possible).

By "ultracompact" and abstract it is understood: much more compact than HTML/CSS and also more domain-oriented, "speaking" the language of webpage's dynamics in response to resizing or changed content, that is, higher level than HTML/CSS constructs.

For an analogy, it is possible to write a program to make a textual search, based on some complex rules, but the same task can be performed by a much more compact regular expression. So, is there similar compact language for HTML/CSS layout?

The goals of such a model could be:

to verify existing design (model checking)
to build robust design given higher level specifications
to check whether a set of requirements is consistent with HTML5/CSS3 engine (e.g., does not require writing javascript to make an adjustment too complex for the declarative languages)
to be a solid platform for even higher level research on qualities ("to check the harmony with algebra.")

Also it could be a language to use for certain GUI-related abstractions, like is usual in programming language domain, where we do not need to use concrete syntax to express an idea of for-loop and we do have all kinds of nice, proven results about main concepts of algorithmic constructions.

Of course, web-browsers possess algorithmic model for rendering, e.g. popular and simplified description can be found here, but as pointed above it does not have the properties listed above.


texts: How making non LL, non LR grammar a valid LL grammar, also makes it a valid LR grammar? Is there any connection between LL and LR conflicts?

texts:
I might unncecessarily overthinking here, but I had this weird possibly meaning less doubt:

  When grammar is neither LL nor LR, it means, both LL and LR parsing tables involve conflicts. LL parsing table may involve FIRST-FIRST and/or FIRST-FOLLOW conflicts, whereas LR parsing table may involve SR and/or RR conflicts. When we use left factoring (or any other approaches) to eliminate conflicts from LL parsing table, it becomes valid LL grammar, and hence also a valid LR grammar. Does this means, eliminating LL conflicts also somehow eliminates LR conflicts? If yes how this happens? Or in other words, how LL conflicts are mapped to LR conflicts? (I believe there should have some minimum connection between LL conflicts and LR conflicts, shouldnt there be?)


texts:
For a given database table:

DB

id   w1,  w2,  w3,  w4,    v
1    A                    X1
2    B                    X2
3    A    B               Y0
3    A    B    C          Y1
4    C                    X3
5    D                    X4
6    B    C    D          Y2
7    C    D    F          Y3
8    C    D    G          Y4
9    E                    X5

There exists an input with expected output based on a string search/match on the table. What we are trying to do is match the input with a combination of rows from the database. The only portion of the row that we use for matching is from w1 to w4. We then use the v column to identify the row. So, for example, the input string E would produce output X5, while input A, B would produce output Y0. In the case that there is no exact match, we want the elements closer to the front of the list to represent as long a string as possible. For example, with input A, B, C, D, E we could match a number of ways, notably Y1, X4, X5, X1, Y2, X5. We prefer the former, because A, B, C (from Y1) is longer than A (from X1). We want the first item in the output to represent as long a string as possible, and only when two potential outputs have the same length for the initial item do we try to get the longest second item we can.

Example 2:

input = A, B, C, D, F

expected_output => Y0, Y3

Explanation:

We would like to find A, B, C, D, F, but there is no match.

Likewise, we would match A, B, C, D if we could, but we cannot.

We do find Y1 is a match for A, B, C, so we use that. Our partial solution is Y1.

Now we look for D, F, but we don't find it.

We find X4 matches D, so our partial solution is Y1, X4.

Next we look for F but then there is no match. At this point we backtrack until we find a solution that does work. We take X4 off our solution and look for a better match for D, but there is no other way to match it, and we can't match a shorter substring, because that would be empty.

We take Y1 off our solution (now it is empty) and look for another way to match A, B, C. There is no other way, so we look for A, B, which we find with Y0. Our partial solution is Y0.

Now we search for the remainder of the input, C, D, F and we find it with Y3. Our solution is Y0, Y3.

Question:

What algorithms could I use or learn to be able to solve this efficiently?

What is the pseudocode or high level overview of how to solve the problem?


texts: Why is there readonly (const) in C++, but not writeonly (sink)?

texts:
C++ initially had "readonly" and "writeonly" qualifiers, before "readonly" was renamed to "const", and "writeonly" removed. My question is: What are the problems with "writeonly" (or a "sink" qualifier)?

There are (non-object oriented) programming languages with "in", "out" and "inout" qualifier for functions arguments. In that context, the meaning of "out" is pretty clear. Writing "result_p = result_p+1" is not allowed if "out int& result_p", and the question whether "result_p += 1" is allowed doesn't arise, because these languages don't have "+=" and similar constructs.

Now "sink" in C++ would be a type qualifier, not just a function argument qualifier. The meaning of "sink" is clear on a semantic level. Information is only allowed to flow into a "sink" qualified object, but no information is allowed to leave a "sink" qualified object. So writing "result_p += 1" would be allowed if "sink int& result_p", but what about "result_p = result_p+1"? Its semantic is fine, but there seem to be no general way to check this based on simple syntax or typing rules. But so what, does anything bad happens if "result_p = result_p+1" is not allowed?


texts: Show that if d(n) is O( f (n)) and e(n) is O(g(n)), then d(n)−e(n) is not necessarily O( f (n)−g(n))

texts: I  have this question as an assignment in my Java Algorithms class, and i'm aware that d(n)+e(n) is the same as O(f(n)+g(n)). I dont know why the same doesnt apply to subtracting. Can someone help me? I'm lost..


texts: Something wrong with this definition of factorial with structural recursion?

texts:
In The Algebra of Programming page 5, the authors defined structural recursion foldn (c, h) over natural numbers:

f  0    = c
f (n+1) = h (f n)

They then went on to defin factorial as follows:

fact = outr . foldn ((0, 1), f)
outr (m, n) = n
f (m, n) = (m + 1, (m + 1) * n)

This doesn't seem right, first of all, foldn ((0, 1), f) does not comply to its definition, secondly, this fold will never terminate, will it?


texts: How to find subset of vectors whose sum has certain characteristics

texts:
Let's say you have list of $n$ vectors with entries from $\{0,1,x\}$ and $x$ is > $n$:

$$
\begin{align*}
L_0 &= [1,0,x] \\
L_1 &= [1,1,1] \\
L_2 &= [1,0,0] \\
L_3 &= [x,1,0] \\
L_4 &= [1,x,0]
\end{align*}
$$

I want to find all combinations of $m$ vectors (subsets of vectors from this list) whose elementwise sum in this combination will have exactly $m$ occurrences of $x$.  Is there an algorithm to do this in less than $O(m^n)$ time?

In my example, if $m=2$, the only valid combination is $L_0 + L_4 = [1+1, 0+x, x+0] = [2, x, x]$.  If $m=1$, valid answer is [$L_0$, $L_3$, $L_4$].

Key is: are there's any way to solve this problem without iterating over all $m^n$ combinations.

This might sound like an interview question, but in fact it is a task that I reduced my problem to.


texts:
Let $A$ be a ring such that all elements of $A$ are complex computable numbers. I'm interested in knowing whether the decision problem that asks, given $P\in A[X]$, if $P$ has a root in $A$ is decidable.
I know that this problem is decidable for the following rings:

$\mathbb{Z}$, since we can easily bound the absolute value of any root of $P\in \mathbb{Z}[X]$ ;
the field of fractions of a ring $A$ for which the problem is decidable, by Gauss lemma ;
any algebraically closed field, in particular the field of computable complex numbers ;
the field of computable real numbers, as a corollary of Sturm's theorem, as pointed out in this comment ;

Is there some general result on the decidability  of this class of problems, maybe by making extra assumptions on $A$? Do we know if there are rings for which this decision problem is undecidable?


texts: Tree Decomposition Construction with Balanced Separations: Why 2/3?

texts:
I am working through the book "Parameterized Algorithms" https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf and at the chapter about tree decomposition I am trying to understand the choice of using 2/3 separations instead of 1/2 separators.
It has also been stated in the exercise 7.33 that there would be a problem but I can't find it. I'd be very grateful for a hint
Thanks


texts:
Here I have a problem in understanding the optimal testing strategy.

In a scenario, You have been given two laptop batteries and a testing device. The testing device will make the battery connected to it (one battery can be connected at a time) deliver x mA, where x is an integer. The testing device is constructed in such a way that the battery will always explode if there’s any risk of explosion at that current.

Now we want a program that receives inputs. Input consists of multiple lines, one line per case (at most 200 test cases). Each line contains a single positive integer n between 1 and 4711 inclusive, giving the current at which the battery is known to explode. Input is terminated by a line containing 0, which should not produce any output.

And produce Output, where for each case, print one line containing the worst-case number of tests to perform when using an optimal testing strategy.

|-----------------|------------------|
|  Sample Input   |  Sample Output   |
|--------- -------|------------------|
    1                0
    2                1
    10               4
    23               7
    0

This was a programming contest question marked as an easy question. but I do not get the definition of the optimal testing strategy.
What can be the boundaries? Generally what this question means?


texts: A* graph search heuristicfor pathfinding

texts:
A* needs a consistent heuristic to work on a graph.

So I'm not sure if the heuristic of a straight line (bird flight) can be used.

For example: the costs to travel to a neighbors node is always positive.

              GOAL

 --------------------
 |                  |
 |      START       |
 |                  |    where to stripes are obstacles.

Am I correct that this the proposed heuristic isn't consistent here as it has to travel away from the goal first?

Is there a good heuristic for this kind of situation?
Or should I keep it with Dijkstra a forget about A*?


texts: I am looking for a problem that can not be solved by computer but can be solved by human while computer can verify if the answer is correct or not. In fact what is the question in my head is that is there a way to clearly show the smartness in human brain compared to huge computation power of the processors.


texts: Algorithm for nearest edge detection with respect to a point (in all directions)

texts:
I'm looking for an algorithm, a set of algorithms, or any pointers/remarks how to solve the following problem:

Given a polygon, a central point, and a set of points scaterred around the central point inside the polygon, I want to find the nearest "edges" being created by those points with respect to the central point. One of the algorithm's parameters should be "distance sensitivity" (meaning how far two points have to be far from eachother to be considered in a different cluster and break the line).

An illustration will maybe explain it better... this could be the input, where the + denotes the central point:

The output would be the following:

I am not very well-versed in computational geometry, so any pointers would be welcome.

I'd naively like to imagine the algorithm as a growing circle spreading outwards from the central point, parts of it getting stuck on the points (larger parts get stuck if the cluster is dense enough), and tearing off at the ends of the cluster because there are no points to support it there.

I have done some research into line-sweep algorithms, which partly fit my criteria. However, what I think I need is some kind of a circle-sweep algorithm.


texts: Defining the goal function in an optimization problem

texts:
I have an optimization problem. There are a few quantities, call them $a, b, c$, that describe how good a solution is. However, they all have different priority, from highest to lowest: $a, b, c$.

The goal is to minimize the values of $a, b, c$. The difference in priorities means that the solution with identical value of $a$, lower value of $b$ is lower than the other solution, no matter what the value of $c$ is. Similarly, if the value of $a$ is lower, then no matter what $b$ or $c$ is, the solution is better better than the other solution.

What's the best way to define a goal function for this problem? I don't know the range of those values. I was thinking about using some weight parameters, like multiplying $a$ by the greatest weight, $b$ by lower weight, and $c$ by the lowest weight value.


texts: Tracking approximate values of specific percentiles

texts: At the moment I use HdrHistogram to track approximate distribution of a stream of values. But I don't really need all percentiles, just three of them. Is there some algorithm to track specific percentiles? Precise algorithm with two heaps isn't feasible because of number of values.


texts: Recurrence relation (not solvable by the master theorem)

texts:
Consider the following recursion:
$\begin{cases}
T(n) = 2T(\frac{n}{2}) + \frac{n}{\log n} &n > 1 \\
         O(1) &n = 1
\end{cases}$.

The master theorem doesn't work, as the exponent of $\log n$ is negative. So I tried unfolding the relation and finally got the equation:
$T(n) = n[1 + \frac{1}{\log(\frac{n}{2})} + \frac{1}{\log(\frac{n}{4})} + ... + \frac{1}{\log(2)}]$.

I do not know how to simplify (inequalities to use???) from here. A trivial method would be to assume that all reciprocal of the log terms are $< \frac{1}{\log(2)}$, and since there are $\log n$ terms, the summation of all the reciprocal-log terms is $< \frac{\log n }{\log(2)} = \log_2 n$, which gives $T(n) = O(n \log n)$. However this is a very poor approximation, as by the master theorem we can check that the time complexity for the recursive relation $T(n) = 2T(\frac{n}{2}) + n$ is $O(n \log n)$. Can someone find a tighter correct upper bound?


texts: Subintervals during backward search of a BWT

texts:
A Burrows-Wheeler Transform (BWT) can be used to find the suffix array intervals for a pattern $P$ by issuing $p=|P|$ paired $rank$ queries
\begin{align}
s^\prime &= C[P[i]] + rank(s-1, P[i]) + 1 \\
e^\prime &= C[P[i]] + rank(e, P[i])
\end{align}
where $s$ denotes the start of the search range and $e$ is the end of the range. Initially $s=1$ and $e=|BWT|$. $C$ is a lookup table containing the count of all alphabet symbols in the BWT that sort lexicographically before $P[i]$.
The search proceeds backwards through the search pattern, so it starts at $i=|P|$ and finishes at $i=1$. For example, given the BWT for string $\text{mississippi\\\$}$ and pattern $P=\text{iss}$, the backward search will first identify the interval $[9,12]$ for $\text{s}$, then $[11,12]$ for $\text{ss}$, and lastly $[4,5]$ for $\text{iss}$.
See [1] for a more complete description of backward search and a walk through the example.
My question is during backward search is it possible to determine which subinterval of the previous character's interval lead to the current character's interval?
For example, given the BWT for string $\text{mississippi\\\$}$ and pattern $P=\text{issi}$, the backward search will first identify the interval $[2,5]$ for $\text{i}$ and then $[9,10]$ for $\text{si}$. What I want to know is what subinterval of $[2,5]$ for $\text{i}$ lead to the $[9,10]$ for $\text{si}$. For this toy example I can see the answer is the subinterval $[3,4]$ of $[2,5]$ for $\text{i}$, but I want to know if/how this can be computed during the paired rank queries described above.
The literature suggests that this could be achieved by utilizing a forward search, but this would require a bidirection representation of the BWT, which seems excessive given that we already know the intervals that contain the subintervals.
Any insight would be greatly appreciated!


texts: How can I compare two recurrence relation to find which one is better on large inputs

texts:
I have two recurrences:

$T_1(n) = 2 T_1(n-1) + n$ if $n > 1$, $1$ if $n = 1$

$T_2(n) = 2 T_2(\frac{n}{2}) + n^2$ if $n > 1$, $2$ if $n = 1$

Does this mean $T_1$ is better than $T_2$ because it has less operations to do?

Edit: I looked at the master theorem and found out that the 2nd one has an $O(n^2)$ runtime.


texts: How to mitigate the hierarchical error propagation in tree-structured classification

texts:
Suppose we have a multi-class classification problem, where the number of classes $K \geq 3$

We use a tree structure of multiple SVMs to divide and conquer the problem, with one example in the figure below.

Generally, in this kind of hierarchical classification, if a sample is wrongly classified in an upper layer, it is less likely to be corrected again in lower layers.

My question: Is there any strategy to mitigate such hierarchical error propagation in tree-structured classification?

Much appreciated!


texts:
This is a homework question. I do not want the solution - I'm offering the solution I've been thinking of and wish to know whether is it good or why is it flawed.

Consider a weighted undirected graph. What edges of it are not a part of any minimum spanning tree (MST)? This problem only makes sense when several edges have the same weight, otherwise the MST is unique.

My idea comes from Prim's Algorithm with a slight change. Let $S$ and $T$ be two sets of vertices the algorithm works with. Instead of adding the minimum edge from $S$ to $T$ on every step, look for the minimum edge and more edges of the same value going from $S$ to the vertex the minimum edge goes to. By doing that, (so I suppose) we will obtain a graph containing all the edges which appear in any MST. If this is right, I can simply XOR the edges list with the original graph edges list to find what edges are not in any MST.


texts: Why the most dominant programming languages didn't follow CSP thread model?

texts:
I was trying to ask this question in StackOverflow, but later realized that this question is more relevant to general computer science, not specific engineering problems. If you think it's not, please let me know.

Recently I've found out what CSP(Communicating Sequential Processes) is.
According to the article Bell Labs and CSP Threads:

Most computer science undergraduates are forced to read Andrew Birrell's “An Introduction to Programming with Threads.” The SRC threads model is the one used by most thread packages currently available. The problem with all of these is that they are too low-level. Unlike the communication primitive provided by Hoare, the primitives in the SRC-style threading module must be combined with other techniques, usually shared memory, in order to be used effectively...

Another article Share memory by communicating from Golang blog says:

Traditional threading models (commonly used when writing Java, C++, and Python programs, for example) require the programmer to communicate between threads using shared memory (...)
Go's concurrency primitives - goroutines and channels - provide an elegant and distinct means of structuring concurrent software. (These concepts have an interesting history that begins with C. A. R. Hoare's Communicating Sequential Processes.)

Based on what I've seen so far, because Hoare proposed CSP in 1978, it seems that there was no reason to use SRC thread model in programming languages like C++(1985), Java(1995) or Python(1990).
So my question is, why the most dominant programming languages didn't follow Hoare's thread model?
Here's my guesses:

Most programmers back then didn't know about Hoare's thread model.
Most programmers are used to traditional thread model.

What do you think?


texts: Is there a connection between the halting problem and thermodynamic entropy?

texts:
Alan Turing proposed a model for a machine (the Turing Machine, TM) which computes (numbers, functions, etc.) and proved the Halting Theorem.

A TM is an abstract concept of a machine (or engine if you like). The Halting Theorem is an impossibility result. A Carnot Engine (CE) is an abstract concept of a heat engine and Carnot proved the Carnot Theorem, another impossibility result related to thermodynamic entropy.

  Given that a TM is physically realizable (at least as much as a CE, or maybe not?) is there a mapping or representation or "isomorphism" of TM or CE which could allow to unify these results and in addition connect to entropy?

There are of course formulations of TM and the Halting Theorem in terms of algorithmic information theory (e.g. Chaitin, Kolmogorov etc.) and entropy (in that context). The question asks for the more physical concept of entropy (if in the process of a potential answer algorithmic entropy arises it is fine, but it is not what the question asks exactly).

One can also check another question in physics.se which relates quantum uncertainty with the 2nd law of thermodynamics. See also: an algebraic characterization of entropy, an algorithmic characterization of entropy, a review and connections between various formulations of entropy


texts:
I was reading up on something called the PRAM model without bit operations.
What exactly does it mean that this PRAM model cannot do bit operations?
I can't find a straightforward definition anywhere.
Surely the different processors will still be able to do all sorts of stuff with bits. The reason why I am asking is that the max-flow problem (which is in P cannot be solved in this model using a polynomial number of processors. So in fact it is a non-trivial implication of the conjecture
that $P \neq NC$. So it is further "evidence" of the $P \neq NC$ conjecture.


texts: Maximum single-precision floating-point format number

texts:
According to this wikipedia article the maximum single precision is 7f7fffff. Can some explain me why it is (7f7fffff)16 and not (7fffffff)16?

(7f7fffff)16 = (0111 1111 0111 1111 1111 1111 1111 1111)2
(7fffffff)16 = (0111 1111 1111 1111 1111 1111 1111 1111)2


texts: How/why is switch made from equation to inequality for certificate of optimality for dual problem in linear programming?

texts:
I am reading Chapter 7 Linear Programming in Algorithms by Dasgupta et al.
I don't get how they switch from an equation to an inequality specifically the part highlighted in red/pink regarding the multiplier $y_1 + y_3 ≥ 1$ instead of $y_1 + y_3 = 1$


texts: Shortest path algorithm using Dijkstra with Fibonacci heap

texts:
Given an undirected connected graph $G=(V,E)$ with positive weights, where $|V|>2009$, and each vertex is of degree of at most $10$.
Give an efficient algorithm to find the $2009$ closest nodes to a given source vertex $s$ (with respect to edge weight).

Is it correct to say that Dijkstra's algorithm with Fibonacci heap will run in $\mathcal O(\log V)$?

Reasoning:
Dijkstra's algorithm with Fibonacci heap runs in $\mathcal O(E+V\log V)$. the amount of vertices pulled out of the heap is $2009$, and the amount of key decreased is at most $2009*10$. Therfore the running time of Dijkstra's algorithm for this case is $\mathcal O(2009*10+2009 \log V)=\mathcal O(\log V)$


texts:
Leslie Lamport describes a algorithm to come to consensus for the case for n>3*m, there m is the number of traitors in n generals.

I perfectly understand why for n=4, m=1 there is consensus trough a majority vote. Lets suppose (like in Leslies proposal) there are three type of messages for different attack time (A1, A2, A3). If no majority is reached the default action is retreat (r).

So even if the commander is a traitor and send different messages A1,A2,A3 to the three loyal lieutenants they will get (trough the recursive algorithm) to state (A1,A2,A3). In this case no majority is reached and the default action is taken (r). Thereby consensus is reached.

Leslie stated, that no consensus cannot be reached with n=3, m=1. Nonetheless if we apply the upper algorithm to the scenario with n=3, m=1 for the example that the commander is a traitor, isn't there the same consensus reached? The commander sends A1, A2 to the two loyal lieutenants, they both will reach the state (A1, A2) and thereby take the default option r. There is my mistake?


texts: What is the fastest to find just smallest prime number to a given number N where N can be as large as 10^18?

texts:
During a programming contest I was asked to find just smallest prime number to given number N.
As Sieve cannot be used and brute force also doesn't work.

So, I was wondering is there any other faster implementation.

Here N -> (2, 10^18).


texts: Select K columns from matrix and one element from each row that has maximum sum

texts:
Given matrix of size N x M (N- rows, M - columns), given integer value K(K < N and K < M). Select arbitrary K columns and create new matrix of size N x K after that select max element from each row and calculate sum - S. Task is to find such K columns, so that this sum S will be maximum for given matrix N x M and value K.

Example:

K: 2
Matrix:
\begin{bmatrix}1&2&3&4\\4&3&2&1\\3&1&4&5\end{bmatrix}

Select column 1 and 4:
\begin{bmatrix}1&4\\4&1\\3&5\end{bmatrix}

Select maximum values from rows:
\begin{bmatrix}4\\4\\5\end{bmatrix}

We got sum 13, this is maximum sum for given matrix and for given K.

It looks similar weighted assignment problem or weighted bipartite matching, but I don't know how to reduce this task to them.

Thank you!


texts: How to use Hoare Logic to Prove this Assertion

texts:
Given this assertion in Hoare Logic:

\begin{align}
&\mathbf{\{p >= 0\}}\\
&s = 0 ; n = 1 ;\\
&\mathtt{while}\ (n <= p)\ \{\\
&\quad s = s + n ;\\
&\quad n = n + 1\\
&\}\\
&\mathbf{\{s == p * (p + 1) / 2\}}
\end{align}

How to prove this using the rules of Hoare Logic. I am not sure where to really begin, I only currently understand (most) of the meaning of the axioms, but not what is required for a proof.


texts: Data structure for or-lookups over bit-field associations maps

texts:
For a mapping between a bit-arrays and values I want cheap lookups using bitwise-or instead of equality.

Slightly more formally, I have a set of associations $k_i \mapsto v_i$ where $k_i \in \mathcal{P}(\mathbb{N})$ is a set of naturals and $v_i$ can be of any type $T$. A query on $q \in \mathcal{P}(\mathbb{N})$ matches pairs $(k_j,v_j) \in \mathcal{P}(\mathbb{N}) \times T$ such that $k$ overlaps with $q$ (ie $q \cap k \neq \varnothing$). Also the maximum element $M$ encountered in any $k_i$ is bounded, typically not larger than 5k and each $k_i$ is small $|k_i| \ll M$, ie the bitfield corresponding to the set $k_i$ would be sparse.

I imagine it could be a tree or a heap with (bitfield,a) values at the leaves and at each node a bitfield that is the bitwise-or combination of all bitfields in it's subtree? I failed to find any literature on the subject. Any pointers?


texts: How Is a Computer Able to Store and Quickly Manipulate All the Data Required For A Computer Display?

texts:
I did some quick math on how much data is contained on a screen at any given instant and I ended up with a number well beyond what I thought was possible. 256 colors for Red, Green, and Blue each define a pixel and there are currently 1920x1080 pixels on my screen so..

256 x 256 x 256 x 1920 x 1080 bits = 4.35 Terabytes of data

Obviously that would require more space than is on my desktop, let alone some Raspberry pi. So how do they do it? Any other resources anyone has for learning how displays work in general I'd love to have a look.


texts: Rewriting gates such as XOR into three basic gates?

texts:
How would I rewrite an XOR gate into the three basic logic gates (AND, OR, NOT). To be more specific, I have to write it in such a way with 2 NOT gates, 2 OR gates, and 1 AND gate. I also have to do it with 1 OR gate, 2 AND gates, and 1 NOT gate.

I'm not looking for just the answer, I'm looking for a way to come up with the answer.

Thanks!


texts: Is a set of TM deciding specific length of language reducible?

texts: For instance, if we know a language $L_1 =  \{ \langle M \rangle \mid ~ \lvert L(M) \rvert = n \} $ is decidable, can we prove that $ L_2 =  \{ \langle M \rangle \mid ~ \lvert L(M) \rvert = n-1 \}$ is also decidable? In other words, prove $L_2$ reduces to $L_1$.


texts: What is the intuition behind the "edit sensitive parsing" tree?

texts:
If I understand right then ESP tree is defined as : given any string $x$ of finite length over an alphabet one can construct "an" ESP tree corresponding to it say $T_x$ such that each leaf of the tree is an element of $x$

Now the above immediately implies that every node in $T_x$ corresponds to some substring of $x$.

This $T_x$ isn't unique - right? Are there any conventions about it? (like is there a convention that ESP must always be such that every vertex has either 2 or 3 children? If yes then why?)
As far as I can see one can't create a tree such that every substring will be represented by some vertex. Do we know any optimality results about what is possible at best?
Is there a natural relation between this and the notion of sketching and embedding of metrics?


texts: Black-box combinatorial optimization problem over permutations

texts:
I am solving general black-box optimization problems like:
x*: f(x) -> min, where x are permutations of length N (N = 50 for example, so brute force search is not possible). Objective function f(x) is represented by stand-alone computer code and x represents configuration of complex system with the response simulated by f(x).

I learned, that in this case I can use many heuristic methods. But, most of these methods use always some kind of local search, which require suitable distance metric at search space (space of permutations x in my case). Under suitable distance metric I mean the metric which fulfill the "locality" property, e.g. small change of permutation x produce small change of objective function f(x). In my case is not known any suitable distance metric with this property, so any kind of local search is nearly the random search.

I have a few questions:

Are there available any heuristic black-box combinatorial optimization methods, which does not use local search and/or any distance metric at search space? I need to overcome the low "locality" of the problem or simply the fact, that any suitable distance metric at search space is unknown.
Is the "locality" property really so restricted at combinatorial optimization in general? May be I miss something..., but the most of real-world black-box combinatorial problem has low or very low "locality" due to the fact, that the common permutation distance metrics (Hamming, Kendal, etc.) are not suitable metrics in general.
Is there any general method how to find suitable distance metric at search space to satisfy at least approximately the "locality"?

Additional remarks:

In real, the black-box function f(x) is realized by stand-alone deterministic simulation code, where x plays a role of discrete configuration of the simulated physical system. So, function f(x) has definitely well defined properties, but this properties are so difficult, that is not possible to simple exploit it.
Because of above mentioned complicated internal properties of function f(x) is not possible to find proper distance metric d(x,x') in search space which fulfill "locality" (similar x and x' in a sense of any distance metric produce similar responses f(x) and f(x'))
So, finally, I am looking for any optimization heuristics, which are able to find any suitable sub-optimal solutions only by informations available by properties of f(x) at fitness space. Like EDA's (Estimation of Distribution Algorithms) for example.

The main reason of this question is, what types of optimization heuristics are suitable to solve this kind of problems.


texts: Prove/ Disprove: If $L$ is a CFL then $A(L)$ is a CFL too

texts:
Consider the operation $A(L)$:

$$A(L) = \{ w: w\in L \land w_R \notin L \}$$

where $w_R$ is the reverse of $w$.

  Prove/ Disprove: if $L$ is a CFL language so does $A(L)$.

I am almost certain there's a counter-example but I couldn't find a proper one. I'd be glad for help!

Thanks


texts: What is the difference between Babbage's analytical and difference engine? Can they even be compared?


texts: How to determine number of instances for resources in a resource allocation graph?

texts: I am struggling to determine the number of instances a resource will have. I have performed extensive research on this, but unfortunately have come up short. I am tasked with drawing a resource allocation graph and I have been provided with the number of processes which is 3 and the of resources which is 5. I have concluded that when drawing the resource allocation graph, I will need to know the number of instances of a resource. Please could someone just help in how I would go about working out or determining the number of instances a resource will have?


texts: Is there a skippable, countable generator for unique permutations up to some symmetry?

texts: Is there a good algorithm for generating all and only the unique permutations of a finite set respecting some kind of symmetry? For example, in Klondike solitaire, the two black suits are interchangeable, the two red suits are interchangeable, and the black suits are interchangeable with the red suits. This results in 4 symmetries, but from a unique game perspective we only need to generate one representative. Ideally this generator would be countable (identify how many permutations there are), and skippable (go to the Nth permutation without generating intermediary permutations)?


texts:
I'm going through an algorithms text book. One of the questions asks:

True or false?
$n + 2n^2 + 10n^4$ is $O(n^5)$.

This is marked as true.
Shouldn't it be $O(n^4)$? What am I missing here?


texts:
I just read an article  "Statistical approach for figurative sentiment analysis on Social Networking Services: a case study on Twitter", which provide an algorithm to analyze tweets, and this article includes 2 formulas which I don't really understand.

Link to the article

I hope maybe someone here can help me.

The first formula is the (4) formula (Page 5)
The second formula is the (6) formula (Page 8)

I will be very thankful if someone will help me with this.

Examples will be most welcome! :)


texts: Is the image of a function the codomain of a function?

texts:
Here is a definition from the functions section in my discrete math textbook (Discrete Mathematics and its Applications 7e, Rosen 2012):

  Let $f$ be a function from $A$ to $B$, and let $S$ be a subset of $A$. The image
  of S under the function $f$ is the subset of $B$ that consists of the
  images of the elements of $S$. We denote the image of $S$ by $f(S)$, so:

  $f(S) = \{t \mid \exists s \in S (t = f(s)) \}.$

  We also use the shorthand $\{ f(s) \mid s \in S \}$ to denote this set.

So I guess I am just a little confused with the idea of an image. Is it the same as the codomain? And where it says, "The image of $S$ under the function ...".  What do you think it means by "under"?  Some examples would be great.


texts: Minimum Weight Directed Subgraph ensuring all pairs reachability?

texts:
After some work on Minimum Spanning Trees and Steiner trees in combinatorial problems I came across this problem that I would like to look further in my research, but I want to know if there is an algorithm for it. I couldn't find anything in Google or Google Scholar.

Given a directed graph $G=(V,E)$ with a weight for each edge given by $w(e)$, find a subset $S \subseteq E$ of minimum cost (sum of weights) such that for every pair $u,v \in V$ of nodes, there is a path from $u$ to $v$ that traverses only edges in $S$.

For instance:

A--2->B
^     |
|2    |2
|     v
C--1->D
 <-3--

In the example, there is an edge from C to D of cost 1 and the opposite direction of cost 3. The solution here would be the edges CA, AB, BD and DC.  This solution has cost 9.

Any variation of Prim or Kruskal fails on this problem, and I can't see any other algorithm that I could modify to work here. Also, I can't come up with any algorithm (I'm starting to suspect its NP-complete, but I am still looking for a reduction).

Can anyone tell me if this is indeed proven NP-complete or if there is a polynomial-time algorithm for this?


texts: Proving Postorder Traversal's Time Complexity

texts:
I am looking at the following algorithm for performing a Postorder Traversal of a binary tree

POSTORDER(root):
if root != nullthen
    POSTORDER(root.left);
    POSTORDER(root.right);
    visit root;
end if;

I am supposed to be able to demonstrate that this algorithm runs in Θ(n) time complexity when the input is a n-vertex tree. But I am not even sure where to begin with doing that.

I have looked at the following sources:

https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/
https://en.wikipedia.org/wiki/Reverse_Polish_notation
https://en.wikipedia.org/wiki/Tree_traversal
https://leetcode.com/articles/introduction-to-n-ary-trees/

I understand WHAT PostOrder traversal does, and I understand WHAT a binary tree is, but I don't know how I can prove that time complexity.

Could anybody help me on this?


texts: Computing similarity of two graphs with partially overlapping sets of nodes

texts: Consider two graphs $G_1 = (E_1, V_1) $ and $G_2 = (E_2, V_2)$ with their associated sets of edges $E$ and nodes $V$. I'm familiar with concepts such as edit distance for computing the similarity/distance between these two graphs. I was wondering if there are any metrics for estimating similarity between graphs where they contain only partially overlapping sets of nodes, for example, if $V_1 = (A, B, C) $ and $V_2 = (B, C, D)$.


texts: Single pair shortest path algorithm with time a constraint

texts:
I am trying to solve the shortest path problem between n cities. Any single pair shortest path algorithm such as Dijkstra's and Bellman-Ford would work here, but if we add a simple additional constraint "the total time should not exceed T time units", then the problem becomes much harder.

More formally:

The input consists of a set of n cities and m roads between pairs of cities. There can be  multiple roads between a pair of cities $(i, j)$. For each road, you are given its departure city $x_i$, its destination city $y_i$, its duration $d$, and its cost $c$. The objective is to find the cheapest path between a pair of cities $(a, b)$ such that the cost is minimized while keeping the duration less than the maximum duration $T$.

I tried thinking on the lines of Dijkstra's and modifying the graph so that it is in some way possible to run a shortest path algorithm on it, but there seems to be no trivial way of doing this. Simple solutions like (follow a greedy strategy until you exceed the time limit, and then move on to the next element in the priority queue) don't seem to work because the use of a priority queue in the Dijkstra's algorithm and DEQUEUING the minimum element from the priority queue behave like destructive operations. There is a need to backtrack (of sorts) but the shortest path algorithms visit each node in the graph only once.

I've tried thinking about other simpler approaches using the Bellman-Ford algorithm, but the time complexity of the algorithm I  turned out writing depended on $T$ (which is not very desirable).

I spent almost 2 days on this and every solution I try either seems to not work, or runs in exponential time. Is this problem NP hard or are there polynomial time solutions possible?

P.S. I am not looking for a practical implementation of this problem, just an algorithm that can solve this problem in polynomial time. Although any thoughts about how to efficiently implement this would be more than welcome :)