texts: How to use stable matching algorithm in order to determine optimal schedule?

texts:
This is a problem 1.6 from the book Algorithm Design by Kleinberg/Tardos:

There's a company that manages ships that do various tasks when in port. There're $n$ ships, $n$ ports, $m$ days in a month such that $m>n$.
At any given day there can't be two ships from the company in the same port. $(*)$
The company wants to perform maintenance on all the ships this month, via the following scheme: they want to truncate each ship’s schedule: for each ship $S_i$, there will be some day when it arrives in its scheduled port and simply remains there for the rest of the month (for maintenance). This means that $S_i$ will not visit the remaining ports on its schedule (if any) that month, but this is okay. So the truncation of $S_i$’s schedule will simply consist of its original schedule up to a certain specified day on which it is in a port $P$; the remainder of the truncated schedule simply has it remain in port $P$.
Now the company’s question to you is the following: Given the schedule for each ship, find a truncation of each so that condition $(*)$ continues
to hold: no two ships are ever in the same port on the same day.
Show that such a set of truncations can always be found, and give an algorithm to find them.

As far as I understand from the example the ship must visit at least one port before it's on maintenance (although this condition is not mentioned in the book). I also assume that each ship is supposed to visit all ports. Then because there're more days than ports and ships we could simply create an array with the all the ports and then upon each encounter of a port we'd check if it's already been visited by another ship: if not then we leave the ship for maintenance at the port; if it's already been visited then we keep going forward until we encounter a previously unvisited port.
This is solution is too simple and it's not using Gale Shapley matching algorithm which I think is expected to be used in the book.


texts:
I'm interested in the time complexity of the following problem:

Given an undirected graph $G=(V,E)$ and a weight function $w: E \rightarrow \mathbb{Z}$ (so weights can be negative, too), color the vertices in such a way that the sum of the weights of the monochromatic edges (i.e. those between same color vertices) is minimized.

The closest NP-hard problem I could find is the "minimum edge deletion k-partition" (https://www.nada.kth.se/~viggo/wwwcompendium/node43.html), however, in that problem $k$ is known and fixed beforehand, whereas in my problem, the  optimal $k$ (i.e. the number of different colors) is not known.

Any hints, pointers, comments are welcome.


texts:
Problem Link - Assign .This problem is known as assignment problem.

I read few solutions  Here is one   and they are trying to solve it using Bit-masking and DP .I tried and thought hard to understand how to solve it but i was unsuccessful ..


texts: What token does a "peek" operation refer to in Lexical analysis?

texts:
Given a grammar for a space delimited list of words:

S     -> word { space word }
word  -> [a-zA-Z]+
space -> [ \t]+

And given the input "Hello World", what token would a peek() operation return?


texts: What is the diference between $\lambda x.1$ and $1$?

texts:
I know that I can $(\lambda x.1) 0 \rhd_\beta 1$. This is the constant 1, but can I contract it automatically? I mean, is $1$ the normal form of $(\lambda x.1)$?
It seems reasonable to do it but when goes to combinators this sense stops, I mean, if I can $\lambda x.1 \rhd_\beta 1$, then I would $\lambda xy.y \rhd_\beta \lambda y.y$ but $(\lambda xy.y) a b \rhd_\beta b$ and $(\lambda x.1) a b \rhd_\beta 1 b$ so that $\lambda x.1 \not\equiv_\beta 1$
What rules I'm missing on Lambda cauculus that forbids the contraction $\lambda x.1 \rhd_\beta 1$?


texts: Strongly Predictive Belief Updating Inference in Bayesian network

texts:
In my AI college course I came up with this question.
Given following information, prove that a Strongly Predictive Belief Updating Inference is solvable in linear runtime (also called O(N) where N is the network size).

Calculating marginal distribution of Bayesian network's nodes when some evidence is given is called Belief Updating Inference.

We call a belief updating problem Strongly Predictive if and only if all the evidence nodes' fathers are evidence nodes themselves.


texts: Heuristics for tree decomposition into k shortest paths

texts:
What kind of heuristics are useful in a tree decomposition of a graph to find the k shortest paths from a given source to a vertex?

Moreover, the local shortest paths at each node in a tree are precomputed. Here, the graph is undirected and weighted. I'm interested in finding only simple paths, i.e., no nodes are repeated in a path.


texts: Will irrational parameters make a problem not well-defined on complexity

texts: Given a set $=\{_1,⋯,_\}$ where all $_$s are rational positive numbers and $\sum_{i\in N}a_i=1$, find a subset ⊆ such that $(\sqrt{2\sum_{i\in S}a_i}-1)^2$ is minimized. Does the appearance of √ make the problem ill-defined with regrading to complexity?


texts: Determine minimum and maximum number of leaves on a complete tree

texts:
I want to determine the minimum and maximum number of leaves of a complete tree(not necessarily a binary tree) of height $h$.
I already know how to find minimum($h+1$) and maximum($2^{h+1}-1$) number of nodes from the height, but what about leaves? Is there a way to determine them knowing nothing but height of the tree?


texts: Algorithm to optimize redistribution of balls amongst urns

texts:
Here is the question:
Say we have k urns with 1 ball in each urn. At each iteration of the game, I pick one urn and redistribute its contents amongst other urns and each urn can receive at most one ball and the urn we selected will need to be empty. Moreover, we can select what urns the balls go into. We have some extra urns if needed (I have not used them though). Our reward is the number of balls from the urn we select for redistribution.

My goal is to find the algorithm (in loose terms, no need for pseudo-code just the idea) which allows to have the highest average reward as the number of itterations goes to infinity. This will imply that if I have at first reward $a_1 , \cdots , a_l$ and then $b$ for infinity, the average will be $b$ as the itterations go to infinity.

So far my best result is an average reward of $r$ for $k=\frac{r(r+1)}{2}$. So this implies that the function of the average reward for $k$ balls is $\frac{-1 + \sqrt{1+8k}}{2}$. Is this the bets possible result?

My reasoning is that for say $k=66$ after a finite number of iterations, I will have $0$ balls in all the urns, except for the last 11, where I have consecutively this distribution: $(0, \cdots , 0 ,11,10,9,8,7,6,5,4,3,2,1)$ So then I can select the urn with $11$ balls and distribute them along all the ones in front and the first urn, we can then always have a reward of $11$. I am not convinced this is the best method though, any insight would help!

Is this problem commonly known?
(I posted this on mathstackexchange, but I was told this is a better place for this question)


texts: Good exposition of tableau for first-order logic with equality?

texts:
I'm looking for a resource (online or printed) that explains in a self-contained way the classic tableau for first-order logic with equality. All I can find are expositions of tableaux for first-order logic without equality, or resources which explains the tableau without equality and then treat equality with the same tableau but by adding axioms, which is ok, but not what I'm looking for.
I'm looking for something that include proofs of soundness and completeness of the tableau.
Any such resource around?


texts:
Hi im stuck on an exercise of ambiguous grammar. I need an example that shows that this grammar is ambiguous. The grammar is defined as follows:

$$S \rightarrow aT | bR$$
$$R \rightarrow a | aS | bRR$$
$$T \rightarrow b | bS | aTT$$

Thanks!


texts: Is there an algorithm to "learn" the nonlinear relationship between variables?

texts: Suppose those random variables are represented as scalar time series with nonlinear relationship (thus applying linear correlation or covariance would be futile) that may change over time, then is there a machine learning algorithm that would approximate or "learn" such relationship?


texts: Is it decidable if there exists some input such that the TM makes at least five moves?

texts:
I am reading this excerpt from Ullman's book:

I have following doubts:

(related to red underline) TM can make 5 left moves or 5 right moves. So it will  need at max 11 cells. Then how it says 9?
(related to green underline) Whats the significance of "finite"? Due to 9 (or 11 if I was correct in point 1)?
(related to blue underline) I am not able to understand the given proof. I tried it myself: I will run TM on all length 1 to 5 strings. If it makes 5+ moves on any of these strings, then "accept", else "reject". Hence decidable. Is my interpretation / approach correct? If correct then what was the significance of thinking about those nine cells?


texts: Generate random weighted graphs representing a road network

texts:
in order to solve a DARP problem I created a Python class, that can generate random graphs. I attribute a random number to every edge which represents the cost to travel over that edge.
My current solution for connecting vertices (and so create an edge) looks like this:

def connectVertices(self, vertexA, vertexB):
    vertexA.addNeighbour(vertexB)
    vertexB.addNeighbour(vertexA)
    weight = randint(1, self.maxDistance)
    self.adjacencyMatrix[vertexA.index][vertexB.index] = weight
    self.adjacencyMatrix[vertexB.index][vertexA.index] = weight

I insert a random integer in the adjacency matrix.
How ever this can creates graph which can not represent realistic road networks. Example:

Node A has a cost of 1 to B.

Node B has a cost of 1 to C.

Node C has a cost of 60 to A.

Since the cost when travelling over B between A and C is only 2, it does not make much sens to have a cost of 60 for the direct connection between A and C.

(I can not solve this problem by reducing the maximal cost, because I will need to generate large graphs.)

Are there algorithms that solve this problem ?

(Or :Is there maybe a python library which generates random weighted graphs which takes my problem in count ?)


texts: Do an ambiguous grammar and its corresponding unambiguous version generate the same language?

texts:
If I have an ambiguous grammar G and its disambiguated version D.
Then which one is true  L(D) ⊂ L(G) , L(G) ⊂ L(D) or L(G)=L(D)?

As I tried with some examples to transform a grammar to it unambiguous version but i found that both are equivalent.

I mean is there a specific set relation between both. Please help me and provide an example if possible.


texts: Data Compression Algorithm for Less repetitive pattern (redundancy)

texts:
Context:

Lossless Data compression (source coding) algorithms heavily rely on repetitive pattern (redundancy)

Questions

Which data compression method/algorithm deals with less repetitive pattern (redundancy) specially ?


texts:
In my programming languages course we are reviewing type inference, i didnt get very well how to make this task. I all ready search at the bibliography of my course (PLAI by Shriram krishnamurthi) which actually sucks big cock since he jump lots of steps in the few examples he expose. Does anybody know how to make the type inference of the following function?:

(define(for-each f lst)
(if (not null? lst
     (begin (f car lst for-each f
                         (cdr lst)))))


texts: Variation to edit distance depending on position still a metric?

texts:
The edit distance between two strings $d(w_1, w_2)$  sums up the cost of edit operations that transform one string into the other. If done right, the edit distance is a metric.

In particular, the cost of an edit operation may depend on the character inserted or deleted, meaning we have costs $w_\text{insert}(a)$ and $w_\text{delete}(a)$ for all characters $a$.

Question: If the cost also depends on the position in the input string where it is applied, will the result still be a metric?

As an example, consider a spell checker that assumes mistakes in the first character of a word are rather seldom as compared to other positions, so when searching for corrected words, a change in the first position would have high cost.


texts: If a language is X-complete, is its complement is X-complete as well?

texts:
I'm looking for an information about closure of complexity complete classes.

Is it true that any language, if the language is X-complete, then its complement is X-complete? Why?

I was thinking that it has to do with accepting states in Turing Machine. You should just switch them so the complexity should be the same but I'm not sure.


texts:
I'm trying to design an algorithm for evenly fitting decimal numbers into a decimal number.

Say I have a set $N$ of decimal numbers ($N_1$, $N_2$, ..., $N_n$) and a target value $Y$. I'd like to see what combination of values of $N$ (values may be used zero to many times) add up evenly to $Y$.

I've accomplished it by selecting random values of $N$ until I either add up to $Y$ or pass it - at which point I start over. This algorithm does not seem efficient, however. Sometimes it takes 50k passes before it lands on an answer.

The set I'm actually working with is 21 dollar values between \$0.89 and \$8.04 and the target is \$43.94.

Is there a simpler algorithm?


texts: Can machines of finite size ever solve their own halting problems?

texts: A real-life computer can only store programs and inputs up to a certain length, which means that its halting problem can be solved with a lookup table. The most obvious way to represent this table grows exponentially with the number of bits in the computer's state description, and so wouldn't fit inside the memory of the computer that it was answering the question about. Aside from trivial cases, are there finite computer-like machines that can answer their own halting problems?


texts: Why do we reject turing machines that use space less than the log of the length of the input?

texts:
In Computational complexity: Modern Approach by Arora and Barak, it's mentioned that

  We will require however that $S(n)> \log n$ since the work tape has length $n$, and we would like the machine to at least be able to remember the index of the cell of the input tape that is currently reading.

What does that exactly mean? I don't see the point, what does "remembering the index of the cell currently read by the head of the input-tape" mean? Any clarifications?

Note that we does not count the movements of the input-tape into our space considerations so we only count for the work-tape


texts: Data structure for a tree of points moving in space

texts:
I'm trying to come up with a data structure for a following model: Nodes representing points in space are structured in a tree (general rooted tree with no restrictions). Let's call these nodes "joints". Joints contain information about their position and their axis of rotation: Whole subtrees may rotate around their parent joint's axis by any given angle.

The described tree can be treated as the input. I need to store this data in some data structure, that would provide these two operations as efficient as possible:

rotate(id, angle): Rotate a given joint with its subtree by a given angle around its parent's axis.
get_position(id): Retrieve the current position of a joint (including leaves) by its id.

(The id may be the original coordinates, some arbitrary integer stored inside the joint etc.)

There are no strict limits on the time complexities of these operations. But obviously I'm looking for a complexity better than linear (logarithmic would be ideal), as that could be achieved with a straightforward approach. Neither there are any strict limits on space complexity. This structure doesn't have to be dynamic necessarily: I don't need insert or delete operations, I only need to store the information about the joints once.

The input tree is not balanced, and there is no way to balance it, as it would loose information about the subtrees' dependencies. So I thought the natural approach would be to construct a different tree structure with some relation other than simply parent node -> subtree as joint -> joints dependent on its rotation. But what relation could give me some good results?


texts: Number of planar graphs, given an embedding

texts:
I want to find an upper bound on the number of planar graphs with $n$ vertices, assuming that we are given some embedding for those vertices beforehand. In particular, Im interested in either showing for every embedding there is $2^{o(n\log(n))}$ planar graphs, or showing that there exists an embedding with $2^{\Omega(n\log(n))}$ different planar graphs.
I know that without fixing embedding there is $2^{\Theta(n\log(n))}$, but my question differs from it since we fix an embedding beforehand.
I believe that still there is an embedding with $2^{\Omega(n\log(n))}$, but I couldn't prove or disprove it. Here is an attempt I made to try and calculate the number of planar graphs for some embedding I believed would be "hard", but it didn't work out as expected.
Thanks in advance!


texts:
I've been reading about the No Free Lunch Theorem, but I can't quite understand what it is about.  I've heard this theorem described elsewhere as the claim that "no general purpose universal optimiser exists". On the other hand, the Wikipedia article talks about 'candidate solutions" that are "evaluated one by one" - if we only consider algorithms of a particular form, then that is a much more limited claim.

Can anyone explain what this theorem actually claims?


texts:
AFAIK, malloc(sizeof(char)) is intended to allocate a 1-byte block of VM and strcpy requires that

  the destination string dest must be large enough to receive the copy

That means theorically that if the length of src is strictly upper to 1, the strcpy operation fails, and it's impossible to copy more than one character to src.

However, the following code shows a counterexample, where 27 characters gets copied to s (including the '\0') as the program displays:

  s length = 26

int
main()
{
  const char *msg = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
  char *s = malloc(sizeof(char));

  strcpy(s, msg);

  printf("%s\n", s);
  printf("s length = %i\n", strlen(s));
  printf("msg length = %i\n", strlen(msg));
}

So, why malloc(sizeof(char)) allocates 27 characters contrarily to what it is intended to allocate theorically? How does this allocation work?


texts: Expected gain of a game of chance with differently-priced tokens

texts:
Foo and Bar are playing a game of strategy. At the start of the game, there are $N$ apples, placed in a row (in straight line). The apples are numbered from $1$ to $N$. Each apple has a particular price value.

The price of $i$th apple is $p_i$.

In this game, the players Foo and bar make an alternative move.

In each move, the player does the following:

If there is more than one apple left, the player tosses an unbiased coin. If  the outcome is head, the player takes the first apple among the apples that are  currently present in a row in a straight line.
If there is a single apple left, te player takes it.

The goal here is to calculate the expected total price value that Foo will get if Foo plays first.

Example 1:
N=5
Apple price val:
5 2 3 1 5

Answer is : 11.00

Example 2:
N=6
7 8 2 3 7 8

Answer : 21.250

Example 3:
N=3
1 4 9

First           Second      Third          Foo Total Val
Foo gets 1  Bar gets 4  Foo gets 9          10
Foo gets 1  Bar gets 9  Foo gets 4          5
Foo gets 9  Bar gets 1  Foo gets 4          13
Foo gets 9  Bar gets 4  Foo gets 1          10

probability 0.5 • 0.5 = 0.25.
Expected value (Foo)= (0.25 *10 )+ (0.25 *5) + (0.25*13)+ (0.25*10) = 9.500

I wrote the following code:

#include<iostream>
using namespace std;
double calculate(int start,int end,int num,int current);
int arr[2010];
int main()
{
    int T;
    scanf("%d",&T);
    for(int t=0;t<T;t++)
    {
        int N;
        scanf("%d",&N);
        for(int i=0;i<N;i++)
        {
            scanf("%d",&arr[i]);
        }
        printf("%.3lf\n",calculate(0,N-1,N/2+N%2,0));
    }

    return 0;
}
double calculate(int start,int end,int num,int current)
{
    if(num==current)
        return 0;
    double  value=0;
    value=.5*arr[start]+.5*arr[end]+.5*calculate(start+1,end,num,current+1)+.5*calculate(start,end-1,num,current+1);
    return value;
}

But the above code is quite slow. The constraints are: price of apples $p_i \le 1000$; $1 \le N \le 2000$; there are 500 test cases. How can I solve this more efficiently?


texts: How to generate response variable during machine learning?

texts:
I am analyzing data of insurance companies and for some reasons the data that was provided doesn't have any response variable of whether an insurance claim is legit or suspicious.

Are there any ways to generate the required response variable from the data that is available to us. I can think of clustering (hierarchical or K-means) as a means to identify clusters. But I am not sure if the clusters developed are true representation of my unreported response variable.

Also, Let me know of any other methods to generate response variable when there is none.


texts:
I came across a modification of the classic house robber problem where the robber cannot rob from $l(i)$ houses on the left of $i$th house and $r(i)$ houses on the right of $i$th house. The modified version will now be as follows:

  You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that if you rob the $i$th house then you cannot rob from $l(i)$ houses on the left of $i$th house and $r(i)$ houses on the right of $i$th house (in the classical problem, $l(i) = r(i) = 1$). Given the amount the money in each house, and the arrays $l$ and $r$, what is the optimal amount to be stolen?

I believe this can be solved by dynamic programming as well. However I have been trying enough without any results and would like some help on this.

Edit 1:
l(i) and r(i) are variable i.e. different for each i.
Example:
House values: 1 3 7 3 7
L array:      0 0 2 2 2
R array:      3 0 1 0 0

The answer is 10, which is obtained by selecting the 2nd and 5th house. To further clarify l(i) and r(i), take the 3rd house for example. l is 2, means that 2 houses on the left cannot be selected (houses 1st and 2nd), whereas r is 1, meaning 1 house on the right cannot be selected (4th house)
Note: The convention for numbering used is, first house is i=1, second is i=2 and so on.


texts: Size of maximum clique given a fixed amount of edges?

texts:
Given an undirected graph $G = (V,E)$, what is the clique number $\omega(G)$ given $|E|$, i.e., the size of the largest clique in a graph with $|E|$ edges.

I think this is doable after realizing that the number of edges in a clique is equal to the triangular number:
$$|E(K_k)| = \frac{1}{2}k(k-1).$$

I am looking for a closed formula.


texts: Can uniqueness of strings (each with an equal number of 1's and 0's) be decided in logspace?

texts:
Let k be a positive even integer.

Given a list of (k choose k/2) k-sequences, each with an equal number of 1's and 0's, is distinctness decidable in logspace if we're only allowed to read the input once?

In more detail:

Let a sequence have k bits.

Let each sequence have an equal number of 1's and 0's.

There are (k choose k/2) such sequences.

Suppose I have a list of sequences.

Suppose there are (k choose k/2) sequences in the list.

Can we decide each sequence is distinct from the others in logspace?

If we can read the input multiple times, we can use two logspace counters - and ensure each sequence is not equal to the sequences that follow.

What if we're only allowed to read the input once?


texts: Select a set of elements from a 2D matrix, such that each element comes from distinct row and column

texts:
We're facing following problem - an n * n 2D Matrix contains doubles (Java). Find a Set of elements such that

Each element in the set comes from a unique row and column combination. That is, once you've selected an element (i, j) as a candidate for a set, that set cannot contain any elements from ith row or jth column.
The size of the set is Maximized. The Matrix may contain NaNs, so it may not be possible to find a set of size n.
The sum of elements on this set is minimum over all sets of this size for this Matrix.

For Example, consider following matrix -

1 2 3 4
4 1 2 3
3 4 1 2
2 3 4 1

This is artificially constructed to demonstrate the problem, solution for this Matrix is going to be the diagonal elements

{1, 1, 1, 1}

Any ideas?

Just to be sure, this is not a homework problem. We're trying to solve this for a client. Problem we're trying to solve is in Transport domain, and basically boils  down to problem statement above.

I've tried to think of a polytime solution, but the first condition seems to be problematic. If it was not in place, this would have been a trivial DP problem - create a temporary 2d array, traverse each row of original array, and for each element, try to find element in last row in temporary array that has the smallest cumulative sum. Make this element's value in temp_arr smallest cumulative sum + this element. Find smallest element in last row and you're done.

I'm trying to see if there is a polynomial time solution. In all probability, it will be easier to code, verify, and debug than any graph theory based solutions.

Edit added after some search -
Just realized that what I was looking for was Hungarian Algorithm for Assignment problem - https://en.wikipedia.org/wiki/Hungarian_algorithm


texts: Understanding LEADING and TRAILING operations of an operator precedence grammar

texts:
I want to understand what the LEADING and TRAILING of non-terminal in an operator precedence grammar physically mean.

I am confused by the various definitions I have read on them.
I understand that the LEADING of a non-terminal is the first terminal which can be present in it's derivation.
On the other hand, the TRAILING of a non-terminal is the last terminal which can be present in it's derivation.
In the following example:

E   ->  E   +   T      -- I
E   ->  T              -- II
T   ->  T   *   F      -- III
T   ->  F              -- IV
F   ->  (   E   )      -- V
F   ->  id             -- VI

By my understanding,

LEADING(E) = { +, *, (, id }
LEADING(T) = { *, (, id }
LEADING(F) = { (, id }

This turns out fine, but my problem is in the TRAILING.

TRAILING(F) = { id, ) }
TRAILING(T) = TRAILING(F) = { id, ) }          -- (1)
TRAILING(E) = TRAILING(T) = { id, ) }          -- (2)

Reason for (2) is that according to productions I and II, the last terminal of the derivation of E will be last terminals in the derivation of T.
Hence, TRAILING(E) = TRAILING(T).
Similarly, TRAILING(T) = TRAILING(F).
Unfortunately the solution to this problem states:

TRAILING(F) = { id, ) }
TRAILING(T) = TRAILING(F) `union` { * } = { *, id, ) }
TRAILING(E) = TRAILING(T) `union` { + } = { +, *, id, ) }

I don't see how * or + can be the last terminals in the derivation of E. Any derivation of E will always end with either an id or ). Similarly, case for T.


texts:
I am wondering if a constrained insert-only form of Levenshtein distance has been implemented before by someone? In my particular use case, all other operations should not count as they are not possible. Only parts of the strings can be stripped off. As an example, if our library has "Hello" and "complex".

These strings can be stripped and we might only see "Hel" or "llo" or "com" etc. I want to explore, if what we see is part of a sequence in our library.

Thanks for any suggestions.


texts: Is there any nontrivial problem in the theory of serial algorithms with a nontrivial polynomial lower bound of $\Omega(n^2)$?

texts:
In  the theory of distributed algorithms, there are problems with lower bounds, as $\Omega(n^2)$, that are "big" (I mean, bigger than $\Omega(n\log n)$), and nontrivial.
I wonder if are there problems with similar bound in the theory of serial algorithm, I mean of order much greater than $\Omega(n\log n)$.

With trivial, I mean "obtained just considering that we must read the whole input" and similarly.


texts: What is the meaning of the mutation rate in genetic algorithms?

texts:
Let us suppose that we have a mutation rate of 5%. What does this mean?

Each gene of each individual has 5% of probability of change to another value? At the end, around 5% of the genes of each individual in the population will be changed.
Each individual in the population has 5% of probability of having a random gene changed to antoher value? At the end, 5% of the population will have a change in some of its genes.

Besides that...Should I apply the mutation operator over all individuals or only to the children generated by the crossover operator?


texts: How to prove the equivalence between Hoare and Floyd assignment axioms?

texts:
How to show that these two axioms are equivalent:

1: $\{G[v/e]\} v:=e \{G\}$

2: $\{F\} v:=e \{\exists v' (F[v/v'] \land v=e[v/v'])\}$

I've tried with $G = \exists v' (F[v/v'] \land v=e[v/v']) $and then I get $G[v/e] = F$, but when I try $F = G[v/e]$ then from $\exists v' (F[v/v'] \land v=e[v/v'])$ I can't obtain $G$.

Is that even correct way to approach this proof?

Thanks!

p.s. There was a question already, but isn't answered: How to show equivalence of the Hoare assignment axiom vs Floyd assignment axiom?


texts: Use Machine Learning to predict when a Gas Station is running out of fuel

texts:
We have years of data on several Gas-Stations.

Data about the Gas-Stations:
the number of tanks, Gallons per tank, Location, number of pumps, kind of fuel, etc.

Data on fuel consumption for x gas station:
Time-Date when filled, Time-Date when empty

Data about consumers:
Gas Price, Peak hours for gas charging, peak seasons for gas charging,

And more of this kind of data, we still need to cure, and clean.

We are always predicting which gas-station will run out of gas next, so we can dispatch a truck to reload the gas-station.
Gas-station with an empty tank is what we need to avoid.

We are limited to finding patterns and we are hoping some kind of ML algorithm, AI service will be able to improve our prediction accuracy.

What would be the best approach to setting an ML environment that could predict:

Wich Gas Station needs to refuel next?

Could we use some of the preexisting algorithms in Google or AWS?

Thanks!

Ok so I am now reading about:
Linear models
https://docs.aws.amazon.com/sagemaker/latest/dg/linear-learner.html

Machine Learning to predict when a gas station will run out of fuel.


texts: Why can you push multiple symbols on a PDA stack at once?

texts:
I'm really new to learning about PDA's and stuff, i understand that on a edge between 2 nodes you'll have something like this a,b->c. This means:

if a is in the beginning of your string and b is on top of your stack you can

remove a from your string (the one you run through the PDA),
remove b from your stack
place c on your stack

and take the edge...

My book also tells me that you can place more then one symbols on your stack. For instance a,b->cd.

I think this is because you can also have this edge  ε, ε -> c wich just puts c on the top of the stack,

so a,b->cd between Node 1 and 2 can by replaced by Node1 - a,b->c - New node -  ε, ε->d -> Node2.
Can someone please confirm if this is correct?

the pda is defined as (Q,E,T,d,s,F) with

Q an finite collection of states
E a finite inputalfabet
T a finite stackalfabet
d a transitionfunction Q x E (including ε) x T (including ε) -> V collection of(Q x T (including ε))
s the startstate
F a collection of eindstates (subcollection of Q)


texts: An algorithm to find highest lines in at least one point

texts:
Suppose we have $n$ lines $L_1, L_2, \dots, L_n$, where $L_i$ has the equation $y = a_i x + b_i$. We call $L_i$ the highest line at $x_0$ if for each $j \in \{1, 2, \dots, n\}$

$$a_i x_0 + b_i \ge a_j x_0 + b_j.$$

Goal: Find an algorithm in $O(n \log n)$ time to return a set of lines that are the highest lines in at least one point.
Hint: Use the divide and conquer technique.

Since we should use divide and conquer technique, I think I should split the problem into two subproblems with size of $n/2$ and try to solve these two first. I don't know what to do next. Thanks in advance.


texts: Shortest path in a weighted graph with coloured edges

texts:
I have a weighted undirected graph with $N$ vertices and $M$ edges. Each edge has its own weight and colour. There are at most 10 different colours in the whole graph. Each time I traverse edges of different colour I have to pay an additional fee equal to $K$. Given two vertices $A$ and $B$, I want to find the shortest path between them.

For example, given a multigraph with 3 vertices, $K = 5$, and 3 edges: ($1\rightarrow 2$ of weight 3 and colour 1), ($1\rightarrow 2$ of weight 5 and colour 2), ($2\rightarrow 3$ of weight 2 and colour 2), weight of the shortest path is 12.

I would like to design an algorithm that would solve this problem in reasonable time. My first idea was to use Dijkstra's algorithm and for every vertex store an information about the edge from which I went into that vertex, but that strategy won't work for the example given above. So I don't have any other idea than brute-force search.

Constraints:

$N \leq 10^5$
$M \leq 10^5$
$K \leq 10^5$


texts: Given a list of integer rectangle areas, find all integer rectangles that they can tile

texts:
Is there an efficient algorithm that takes in a list (multiset) of integer rectangle areas and finds all possible integer rectangle tilings?
Every integer rectangle area in the list (multiset) must be used exactly once (corresponds to exactly one rectangle).

For example, if we were given $$(2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, 12, 1, 1, 14, 1, 1, 16, 1, 1, 18, 1, 1, 20, 1)$$
then one possible integer rectangle tiling is:

which uses the given list to tile a $11\times 12$ rectangle.
So far, I've found What rectangles can a set of rectangles tile? on MO, and am trying to track down and adapt the references to my problem.
A similar but different problem is Filling rectangles with integer-sided squares.


texts: What does it mean when a time complexity has another time complexity within it?

texts:
Sometimes, when reading about algorithms or other theoretical topics, I see time complexities that include other time complexities within the expression.

For instance, "the best fixed-parameter tractable algorithm for the vertex cover problem has a time complexity of $O(1.2738^{k} \cdot n^{O(1)})$."

What does this $O(1)$ expression mean? Can I just replace it with any constant and the time complexity will still hold?


texts: When the data size and processor speed are both multiplied by 10, then a linearithmic algorithm takes double the time to finish?

texts:
Robert Sedgewick mentioned, if a computer can handle 10x data and the processor is also 10x as fast, then a $ O(n^2) $ algorithm actually runs slower than before.

Is this the correct idea when a computer has 10x RAM and can handle 10x data all at once, and also have a processor that is 10x faster, then:

A $ O(n^2) $ solution is slower, because now $ n^2 $ is 100 times, but processor is only faster by 10 times. So the time it takes to solve the problem is 10 times more. So if it took 1 hour to solve the problem before, now it would take 10 hours.
If it is a $ O(n \log n) $ solution, then roughly speaking, for $ n \log n $, it is

$ (100 \log 100) / (10 \log 10)
  = (100 / 10) \times  (\log 100 / \log 10)
  = 10 \times log_{10} 100 = 20 $

and since the processor is 10 times as fast, that means now the algorithm is "half as fast"? (meaning if it took 1 hour to solve the whole problem before, now it would take 2 hours)


texts: Multi-dimensional Neural Network for fingerprint matching

texts:
I want to use “Fingerprint matching using multi-dimensional ANN”
by Rajesh Kumar and B.R. Deva Vikram [content link] for fingerprint identification. But I have a serious problem understanding what is a Multidimensional Artificial Neural Network.

I searched for keywords MDANN and Multidimensional ANN but I can't find anything. I also can't be sure what Kumar meant about a MDANN in his article. So far, the closest thing I can relate with Kumar's MDANN is Convolution Nets but I don't believe this is what he meant. Can anybody help me about understanding this type of ANN?


texts: Link-cut trees: using access() and link()

texts:
I am having some trouble on understanding link-cut trees, so I need some help.
Suppose that we have nodes $A, B, C, D$ and we want to do the following operations:

Link(A,B)

Link(B,C)

Link(C,D)

Following instructions of https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-851-advanced-data-structures-spring-2012/calendar-and-notes/MIT6_851S12_L19.pdf, I get

However, when we draw preferred paths, I should get

Am I doing something wrong when doing access(X)?
Thanks in advance.


texts: How do stable functions 1 => 1 relate to Bool?

texts:
One way to interpret the (simply typed) lambda calculus is via coherence spaces (Proofs and Types, chapter 8).  For example, we can consider the space containing token element ($\mathbf{1}$) and the space containing two incoherent tokens ($\mathbf{Bool}$).  These are given as follows:

$$
  \mathbf{1} = \{\emptyset, \{0\}\}\\
  \mathbf{Bool} = \{\emptyset, \{t\}, \{f\}\}
$$

We can then consider the stable functions from $\mathbf{1}$ to itself:

$$
    F_1(\emptyset) = \emptyset, F_1(\{0\}) = \emptyset\\
    F_2(\emptyset) = \emptyset, F_2(\{0\}) = \{0\}\\
    F_3(\emptyset) = \{0\}, F_3(\{0\}) = \{0\}
$$

The trails of these functions are as follows:

$$
    \mathcal{Tr}(F_1) = \emptyset\\
    \mathcal{Tr}(F_2) = \{(\{0\}, 0)\}\\
    \mathcal{Tr}(F_3) = \{(\emptyset, 0)\}
$$

This again forms a coherence space

$$
    \mathbf{1 \Rightarrow 1} = \{\emptyset, \{(\{0\}, 0)\}, \{(\emptyset, 0)\}\}
$$

Which, just like $\mathbf{Bool}$, has two incoherent tokens.  As far as I can see, the two should be equivalent, and there exists a stable function of type $\mathbf{(1 \Rightarrow 1) \Rightarrow Bool}$ which maps $F_2$ to $f$ and $F_3$ to $t$.

Can this function be expressed in the lambda calculus?  If not, why is it part of the interpretation?  Can we see $\mathbf{Bool}$ and $\mathbf{1 \Rightarrow 1}$ as "the same" due to the similarity in coherence space?


texts: Does there exist any unrelativized separation between a quantum complexity class and a classical one?

texts:
I'm familiar with results of relativized separation for BPP-BQP, BQP-PH and NPC-BQP. I'm also aware that while e.g. Factoring is not believed to be in BPP, it hasn't been proven and so we're not quite near proving BQP!=BPP.

My question is, do we have any certain, theoretical, unrelativized proof that quantum computers are "superior" to classical one on any specific problem - Where here, I define superior to include any sort of runtime complexity superiority, so e.g. a quadratic improvement would qualify in this regard.

I'd expect Grover's algorithm to qualify for this criterion - But despite being supposedly "obvious", I'm not sure if it's been proven that classical computers can't solve it in sqrt(n) time as well, in a non-black-box model (i.e. unrelativized).


texts:
I have this language: $L = \{a^{n+2} b^m a^{2n} b^{3n}\mid n,m >=0 \}$ and I am trying to prove that it is not CFL.
I assumed that my word is $a^{p+2} b^m a^{2p} b^{3p}$ (where $p$ is the pumpung length) and I applied the pumping lemma. I can find a contradiction for every case except for the case when the part that I am pumping is only $b$'s (from $b^m$). What would be the best choice of the word for pumping lemma?

I've already read some questions here that are similar to this one, but this kind of combination is diferent from those. First, third and fourth terms are in a relation here despide the examples where are other kind of relations.


texts: Proof that $\{0^i1^{i^2}:i\in\mathbb{N}\}$ is not context free

texts:
I am to prove that $L :=\{0^i1^{i^2}:i\in\mathbb{N}\}$ is not context-free. I presume that I can do this with the Pumping Lemma and the word $0^p1^{p^2}$, where we assume for a contradiction that $L$ has a Pumping Length of $p$, and here's my attempt:

Let $0^p1^{p^2}=uxyzv$ such that $xz$ is non-empty, $xyz$ is of length $\le p$ and $ux^iyz^iv\in L$.

Case 1: if $xyz$ is entirely within $0^p$ then $ux^2yz^2v = 0^p0^k1^{p^2}$ for some $k>0$ and hence $ux^2yz^2v \notin L$.
Case 2: if $xyz$ is entirely within $1^{p^2}$ then we get the same contradiction (with $0^p1^{p^2}1^k$).
Case 3: suppose that $x = 0^i$, $z = 1^j$. Then $ux^0yz^0v=0^{p-i}1^{p^2-j}$.

Then I want to show that $(p-i)^2 \ne p^2-j$, but I'm not sure how to do this.


texts: Analyzing the encoding of a DFA by a deterministic Turing machine

texts:
Define $L=\{\langle D,R \rangle \mid D$ is a DFA, $R$ is a regular expression, $L(D)=L(R) \}$

Is $L$ decidable?

Is $L$ decidable in polynomial time ($L \in P$)?

I am trying to ask: can a TM analyze a DFA encoding to output with a regular expression encoding on its tape and how fast can it be done?


texts: Why does the category of language types have morphisms, not functors?

texts:
I am probably not phrasing this question well, so please bear with me as I try to explain what I mean.

I am working on learning category theory, as applied to programming.  So far, I understand that:

Objects in a category are "unbroken"; you're not supposed to peer inside them to see their internal structure.
Any Set is a category
Programming language types can be thought of as sets.  (Bool is the set True, False; Int is the set of all integers; etc.)
Thus, all of the types in a language form a category of sets.
Morphisms are arrows between objects.
If those objects are themselves categories, then the morphisms get called functors.

Taken together, that would imply that a function from Int to Bool is a functor, because it's a map from the the set category Int to the set category Bool.

However, I have also read elsewhere (in particular https://www.johndcook.com/blog/2014/05/10/haskell-category-theory/), that thinking of it that way is wrong and we really shouldn't be talking about language types being a base category with "just" morphisms.  But I don't see how that fits with my previous logic.

I therefore must conclude that my previous logic is faulty, but I'm unclear how or why.  What is the right way to conceptualize this?  Are Sets just extra special exceptions?  Or is it really just an arbitrary matter of preference for how to view the problem space?  Or am I just flat out wrong somewhere?


texts: What is the Difference Between Many-to-Many (M:M) Threading and Hybrid (M:N) Threading?

texts:
I have been researching threading and come across several websites which all say contradicting statements about which and how many thread models exist. Some websites say there are only three: 1:1, M:1 and M:M, while others say the three are 1:1, M:1 and hybrid (M:N). Still others say there are four types, including 2-level threading?

Google and stack exchange haven't been able to come up with a clear answer as of yet. I was hoping for someone to shed some light on this situation, namely the difference (i.e pros & cons) between M:M, M:N and two-level threading types.


texts:
I have been investigating parallel algorithms to compute certain two-dimensional dynamic programming recursions (on natural parameters); see also here. Under certain assumptions, cases one and two can actually be computed in parallel -- and very well. However, if you assume that communicating array entries from one thread to another is more expensive than a normal memory access (as might be the case on real machines), these algorithms are no longer always strongly work-efficient¹. In fact, I conjecture that in this scenario there is no strongly work-efficient parallel algorithm general for these classes of problems, even if we consider only non-pathological recursions.

Towards proving this, I have made the following abstraction for the domain and parallel algorithms. Note that I assume here that such algorithms allocate computations of individual entries to processors in a deterministic way; I do not think the result changes if we allow nondeterminism/randomisation in this regard, but I have no proof.

  Let $G_n = (V_n, \emptyset)$ with $V_n = \{(i,j) \mid 1 \leq i,j \leq n \}$ be a family of empty $n\times n$ grid graphs. Let furthermore $c : \mathbb{N} \to (V_n \to \{1,\dots,p\})$ a coloring for this family which asymptotically divides $V_n$ in equal parts, that is

  $\qquad \displaystyle |\{v \in V_n \mid c(n)(v) = c_i\}| \underset{n \to \infty}{\longrightarrow} \frac{n^2}{p}$

  for all colors $c_i \in \{1,\dots,p\}$.

The claim is that we can choose edges so that we create no circles and no node has more than linearly many incoming edges, but there are quadratically many edges whose nodes have different colors²:

  (For any such coloring, ) There is a family of sets of directed edges $E_n = V_n \times V_n$ so that

  $((i,j), (i',j')) \in E_n \ \Longrightarrow i' \geq i \land j' \geq j$, that is edges do not point up or left³,
  for all $n \in \mathbb{N}$, $(V_n,E_n)$ has no directed cycles,
  $D_n := \max_{u \in V_n} \operatorname{indeg}(u) \in O(n)$ and
  $C_n := |\{(u,v) \in E_n \mid c(n)(u) \neq c(n)(v) \}| \in \Omega(n^2)$.

Is this (similar to) a known problem? Does it hold, and how can you (dis)prove it?

Example

Consider this coloring (which roughly corresponds to an algorithm I have investigated):

[source]

For edges as implied by the Levenshtein distance recursion, that is

$\qquad \displaystyle E_n = \bigcup_{1 \leq i,j \leq n}\{(i,j)\} \times \{(i-1,j), (i-1,j-1), (i,j-1) \} \cap \{1,\dots,n\}^2$,

we have $D_n = 3$ and $C_n = 8n-4$, so this is not the $E_n$ we are looking for. If we draw edges from every node to all others to its right, that is

$\qquad \displaystyle E_n = \{ ((i,j),(i,j')) \mid j' > j \}$,

we get $D_n = n-1$ and $C_n \geq \frac{3}{4}n^2$, so the coloring is defeated.

"Strongly work-efficient" means here that the parallel algorithm on $p \in \mathbb{N}$ cores does not take more time than $\frac{T^s}{p}$ in the limit, with $T^s$ the runtime of a (good) sequential algorithm.
That corresponds to a not-too-dense dependency structure of a recursion's domain which causes the parallel algorithm to communicate too many results between threads.
That corresponds to case one. Case two can be modelled similarly by requiring $i' > i$.


texts: How does an assembler manage varying offsets when using a literal pool?

texts:
I am trying to write a simple multi-pass assembler.
Wikipedia states that:

Multi-pass assemblers create a table with all symbols and their values
in the first passes, then use the table in later passes to generate
code.

And

the assembler must be able to determine the size of each instruction
on the initial passes in order to calculate the addresses of
subsequent symbols

Now since the instruction size of the architecture I'm using is limited, it turns out that any instruction whose operand wouldn't fit in 2^12 bits require the use of a literal pool . The issue I have is that from what I understand, using a literal pool necessarily adds multiple instructions, for instance:
// pseudo assembly
load [$sp+200] $a  // Load the address stored in the pool at offset 200 from current instruction
jump $a // Jump to this address

Not only now requires two instructions instead of one, but also adds a new element to the pool at the end of the current section, so say some previous instruction used to jump to an address past the pool, say for instance address  (2^12)-1 and now we add elements to the pool, not only will the address it used to jump to not be valid anymore, the new address will now be too big and require the use of the literal pool too, hence offsetting once again the position of some instructions and causing even more instructions to need to update their pointed addresses and so on.
It seems like something like this would also quickly have a pretty high algorithmic complexity as you need to run over your program once again each time you need to use the literal pool?
What are the solutions for this?
I see Wikipedia also mentions that:

This means that if the size of an operation referring to an operand
defined later depends on the type or distance of the operand, the
assembler will make a pessimistic estimate when first encountering the
operation, and if necessary, pad it with one or more "no-operation"
instructions in a later pass or the errata. In an assembler with
peephole optimization, addresses may be recalculated between passes to
allow replacing pessimistic code with code tailored to the exact
distance from the target.

So maybe that's an answer to my problem but I wonder if I'm missing something else? Should I for instance consider that all my instructions will need to use the literal pool and then remove all the instructions that don't actually need to in a later pass? Even in such a case it seems that I would still need to go over the assembly code multiple times, since removing instructions might make some addresses small enough that other instructions can now also stop using the literal pool, and so on (basically the same issue as what I mentioned above).
How should I handle this?
Thank you


texts: Does the closure of a function include the actual parameter passed to the function?

texts:
A closure of a function includes the environment when calling the function.

Does the environment included in a closure of a function include the actual parameters for the function?

If I am correct, from mathematical logic point of view, a closure for an expression consists of the free variables of the expression. So I guess the answer to the question is no.


texts:
Using Dijkstra algorithm, how can I find the next shortest path in a directed weighted graph? (When saying next, I mean that the next path must be heavier than the lightest path and not equal). The two paths can have some shared edges.
I thought about storing for each vertex two fathers, and trying to build the second path from those fields, but I'm not sure how I can guarantee that I will create the desirable path.
The implementation should stand in Dijkstra time complexity.

Any suggestions?


texts: Can two different complexity classes be equal relative to an oracle? Example request

texts:
Is there a known example of two complexity classes, $A$ and $B$, such that:

$A \neq B$;
there is an oracle $O$ for which $A^O = B^O$?

I strongly believe that there are such examples, as otherwise $P = PSPACE$ (note that $P^{PSPACE} = PSPACE^{PSPACE}$), but I was looking for an example of this.


texts: Are there some good algorithm to select m by three matrices which satisfies certain conditions?

texts:
I would like to find an algorithm which select matrices satisfying certain conditions.

We consider integer matrices (entries of the matrices comes from $\{1,\ldots,n\}$ for some positive integer $n$) and the numbers in each row are different from each other.

Let me first explain some definitions.

We call a matrix $M$ with m rows and k columns canonical if for all $i \in [2, m]$ and $j \in [2, k]$, $M_{i,j} > M_{i-1, j-1}$ and for all $i \in [2,m]$ and $j \in [1,k]$, $a_{ij} \ge a_{i-1,j}$. For example, $\left(\begin{array}{ccc}3 & 5 & 9\\2 & 5 & 8\\1 & 4 & 7\\1 & 4 & 6\end{array}\right)$ is canonical.

Let $M$ be a matrix with $k$ columns. Denote by $I_j$ the set of the elements in the $j$th row. We say that two rows $j_1, j_2$ of $M$ i-interlacing if $|J_{j_1} \backslash J_{j_2}|=|J_{j_2} \backslash J_{j_1}|=i$ and $J_{j_1}\backslash J_{j_2} = \{a_1,a_2,\ldots,a_i\}$, $J_{j_2} \backslash J_{j_1} = \{b_1,b_2,\ldots,b_i\}$, either $a_1 < b_1<a_2<b_2 < \cdots < b_{i-1} <a_i < b_i$ or $b_1<a_1<b_2<a_2 < \ldots < a_{i-1}<b_i<a_i$. In particular, if two rows of a matrix are identical, then we say that the two rows are $0$-interlacing.

For example, the first row and the second row of $\left(\begin{array}{ccc}3 & 5 & 9\\2 & 5 & 8\\1 & 4 & 7\\1 & 4 & 6\end{array}\right)$ are $2$-interlacing. The third row and the fourth row of the matrix are $1$-interlacing.

For a matrix $M$ with entries in $\{1, \ldots, n\}$, denote $x=x(M)=(x_1, \ldots, x_n)$, where $x_i$ is the number of entries in $M$ which equal to $i$. Denote $q(M)=\sum_{i=1}^n x_i^2 + \frac{2-k}{k^2} (\sum_{i=1}^n x_i)^2$, where $k$ is the number of columns of $M$. For example, let $M=\left(\begin{array}{ccc}3 & 5 & 9\\2 & 5 & 8\\1 & 4 & 7\\1 & 4 & 6\end{array}\right)$. Then $x(M) = (2,1,1,2,2,1,1,1,1)$ and $q(M)=2$.

I would like to find all $m \times 3$ matrices $M$ with entries in $\{1, \ldots, 9\}$ which satisfy the following conditions:

(1) in each row of $M$, any two entries are different from each other; the numbers in each row are increasing from left to right;

(2) any two rows of $M$ are $i$-interlacing for some $i \in \{0,1,2,3\}$;

(3) there are two rows of $M$ which are $3$-interlacing;

(4) $M$ is canonical;

(5) $q(M)=2$.

In the cases of $m=2,3,4$, I use many for loops to find out all such matrices. But when $m \ge 5$, it takes infinite time. Is there some fast algorithm to find out all the matrices which satisfy the conditions? Thank you very much.


texts:
I have the following CFG $G$:
$$ \begin{align}
S &\rightarrow aAbb \mid aaBb \\
A &\rightarrow aAbb \mid \epsilon \\
B &\rightarrow aaBb \mid \epsilon \\
\end{align} $$

I have to create a PDA (pushdown automaton) to recognize this language however I am unsure on how to do it. So far I have this(revised based on feedback from user Hendrik Jan) :

I understand that it should accept the last one ($aaaabb$) however it does not for the current version.


texts:
Consider a cascade of classifiers and a binary classification task. Cascade consists of some number of strong classifiers (n) each of which consists of some number of weak classifiers (m_i, where i = 1..n).

You have 3 numbers of interest: true positive rate, false positive rate and time of detection (you can choose by your own whether it will be mean time of worst case time).

You can arbitrarily choose n, m_i for each i and vector of weights of positive and negative examples for each i. Each weak classifier is just a decision tree of length 1. Also, some meaningful type of boosting (ada or real) occurs inside each strong classifier.

Time of detection is just a linear monotonic function of the total number of weak classifiers.

Can anyone suggest how to optimally train this cascade (this structure was developed by Viola and Jones for face detection) or maybe heard of some articles where this problem was solved?

First paper of Viola & Jones: https://www.cs.cmu.edu/~efros/courses/LBMV07/Papers/viola-cvpr-01.pdf

Second paper of Viola & Jones: http://www.vision.rwth-aachen.de/teaching/cvws08/additional/viola-facedetection-ijcv04.pdf


texts: Computing childrens of ith node of a d-ary tree

texts:
Assume that we represent a complete d-ary tree in an array[1,...n] (this is a 1-based array of size n).
The formula for indices of children of node no. i is given as:
{(1-i)d+2,
... , min{n,(1-i)d+d+1}}
I am not able to get the intuition to arrive at this formula.
Can someone please help ?


texts: Difference between delayed branches and out-of-order execution

texts:
I have been reading about instruction pipeline and I stumbled upon the term delayed branches. From what I have understood, delayed branches will keep the pipeline busy, by executing instructions, regardless of the outcome of the branch. This will avoid the usages of NOP instructions.

What I do not understand is, how is it it different than Out-of-order execution? In the following example, which I just made up:

1    MOV eax, 5
2    MOV ecx, 6
3    MOV ebx, 2
4    CMP eax, ecx
5    JG label1
6    SUB ecx, ebx
7    CALL someFunc
8 label1:
9    SUB eax, ecx
10    CALL someOtherFunc

if I have understood delayed branches, before the decision is made, whether the jump to label1 will occur, the instructions on line 6 and 7 will be loaded in the pipeline. But isn't this exactly out-of-order execution?


texts: Known facets of the Travelling Salesman Problem polytope

texts:
For the branch-and-cut method, it is essential to know many facets of the polytopes generated by the problem. However, it is currently one of the hardest problems to actually calculate all facets of such polytopes as they rapidly grow in size.

For an arbitrary optimization problem, the polytope used by branch-and-cut or also by cutting-plane-methods is the convex hull of all feasible vertices. A vertex is an assignment of all variables of the model. As a (very simple) example: if one would maximize $2\cdot x+y$ s.t. $x+y \leq 1$ and $0\leq x,y\leq 1.5$ then the vertices $(0,0)$, $(0,1)$ and $(1,0)$ are feasible vertices. $(1,1)$ violates the inequality $x+y\leq 1.5$ and is therefore not feasible. The (combinatorical) optimization problem would be to choose among the feasible vertices. (In this case, obviously $(1,0)$ is the optimum). The convex hull of these vertices is the triangle with exactly these three vertices. The facets of this simple polytope are $x\geq0$, $y\geq 0$ and $x+y\leq 1$. Note that the description through facets is more accurate than the model. In most hard problems - such as the TSP - the number of facets exceeds the number of model inequalities by several orders of magnitude.

Considering the Travelling Salesman Problem, for which number of nodes is the polytope fully known and how much facets are there. if it is not complete, what are lower bounds on the number of facets?

I'm particularly interested in the so-called hamiltonian path formulation of the TSP:

$$min \sum_{i=0}^{n-1}(\sum_{j=0}^{i-1}c_{i,j}\cdot x_{i,j}+\sum_{j=i+1}^{n-1}c_{i,j}\cdot x_{i,j})$$ s.t.

$$\forall i \neq j:\ \ 0 \leq x_{i,j}\leq 1$$
$$\forall i \neq j\ \ \ x_{i,j}+x_{j,i}\leq 1$$
$$\forall j \ \ \sum_{i=0}^{j-1}x_{i,j}+\sum_{i=j+1}^{n-1}x_{i,j}\leq 1$$
$$\forall j \ \ \sum_{i=0}^{j-1}x_{j,i}+\sum_{i=j+1}^{n-1}x_{j,i}\leq 1$$
$$\sum_{i=0}^{n-1}(\sum_{j=0}^{i-1}x_{i,j}+\sum_{j=i+1}^{n-1}x_{i,j})=n-1$$

If you have any information about polytopes of other formulations of the TSP, feel free to share that too.


texts: Using a 16-bit 2,s Complement normalised floating-point representation; 10-bit fractional mantissa and a 6-bit integer exponent: express 2.171875

texts:
So far I know how to normalize when you are given, say:
1111010010 Mantissa, and 000100 exponent
and are told that it's a positive number:

1.111010010 and the exponent value is 4
move point 3 to the right: 1111.010010
subtract exponent by 3 = 1; 000001
replace extra binary digits behind sign bit with trailing 0s
1.010010000

so 1.010010000 , 000001
is the normalized form.

Now how do I express 2.171875 under the same representation?
I started by converting it to binary: 10.0010110 but how do I represent that as 10-bits 2'C Mantissa and 6-bits exponent to begin with? Or am I completely lost?


texts: How to solve this job scheduling programming problem?

texts:
I am trying to solve this question. The question is a variation of job scheduling. There are n processes given to you with their execution time Ti and individual deadlines Di. A process can be executed anytime before its deadline. A process can not be executed after its deadline is over. So, you have to find the maximum number of processes that can be executed. Given that n <= 1000 and Ti & Di <= 1,000,000 For example:

Ti Di
3  4
4  8
11 23

Answer = 3

I tried to solve this question using branch & bound mechanism. I first sort the processes on the basis of deadline. Then like 0/1 knapsack, I recursively took 2 cases. One is to take current process and other one is to discard this process. But the complexity of this approach is 2^n and it gave me TLE. Please suggest a better approach for this problem.


texts: Algorithm to evenly distribute a hierarchical dataset

texts:
I am working on a chatbot designer interface. The dataset for the conversation flow consists of messages. Each message has a parent message and can have multiple possible next messages. The system displays one of the possible next messages depending on the reply. This makes it a complicated structure of parent-children relations.
On the dialog flow designer interface, the user is able to drag messages around in order to achieve a visual clarity of the designer dialog flow. This is loads of work for the user.
I want to implement an algo that would do this job for the user. So the messages should distribute themselves at even distances and making sure that their children are also around their parent message evenly distributed.
I have not studied algos, so I am not sure what jargon to look for. I don't even know the proper tag to use in this question. What this kind of algorithm is called and how to achieve this?


texts: Metrics for image/visual complexity in computer vision/graphics?

texts:
Could anyone kindly point me to revenant literature in computer vision/graphics that detail on metrics for image/visual complexity and how to regularize that?

More specifically, I am trying to design a neural algorithm for creating business logos and one major difference from image generation problems in CV/CG is the simplicity required of logos. I have been thinking along the lines of adding a visual/image complexity term to be regularized and penalized as the algorithm learns the balance between lower-level style and higher-level meaning/content of multidimensional input images and descriptions. I have been searching along but couldn't find related resources... Could anyone shed some light on that?


texts: What do I need to know about algorithms?

texts:
Drawing from Are algorithms (and efficiency in general) getting less important?, I get that algorithms are more important than ever, but I need to know anything about them other than their complexities?

I would expect to use algorithms out of a library of some sort that has been written by people that are much much more knowledgeable than me, and have been thoroughly tested (most of the STL comes to mind here, but also boost, and probably every other library that someone would care to name).

Thus, unless I am a library maintainer/implementer of some sort, do I need to know anything about these algorithms?


texts: Connected Components - Linear Decision Trees

texts:
What does connected components mean in the context of non-graphs? Graphs have vertices and the vertices are connected by edges. Hence, you can build a spanning tree (for example) by systematically joining connected components (where connected components refer to connected subgraphs).

Previous discussion on this topic reveals that each connected component of a linear decision tree on some function F represents a particular region bounded by a set of half-planes and hyperplanes. For linear decision trees applied to the element uniqueness problem, we have 2 possible type of connected components (correct me if I'm wrong) - YES and NO components.

Apparently there is only 1 NO component, and at least n! YES components when for linear decision trees applied to the element uniqueness problem on a set of "n" distinct items. I can understand the number of YES components (simply permute all items), but I'm not sure why there's only 1 NO component.


texts: Finding any $\epsilon$ vs finding minimal $\epsilon$ for case 3 of Master theorem

texts:
I have a recurrence relation:
$$T(n) = 3T(\frac{n}{4}) + n\lg n$$

and I want to prove that $T(n) = \Theta(f(n))$ using Master theorem. There's also an example in my textbook on this relation, they're choosing  $\epsilon = 0.2$. For example:

$$n^{\log_b a}=n^{\log_4 3} \Rightarrow   n\lg n = \Omega(n^{0.79+\epsilon})$$

Why would we choose $\epsilon = 0.2$, why couldn't we have chosen something like $\epsilon = 0.0001$, wouldn't this already be enough?


texts: Find the minimum amount of swaps in fixed indices to sort an array

texts:
When given the length of a source array, I want to generate the array of swaps that need to be performed in order to sort the source array. I want to make this array as small as possible. Swaps will be performed only if necessary for sorting, as defined by the following function.

def compare_swap(array, a, b):
    if array[a] < array[b]:
      (array[a], array[b]) = (array[b], array[a])

Example

input: 3
Output: [(0,1), (1,2), (0,1)]

What I mean is something like network sorting.

I want to understand how to calculate the number of such swaps and how to generate such array exactly.


texts: Is the Time Complexity of Trial Division Exponential?

texts:
I know that there is already a similar question asked on here, but after reading the wiki page on trial division, I am confused, and the other answer doesn't help. The wiki page states that when doing trial division, "If a variant is used without primality testing, but simply dividing by every odd number less than the square root the base-2 n digit number a, prime or not, the algorithm can take up to about 2^(n/2) time".

Using such a variant, however, why wouldn't the time complexity be O(sqrt(n)) in the worst case? In the worst case you check all the numbers up to sqrt(n). So in the worst case, the algorithm would depend on the sqrt of the number of natural numbers before n, no? Also, would a variant that divides a number n by every natural number less than n until a factor is found in order to determine if n is prime is used be linear in time?

Link to the wiki I'm talking about: https://en.wikipedia.org/wiki/Trial_division (Quote pulled from the section titled, "Speed")

Side Question: Is this post better suited here as a new post, or should I have posted this question as a follow up to the other, similar question on trial division that was posted 4 years ago on here? I'm new here so I'm not sure what's preferred.


texts: For Loop Range with Smaller Number on Right

texts:
Simple question from an algorithm noob...

If $i=1$ then the inner loop will include what I believe to be an invalid range. Is this acceptable pseudocode?

For i=1 to n
  For k=1 to i-1
    ...


texts: Of which Chomsky-type is the language $L = \{a^jb^ic^{2i} | i,j \in \mathbb{N}^0\}$?

texts: At first I thought the language would be context sensitive because it seems that it can be shown with the pumping lemma for regular languages, that it's not a regular language and analogously with the pumping lemma for context free languages, that it is not context free. But it upon further pondering I came up with a pushdown automaton that would match this language. So I'm a bit at loss as to what type of language it is. I hope someone can help.


texts: Logarithms using digit recurrence, how many bits to store in a LUT?

texts:
In a known method for approximating logarithms the following decomposition is adopted (assuming $x \in [1,2)$):

$$
log_2(x) = 1 + \sum_{j=1}^{+\infty} w_i log_2(1+2^{-j})
$$

Where all the coefficients $log_2(1+2^{-j})$ are stored in a LUT table, however for practical reason one can store only values $\psi_j \approx log_2(1+2^{-j})$, this book shows an error bound when the $log_2(1+2^{-j})$ are exactly stored, the error is expressed as absolute error (you can look at the section 5.2 of the book). However it doesn't say anything about how many digits should be stored in the LUT in order to have a required accuracy (you can assume absolute error).

I could try some kind of exhaustive search, but I'm quite sure that has to be some "smarter way" to do that, and perhaps I'm not aware of that...

Is there any further reference you could point me out? If not, how could I approach the problem?

Maybe it is not useful but this method I believe is a particular case of the CORDIC iterations, so if there's a way to derive a bound there probably there's the same thing here.


texts: Clear, complete, proof that a language is Turing Compete?

texts:
I have seen web sites that purport to "prove" that HTML5+CSS is Turing Complete.

I have seen web sites that purport to "prove" that SQL is Turing Complete.

I have seen a bunch of web sites that purport to "explain" what it means to be Turing Complete.

Enough!

Where can I find a book (written by an expert in computability theory) or a peer-reviewed article (in a reputable journal) that shows a proof of, "This language XYZ is capable of describing a computational machine which has the same computational power as a Turing Machine"?


texts: Is there a formal name for this graph operation?

texts:
I'm writing a small function to alter a graph in a certain way and was wondering if there is a formal name for the operation.  The operation takes two distinct edges, injects a new node between the existing nodes of each edge and then adds an edge between the two new nodes.  For example:

add new nodes a and b to the graph
let edge1 = (x,y), let edge2 = (u,v)

delete edge (x,y)
create edges (x,a), (a,y)

delete edge(u,v)
create edges(u,b), (b,v)

create edge (a,b)


texts: How to solve this very complicated assignment problem

texts:
A set of m items need to be placed into n stacks, where m > n. Each stack has z positions. An item has different widths when placed into different positions in a stack.  The width of an item depends only on the position within the stack but not on which stack it is placed in. The width of a stack is the maximum of the widths of z items placed in it.
The objective is to place the items in the stacks so that the sum of the widths of the stacks is minimum. No position in the stacks could be left unassigned. That means we have to choose z x n items out of m items to be placed in the stacks.

I tried to map this problem to different types of assignment problem but could not find one that exactly matches the constraints and objectives.
What would be a good approach to solve this problem?

Edited based on D.W. s comment:
I am looking for a practical solution. The number of stacks n is not large..it would be around 10. The number of positions within a stack, z is at most 36, but 9 is the most frequent number of positions. The number of items m on average is around 100-200. The widths are NOT integers, but floating point values (precision of 0.01 is good enough). I have not tried the integer linear programming approach...I need a very fast solution that can work for online calculation of some scheduling in an embedded system.


texts: How to solve the minimum-cost flow problem on a complete graph, with a concave cost function of flow for each edge?

texts:
Here is the problem:

Input:

A series of source/sink nodes at fixed positions with given outwards/inwards flow
Edges are NOT specified. The edges can connect any nodes.
The  total source and sink flow match
A concave cost function that gives a cost per edge in terms of flow capacity

Expected output:

The minimum costing graph (not necessarily fully connected) that connects all sources to sinks and permits the required flow, without creating extra nodes.

Therefore the network topology is unspecified and should be optimized.

Many thanks.


texts: Prove key of leaf is larger or smaller than key of parent if leaf is largest key in smaller tree or smallest in larger tree with respect to parent

texts:
Show that for any leaf v in a binary search tree, if u is the parent of v, then either key[v] is the largest key in the tree smaller than key[u], or key[v] is the smallest key in the tree larger than key[u].

I don't understand "key[v] is the largest key in the tree smaller than key[u]" and "key[v] is the smallest key in the tree larger than key[u]." Can someone help explain the problem to me?


texts: Mathematically calculating time complexity

texts:
This is a thread about mathematically calculating time complexity of nonlinear functions. I know that those questions were asked a lot, but it didn't make me understand fully the subject.

Also I understand that it's impossible to calculate every function, but usually we can (otherwise we have not been asked to do so on the exam).

I know how to mathematically  calculate the time complexity of the following function:

for(i = 0; i <= n-1; i++) {
    for(j = i + 1; j <= n - 1; j++) {
        // loop body - const O(1)
    }
}

I would calculate it as following: (hope without mistakes)

$$\begin{align*}
    \sum_{i=0}^{n-1}\sum_{j=i+1}^{n-1}1 & \overset{(1)}{=}\sum_{i=0}^{n-1}((n-1)-(i+1)+1)\\
 &=\sum_{i=0}^{n-1}(n-i-1)\\
 &=n\cdot\sum_{i=0}^{n-1}1-\sum_{i=0}^{n-1}i-\sum_{i=0}^{n-1}1\\
 &\overset{(2)}{=}n\cdot\sum_{i=0}^{n-1}1-\sum_{i=1}^{n-1}i-\sum_{i=0}^{n-1}1\\
 &\overset{(1)}{=}n\cdot((n-1)-0+1))-\sum_{i=1}^{n-1}i-((n-1)-0+1)\\
 &=n^{2}-n-\sum_{i=1}^{n-1}i\\
 &\overset{(2)}{=}n^{2}-n-\frac{(n-1)\cdot n}{2}\\
 &=\frac{2n^{2}-2n-n^{2}+n}{2}\\
 &=\frac{n^{2}-n}{2}\\
 &=O(n^{2})
\end{align*}$$

when I use the following equations:

$$\sum_{i=m}^{n}1=n-m+1 \,\,\,(1)$$
$$\sum_{i=0}^{n}i=\sum_{i=1}^{n}i=\frac{n(n+1)}{2} \,\,\,(2)$$

But when I get across with much harder function, as following:

example 1:

int x = 2;
while (n < x) {
    x *= x;
}

example 2;

int i = 1;
while(i < n) {
    if((n – i) % 2)
        i *= 3;
    else
        i *= 2;
 }

I get lost. I really don't know where to start calculating. I always can start inserting different values for n, and guessing the time complexity, but it does not feels right (and also it can be misleading).

Is it even possible to mathematically calculate the time complexity of those examples? how should I approached those questions? Maybe is there somewhere a list of possible tricks?


texts: Minimum cost to convert one array to another

texts:
Given two arrays $A$ and $B$ of integers, both of size $N$, such that for all $0 \le i \le N-1$, $A[i] \ge B[i]$, we have to convert array $A$ to array $B$. For this we can do only one type of operation: choose some $l$ and $r$ ($0 \le l \le r \le N-1$) and set the values of $A[l],A[l+1],\ldots,A[r]$ to $k$, where $k \le A[i]$ for all $l \le i \le r$. Find out minimum operations to convert $A$ to $B$.

I was thinking about dynamic programming solution but could not figure it out.


texts:
I once thought that any analog computer is any computer which "doesn't need electrical current to work".
I once thought that any digital computer is any computer which "does indeed need (a correctly distributed) electrical current to work".
I found out both assertions as wrong.
What are analog and digital in computer science?


texts: Is the reverse of a closed under operation maintainable?

texts:
I'm looking at the following question from this handout:

  The class of decidable languages is closed under union

My question is, does this hold in reverse? Is there a phrase for this?
Basically, if $L_1 ∪ L_2$ is decidable would $L_1$ and $L_2$ be decidable as well?

I believe it does, by making one machine $M$ to emulate both on any given input string and have the following:

Save a copy of input somewhere (multitape)
Run M1
    If it accepts, accept
Reset the tape using copy
Run M2
    If it accepts, accept
Both machines have rejected, so reject

Does this work? If so, would this also apply in the case of intersection as well?


texts:
I have just reached the priority queue section where the book I am currently reading about algorithms talked about max-heaps and min-heaps. As a part of its structure, the book would ask the reader a question about the content of each chapter. In this chapter, the book asked the reader to agree or disagree with the following statement, and asked the reader the following question (included below).

Statement: "Joe made a claim that the minimum element of a max-heap which is binary must be one of its leaf nodes".

Question: "Which of the following statements did you have to assume to hold true in order to make a decisively decide whether the statement above is true/false?"
(1) All nodes in the max-heap should be distinct/unique.
(2) There is only one maximum among the nodes

After some thought, I have agreed with this statement since I know that based on the properties of a max-heap every parent node should be greater than or equal to its children. In order to decide, I had to suppose that (1) is true. Would assuming that (2) is true would also be helpful, or even more appropriate than supposing that (1) is true to come up with a decisive choice?


texts: How to avoid permutations in the n-Queens problem?

texts:
EDIT: if you are not familiar with the problem and the solution, it's nicely explained here.

I have solved the n-Queens problem as an exercise using backtracking (recursion), but the problem I have right now is I get multiple permutations of the same solution:

n = 4
(0,1) (1,3) (2,0) (3,2)
(0,1) (1,3) (3,2) (2,0)
(0,1) (2,0) (1,3) (3,2)
(0,1) (2,0) (3,2) (1,3)
(0,1) (3,2) (1,3) (2,0)
...

For n=4 i get a total of 48 solutions. Of course there are rotations and mirroring which are fine and should be included, but as you can see in the example above permutations of the exact same solution appear.

My program works as follows:

solve(queens){
    if (n_queens_are_on_the_board){
        remember_solution();
        return;
    }
    for(x: 0 to n){
        for(y: 0 to n){
            if(current_position_not_attacked){
                add_queen_to_current_potision();
                solve(board);
                remove_prevously_added_queen();
            }
        }
    }
}

Obviously I can just find the permutations and remove them from the final result, but is there a faster way of getting rid of them or ideally completely avoiding them?

Any help is appreciated.


texts: If I write code in machine language, then I have access to the CPU in both modes (user and kernel), since the OS is bypassed, correct?

texts: Codes written in machine language can have access to both CPU modes (Kernel and user), since the OS is bypassed, correct?


texts: Create a grammar that generate the language a^n . b^m . c^q . d^p such that n + p = q + m

texts:
I'm stuck on this question. I'm struggling on how to keep track of the number of a and d I have generated.

The professor hasn't given the correction.

I have seen similar questions but the condition is different, I can't find the grammar. Is it possible to prove that it is not context free?

EDIT: taking inspiration from other slightly similar solved question, here's my solution, but I think it could be factorized/improved

S -> S1 | S2
// S1 is the case where I will try to pair a with c (i.e when there more c than d), S2 is the case where I will try to pair d with b (i.e when there are more b than a)
S1 -> XY
X -> aXc | Z // for each a generate a c
Z -> aZb | epsilon // for each a generate a b
Y -> cYd | epsilon // for each d generate c
// since all the b's have been generated along with a's, i did not find a way to pair d's with b's
S2 -> UV
U -> aUb | epsilon
V -> bVd | W
W -> cWd | epislon


texts: Given a boolean matrix A of size n, A^p can be computed in space O(log n log p)

texts:
The solution to this problem can be found here. It says:

  To multiply $k$ matrices, we generate the result entry by entry, by running a counter $t$ and generating the $it$th entry in the product of the first $k − 1$ and the $tj$th entry in the last matrix. Inductively, we need to maintain $k$ counters which can be done in $O(k \log n)$ space. Finally, note that using repeated squaring, we can compute $A^p$ using $O(\log p)$ matrices, which are different powers of $A$. To generate each of these matrices, we just need $A$ and a single counter. Hence the total space needed is $O(\log p \log n)$.

What I don't understand is that in the case of multiplying $k$ fixed matrices, they're part of the input tape so no space is needed for them in the work tapes. In the case of the $A^p$ computation, the intermediate results $A^{2^t}$ must be stored somewhere demanding more space. So how can this be done in $O(\log p \log n)$ space?

Thanks!


texts: Interactive proof system for graph nonisomorphism

texts:
$\mathit{GNI} \in \mathrm{PCP}(\mathit{poly}(n),1)$

  GNI is the language of nonisomorphic graphs. Given two grapsh $G_0$ and $G_1$ with $n$ vertices, a verifier expects $\pi$ to contain, for each labeled graph $H$ with $n$ vertices, a bit $\pi[H] \in \{0,1\}$ corresponding to whether $H \equiv G_0$ or $H \equiv G_1$ (arbitrary if neither case holds). Then the verifier can pick a random bit $b \in \{0,1\}$ and a random permutation of $G_b$, $H$. The verifier accepts iff the corresponding bit of $\pi[H]$ is $b$. If $G_0 \not\equiv G_1$ then the verifier accepts with probability $1$ while if $G_0 \equiv G_1$, then the probability of accepting is at most $1/2$.

I was reading this slide and got confused about the following part:

  A bit $\pi[H]\in\{0,1\}$ corresponding to whether $H=G_0$ or $H=G_1$ (arbitrary if
  neither case holds)

But what if both cases hold? In that case, $G_0$ and $G_1$ are isomorphic, and how should we assign the bit? I hope that there's an example.


texts:
I was working through an NFA to DFA conversion tutorial: where I'm converting the following NFA to a DFA:

I used lazy subset construction which I'm sure the tutorial did as well because we had the same transition table of:

delta      |  0        |  1       |
===========+===========+==========+
{a}        |{a,b,c,d,e}|{d,e}
{a,b,c,d,e}|{a,b,c,d,e}|{b,d,e}
{d,e}      |{e}        |{∅}
{b,d,e}    |{c,e}      |{e}
{e}        |{∅}        |{∅}
{c,e}      |{∅}        |{b}
{b}        |{c}        |{e}
{c}        |{∅}        |{b}

However, there state diagram for the resulting DFA is this:

I'm confused as to why the set {b,d,e} isn't being labeled as an accepting state.

Also, I don't know if I'm allowed to ask this but if there is a place with more NFA to DFA converting practice I'd love to know, right now I'm just using any old study guide I can find on google.


texts: Clarification on the definition of strongly NP-hard

texts:
I am seeing two definitions of strongly NP-hard that seem to be slightly different:

A problem is strongly NP-hard if a strongly NP-complete problem has a polynomial time reduction to it.
A problem is strongly NP-hard if it is still NP-hard when all numbers in the input are bounded by a polynomial in the length of the input. Or equivalently, if it is still NP-hard when the input is given in unary.

Wikipedia gives Definition 1, but Definition 2 seems to be more common overall. Both definitions preclude the existence of a pseudo-polynomial time algorithm to such a problem. However, it seems to me that Definition 1 is stronger since there might exist a problem for which there is no pseudo-polynomial time algorithm, but also no strongly NP-complete problem can be reduced to it. This would be a strange problem indeed, but I don't see why it can't exist.

So am I missing something or is one of the definitions slightly off?


texts:
I read about Minterms i.e. sums of products, simplification using
Karnaugh Graph. Can this graph be used for Maxterms, i.e. products
of sums, as well? If yes, then how?

If not, then is there some other similar way to use, for simplification of Maxterms?  I know, one can always convert Maxterms to Minterms and then use K-Map. I mam looking for some direct way.


texts: I know that Graph Isomorphism should be able to be verified in polynomial time but I don't really know how to approach the problem. Any help would be appreciated.


texts: Algorithms / heuristics for a distributed sorting problem

texts:
The setting:

There's a cluster of $k$ computers (= nodes). For simplicity, assume their hardware is identical.
The network topology can be complicated, but let's simplify and assume it's a clique with fixed bandwidth B bits/time unit between each pair of nodes.
Each node has its own limited amount of memory, $M$.
There's a multi-set of $n$ integers (of fixed width $w$ bits), and each node has some of these integers.
The number of elements is not uniform among the nodes.
There are more elements to be sorted than there are cluster machines, i.e. $k < n$, and you may assume $k \ll n$ if you like.
Each node has "scratch space" which is at least $s$ times the average space taken up by data on a node (i.e. at least $snw/k$). So we have $\Theta(n)$ extra space to use, but it's distributed among the nodes.

I'm interested in algorithms for sorting the data. The desire is to minimize  the overall time, with network traffic taking up time according to the stated bandwidth.

Notes:

I haven't defined exactly what each node can do in a given time unit, and that's intentional. Assume the nodes are abstract RAM machines with one operation per time unit, or choose a different model if you like. The real life motivation involves actual full-fledged physical computers in a cluster.
It does not matter which node in the cluster ends up with which elements, provided that the nodes' elements can be concatenated to form a sorted sequence (and each node holds the positions of the elements it holds in this concatenation).
It's useful, though not necessary, for each node to know which other node ends up with which elements.
Randomized algorithms are acceptable, but only Las Vegas rather than Monte Carlo, i.e. the result must always be correct.
Assume there are no node faults and no communication faults.
Node clocks are sort-of-synchronized, but the algorithm shouldn't do anything funny and cute using perfect synchronization.
A node does not and cannot have more than $n_\text{node-max}$ elements - both before and after the sort. i.e. the element distribution skew is bounded.
Algorithms in which the inter-node activity parallelizes well are desirable.
Important: I'm interested two variants of the sorting:

Data becomes sorted among the nodes, but not necessarily within the nodes, i.e. for the appropriate order of nodes and for $x \neq y$ in nodes $v_i$ and $v_j$ respectively -  $x < y$ implies $i \leq j$ (but weak inequality doesn't apply, because two consecutive nodes can have identical values). (obviously, if we reach this state, the rest of the data can be sorted in $\tilde{O}(M/sw)$ by each node performing its own local sort.)
Data becomes completely sorted - within and between nodes.

Finally, if there are similar, related problems you know of but not a solution to mine, leave a comment or speculate in an answer on how they might be adapted.


texts: What is the relation between a programming language and the language of its input?

texts:
I find some references say that

  all the features of programming language fall within what can be captured by context-sensitive grammars. In fact, no programming language known to humankind anything that cann't.

and

  Actually, most of programming language is context-free language.

Q1: Are the claims correct? I did not find some bibiographies about a precise description or even a proof.

Let $\Gamma$ be the alphabet of the instructions of a programming language. Given a specific procedure $P$, all of its control flows belong to $L_{P}$. $L_{P}$ describes how does it control its data.

At the same time, for every $x \in \Sigma^*$, $P$ computes it and gives an output $P(x)$. Assume that $P$ is used to slove a decision problem, i.e., $P(x) \in \{ 0,1 \}$. There is a language $L'_{P} = \{ x \in \Sigma* \mid P(x) = 1 \}$. If we regard $P$ as a machine, $L'_P$ describes the computational power of $P$.

It is obvious that $L_P$ and $L'_{P}$ are totally different.

Q2: What is the relation between $L_P$ and $L'_{P}$? Is there a conclusion such that
$$L_P \in CFL \Leftrightarrow L'_P \in CFL$$
or
$$L_P \in CSL \Leftrightarrow L'_P \in CSL$$


texts: Why are Oracle Separations Counted as Evidence toward Unconditional Separation?

texts: Particularly, we already have some oracle separation results such as $\mathbf{BPP}^A\neq \mathbf{BQP}^A$ [Simon], $\mathbf{NP}^A\not\subseteq \mathbf{BQP}^A$ [BBBV], and $\mathbf{BQP}^A\not\subseteq \mathbf{NP}^A$ [Bernstein and Vazirani]. But given that most problems are non-relativising, how does such oracle separation even counted as evidence of unconditional separation? Or do we need to discuss it case-wisely?


texts: More Information about the Question Answering System called LUKE

texts:
LUKE is a new state-of-art in question answering system and after googled keywords LUKE Studio Ousia NAIST and RIKEN AIP (I suppose LUKE is a colaboration between several research centers) I couldn't find any information.

LUKE is mentioned in the following pages:

https://paperswithcode.com/sota/question-answering-on-squad11.

https://sheng-z.github.io/ReCoRD-explorer/.

Is there here anyone with insider information able to explain LUKE?


texts: Undirected graph whose BFS and DFS trees have roots of degree 2

texts:
Draw a graph on $5$ vertices that satisfies all of the following conditions:

$G$ is an undirected connected graph.
For every node $v∈V$, in the spanning tree received by BFS($v$), $\deg v=2$.
For every node $v∈V$, in the spanning tree received by DFS($v$), $\deg v=2$.

I was trying to draw many graphs but none of them satisfied all of the conditions.
I was also trying to disprove that such a graph exists, but couldn't find any strong claim that I could use for my proof.
Can you give me a hint?


texts: Why is there no extensive Standards Body overseeing ISAs, Bitcodes, Code Representation, etc... as there is in the case of Unicode

texts:
There exist a vast array of prominent bitcode formats, each suited for their specific task:

LLVM IR:

This format is build around a XML like binary streams model, designed to be used as a common compiler target across a multitude of Architectures and languages.
JVM bytecode:

Java compile target, mainly; increasingly reused as a larger target in that ecosystem.
Khronos Spir-V:

Shader language target, graphics hardware abstraction.
Web Assembly:

Built as a target to better integrate ecosystems and existing code within the browser context.
Specialized: (Ex. Lua and Python Bytecodes):

Interpreters generally execute bytecode during execution whether, explicitly or not.

The hardware/ISA ecosystem is equally split, particularly amoung ARM, i386/x86, x86_64, Microchip/Atmel and now Risc-V.
Fragmentation also exists in the computer graphics industry, which in many ways has outpaced CPU growth in recent times.
Hardware Acceleration Layer/API design is primary split between Khronos and Microsoft, but now apple and Google are joining in; Even in the case of the two leading providers, backwards compatibility has proven to be a difficult problem, leading to increased segmentation and overhead.

I only see these problems getting worse in the future with the current state of traditional Moore's Law, increasing use of accelerators and FPGAs, IoT proliferation, diverse memory types and caching mechanisms, hyperscaling, etc...

In the past, segmentation has been forsean and in the case of character set localization, avoided. This is why the Unicode Consortium was Established, independent of any single company/organization. The Unicode Consortium has managed to standardize over 100,000 character encodings to date and this is virtually universal.

Theoretically I see no reason why this cannot be accomplished in the bitcode/turing realm.

https://www.quora.com/unanswered/Why-is-there-no-extensive-standards-organization-for-instruction-set-architectures-ISA-and-bitcodes-as-there-is-in-the-case-of-Unicode-1

In Response to Community:

@Gilles Unicode acts as a super-set of its predecessor, ASCII; it conforms to UTF-8, UTF-16 and UTF-32 standards. Modern microprocessors are no strangers to expanding type codes in their instruction decoding pipelines. Any machine can emulate larger types than its baseline and architecture level support for this is not uncommon.

Reference:

VLIW Architecture
Unicode Consortium


texts:
I understand any fraction to be a quotient of integers which isn't 0, but after coming across the term "float" in various programming languages (such as JavaScript) I misunderstand why it is even needed and we don't say a fraction instead.
What is the difference between a fraction and a float?


texts: How to visualize non-deterministic pushdown automata?

texts:
My friend and I are working on this project for our Formal Languages and Automata class that consists in building a pushdown automaton. A part of the project that is bothering me is how to visualize the automaton in action.

What mean in visualizing is, for example, this, a non-deterministic finite automaton that accepts a*+(a.b)*. You can actually try it here. In the lower left corner there is a input field for the word you wanna try and on it’s right side there is a button that starts the process. For each letter being consumed you have to click once inside the canvas, or you can select the “Leitura automática” button for automatic reading. BTW, the source code is here, even though I don’t expect anyone to understand it, it is not well written and the documentation is almost non-existent (and it’s also written in Portuguese).

I read in the internet about a deterministic PA, but this approach with the single stack is not helpful if I wanna build automata that can follow multiple paths at once(like my finite non-pushdown one, that tests all possible paths at once, instead of trying one and backtracking if it fails). So I don't know if I'm in the right place, but my question is: how can I do something similar for a non-deterministic pushdown automata?


texts: Is unrestricted grammar equivalent to deterministic Turing machine?

texts:
Suppose we have unrestricted grammar but with restrictions on how rules are applied: we take first rule, search in string left to right and apply it as we go. If no match found, we proceed with second rule and so on. Else, if match(es) is found, we return to first rule and start of the string and start loop again.
I have 3 questions:
1. Have anybody studied transformations with similar rules?
2. Which machine accepts language corresponding to such grammars and rules?
3. How one can alter described algorithm to make deterministic Turing machine such a corresponding machine?


texts: Karp hardness of a guarding set in digraph

texts:
Our problem is to decide whether a digraph has a guarding set of size at most $k$. Definitions are following.

A digraph $G(V,A)$ has $V(G)$ as its vertex set and $A(G)$ as its arc set. A guarding set $S\subseteq V(G)$ is a set of vertices such that:

  For each vertex $v\in V(G)$, some of its incoming neighbor $u$ (i.e.
  $(u,v)\in A(G)$) is included in $S$ (i.e. $u\in S$) and some of its
  outgoing neighbor $w$ (i.e. $(v,w)\in A(G)$) is included in $S$ (i.e.
  $w\in S$)

  In case of empty incoming neighborhood or empty outgoing neighborhood,
  the vertex $v$ itself must be included in $S$. In other word, we may think that the incoming neighborhood and outgoing neighborhood of $v$ both include $v$.

Informally, imagine a facility in which one can enter at some entry points and exit at some exit points, a guarding set for this facility needs to be placed at least at some entry point (maybe where one can enter secret area of the facility) and at some exit point (maybe where one can bring out the secrets from the secret areas inside). Hope that this suffices to explain the terminology.

Our problem is now formally defined:

  Input: A digraph $G(V,A)$ and a natural number $k$

  Output: YES if $G$ has a guarding set of size $k$, otherwise NO

What is complexity of this problem?


texts:
I came across this problem which says that given disjoint sets $A$ and $B$ s.t $\bar{A}$ and $\bar{B}$ are both computably enumerable (c.e.), there exists a decidable set $C$ s.t. $A \subseteq C$ and $C \cap B = \emptyset$.

I think one way to construct $C$ is to show that $\bar{A}-\bar{B}$ is c.e., but is the set difference $\bar{A}-\bar{B}$ for this particular case c.e.?


texts: The complement of $\{w: w\text{ has equal numbers of $a$'s, $b$s' and $c$'s}\}$ is context-free

texts: Let $L$ be the language $\{w \mid w \text{ has equal numbers of \(a\)'s, \(b\)'s and \(c\)'s}\}$. Prove that its complement $\overline{L}$ is context free.


texts:
i am new to analysis of algorithm . i am having an if condition.

If (I !=j AND A[i]==A[j])

i am counting the operations as

i) accessing element from Array A[]
ii)compairing i!=j

iii) compairing a[i]==a[j]

according to me this statement is performing 3 Actions. is it so ? if not than please clarify... thanks


texts: Computing FOLLOW sets of left recursive grammar

texts:
Left recursive ambiguous expression Grammar:

$E \rightarrow E+E \mid E*E \mid (E) \mid \mathbf i\mathbf d$

I tried computing FIRST and FOLLOW sets of both left recursive grammar and after eliminating left recursion. In both the cases, I was able to compute FIRST sets successfully, but not FOLLOW sets. I have shown the work I did to compute the two sets below.
Note that to compute FIRST and FOLLOW sets, I followed the rules given in Compilers Principles, Techniques, & Tools Second Edition or The Dragon book

I computed FIRST and FOLLOW sets of left recursive grammar following this post.
Computing FIRST sets:

$First(E)$ = $First(E+E)$ $\cup$ $First(E*E)$ $\cup$ $First\bigl((E)\big)$ $\cup$ $First(id)$
Since $\epsilon\not\in\text{First}(E)$, ignore the rules $E$ $\rightarrow$ $E+E\mid E*E$
Therefore, $First(E) = \{(, id\}$

Computing the FOLLOW sets:

$Follow(E) = First(+E) \cup First(*E) \cup First\bigl()\bigr) \cup Follow(E) \cup$ {\$}
See that there is a recursive $Follow(E)$. I am not sure how to resolve this. I know that, a set does not include duplicates, so no matter how many times I union $Follow(E)$ with itself, the result does not change, though I am not sure if my argument even applies in this case. How do I proceed from here?

Since I was stuck, I tried computing FIRST and FOLLOW sets after eliminating left recursion.
Grammar after eliminating left recursion:

$E \rightarrow (E)E' \mid \mathbf i\mathbf dE'$
$E' \rightarrow +EE' \mid *EE' \mid \epsilon$

Computing the FIRST sets:

$First(E') = First(+EE') \cup First(*EE') \cup \{\epsilon\}$
Therefore, $Fisrt(E') = \{\epsilon, +, *\}$
$First(E) = First\bigl((E)E'\bigr) \cup First(\mathbf i\mathbf dE')$
Therefore, $First(E) = \{(, id\}$

Computing FOLLOW sets:

$Follow(E)$ = {\$} $\cup First\bigl()E'\bigr) \cup Follow(E')$
$Follow(E') = Follow(E) \cup Follow(E')$
Again I am stuck with the recursion issue. How do I proceed from here?

I suppose FIRST and FOLLOW sets do not change with elimination of left recursion, or do they?
If yes, should one always calculate the sets after elimination of left recursion?