texts: O(V+E) algorithm for computing chromatic number X(g) of a graph instead of brute-force?

texts:
I came up with this O(V+E) algorithm for calculating the chromatic number X(g) of a graph g represented by an adjacency list:

Initialize an array of integers "colors" with V elements being 1
Using two for loops go through each vertex and their adjacent nodes and for each of the adjacent node g[i][j] where j is adjacent to i, if j is not visited yet increment colors[g[i][j]] by 1.
After doing this the maximum integer in the array "colors" is the chromatic number of the graph g(if the algorithm works).

Here is my C++ code:

#include <bits/stdc++.h>
using namespace std;

struct graph {
    vector<vector<int>> adjL;
    vector<int> colours;
    vector<bool> vis;
};

int chrNUM(graph& G) {
    int num = 1;
    for(int i = 1; i < G.adjL.size(); i ++) {
        for(int j = 0; j < G.adjL[i].size(); j ++) {
            if(!G.vis[G.adjL[i][j]]) {
                G.colours[G.adjL[i][j]] ++;
                num = max(num, G.colours[G.adjL[i][j]]);
            }
        }
        G.vis[i] = true;
    }
    return num;
}

void initGET(graph& G, int N, int M) {
    cin >> N >> M;
    G.adjL.assign(N + 1, vector<int>(0));
    G.colours.assign(N + 1, 1);
    G.vis.assign(N + 1, false);
    for(int i = 0; i < M; i ++) {
        int u,v;
        cin >> u >> v;
        G.adjL[u].push_back(v);
        G.adjL[v].push_back(u);
    }
}

int main() {
    graph g;
    int n;  //number of vertices
    int m;  //number of edges
    initGET(g, n, m);
    cout << chrNUM(g);
}

I am wondering if there is a flaw? Maybe it works for certain graphs only? Maybe it gives X(g) for smaller graphs but a value higher than X(g) for larger graphs? I found it worked correctly for all the graphs I have tried (up to 20 vertices). I know this is an NP complete problem but I want some counterexamples for my algorithm if possible or an explanation as to why the method won't work. I have also got a recursive (DFS) solution which is a bit different but mostly similar to this. Any ideas?

Thanks in advance!


texts:
"Cookies" are a user-facing computing construct. They are codified in many technical specifications, including the earliest reference in an HTTP spec, RFC 2109, published February 1997.
Many claim the use in HTTP followed from UNIX "magic cookies." Eric Raymond provided a definition of what a "magic cookie" is:

Something passed between routines or programs that enables the receiver to perform some operation; a capability ticket or opaque identifier [...]

OK.
But why did the UNIX community start using the phrase "cookie" to begin with? Is it because you put cookies into a jar, and take them out? When did this whole thing begin? Does anyone have a citation of the first usage?


texts: MESI Protocol Invalid cache line is attempted to be stored?

texts:
I am implementing a sample MESI simulator having two levels of cache (write back). I have added MESI status bits to both levels of cache. As it is a write back cache, the cache line is updated to L2 only when it is flushed. My doubts are

what should be the behavior when a cache line with INVALID state is flushed from L1 cache. Will it just ignore the transaction? It seems that is the only possibility..but it doesn't seem right.
Consider processor1(P1) modifying a cacheline shared by processor2(P2). Then that cache line in P2 will get status INVALID. If P2 has to update the same cache line in future and sees the state is INVALID, it should read the updated value from??what if it is still in modified state in P1(not yet written back to L2/Main memory)?
Consider a similar situation that P1 has a cache line in MODIFIED state, P2 has the same line in INVALID state. When P3 tries to retrieve the same line, it broadcasts a request to all L1 caches. According to the theory,if P3 cant get the cache line from any other L1 caches, it sends request to L2/main memory. In this case where will P3 get the requested cache line from? From P1 or from the L2/main memory? Or will P1 update to the main memory first and then send the cache line to P3?
I am using LRU for flushing the cache(write back). When flushing a cache if it is INVALID what should be the behavior? It just ignores the line?


texts: Disruption in the context of Genetic Algorithms

texts:
I'm trying to do a homework problem which references "disruption" in Genetic Algorithms.

  True or false? For  1-point  and  2-point  crossover,  the  schemata
  which  have  bits  that  are  close  together  on  the string encoding
  are more likely to be disrupted by crossover.

I think that it is referring to is the creation of children distinct from their parents.

For example, combining the following two parents at a single crossover point at the second digit would just create the same parents again. Thus, no disruption would occur.

p1: 00000
p2: 00001

However, combining the following two parents at a single crossover point at the second digit would create some disruption.

p1: 00000
p2: 01001
c1: 01000
c2: 00001

By intuition, I would measure disruption as the number of bits that are different in a child as compared to the two parents. However, I have no formal definitions of this, despite turning to Google. The closest I've come is to Holland's Schema Theorem, which I think is related, but I would still like a definition or an explanatory reference.


texts: Is the sieve an improvement for prime finding over an optimized algorithm?

texts:
I don't think it is, as you have to loop through each set multiple times at least.

implementation of sieve in JS - in the answer at the bottom.  The link shows a 10X improvement using sieve.

In this case it is faster b.c. the function changes the integers to bits and is working with bits instead of integers.

But if you look at the structure of the code it has 3 loops.  An optimized non sieve version has only 2 loops.

For example here is an optimized algorithm:

function findPrimes(n){
  const primes = [2];
  label: for(let i = 3; i <= n; i += 2){
    for(let j = 0; j < primes.length; j++){
      if(i % primes[j] === 0) {
        continue label;
      }
    }
    primes.push(i);
  }
  return primes;
}

and here is the sieve method using bit-wise operations.

  "sieve": function sieveOfEratosthenes(n) {
    var sieve = new Int32Array(Math.ceil((n + 1) / 64)).fill(-1);
    var primeVals = [2];

    for (var i = 3; i * i <= n; i += 2) {
      if (sieve[i >> 6] & (1 << (i >> 1 & 31))) {
        primeVals.push(i);

        for (var j = i * i; j <= n; j += i + i) {
          sieve[j >> 6] &= ~(1 << (j >> 1 & 31));
        }
      }
    }

    while (i <= n) {
      if (sieve[i >> 6] & (1 << (i >> 1 & 31))) {
        primeVals.push(i);
      }
      i+=2;
    }
    return primeVals;
  }


texts:
If it is possible to construct an SLR parse table with no conflicts for a particular grammar does that mean that the grammar is unambiguous?

I think that since we have constructed the parse table which means for every sentence we would be able to decide whether the string will be accepted or not. But I am a little bit confused on whether it is really true or not. Actually, I am trying to prove that a grammar is unambiguous and I constructed parse table with no conflicts.


texts:
I'm autodidacting Pierce's Types and Programming Languages. On page 27 he states a definition for "terms, concretely" in constructing a language of terms, thus:

For each natural number $i$, define a set $S_i$ as follows:

\begin{align}
S_0 & = \emptyset \\
 S_{i+1} & = \;\;\;\{true, false, 0\} \\
& \;\;\;\cup \; \{succ \: t_1, pred \: t_1, iszero \: t_1\ |\: t_1 \in S_i\} \\
&  \;\;\;\cup \; \{if\: t_1 \:then \: t_2 \:else \: t_3\: |\; t_1, t_2, t_3 \in S_i\} \\
\end{align}

where $succ\: t$ is the successor of $t$, $pred \:t$ is the predecessor of $t$ and $iszero \:t$ tests if $t = 0$. Finally, let

$$S = \bigcup_i{S_i}$$

where $S_0$ is empty; $S_1$ contains just the constants (I assume $true, false, 0$ is meant); $S_2$ contains the constants plus the phrases that can be built with constants and just one $succ, pred, iszero$ or $if$; $S_3$ contains these and all phrases that can be built using $succ, pred, iszero$ and $if$ in $S_2$; and so on. $S$ collects together all the phrases that can be built in this way, i.e., all the phrases built by some finite number of arithmetic and conditional operators, beginning with just constants.

Then as an exercise: How many elements does $S_3$ have? And the answer is (from back of book): $|S_{i+1}| = {|S_i|}^3 + |S_i| \,\times\,3+3$, and $|S_0| = 0$. So $|S_3| = 59439.$

I really get lost when he says what $S_1$ and $S_2$ are. Anyone who could get me started on what is going on here, or could point me to another treatment of these ideas would be appreciated.


texts: Comparing different asymptotic notations

texts:
Suppose we have 3 algorithms complexity times at the worst case:

A = $O(nlogn)$
B = $O(n\sqrt{n})$
C = $\Theta(n)$

In my opinion, it is not possible to define the best solution, since we don't know how Cgrows. I'd like to confirm if that's correct.


texts: Complexity of finding these original parameters

texts:
I am given (or rather, generate randomly) three positive integers $a, b, c$. I want to know if there exist integers $m \ge 2, s \ge 1$ such that $ms+m = a, ms+1 = b, 2s+1 = c$. If there are multiple solutions, I want the minimal (if possible).

It is clear that $c$ has to be odd, so if $c$ given to me is not, then I can immediately stop the computation. However, I'm not sure what other cases there can be.

Also, I'm not sure if there is a better alternative than the following (or even brute-force): let $d = \min(a, b, c)$, and have $m, s$ be roughly $\sqrt{d}-m$, and try brute-force starting from there.


texts: How does Paxos maintain the promise that future proposal will not break the current chosen value without knowing the future?

texts:
I was studying Paxos from:

http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf

and I was trying to understand page 4, specifically, the following paragraph:

"To maintain the invariance of $P2^c$, a proposer that wants to issue a proposal
numbered n must learn the highest-numbered proposal with number
less than n, if any, that has been or will be accepted by each acceptor in
some majority of acceptors. Learning about proposals already accepted is
easy enough; predicting future acceptances is hard. Instead of trying to predict
the future, the proposer controls it by extracting a promise that there
won’t be any such acceptances. In other words, the proposer requests that
the acceptors not accept any more proposals numbered less than n. This
leads to the following algorithm for issuing proposals."

Where condition $P2c$ is:

"For any v and n, if a proposal with value v and number n is issued, then there is a set S consisting of a majority of acceptors such that

(a) no acceptor in S has accepted any proposal numbered less than n, or

(b) v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S."

I was specifically confused about the section I have in bold. I was confused why, if we want to develop some hypothetical consensus distributed algorithm, why do we need to know about higher sequence numbers that have not happened? What is the intuition behind that?

Sorry if my title is a little strange, I was not sure what was a good title for the question.

Author: Leslie Lamport

Title: Paxos made simple

Institution: Microsoft Research


texts: Partitioning list into two parts of almost equal sum

texts:
I was given this problem in class, and I have no idea how to solve it. The problem is:

"Given a list of positive integers, divide the numbers into 2 groups such that the difference between the sum of each group is minimal, print that difference. The algorithm must be efficient."

I guess by efficient they mean do not just brute force every option, any ideas?
I tried summing all the numbers and dividing by 2, then the problem is equivalent to finding a group that is the closest to that number, also now you can go over all  the options but once you get to a point where you can only add numbers but your above that number you  can stop.


texts: Is the bitwise-xor of a Uniform bit string and a non_uniform bit string Uniform?

texts:
Having two bit strings $x,y \in \left\{0,1\right\}^n$, where $x$ is selected following a uniform distribution but $y$ is not.

Is $z = x \oplus y$ uniform?


texts: Algorithm for finding 2 missing items in a stream of integers

texts:
I saw this post and wondered why the approach described in the accepted answer works. The same problem and solution is described a bit nicer here.

So let's say we receive a stream of $n-2$ pairwise different numbers $a_1 + a_2 + \cdots + a_{n-2}$, from the set $\left\{1,\dots,n\right\}$. What I learned from the above post is that for the problem of finding 2 missing numbers $x$ and $y$, given a stream as described above, can be solved by finding the solution to the following system of equations:

\begin{alignat*}{4}
 x+y & {}={} & \dfrac{n(n+1)}{2} - (a_1 + a_2 + \cdots + a_{n-2}) \\
 x^2 + y^2 & {}={} &  \dfrac{n(n+1)(2n+1)}{6} - (a_1^2 + a_2^2 + \cdots + a_{n-2}^2)
\end{alignat*}

Now it is easy to convert this into a single pass algorithm which supposedly returns the two missing numbers for a given stream.

How would one prove this algorithm's correctness?  I think showing that the system must have exactly two solutions would be enough to prove correctness but I'm not sure how to approach this?

How can I convince myself (and others) that the algorithm is correct?


texts: If a user confirmed a booking or transaction on the database system, but it failed and it falls over to the replica, what if the transaction is lost?

texts:
This is an overall system design and DBMS question:
If the user books a ticket or an item on a website, how do we solve the issue of confirming a ticket is sold to the user, but the main Database System breaks down, and the secondary DMBS doesn't have that information yet?
Is the most common solution just to not commit the transaction until both the master and slave DBMS has confirmed?


texts:
The question for my homework is to create a two-tape DFA for accepting two string such that u is 2x the size of v.

I am just confused on where to go with this, i understand this in a base sense but i can't figure out how i would find if it is 2x V after getting beyond V


texts: Is it or is it not correct to say that the expected runtime of an algorithm is its runtime on the expected problem size? Why?

texts:
Say we have an algorithm that takes time $T$ to process a problem of size $n$.

Is $\langle T(n)\rangle $ = $T(\langle n\rangle)$?


texts: Maximum Capacity Path Problem with constraints

texts:
I was trying to develop an algorithm for maximum capacity problem with constraints but couldn't figure out the necessary changes required for correct output.
The problem is: Given an undirected graph with two parameters (weight,cost). We need to find the Maximum Capacity path problem from source to destination such that the cost of the path(sum of the edges of path) is within a fixed value specified by the user. In other words, it(sum of cost parameter along the path) is upper bounded by a constant value.
I modified the existing algorithm by adding and extra cost constraint while relaxing the edges but was unable to make it work for all types of graph. I was also wondering if this problem is NP-Complete.


texts: Algorithm to pack any small boxes into a big box

texts:
I have a container with a certain dimension. A number of small boxes that may be different in size is to be packed into the container. How to arrange the small boxes such that the container contains as many as possible?

No rotation is allowed.
The heavier boxes must not be on the top of the lighter ones.
Approximation is allowed.

I am looking for the algorithm so I can implement it in a software.


texts: Maximum integer in a sorted list which also is in an unsorted list

texts: If I have a sorted list $A=[a_1, \dots, a_n]$ such that the integers $a_1\leq a_2\leq\dots\leq a_n$, and an unsorted list $B=[b_1, \dots, b_k]$, which includes at least one integer also in $A$, can I then find the maximum integer in $A$ which also is in $B$ in $O(k\log n)$ time? If so, how?


texts: Must you work with all qubits in a circuit when applying a gate?

texts:
When looking at this question:
How to apply a 1-qubit gate to a single qubit from an entangled pair?

And other questions, it makes it seem like when you have a quantum circuit involving $N$ qubits, that when you want to peform a gate operation on a subset of the qubits, that you must still make a matrix that applies to all qubits.

Is this always true, or is it only true in the case where qubits are entangled?

In other words... is it only entangled qubits that we have to process together, or must all qubits in a circuit be processed together?


texts: What was the impact of Impagliazzo's A Personal View of Average Case Complexity?

texts: I'm studying his paper and I was wondering how the community reacted to it. Yes, Average Case Complexity has come a long way since then, but I want to know if it was directly influenced by it.


texts: How to use Type application Rule to get a desired type

texts:
In type application Rule :

$$\dfrac{ \Gamma \vdash t_1  : T_{11} \to T_{12} \qquad \Gamma \vdash t_2 : T_{11}}
        { \Gamma \vdash t_1 \ t_2  : T_{12} }
        \textsf{ (T-App)}$$

if we deriving the term from bottom up, how to get $T_{11}$ from ? How you'll know what is $T_{11}$?  Its not clear to me.


texts: Why do agents always employ the same algorithm when playing a congestion game?

texts:
I've been conducting research into congestion games and have come across many papers that study the effects on the outcome of a game played by agents employing a particular algorithm e.g. seeing how quickly Nash equilibrium is approached when using a modified version of fictitious play.
Is there any particular reason as to why there hasn't been any research conducted that looks into agents using different algorithms playing a single congestion game? For example, agents who uses fictitious play playing alongside agents who use a q-learning algorithm.


texts: Algorithm to find out if a set contains two number with sum in the same set using a blackbox function

texts:
I need help with the following question -
There is a set S of n integers.
Given a black box which returns three integers a,b,c in S such that a+b+c = 0 if they exist.
One needs to devise an algorithm that makes only one call to the black box to find out if S contains
three integers such that a+b=c
The question also had a hint -
Construct a set S' such that there exists  a',b',c' in S' such that a'+b'+c'=0 if and only if
there exists a,b,c in S such that a+b=c
Thanks


texts: Proof of Fundamental Lower Bound on Regret

texts:
Online Convex Optimization sees optimization as a continuous process in which the algorithm learns new aspects of the problem and improves upon.

Every iteration consists of the player making a decision $x_t$ from a convex and bounded decision set $\mathcal{X}$. After we made our decision the adversary returns the loss for our decision, $f_t(x_t)$. Often the gradient of the loss function is accessible too, $\nabla_{x_t}f_t(x_t)$. This loss function $f_t$ can change, follow any distribution, but is always convex and bounded.

Any OCO algorithm (such as online mirrored descent or regularized follow the leader) aims to minimize regret, the loss of your decisions minus the loss of the best decisions in hindsight. This is defined as $\mathcal{R}_T := \sum_{t=1}^Tf_t(x_t) - \min_x \sum_{t=1}^Tf_t(x)$.

Using (a.o.) two bounds;
$$ ||x - y|| \leq D \quad \forall \quad x, y \in \mathcal{X}$$
$$ ||\nabla_x f_i|| \leq G \quad \forall \quad i \leq T \quad \forall \quad x \in \mathcal{X}$$
it is possible to derive an upper bound on regret for most algorithms. Online Gradient Descent is for example guaranteed to converge with $\mathcal{R}_T \leq \mathcal{O}(GD\sqrt{T})$.
Now, different algorithms benefit different convergence rates.
Although most algorithms converge $\Big(\lim_{T\rightarrow\infty}\mathcal{R}_T/T = 0\Big)$, no matter how good your algorithm, at iteration 0 you have no information about $f_t$. It takes a certain number of iterations before you can make optimal decisions. Therefore there must be a fundamental lower bound any algorithm can achieve as an upper bound. It turns out to be $\mathcal{O}(GD\sqrt{T})$.

Theorem 3.2, in [1] states:
Any algorithm for online convex optimization incurs $\Omega(DG\sqrt{T})$ regret in the worst case. This is true even if the cost functions are generated from a fixed stationary distribution

They don't proof it however. They give an example which sketches the proof, but if someone could explain the proof or give a different proof that any algorithm will have a an upper bound on its regret greater or equal than $\mathcal{O}(GD\sqrt{T})$.

**[1] E. Hazan - Introduction to Online Convex Optimization **
https://arxiv.org/pdf/1909.05207.pdf


texts: Whats is the name for a complexity like $n^{\log \log n}$ ? Is this exactly subexponential, or less than that ?


texts: Why is there no regularity condition in case 1 of the master theorem?

texts: In case 3 of the master theorem, which is applicable when most of the work is being done at the top node (roughly speaking), we also need a regularity condition that the work done at the topmost level is greater than that at the bottom levels, in addition to it being greater than work being done at last level. However, in case 1, which is applicable when most of the work is being done at the last level, we assume that it will be greater than all the previous levels. Why is that? Shouldn't there be a regularity condition for case 1 also?


texts: Monitoring files in preservation archives

texts:
What are efficient and accurate techniques for monitoring the recoverability and integrity of files in very large preservation archives?

In very large archives, the time taken to recompute checksums periodically (scrubbing) is substantial, perhaps taking more than all the available time depending on the read bandwidth available! Also, each access to a preserved file increases the risk of damage due to hardware or software failure. Tapes are most stable in a cold, dark place far from exposure to the hazards of data centers. Disks are most at risk when the read/write head is flying close to the medium. All approaches are probabilistic, so which are most efficient and accurate?

To give the problem specificity, let's assume a fixed probability of local single-bit errors for each medium (one probability for tape, another for disk, SSD, etc) during a standard time period, and ignore all other types of errors (loss of an entire volume, for instance). We can also assume a fixed read bandwidth for each medium.


texts:
If we start a new process with

exec('process-2')

Does this cause an immediate context switch in order to halt the current process and then start the new 'process-2'?

Edit:
This is a theoretical question with no specific OS intended, but you suppose it's some UNIX like OS.

There is no specific details about exec, the only thing I know is that exec halts the current program execution and executes the other program.

Also the assumption here is that we are using a uni processor system.


texts: Data versioning in a relational database

texts:
I've been working on an industrial project where my job was to design a data model in-memory and in a relational database in such a way, that can capture the time-varying nature of the production planning of a factory. In other terms, there exist input data and whenever a planning occurs, I have to take a snapshot of the current state of the world and store it.

My solution was to add a header object/table for all relevant input data and output data and have them reference each other's header by its unique auto-incrementing id. Such headers are then considered final and immutable and I do a deep-copy only if something needs to change.

I believe this approach isn't new but I can't recall any (relational-) data modelling courses explicitly mentioning this. My PhD advisor (who is not into general CS) wants me to have a thesis point about this and I'm unable to convince him that either this isn't new or at most a trivial extension to some existing methodology. I've tried searching Google Scholar, but didn't find any articles, perhaps due to wrong keywords.

Can someone point me into the right direction?


texts: Looking for an esoteric graph theory algorithm

texts: So I'm sure this is an unusual question for this type of site, but I am to give a talk on algorithms for discrete graphs in a few weeks. It has been specified that the talk is to be on some algorithm which will be unfamiliar for those attending. It it to be some graph traversal algorithm at about the junior level. Does anyone know of any such algorithm which is a bit removed from main stream graph theory?


texts: Why the Goemans-Williamson's MAX-CUT algorithm relax the variables to vectors of $n-$dimension on unit sphere?

texts: Why not to some constant like 3 or 4 dimension? I suspect that it is because Cholesky Decompostion will work only for $n \times n$ matrix $B$ where $B^TB = P$ where $P$ is a semidefinite matrix. Is it true? Or there is something else?


texts: Greedy algorithm for subset sum on powers of 2

texts:
I have some $n$ numbers which are powers of $2$, say $a_1,a_2,a_3,\ldots,a_n$ which are not necessarily all distinct. I have option to give them any sign. I have to find if I can make their sum after that equal to num.
I have following algorithm which I am sure will work, by a lot of arguments and verification, but I am not able to prove it:

We sort the array.
Initialize another variable temp to $0$.
We traverse from highest element to lowest element.
If temp>num then subtract $a_i$, else add $a_i$. If in the end temp=num then it's possible to assign signs such that we can make num out the array, otherwise it is not possible.

How to prove that the algorithm works?


texts: Is there any optimization technique for DP with $f[i][j] = \min_{z<j}{f[i-1][z] + G[i][j-z]}$ where G[i] is increasing and positive?

texts:
Given a dynamic programming formula like
 $f[i][j] = \min_{z<j}{f[i-1][z] + G[i][j-z]}$ where $G[i][j]$ is positive and increasing along $j$ for all $i$s. Is there any optimization to make it faster than $O(N^3)$?


texts:
I have to write an algorithm that exactly reflects this recurrence:
$$
T(n)=\begin{cases}
Θ(1)\;\;\;\;n \leq 1\\
2T(n/2)+log^2(n)\;\;\;\;n >1
\end{cases}
$$
I have tried this way:

//the array starts from 1
    mergesort(A[], b, e)
    {
       if(b < e)
       {
          p = (b+e)/2;
          mergesort(A, b, p);
          mergesort(A, p+1, e);
          for(i = 1; i <= e; i = i*2)
             for(j = 1; j <= e; j = j*2)
                puts("");
       }
    }

does the algorithm respect the recurrence?

EDIT:

could a solution be?

//I have only changed the two fors
            mergesort(A[], b, e)
            {
               if(b < e)
               {
                  p = (b+e)/2;
                  mergesort(A, b, p);
                  mergesort(A, p+1, e);
                  for(i = 1; i <= e-b; i = i*2)
                     for(j = 1; j <= e-b; j = j*2)
                        puts("");
               }
            }


texts: Semantic/DRT methods for conversational agents / chatbots / dialogue systems - reference request?

texts:
The wiki pages about chabots mention that statistical methods, keyword search and precompiled answers are used for the chatbots. But I feel that there should exist different - semantical approach for constructing chatbots. There are formal semantics of natural language (recent results in http://www.springer.com/gp/book/9783319504209) that expresses natural language into lambda calculus and translates those expressions into further logical expressions like deontic logic expressions. And then there is discourse representation theory. So - in essence one can imagine the conversational process as interactive logical inference process in which conversational agent as Belief-Desire-Intention agent strives to achieve some goals by producing texts using formal semantics of natural language and the logical inference (inference control).

So - are there research efforts or research trends along the described lines? Google gives nothing important for joined phrases 'discourse represenation theory and chatbot', etc. But Google is not helpful in many many cases in which scientific endeavours uses completely different keywords. So - I am asking for keywords and maybe some reference works.


texts: Are all decidable languages mapping reducible to its complement?

texts:
I dont think this is true, take the language with a single element L = {0}, then the complement L' would have infinitely many strings (everything that isn't 0). So if it were true that A is mapping reducible to its complement, everything in L' can be obtained via a computable function from some element in L, i.e  010 is in L' however there is no x in L that gives f(x) = 101, since theres only one element, 0, it maps to one result.

Would this be correct?


texts: Closure against right quotient with a fixed language

texts:
I'd really love your help with the following:

For any fixed $L_2$ I need to decide whether there is closure under the following operators:

$A_r(L)=\{x \mid \exists  y \in L_2 : xy \in L\}$
$A_l(L)=\{x \mid \exists  y \in L : xy \in L_2\}$.

The relevant options are:

Regular languages are closed under $A_l$ resp. $A_r$, for any language $L_2$
For some languages $L_2$, regular languages are closed under $A_l$ resp. $A_r$, and for some languages $L_2$, regular languages are not closed under $A_l$ resp. $A_r$.

I believed that the answer for (1) should be (2), because when I get a word in $w \in L$ and $w=xy$ I can build an automaton that can guess where $x$ turning to $y$, but then it needs to verify that $y$ belongs to $L_2$ and if it won't be regular, how would it do that?
The answer for that is (1).

What should I do in order to analyze those operators correctly and to determine if the regular languages are closed under them or not?


texts:
This is a question posted for extra practice (i.e., not for credit):

  Can an algorithm with $\Theta(n^2)$ run time be faster than an algorithm with $\Theta(n\log n)$ run time? Explain.

I'm not sure how to approach it. I see lots of near-answers online using $O(\cdot)$, but $\Theta(\cdot)$ is a little different because it means there is both an upper and a lower bound of $n^2$ and $n \log(n)$, respectively.

So, at its absolute best case, a $n^2$ algorithm may run in $\frac{1}{a}n^2$ time, which for large $a$ may be very fast compared to most quadratic algorithms. However, since $a$ is constant, as $n \to \infty$, the time for even a $\frac{1}{a}n^2$ algorithm will far surpass a $bn\log(n)$ algorithm, even if $b$ is very large.

This would lead me to believe the answer is no, an algorithm that runs in $\Theta(n^2)$ cannot run faster than a $\Theta(n \log n)$ algorithm when analyzed asymptotically as I have done.

With this said, if the thing that makes the $\Theta(n \log n)$ algorithm $\Theta(n\log n)$ happens very frequently but the thing that makes the $\Theta(n^2)$ algorithm $\Theta(n^2)$ does not happen frequently at all (either due to the nature of the algorithm or optimized design), then the amortized complexity of the $\Theta(n^2)$ algorithm may in fact be less than that of the $\Theta(n \log n)$ algorithm — even if the asymptotic complexity says otherwise — right?

If the two complexities given were $O(\cdot)$ rather than $\Theta(\cdot)$ then I may be inclined to side with the latter argument. The presence of the lower bound that $\Theta(\cdot)$ implies is giving me second thoughts though. Can anyone help point me in the right direction here and clarify if it seems that I am misunderstanding the use of $\Theta(\cdot)$ for asymptotic versus amortized analysis.

Edit: I don't think this is a duplicate of Sorting functions by asymptotic growth. I am familiar with how to use limits, etc. to classify and sort algorithms asymptotically. Speaking strictly in terms of asymptotics, I think the answer to my question is definitely no. The question quoted (as worded) seems more general though; it wants to know if there is any way that a $\Theta(n^2)$ algorithm can out perform a $\Theta(n \log n)$ algorithm. Is such an occurrence possible when considering amortized analysis rather than asymptotic analysis and the algorithms are structured as described above? Or is this irrelevant and the answer is still no?


texts: Deciding on Sub-Problems for Dynamic Programming

texts: I have used the technique of dynamic programming multiple times however today a friend asked me how I go about defining my sub-problems, I realized I had no way of providing an objective formal answer. How do you formally define a sub-problem for a problem that you would solve using dynamic programming?


texts: Which is faster operations on register operands or immediate operands?

texts: I am reading the book Computer Organization and Design. It compares instructions on memory and instructions on registers but doesn't say anything about the speed of instructions when the source operand(s) is/are constants. In that case which will be faster register operands or immediate(constant) operands ?


texts:
Overfitting happens for some methods in certain conditions, but there is generic rule for all linear classifiers to overfitting?
I know that regularization is a remedy for overfitting, but I am asking the behavior of methods before regularization.


texts:
I am learning compilers and I am troubled by how to create the context-free grammar of a language. Is there a method I can follow to create the context-free grammar for most language ?
I'm new to this field so the question is basic,and I hope you can help me.


texts: Turing machine for $u<v$ with $u$ and $v$ positive binary numbers

texts: I was wondering how would I go about constructing a Turing machine that accepts $u < v$ with $u$ and $v$ positive binary numbers: for example $10<100$ is accepted but $11<10$ would not be. (We can assume that the leftmost digit is always a $1$). I was thinking that I should start by changing the $1$s to $X$s but that doesn't seem to work out.


texts: Building heaps and heapsort using linked list

texts:
I know that linked list is not a appropriate data structure for building heaps but I am interested in knowing the time complexity of building heaps and heapsort using linked list.

One of the answers here (https://stackoverflow.com/a/14584517/5841727) says that heap sort can be done in O(nlogn) using linked list which is same as with arrays.

For building a heap, I think that heapify operation would cost  O(n) time in linked list and we would need (n/2) heapify operations leading to time complexity of O(n^2). Is it correct?

Also, can someone please tell how to achieve O(nlogn) complexity (for heap sort ) using linked list ?


texts:
I'm confused about Turing reducible things.
I understanded Turing reducible like this
"There is an oracle algorithm which is about set A and when this algorithm is derived from oracle algorithm of set B, it is called A is Turing-reducible to B"
So by this, I have to solve the problem.

N is the set of natural numbers = {1, 2, 3, ...}
Let A be the set of all even natural numbers.
Let B be the set of all odd natural numbers.
Prove that A is Turing-reducible to B.

Here is what I have thought.
The oracle algorithm of A is n%2==0 which n belongs to natural numbers.
And oracle algorithm of B is n%2==1 which n belongs to natural numbers.
How can I derive n%2==0 from n%2==1 ?
Or my approach is wrong?
Thanks for your help.


texts: Travelling Salesman Problem: Distance between solutions

texts:
I'm designing a genetic algorithm to solve the travelling salesman problem. So far, I've gotten fairly good results. I'm now trying to improve on them by implementing some sort of diversification scheme (like fitness sharing and crowding), although I'm struggling with the conceptualisation of the inter-solution distance a bit.
Solutions represent a path that goes through all cities, i.e. a permutation of the order in which they are visited. This is represented in my code by np.arrays. If I want to know how similar two solutions are, I basically want to find the distance between two permutations of n_cities elements. I currently have two ideas for the distance function.

Levenshtein distance, which is simply 'how many atomic edits are two sequences removed from each other.
Hamming distance, which denotes the number of positions that are the same.

Note that, for each solution, I make sure to cycle it so it starts in the same position (city). Otherwise these metrics won't make sense.
Which of them is more appropriate? Is there a better solution? I've browsed a number of articles, but haven't really found an answer yet.


texts:
I am trying to find a correct invariant of BFS. If we represent a queue as $ Q =
 [a_0;...; a_n]$ such that : $Q.pop() = a_n$ then I found the following invariant which I think is correct (we denote by $Q$ the queue used to run the BFS, $s$ the node in the graph from which we begin the BFS and $d$ the distance between two nodes in the graph):

all elements in $Q$ are in decreasing order (i.e., for all $i <j$, $d(s,a_i) \geq d(s, a_j)$ ) and  $d(s,a_n) \leq d(s,a_0) \leq d(s,a_n)+1$.

So in the queue there aren't three nodes $a_i, a_j, a_k$ that are all at  distinct distances from $s$.

So is this invariant correct? Is it the common invariant to use or we generally use a "simpler" invariant? (In this case It would be very nice if you can give this invariant.)

Thank you very much!


texts: Is O(|A| + |B|) the size of the union of two synchronized DFAs A and B?

texts:
In general, the size of the DFA resulting from the union of two DFAs A and B is O(|A|.|B|) in the worst case (usually the product construction is used to compute the union).

Let's consider the class of 'synchronized DFAs' as the class of DFAs having a synchronizing word : https://en.wikipedia.org/wiki/Synchronizing_word

After looking at some examples of synchronized DFAs A and B, it seems possible to always build a synchronized DFA for the UNION of A and B with a size O(|A| + |B|) in the worst case.

Does anybody have any information, proof or paper about the union of two synchronized DFAs in O(|A| + |B|) ?

Many thanks,
Luz


texts:
I am working on a problem which could be reduced to a graph optimization problem as below.

A set of colored nodes is given.
The edges are to be inserted between the nodes.
A node can have only 4 edges at max.
A table provides rules for profit contribution from the edges.

Eg.,

An edge connecting red to red: profit is 10
An edge connecting red to blue: profit is 20

The total number of colors is typically around 20 to 30, but it can go as high as 50. Correspondingly the table for profit(edge) would be a long list but it won't list all possible combinations. The profit for edges not specified in the table is assumed zero.

The problem is to optimize the connections (edges) such that the total profit is maximized.

I am wondering if this problem, maybe in some other way, is known. If so, please provide any pointers that might be of help. Thanks.


texts:
Lately, I asked this question to find the maximal set of elements $S$ of a given array $T$ such that every element of $S$ is greater than or equal to the cardinality of $S$.

My question is now different. How to find all maximal sets $S_i$ of a given array $T$ such that every element of $S_i$ is greater than or equal to the cardinality of $S_i$.

For example, if $T=[9, 8, 2, 2, 1]$, then all maximal sets that satisfy the condition are $S_1=[9, 8]$, $S_2=[9, 2]$, $S_3=[9, 2]$, $S_4=[8, 2]$, $S_5=[8, 2]$ and $S_6=[2, 2]$.

My recursive solution or the solutions given in the previous question do not generate all maximal sets.

Is there any efficient algorithm that finds all maximal sets of such problem?

I think one way to solve the problem is to find a maximal set $S$ and return its size $|S|$--using any algorithm from this question. Then, generate all combinations $\displaystyle\binom{|T|}{|S|}$ and find which one of these combinations satisfies the condition. But can we do better?


texts: Finding mergable groups in a directed graph

texts:
I have a directed graph, $G = (V,E)$ (a dependency graph actually) and I want to find groups of nodes that can be considered as a single unit.

I define a group as a set of nodes, $A$, such that any node outside of the group, $v \in A^c$, that has an edge to a node inside, must have an edge to every other member of the group:

if $\exists u \in A: (u,v) \in E$ then $|\{\ (v,w)\ |\ \forall w \in A\ \wedge\ (v,w) \in E\ \}| = |A|$

Once groups are found, then a merge can be made, i.e. add a node $u'$ in G and for all edges from $v \in A^c$ to $u \in A,$ make an edge from $v$ to $u'$. Finally, remove all original nodes and corresponding edges in G, thus constructing a reduced graph.

This is similar to reducing a state machine.


texts: Solving T(n)=T(n−1)+2T(n−2) using substitution

texts:
I am trying to solve the following Recurrence relation using substitution method and I am stuck almost half way.
I know the answer is 2^n but I can't reach it.

At first, my question is:
Who decicdes the base cases? when do we take T(n)=1 for n=1 or T(n)=1 for n=0?

The work I have done till now is as follows:

T(n) = T(n−1) + 2T(n−2)

T(n-1) = T(n-2) + 2T(n-3)

T(n-2) = T(n-3) + 2T(n-4)

Thus, using these, we can subsitute and we get

T(n) = T(n-2) + 2T(n-3) + 2T(n-2)

T(n) = 3T(n-2) + 2T(n-3) (add and then substitue again)

T(n) = 5T(n-3) + + 6T(n-4)

Now assume we go till k, but I am not able to generalize the usage of k and find a correct assumption that will lead to a result of time complexity of Big O of 2^n


texts:
2-SAT is in P; 3-SAT is NP-complete.
Exact cover by 2-sets is in P; exact cover by 3-sets is NP-complete
Two-dimensional matching is in P; three-dimensional matching is NP-complete
Graph 2-coloring is trivially in P; graph 3-coloring is NP-complete

Are there other well-known or important examples that are similar, in that there is a family of problems with a natural parameter $n$, where the problem is known to be in P when $n<3$ and known to be NP-hard when $n≥3$?


texts: How to turing reduce equivalent languages $Q$ to infinite language $I$

texts:
Given two languages:

$Q= \{(\langle M_1 \rangle , \langle M_2 \rangle ) \mid L(M_1) = L(M_2)\}$

$I= \{\langle M \rangle \mid \;\vert L(M) \vert = \infty \}$

I'm trying to Turing reduce $Q$ to $I$ ($Q \le_T I$), not the other way around as solved here

Any ideas on how to solve this? What exactly will the Turing machine do here and which part is getting solved by the mysterious Oracle?


texts: Tiny question about Coding conventions for Lomuto partition code

texts:
Just out of curiousity: Both Introduction to Algorithms (Cormen et al), Wikipedia, and prior cs.stackexchange questions all present the Lomuto partition as:

algorithm partition(A, lo, hi) is
pivot := A[hi]
i := lo - 1
for j := lo to hi - 1 do
    if A[j] < pivot then
        i := i + 1
        swap A[i] with A[j]
swap A[i + 1] with A[hi]
return i + 1

which is a bit hard to remember.  I'm wondering why the following restatement isn't used instead. Suppose we do a change of variable, with i' = i+1 and swap the two lines after "if A[j] < pivot" accordingly.  In this case we have:

algorithm partition(A, lo, hi) is
pivot := A[hi]
i' := lo
for j := lo to hi - 1 do
    if A[j] < pivot then
        swap A[i'] with A[j]
        i' := i' + 1
swap A[i'] with A[hi]
return i'

so then the final statement is just

algorithm partition(A, lo, hi) is
pivot := A[hi]
i := lo
for j := lo to hi - 1 do
    if A[j] < pivot then
        swap A[i] with A[j]
        i := i + 1
swap A[i] with A[hi]
return i

I know that this isn't a big improvement, but is there some reason that the presentations I've seen all use the original formulation?

Thanks!


texts:
I have a question that asks me to find the minterm expression of two functions added together. The two functions in this case are

F = m(0,4,5,6)

G = m(0,3,6,7)

At the moment my reasoning is that the minterm expression of F + G would be the combined minterms of each function, taking out any repetition. So the result would be:

H = m(0,3,4,5,6,7)

but I feel the problem cant be that simple, this obviously isn't the correct solution. Would finding the solution require me to break up the minterm expressions of each function back into their variable, then add them together and simplify? Thank you for any input


texts: How are boolean circuits used for solving P vs NP?

texts: In the paper https://web.stanford.edu/~gavish/documents/sipser-pvsnp.pdf , it is mentioned under the Status section that boolean circuits have been used to try and solve P vs NP. Can anyone explain to me in simple terms how boolean circuits are used for solving P vs NP?


texts:
Related to this, but I felt it was more appropriate to ask as a separate question:

The complexity of Shor's algorithm is of order

$$O\left(n^2\,\log(n)\,\log(\log(n))\right)$$

with $n$ the bit length of the number to be factored. This paper asserts that on a terahertz range quantum computer (i.e. $10^6$ instructions per second) a thousand digit decimal number will take 84 seconds to factorize. It makes this assertion based on taking $\log$ to be $\ln$. By changing the $\log$ base it's obviously possible to get quite different answers e.g. $\log_2$ gives a result of 460 seconds.

My question is, is it at all meaningful/correct make such precise assertions as to run time based on this information?


texts: Count paths of length $n$ that a player can take

texts:
I'm writing a video game, and I'm trying to find an efficient way of calculating this. The goal is to count the number of paths of length $n$ that a character can take, where the character can move left, right, or up. The caveat is that the character cannot go back to the same position in a path.

I've come up with a mediocre brute-force method the count the paths, but any ideas on an efficient way to calculate this?


texts: Can someone explain this conclusion for Finite State Machines?

texts:
PS It isn't a homework problem..
(But the results seems to be working for me when I checked manually a couple of values of m and n)

Let's say I have two FSM's(calling them A and B)

A is the the machine for checking divisibility by any +ve number (calling it m)
B is the the machine for checking divisibility by any +ve number (calling it n)
(m and n aren't equal)

Now we have a third machine (C) for which we need to find the number of states it will have if the goal of that machine is A machine(FSM) which will accept Divisibility of both $n$ and $m$)

So here are the claims for the count of states for $C$,

if $GCD (m,n)$ equivalent to $1$, then the number of states in C is $m*n$
if $GCD (m,n)$ isn't equivalent to $1$, then number of states in C is $LCM(m,n)$

(EDIT 1- Both are technically the  same thing, check the comments and the answer)

(Edit -2  I meant this, if we have strings given to us over {0,1}, and the machines will then calculate the divisibility by the given number and with result in either of the (let's say the number we are dividing with is n) n-1 states as we can have n-1 modulo values possible)

I have checked the results for few m and m manually and they seem to be correct for them..

But why it's so?(I know that A and B will have m and n as count of states respectively for minimal DFA)


texts: How to reduce language is finite to language is regular?

texts:
I'm trying to reduce $FIN \leq REGU$, where:

$$FIN = \{ \langle M \rangle \vert T(M) < \infty \} \\ REGU  = \{\langle M \rangle \vert T(M) \in REG\}$$

Now one thing I have done so far is this:

$ w \in FIN \implies | T(M_w) < \infty \implies \exists n \in N: L(M_w) = \{w_0, \ldots, w_n \} \implies \exists  \ \text{DFA} \  A: L(A) = L(M_w)  $

What I want to show now that : "to decide if a language is regular is at least as hard as deciding wether it is finite"

Thats where I'm stuck.

I want to remark that this is not homework but, but a exam preparation question.


texts: Do all NP complete problem have polynomial verifier?

texts:
Say we want to factor a large number.

Factoring it is in NP.

Verifying it is definitely in P.

However, how do we know that there is no other factors besides the one we found?

So it seems that verifying it isn't in NP either.

Now I am getting confused with NP definition here. I know that NP includes all P.

But then there is this side definition that NP are problems with polynomial verifier.

Is there a proof that all NP problems have P verifier?

If the answer is true, yes all NP problems and hence all NP complete problems have P verifier, then please tell me the proof.


texts: What is the complexity of k-clique problem with a predetermined vertex in the solution?

texts:
Clique (from WikiPedia):

Clique is a subset of vertices of an undirected graph such that every
two distinct vertices in the clique are adjacent; that is, its induced
subgraph is complete.

K-Clique problem: Finding a clique of size K. This is NP-complete according to Wiki,

Cliques have also been studied in computer science: finding whether there is a clique of a given size in a graph (the clique problem) is NP-complete, but despite this hardness result many algorithms for finding cliques have been studied.

Let us consider a "constrained k-clique problem" - which is a k-clique problem with a constraint of having a predetermined vertex included in the solution. What would be the complexity of this problem? Is it a known problem in the literature?


texts: How to disprove that DTIME(f) = NSPACE(f)?

texts: Is there an easy way (maybe by using hierarchy theorems) to disprove that $DTIME(f) = NSPACE(f)$ for any computable $f: \mathbb{N}\rightarrow\mathbb{N}$ with $f(n)\geq n$?


texts: Divide and conquer algorithm for a gas station problem

texts:
I never heard about this variation of the gas station problem. The statement is as follows:

There is just one road connecting the n+1 cities c0, …, cn
consecutively. You want to go from c0 to cn stopping at most s times
to fill the tank of the car. There are gas stations at the cities, but
none on the roads. The length of each road is ℓ0, …, ℓn−1. Which is
the minimum range for your car? Suppose that you start with a full
tank.

This has to be done in something like nlogn, because I already tried the n^2 approach and is not good. I don't know how to decide if I should refill at some point or not.
For this inp:
5 0
100 300 500 200 400
5 1
100 300 500 200 400
5 2
100 300 500 200 400
5 3
100 300 500 200 400
5 4
100 300 500 200 400

The output should be:
1500
900
600
500
500
(Consider that the input is a sequence of n and s, followed by n naturals that represents l_i.
Source


texts: Should we not reuse constants in tableaux proofs?

texts:
I am trying to understand the proof of the following using tableaux:
$$
\exists x\forall y.r(x,y) \to \forall x \exists y . r(x,y)
$$

This is how it works out:
$$
(1) \space \exists x \forall y .r(x,y)
\\
(2) \space \lnot(\forall x \exists y . r(x,y))
\\
|
\\
(3) \space \forall y.r(a,y)
\\
(4) \space \lnot \exists y.r(b,y)
\\
(5) \space r(a,a)
\\
(6) \space r(a,b)
\\
(7) \lnot r(b,a)
\\
(8) \lnot r(b,b)
$$

I understand that (4) is derived from (2). However, shouldn't that be
$$
\lnot \exists y.r(a,y)
$$
reusing the constant a which was introduced by (3)? This is because we are expanding the quantifier:
$$
\lnot(\forall ...)
$$

Can anyone explain?


texts: Parser theory: How to systematically compute FOLLOW sets?

texts:
Forgive me for my ignorance as I am self-teaching myself some of this theory... I am having some trouble understanding how to systematically/algorithmically compute FOLLOW sets, given that I have computed the FIRST sets.

For the following grammar:

E -> TE'
E' -> +TE' | ε
T -> FT'
T' -> *FT' |  ε
F -> (E) | id

I found that the FIRST sets are:

FIRST(E) = { (, id }
FIRST(E') = { + ,  ε }
FIRST(T) = { (, id }
FIRST(T') = { *,  ε }
FIRST(F) = { (, id }

When it comes to computing the FOLLOW sets, I am trying to use the following rules:

1. $ goes into the set FOLLOW(S) where S is the start symbol.
2. If A -> aBb, then (FIRST(b) - { ε }) is in FOLLOW(B).
3. If A -> aB then everything in FOLLOW(A) is in FOLLOW(B)
4. If A -> aBb and ε is in FIRST(b), then everything in FOLLOW(A) is in FOLLOW(B).

Obviously, the step I am most certain here is that

FOLLOW(E) contains $, based on rule 1. But everything after that, I seem to have a hard time following a pattern on how to systematically compute the FOLLOW sets. For example, to compute FOLLOW(E), how are we supposed to approach this?

E -> TE', looks like A -> aB , so everything in FOLLOW(E) is in FOLLOW(E'). Where to go from here? Do I compute FOLLOW(E')? Then going to FOLLOW(E'):

E' -> + TE'... looks  like A -> aBb. Then that means FIRST(E') - {  ε } is in FOLLOW(T). So I do know that { + } is in FOLLOW(T).

As you can see, with the way I have interpreted this, I am going around all over the place computing the FOLLOW of another production. Ultimately, I end up losing track on what terminal symbols go into which follow set. :(

I am for sure misunderstanding something here.

What is the right approach/ordering to compute the FOLLOW sets?


texts: Time complexity of min() and max() on a list of constant size?

texts: If you use min() or max() on a constant sized list, even in a loop, is the time complexity O(1)?


texts: want to know concept behing Multilevel paging

texts:
In order to use large size page table hierarchical paging is done .
In case of two level page table scheme . for :
logical address space - 32bit - $2^32$
page size - 4kb i.e $2^12$

It is mentioned that page number is divided evenly :

i.e page number p1 - 10 bits
    page number p2 - 10 bits
    page offset d - 12bits.

I got this...... but my question is different. I didn't get the concept behind it.
What I thought for that I will take 1 example.

Take the address 0x00FF1234. The binary representation of this address is 00000000111111110001001000110100. By splitting this up, we get 0000000011 1111110001 001000110100, or 0x3 0x3F1 0x234.

0000000011 this number  is pointing to 4th entry in the 1st level table. Means there are
 0000000000 to 1111111111 unique numbers ( entries ) in the 1st level table. These gives the address of the 2nd level table.
 In this we are referring 0000000011 entry. Now does this entry contain some address which points to the base of the 2nd level table ? Now we are being pointed to 1111110001 address means 0000000011 containing 1111110001  address ( I am thinking ) if yes then why only that address ? why not other address ?
Means here I want to ask what exactly happens behind this jumping. And how ? I read somewhere here about CR3 register and all that but didn't get anything. I don't want that much deep. I just want to solve basic example of paging , TLB , virtual memory for GATE exam.
And what is this page size ( I always consider it as d as offset and solving problem )
For example : Page size is 1024 byte ... means d = 10 bytes. Does it mean , it ranges between 000....( 10 times) to 111....( 10 times) ? Not getting this concept properly.


texts:
I am looking for an algorithm (or hint where to start), for Toads and Frogs Game. What I am interested in is not how to solve the problem (it's NP-hard), but how to plan one player's moves. I.e. how to design a computer player (AI), which could win against another player (another program or human player). I was looking for some clues but with no luck so far, there's not much about it on the Web.

Link to game description on Wikipedia.

And here you can play the game. Please bear in mind, that starting positions may not be that straightforward. They may be mixed up from the very start.


texts: What are the current state of art approximation algorithm for NP-Hard problems?

texts:
I came cross some works try to use deep learning to approximate NP-Hard

https://arxiv.org/pdf/1810.10659.pdf

Though the paper seems to have very good results but based on the citations. I'm quit doubt if it really the state of art approximation for NP-hard problem.

I'm wondering what are some state of art NP-Hard approximation algorithms for each problems ?


texts: Is $\{u\#v \mid u\not=v\}$ context-free?

texts:
Is the following language context-free?

$$
\{u\#v\in\Sigma^* \mid u\not=v \text{ and } u,v\in\{0,1\}^*\}
$$

You can assume $\{0,1,\#\}\subseteq\Sigma$.

Unnecessary background information: I am grading papers, and a student cited that this language is context-free to state that it is decidable. My intuition says that the language is not context free, but if someone could confirm this for me or even point me to a proof, that would be fantastic.


texts: Heap-like notation of a BST (BFT bit-vectors) for succinct representation

texts:
I'm researching the topic of succinct tree representations right now and came across this presentation. On slide 17 there is an example of heap-like notation of a BST (using BFT bit-vectors) and the author claims that the amount of bits needed to represent a tree of $n$ elements (without their values) is exactly $2n+1$.

According to my calculations, it's $2n-1$. Here they are:

As in this representation every BST is represented as a complete tree, for the complete tree of height $k$ it has $2^{k+1}-1$ nodes.
On average for $n$ nodes tree has a height of $log_2n$.
Replacing the $k$ from the first list item with the average BST height from the second list item I received:

$$2^{log_2n+1}-1=2n-1$$

What am I missing in my calculations? Where do these 2 extra bits come from?

Thanks in advance for your answer!


texts: State-of-the-Art techniques on dynamic shortest path computations

texts:
Suppose that I would like to find the shortest path between two vertices in a dynamic graph, where the cost function of an edge changes occasionally. I understand that an efficient algorithm to target this problem must have efficient ways to handle the "cost updates" and the shortest path queries.

Does anyone know what is the state-of-the-art method proposed for this problem? And how is the performance like? If you could provide me with a reference as a starting point for my research on this topic, it would be greatly appreciated.

The weights of the graph do not change while a shortest path computation is carrying on. It is safely to assume that the cost updates of edges happen periodically, like every 15 minutes.


texts: What is the practical limit to how many object classes you can detect with Faster RCNN?

texts:
I am trying to follow this tutorial where the Faster-RCNN-Inception-V2-COCO model from TensorFlow's model zoo is used to detect playing cards. I was wondering what is the practical limit to the number of object classes that I could use this to detect, specifically what I would want to do is to detect every letter in the English language(distinguish capital and lowercase from each other), number and mathematical symbol. Would this model work with that many different classes?

Also If I want to detect some words, would it make sense to label all characters that make up a word and also label the word(assuming there are only a few important words I want to actually detect).


texts: Let $L_1$ be a DCFL and $L_2$ be recursive language. Is $L_1 \cap L_2$ a DCFL?

texts:
Let $L_1$ be a DCFL and $L_2$ be recursive language. Is $L_1\cap L_2$ a DCFL?

According to me the intersection should be a Recursive language. However the answer given is DCFL. Can anyone confirm?


texts: How are Complex Numbers and Complex Analysis used in CS?

texts:
The world is 3D and data of it is usually (as far as I know) represented and processed with real numbers. I've seen very few cases where complex numbers are used in programming and none when it comes to processing anything that doesn't explicitly require complex numbers.

How are complex numbers used it Computer Science and Programming? Which areas in CS/IT use it?


texts:
Let $M$ be an $m\times n$ matrix with all elements in $\{1,0\}$, $m >> n$. Let $\mathbf{v}_0, \ldots, \mathbf{v}_n$ be the columns of $M$.

I want to find all sets of columns $S = \{\mathbf{v}_{i_1}, \ldots, \mathbf{v}_{i_k}\}$ so that for every row there is at least one column $\mathbf{v}_{i_j}, \ldots, \mathbf{v}_{i_k}$ that has a $1$ in that row, with the constraint that $S$ is minimal in the sense that deleting any element of $S$ means $S$ no longer meets these requirements.

Without the minimalness constraint, this is a trivial instance of (monotone) SAT - define a variable corresponding to each column of $M$, and just read the CNF clauses from the rows of $M$.

How can I approach the problem as described? I tried encoding the minimalness requirement as additional boolean constraints (which would make the problem regular SAT and I could use a SAT solver), but this gives $n^m$ additional clauses in CNF form, which is intractably large.


texts: Table-Driven Lexer and the Classification Table

texts:
I'm trying to implement a compiler for a custom language as part of an assignment.
I am still trying to figure out how to build the lexer. From what I understand, for a table-driven lexer, we have 3 tables:

Classification Table
Transition Table
Token Type Table

My problem is mainly coming from the fact that the only example I've seen of the concept of a table-driven lexer is the "famous" (because I see it in every University's online notes) Cooper & Torczon DFA for reading digits. Page 25
From what I gather, the purpose of each of these is as follows:

1: To classify the atomic parts of the language, such as digits (0,1,2,3....) and letters (a,b,c,...)
2: To define what should happen next according to what's just been classified (If digit, go to state X, if letter, go to state Y)
3: Apparently this is used to check whether or not the string is accepted. Honestly I don't even know what the point of this is.

The grammar I'm trying to build a compiler for is much more complicated than the examples I've seen online. It contains more "atomic" symbols, such as operators (*,+,-,/,>, etc..) and reserved keywords (if, for, while, etc...)
By atomic, I mean symbols that stand on their own. (I.e. if is a symbol in its own right, not i and f)
This poses a problem for me, since I won't be able to know if I'm reading if or a string of the form aifb
Here's what I'm currently trying to do:

First, I'm building a CAT (classifier table) for all the atomic symbols of the language. I don't know if this is the right thing to do, especially when I have 52 letters (English alphabet), 10 digits and reserved words.
I will then merge all the CATs together. So I will have one big CAT that covers letters, digits, and reserved words.
Then, I will build a (big) transition table, so that when I read a character and determine its classification (problem: What about reserved words that take more than 1 character?) I will know where to transition to next.
These tables are used by a simple DFA class which, once the lexeme is read, will spit out a token.

The assignment specifies that I have to use a table-driven lexer.


texts:
I'm trying to figure out if there is a proper or commonly accepted name for this particular function (f).

float clamp(float min, float max, float v)
{
    if (v < min) return min;
    else if (v > max) return max;
    else return v;
}

float f(float min, float max, float v)
{
    float t = (v - min) / (max - min);

    return clamp(0.0, 1.0, t);
}


texts: Are two-level schedulers only useful to manage swapping?

texts:
Two-level scheduling is useful when a system is running more processes than fit in RAM: a lower-level scheduler switches between resident processes, and a higher-level scheduler swaps groups of processes in and out.

I find no other mention of two-level scheduling in Andrew Tanenbaum's Operating Systems: Design and Implementation, 1st ed. Exercise 2.22 asks why two-level scheduling might be used; I don't know whether it's there as a reading comprehension check or there are other reasons not prominently mentioned in the text.

Is two-level scheduling useful to manage other resource contentions, besides memory?


texts: What is the difference between deterministic and confluent?

texts:
I understand deterministic as a function for some input will always give the same output, and these inputs and outputs can be sets of values represent by a predicate.
I understand confluent as convergence of a rewriting system, ie the rewritten terms always converge to some term, which could also represent a predicate.
It seems like these definitions are very similar in what they achieve.
Would all deterministic systems be confluent and vice versa?
Or is determinism really about the paths taken and exact timmings of computations to reach an answer, ie a deterministic algorithm must always have the same trace of paths for every run?
Also there is a notion of choice in non-deterministic algorithms, how does this fit in?
I feel like these definitions should work across sequential and concurrent systems, but for concurrent systems the exact timings are less important as the scheduler controls this.


texts:
I am coding in Matlab:

m = [40 50 60]; X=[];        % [] makes an empty matrix
for j=1:3
    for i=1:3
        x=zeros(m(i),1);     % a vector of m(i) zeros
        X=[X;x];             % store x under the old previous ones
    end
end

and would like to run the code in parallel. Is there a way to calculate from which index to which index in X I will be in a given loop storing in please?


texts: Is the image of a total, non-decreasing function decidable?

texts:
This is an exercise I've been struggling with for a while:

  Let $g : \mathbb{N} \to \mathbb{N}$ be a total, non-decreasing function, i.e. $\forall x > y.\ g(x) \geq g(y)$. Is the image $I_g$ of $g$ a recursive set?

Intuitively, I know that the image $I_{g}$ is not recursive, as $g$ is not strictly monotonic. In fact, it's because that $g$ is not strictly monotonic that $g$ could be a constant function so testing if $y \in I_{g}$  may not finish as it could be that $\forall x, g(x) = c$, $c$ being a constant s.t. $c < y$. Then, testing if there is an $x$ s.t. $g(x) = y$ incrementing $x$ as the $g(x) < y$ may go forever.  On the other hand, it could be that after a while, (for a sufficiently greater $x$) it happens that $g(x) > c$ and $g(x) = y$. If it were stricly monotonic, though, then it would be recursive as I would be able to test if $y = g(x)$ incrementing $x$ until the equality is satisfied or $g(x) > y$ (then $g(x)$ wouldn't get stuck in the same value because $x_1 > x_2$ implies $g(x_1) > g(x_2)$).

However, I haven't been able to prove this formally. Can this intuition become part of a formal proof? Or at least could you give me some help in proving it in some other way? A hint or some outline of a proof would be great.


texts: Proof for Turing Machines being able to simulate any algorithm in the same time complexity

texts:
I have always read that Turing machines can simulate any algorithm, without changing the time complexity of the algorithm, and hence it is easier to study the Turing machine equivalent of the algorithm while doing proofs.

However, I am unable to find a proof for this statement. Is there a formal proof of why the Turing Machine model should be able to simulate any algorithm within the same time complexity?


texts: Is $L=\{a^ib^jc^k : i\leq j\leq k\}$ context-free?

texts:
I have an exam and in preparation I found this language. We are supposed to determine where in Chomsky hierarchy it stands. The language is $L=\{a^ib^jc^k : i\leq j\leq k\}$. I can easily build a linear turing machine, that would delete a, b and c for each a and then b and c for each b and if the only thing left, will be c, then the word belongs to the language. So I know the language is context-sensitive. What I can't figure out is if the language is context-free.

I tried to build a pushdown automata but I couldn't find any. I also tried to use the pumping lemma but wasn't able to find a good word to prove it's not context-free.
Could you help me?


texts: Is "lazy evaluation" part of the compilation process or a run-time feature?

texts:
I'm studing the Clean functional programming language, and like other functional PL it uses Lazy Evaluation.

The thing that I can't get is when a PL that using that kind of evaluation evaluates the needed parameters.
Does the compiler recognize which parameters are used and generate the code for evaluating them? or maybe some run-time mechanism takes responsibility to evaluate the parameters?

My question is about the concept of Lazy Evaluation in general, not just about this particular language.

Thanks in advance!


texts:
I'm looking for an appropriate technique to search for clusters. My underlying data is 70,000 respondents to about 2500 multiple choice questions. Most respondents have not answered most questions. I have no expectations as to how many clusters I might expect or how clustered this data might be but am interested to explore if there are personality types wrt. to the kinds of questions asked, and if so, how well defined they are.

My thinking is that the best approach might be to transform the data into a graph and run a cluster analysis on that. Each node is a respondent and each edge is a distance between '0' or '1' derived from how similarly the respondents answered whatever questions they both responded to (or no connection at all, if they answered very few common questions) but I'm struggling to identify an appropriate algorithm for this situation.

Note: it seems likely that this graph setup will violate the principle of triangularity ie. there is no reason to suppose that $ dist(i, \ j) \leq dist(j, \ k) + dist(k, \ i) $ will always hold.


texts: What is the instruction format for an accumulator machine?

texts:
I need to learn about accumulator machines, but there is next to nothing written about them. Computer architecture channels seem to be flooded with general-purpose register ISAs (like MIPS, x86, etc).

I know that accumulator machines only have one register (called the Accumulator Register) that is implicit and not specified in any of the operations. In general, an instruction for an accumulator architecture is supposed to look something like: add memaddress.

However, I need to get more specfic. I need to know exactly how many bits are in the various instruction fields (i.e. opcode) for an instruction of an accumulator machine.

I have the following accumulator machine:

$2^{24}$ words of memory (words are 32-bits wide)
Fixed format instruction (but how many bits??)
A 32-bit accumulator register
An index register X
Index addressing mode: address field + X when indexing is indicated in the instruction
Capable of performing a total of 128 operations

The last bullet tells me that the opcode of an instruction would be 7 bits since $2^{7}=128$.

What would the instruction format be for a load/store instruction vs. an arithmetic instruction like add? It would help greatly if I knew how many bits the fixed format instruction should be.


texts: Normal form after decomposition of a relation

texts:
I came across a text recently which claims that if we perform a lossless decomposition of a relation R into smaller relations R1 and R2, and if R is in 3NF, both R1 and R2 are 3NF.

I felt a bit suspicious regarding this claim, but couldn't find anything to prove this statement wrong.

Am I correct in thinking that this statement doesn't hold all the time, or Am I wrong? It would be really helpful if someone can correct me if I am wrong?

Thanks in advance!


texts: Check if a given polynomial is primitive

texts:
I try to estimate error detection capabilities of arbitrary CRC polynomials. One important criteria is if a given polynomial is primitive. So I need an algorithm to check that. My goal is to write a C or C++ routine.

Unfortunately I only found analytical solutions for the problem on the web.

Is there some numerical algorithm for testing a given polynomial for primitivity?

Please consider that my mathematical knowledge wasted away during the last two decades. Any algorithm descriptions, pseudo code or code in a common programming language would be very helpful.


texts:
I have an assignment in my university where I have to implement Uniform Cost Search and A* Search.

We have an input which includes a map and queries.

The map is weighted, directed graph, represented by an adjacency matrix. The queries include Uniform Cost Search and A* Search queries (Ex: Uniform(or A*) + initial location + goal location)

I cannot use heuristic functions based on physical distance because we have no knowledge and extra information about this graph except distances between vertices.

Is there any way to find a heuristic function in this case ?

(Is it possible to use prior results from Uniform Cost Search in the queries to extract information from the graph?)


texts: Arrange objects in space so that the outline takes the least surface/volume

texts:
Imagine you have a number of 2-dimensional objects. The question is how to fit them all in a rectangular space in such a way that this rectangle takes the smallest area possible.

On the below image you can see (more or less) what I mean:

The objects are packed quite efficiently (there is little empty space).

What I am after eventually is doing the same in 3D, but 2D is easier to start with. Of course all translate/rotate operations can be applied to those objects.

My quick research online did not bring any meaningful answers, but my first thought was to find longest edges of given objects and to position them along these edges to minimize space. Do you have any other ideas on how to approach this? Or maybe there already are some papers concerning this problem?


texts: Comparing A* search to Simulated Annealing

texts:
Good Afternoon,

I am comparing A* search to Simulated Annealing for an assignment, mainly the algorithms, memory complexity, choice of next actions, and optimality. Now, I am not 100% sure about my answer, and was wondering if someone could give me some input.

A*: Optimal, finds path of shortest distance to goal state based on heuristic.

SA: Complete, stochastic, randomly selects next state and either rejects/accepts based on change in energy state. If it is a bad move (less energy than previous state) then it either accepts/rejects based on probability.

Now, I understand that A* requires bookkeeping in order to track the path from goal state to start state. This is why I think that the memory requirements would be linear, where there are n nodes in the path from start to finish.

On the other hand SA doesn't require bookkeeping, since it's trying to find the state with the maximum "energy". Could someone explain exactly what "energy" would mean? Also, I am confused about comparing the functions of these two algorithms. A* is good at finding the path to a goal state (which is already known) with the lowest cost, whereas SA only finds a state that is most desirable. what is the point of comparing A* to SA when they seem to have two different purposes?


texts: Does there always exist equivalent (M)(I)LPs with and without objective functions?

texts:
For computing pure Nash equilibria (game theory), there exists a MILP method in literature (clicky).

In the proposed MILP, there is no objective function. A solution is a pure Nash equilibrium if it is a feasible solution of the MILP.

Should there, in theory, exist an equivalent MILP with an objective function so that a solution is a pure Nash equilibrium if the objective function is minimized/maximized (e.g. equal to 0). Such MILP would be useful in this context as to still have an approximation if there exists no feasible solution in the first 'objective function-less' MILP (i.e. there exists no pure Nash equilibrium).

I gave context to the question but the question is general: for a (M)(I)LP without an objective function, is there always a reduction from and to a (equivalent) (M)(I)LP with an objective function? Can such reduction be done in polynomial time?


texts: What should be the way to design code for such a situation?

texts:
I have a graph as given below:

Let us assume one node as transmitter and another as receiver.

We need to transfer particles in every time slot constrained by maximum particles N and minimum 0. The combination of which particle in which time slot makes a code. I mean if 2 1 0 0 is a code that means that 2 particles in slot zero 1 in slot 1 and 0 particles in slot 2 and 3
Now let us suppose that any particle in a time slot can take any path and suffer through at most K delays. Delays are given by number of dots. More dots more delay. The delay to particles can be assigned randomly. The maximum delay for this graph is 4 it can be generalized to K.
How to design codes so that information is reliably transferred across transmitter and receiver.

I just want to know how these codes are constructed, assuming that other codes must exists to be revealed. Also please tell me the prerequisites I need for such problem as I am not a computer engineer. One way is given in here


texts:
Algorithm to distribute elements evenly among a population

In the software I am doing I have three different categories:

Maize:
    1- Variety A
    2- Variety B
    3- Variety C
    4- Variety D
    5- Variety E
    6- Variety F
    7- Variety G
Fertilizer:
    1- Type A
    2- Type B
    3- Type C
    4- Type D
Management
    1- Form A
    2- Form B
    3- Form C
    4- Form D
    5- Form E

With this categories I need to produce combinations of Maize+Fertilizer+Management. So I get 140 combinations. I need to distribute the 140 combinations into 200 recipients randomly (some will repeat of course) but balanced (to avoid to many of one type of combination)

I saw this post but I might have a different case.

Is there an algorithm to do this?


texts:
I have two questions about how to use pumping lemma for regular languages to show that two languages are not regular. I would appreciate if someone can confirm if my answers make sense, and if not, what needs to be done

1) Prove that the following languages aren't regular. You can use the pumping lemma and the closing of the class of the regular languages under union, intersection and complement.

a) $L_1 = \{w \in \{0,1\}^* \mid w  \text{ is not a palindrome}\}$

My solution: Pick up w as the string $010010$. $x = \varepsilon$, $y = 01$ and $z = 0010$. By the pumping lemma the string $xyyz$ should also be regular. However $xyyz = 01010010$ which is not a palindrome. So, by contradiction, $L_1$ is not a regular language.

b) $L_2 = \{ wtw \mid w,t \in \{0,1\}^* \}$

My solution. Pick up w as the string $0101$ and pick up $t=011$ as the other string. So $wtw= 0101\ 011\ 0101$ which belongs to $\{0,1\}$. By the pumping lemma, the string $xyyz$ should also be regular. However, choosing $y=110$ of $010\ 0|11\ 0|0101$, the string $0101\ 011\ 110\ 0101$ is produced which cannot be generated by $wtw$. So, by contradiction, $L_2$ is not a regular language.

Many thanks to any help.


texts: Functions are relations but all relations may not be functions.Can there be an algorithm for a relation which is not a function?What has theory of computation got to say about relations in general.


texts: Dijkstra’s in a graph with negation of edges

texts: Let say I have a directed graph G with positive edges and I create a new graph, G', by replacing the weight of each edge by the negation of its weight in G. If for a given source vertex s, I compute all shortest path from s in G' using Dijkstra’s algorithm. Will the resulting paths in G’ be the longest (i.e., highest cost) simple paths from s in G. True or false? And please, justify.


texts:
Let $v$ be a vector of positive integers of length $n$. I want to find the highest $k$ such as there are at least $k$ elements of $v$ that are greater or equal to $k$.

What would be the best algorithm for finding $k$?

Examples:

$v = (1, 2, 3, \ldots, 100) \rightarrow k = 50$, because there are at least 50 elements that are greater or equal to 50 (there are even 51 of those, fifty through a hundred, but that doesn’t matter); but there are only 50 (so—less than 51) elements greater or equal to 51.
$v = (100, 101, 102, 103, 104) \rightarrow k = 5$, because all five elements are greater or equal to five, and there cannot possibly be six elements greater or equal to six.
$v = (1, 1, 1, 100, 100, 100) \rightarrow k = 3$

Any ideas how to approach this?

My initial idea is this:

Sort the vector in descending order in $O(n \log n)$
Starting with the median (it seems, intuitively, as a good place to start), check if a number on a set position $i$ is greater or equal than $i$—since everything to the left of it is greater to equal to it (the vector is sorted), we know there are at least that many elements that are greater or equal to $v[i]$.
Go right or left accordingly to what was found—if we found that there are not enough values greater to $v[i]$, let’s try with the smaller-or-equal number, $v[i+1]$. If it was big enough, go the opposite direction, checking $v[i-1]$.
Our work is done when there is some $i_m$ for which the requirement holds, but it doesn’t hold for $i_{m} + 1$. That would require at most $O(n)$ checks.
Thus, the slowest part is the sort itself, making the algorithm $O(n \log n)$ total.

I’m curious if this is the best we can do, or can we possibly make it even faster.


texts:
Introduction

I've been developing interest in complexity classes and thought I was unable to prove my problem is NP hard, so I wanted to see if it was P-hard. I wanted to see if my puzzle solving is special.  I have linked a previous question of mine to help clarify what is mentioned below.  Explained here

Random Instance of 2-SAT used for attempt reduction

  I took an instance of my problem X

  Let's say my problem X is determining if a puzzle is valid for my language

  (a∨¬b)∧(¬a∨b)∧(¬a∨¬b)∧(a∨¬c)

  Instance of X

  a = shift(L) puzzle

  ¬ a = invalid puzzle

  ¬b =  invalid puzzle

  b = shift(L) puzzle

Reduction into Shorter Instance

  (a∨¬b)∧(¬a∨b)

This boolean expression is only checking for 2-sat. Being True  (valid puzzle) or False (invalid puzzle).

My idea is that a deterministic machine will consider n^2 x n^2 puzzles as invalid if the lower right-hand box is not filled. My puzzles are solved in quadratic time when provided a puzzle with this n x n box. Any other puzzle will simply fail to be solved if it does not follow my language. I have used an algorithm that can determine in poly-time that those failed puzzles are invalid puzzles. Because, the solver will not know it as an invalid puzzle. So it will try to map it out in my language thus giving an invalid puzzle.

Question

I have the algorithm and proven that it works in poly-time, the problem is that I only know how to prove it by showing the algorithm. I just don't know how to write it out mathematically. How would I properly do this?


texts: Segmenting an English string with no spaces using dynamic programming

texts:
Suppose you have a function quality(x) that returns the quality of a sequence of letters x. Given a string such as "howareyoutoday," what is the most efficient way to determine that the segmentation is "how are you today" (i.e. quality(how)+quality(are)+quality(you)+quality(today) is the maximum quality possible)?

I was thinking that we could have something like the following:

A[0] = h, A[1] = o, ..., A[n] = y
Q[0] = quality(A[0]), Q[1] = quality(A[0]A[1]), ..., Q[n] = quality(A[0]...A[n])

Now to determine the segmentation, we find max{Q[0], .., Q[n]} which will return some Q[i] (the first space is after this). Then, we find max{Q[i+1], .. Q[n]} which returns another Q[i] (second space is after this), etc. until max returns Q[n].

I have some questions though: is this method even correct, and does it use dynamic programming? It seems to me that it does, since we build the initial Q with subproblems to the original problem. Also, is this an optimal solution? To my understanding, the worst case would be O(n^2), which would be when max returns Q[0], then Q[1], then Q[2], etc.


texts: Finding the maximum of a bitonic sequence

texts:
Given to us is an array $B[1],\ldots,B[n]$ as input, which satisfies the following property: there exists a special index $i^* ∈ \{1, \dots , n\}$ such that $$B[1] < B[2] < \dots < B[i^*− 1] < B[i^*] > B[i^* + 1] > B[i^* + 2] > \dots > B[n].$$

It is noted that the index $i^*$ is not given as part of the input.

The question asks me to design an algorithm for computing the index $i^*$, whilst trying to ensure it has the smallest running time possible.

I just wondered if anyone could produce this algorithm and explain your thought process on how you came up with it if possible? Stuck on these type of questions


texts: Solve SUBSET SUM for Reciprocals of Primes

texts:
Let $p_1, ..., p_n$ distinct prime numbers with $P = \prod_{i=1}^{n}{p_i}$ and $A=(a_1, ..., a_n)$ with $a_i = P/p_i$.

Problem

Show the SUBSET SUM problem $(A, \alpha)$ can be solved in polynomial (not pseudo-polynomial) time for every $\alpha \in \mathbb{N}$ and $P, p_1, ... , p_n$ unknown.

First attempts

$P$ and $ p_1, ... p_n$ can be calculated with $P = \sqrt[n-1]{\prod_{i=1}^{n}{a_i}}$ and $p_i = P / a_i$.

Now we can write the problem as $\alpha/P = 1/p_{i_1} + ... + 1/p_{i_n}$


texts:
A boolean algebra expression can be converted into an idempotent algebra using
$$\bar a \equiv 1-a, \qquad a \vee b \equiv a+b -ab, \qquad a \wedge b \equiv a \otimes b$$

where $\otimes$ is the idempotent product (no powers).  For example, $$(a+b)\otimes(a-b) = a -ab +ab - b = a-b.$$

The CNF formula

$$\phi = (a\vee b) \; (b \vee c)(b \vee \bar c)(\bar b \vee   \bar c) \; (a \vee c)(\bar a \vee \bar c)$$

can be converted into what I would call the idempotent expression
$$\phi = (a + b - ab)\otimes (b-bc) \otimes (a+c-2ac).$$

This expression expands to give $\phi = ab - abc$.  I would like an algorithm that, given a CNF formula as input, outputs the term with the lowest homogeneity.  In this example, the oracle would return $ab$.  (If there are multiple terms all with minimal homogeneity, the algorithm can return any one of them.)

Question 1: What is the complexity of this task?  How high in the polynomial hierarchy is it?

Secondly, given a different idempotent expression $$\phi = ac+ad+bc+bd-abc-abd-2acd-2bcd + 2abcd,$$

I am interested in summing over the terms with equal homogeneity. By letting all variables be $\epsilon$ we get
$$\phi = 4\epsilon ^2 - 6\epsilon^3 + 2\epsilon^4.$$
This yields a homogeneity vector of $[0,0,4,-6,2]$.

Question 2: What is the complexity of computing the homogeneity vector, given an idempotent expression as input?   How high in the polynomial hierarchy is it?


texts: Reducing Independent Set to a problem to prove that it is NP complete

texts:
Given:

A set of available customers $c_1, c_2, \dots, c_n$.
A set of available foods $f_1, f_2, \dots, f_m$.
Each customer will choose a subset of the available food.

Problem:

Find the maximum number of customers that can be chosen, such that no two customers share the same food.

Question:

How to reduce the independent set problem to this problem, in order to prove that this is an NP-Complete problem ?


texts:
I have benn wondering about the following possibility: if I have multiple hardware threads on the same
core, and then someone decides to use shared register to allow fast synchronization among threads that run on the CPU, and implements test-and-set on the register instead of doing it in main memory.
Will this work? and if it works, why?


texts: Scheduling algorithm to minimize the number of late jobs

texts:
There are $n$ (non-recurring) jobs where each job $i$ has an arrival time $a_i$ and a duration $t_i$. All the jobs share a deadline length $d$ (deadline for each job is $a_i + d$). The problem is to find a (non-preemptive) scheduling time $s_i$ for each job on a single processor/machine such that the total number of missed deadlines is minimized (or maximize the number of on-time jobs).

So, even in cases where not all deadlines can be met, we want to find out the schedule that meets the maximum number of deadlines. Does this problem even have a polynomial solution? I tried a dynamic programming approach, but I can't really identify the subproblems.

For example, given this set of jobs (where each job is described by $(a_i, t_i)$): [(0, 50), (5, 20), (25, 40)] where $d = 60$, the best we can do is to meet 2/3 deadlines with a schedule like this: [(5,20), (25, 40), (65, 50)].


texts:
Given recurrence:

  $T(n) = T(n^{\frac{1}{a}}) + 1$ where $a,b = \omega(1)$ and $T(b) = 1$

The way I solved is like this (using change of variables method, as mentioned in CLRS):

Let $n = 2^k$

$T(2^k) = T(2^{\frac{k}{a}}) + 1$

Put $S(k) = T(2^k)$ which gives $S(\frac{k}{a}) = T(2^{\frac{k}{a}})$

$S(k) = S(\frac{k}{a}) + 1$

Now applying Master's Theorem,

$S(k) = \Theta(log_2(k))$

$T(2^k) = \Theta(log_2(k))$

$T(n) = \Theta(log_2log_2(n))$

I believe my method is incorrect because $a = \omega(1)$ doesn't necessarily mean that $a$ is a constant (or is it ?) and hence Master's Theorem is not applicable. Following the same line of reasoning, this also means that $b$ may not be a constant, but that would make "$T(b) = 1$" condition meaningless. Can anyone help clear out my misconceptions (if any) ?

Thanks


texts: Minimal number of resources such that the system is considered safe?

texts:
In a system with a single type of resource, there are 8 processes with the following maximal requirements:

Process
P1
P2
P3
P4
P5
P6
P7
P8

MAX
75
60
65
35
30
45
30
30

Specify the minimal value for the total number of available resources, so that the state of the system is considered safe, in the scenario where the initial allocation of resources is

Process
P1
P2
P3
P4
P5
P6
P7
P8

Allocation
12
5
10
5
5
0
0
10

I understand that the minimum number of resources should be computed by the following formula:
$$R \ge P \cdot (N-1) + 1$$
meaning that we would have:
\begin{align}
    R &\ge 8 \cdot (74+59+64+34+29+44+29+29) + 1 \\
    R &\ge 8 \cdot 362 + 1 \\
    R &\ge 2897
\end{align}
However, this does not seem right. The number seems too big and I don't see the purpose of the initial allocation in this exercise.
Am I doing something wrong? Am I using the wrong formula?
Please help me understand how to solve this kind of problems.


texts: which of the following languages are Recursively Enumerable?

texts:
Which of the following languages are recursively enumerable?

A={⟨M⟩∣ TM M accepts at most 2 distinct inputs}

B={⟨M⟩∣ TM M accepts more than 2 distinct inputs}

For first language I think that we can enumerate all the TM's which accept at most 2 distinct inputs using dovetailing method and same is the case with B language.

But on the contrary, both languages are complement of each other so if one is R.E then other one cannot be. So I know that I am going wrong somewhere.

Can someone please explain me how to find if these languages are R.E ?


texts: Counting triplets from three arrays satisfying the equation x^2 = yz

texts:
Let's say I have three arrays of positive integers X, Y and Z. You can assume that each of the arrays have atmost $N$ elements. All the arrays contain unique elements.

You're allowed to form a triplet of integers $(x,y,z)$ such that $x$, $y$ and $z$ are elements from arrays X, Y and Z respectively.

I want to count the number of such triplets satisfying the equation $x^2 = yz$. I can only think of an $O(N^2)$ solution using simple hashing. I was wondering if there exists a better solution with a time complexity of $O(N \lg N)$ at least, if not $O(N)$.


texts: Computer Architecture: How does the parallel prefix adder speed up carry generation?

texts:
I am confused by how the parallel prefix adder (the one described in this presentation: https://users.encs.concordia.ca/~asim/COEN_6501/Lecture_Notes/Parallel%20prefix%20adders%20presentation.pdf) speeds up carry generation (specifically the Ladner-Fischner adder architecture). I understand how carry generation in a non-parallel CLA (carry-look ahead) adder works—carry bits are computed using just the initial carry bit ($C_0$) and propagators and generators:
$C_{i} = G_{i - 1} + P_{i - 1}G_{i - 2} + P_{i - 1}P_{i - 2}G_{i - 3} + … + P_{3}P_{2}P_{1}P_{0}C_{0}$
But how exactly are carry bits computed in a parallel fashion for a parallel adder? I am having trouble with the grouping. I know that in a typical arithmetic expression like the one below:
$a + b + c + d$
We can group in the parallel fashion:
$(a + b) + (c + d)$
But how are the terms in the $C_i$ formula grouped? Especially since the first step of the adder is to generate all the individual $P_{i}$ and $G_{i}$ units but the terms in the $C_i$ have a lot of $P_{i}$ and $G_{i}$ combined together.


texts: Construction of NPDA with inequality check

texts:
I'm currently struggling to construct a nondeterministic PDA with an amount of states in $O(n)$ that accepts the following language:
$L = \{wcx \, | \, w,x \in \{a,b\}^n \land w \not= x\}$ with c being a delimiter.

In lectures we discussed DPDA that accept $wcw^R$ or NPDA that guess  the middle of the word with an $\varepsilon$-transtion and accept $ww^R$.

My idea has been to save $w$ in the stack but then I can't really assure the inequality of $w$ and $x$ then.


texts: When is the concatenation of two regular languages unambiguous?

texts:
Given languages $A$ and $B$, let's say that their concatenation $AB$ is unambiguous if for all words $w \in AB$, there is exactly one decomposition $w = ab$ with $a \in A$ and $b \in B$, and ambiguous otherwise. (I don't know if there's an established term for this property—hard thing to search for!) As a trivial example, the concatenation of $\{\varepsilon, \mathrm{a}\}$ with itself is ambiguous ($w = \mathrm{a} = \varepsilon \mathrm{a} = \mathrm{a} \varepsilon$), but the concatenation of $\{\mathrm{a}\}$ with itself is unambiguous.

Is there an algorithm for deciding whether the concatenation of two regular languages is unambiguous?


texts:
for(i = 0; i<n; i++) {
    for(j = 1; j<i*i; j++) {
        if(j % i == 0) {
            for(k = 0; k<j; k++) {
                //statement;
            }
        }
    }
}

Here, it's been asked to find the time complexity. I think it's O(n^4), but prof. said it's wrong. Can someone explain how this works ?


texts: How many roots are there in an undirected root

texts: Given an undirected tree with 7 nodes how many roots would this tree have. My intuition tells me that because the tree is undirected it would either be 7 or 0. How would I solve this?


texts: Algorithm to decide whether two vertices are ancestors/descendants of each other

texts:
Is there an algorithm that performs the following:

Input: A directed graph and two vertices within that graph
Output: Whether one of the two vertices is the ancestor of the other

For example, in this graph:

A is an ancestor of D. B is neither the ancestor nor the descendant of C.

The best I can think of doing is performing a DFS/BFS from each of the two input vertices and seeing if either search includes the other vertex. This takes O(|V| + |E|) time. Is there a well-known, faster algorithm?


texts: Matching Algorithm - How to maximize matched quantity with unique matching rules?

texts:
Given a set $S=\{A,B,\cdots,H\}$. Elements in $S$ can be matched according to the following rules:

$$\begin{aligned}
A\leftrightarrow B\\
C\leftrightarrow D\\
B+C\leftrightarrow F\\
D+A\leftrightarrow E\\
G+H\leftrightarrow B\\
\end{aligned}$$

The input to the matching algorithm is an array of variable size consisting of elements in $S$. Each item in the array has a particular size or "quantity" that can be matched (I imagine this can simply be modeled as edge weights).

For notational clarity -

$A \leftrightarrow B$ indicates "If an item exists in the input array of type A, it may match with an item of type B". The reverse is also true, so if there is $B$ it may match with $A$.

$B+C\leftrightarrow F$ indicates "If an item exists in the input array of type $B$, and another of type $C$, they may together match with an item of type $F$", the reverse is also true, so if there is $F$ and $C$, they may together match with $B$. $F$ by itself may not match with either $B$ or $C$.

The first question is, how to maximize the total quantity matched?

Second question is, how to optimize time complexity? If the algorithm is NP, please provide some proof or reason as to why it cannot be solved in P.

Intuitively, I think the problem could be modeled as a weighted bipartite graph and solved with a max-flow algorithm or dynamic programing. Once I construct the bipartite graph, the problem becomes easy to solve as bipartite graphs have been heavily studied.

The challenge is I'm not sure how to algorithmically construct the graph in a provably correct way given the rules or if it implies a different approach should be used. I'm thinking it may help to sort the input array by quantity and then not connect an edge if a vertex is marked as 'matched', but that alone doesn't solve the problem (i.e. BFS/DFS do not seem so help). Other potential avenues may be more generally 2D dynamic programing or set covers (although set covers are also in NP).

An Example with the (not quite bipartite) Graph Approach:

Take input array $[A:5,\ A:4,\ D:6,\ B:3,\ E:5]$, where $A:5$ indicates an item A with quantity 5. The bipartite graph should look like the below where the colors indicate potential matches (ignoring quantities) except that it allows for impossible matches, namely $\{A, E, A, B\}$ should not be possible but is according to the graph:

The potential matches should be:

$A, E, D$ (top edges)
$A, B$ (bottom edges)
$A, E, D$ (first bottom then top edges)
$A, B$ (top then bottom edges)

Ultimately the solution including quantity would be 2 matches with some quantity left over:

${A:5/5,\ E:5/5,\ D:5/6}$
${A:3/4,\ B:3/3}$

Left over

$D:1$
$A:1$


texts: Is language equality for linear context-free grammars decidable?

texts:
Let's consider two context-free grammars $G_1$ and $G_2$ and ask the following question: Is $L(G_1) = L(G_2)$, that is, are the two grammars equivalent?

In general, this problem is undecidable. However, if both $G_1$ and $G_2$ are left-linear (or right-linear) grammars, then the problem is decidable, because both grammars describe regular languages.

My question is whether or not the same problem is decidable when both grammars are linear. Also, if anybody can point to relevant literature, that will be highly appreciated!