texts: How to efficiently specify a MILP constraint with nested AND and ORs

texts:
Let's say I want to set  x1=1 if (x2=1 AND x3=1 AND x4=1) or (x5=1 and x6=1) or (x7=1) else x1=0

All of the xs are binary variables.

My first thought is I have to add 3 additional variables, let's say y1, y2, y3 and 12 constraints like this

3*y1-x2-x3-x4<=0
y1-x2>=0
y1-x3>=0
y1-x4>=0
2*y2-x5-x6<=0
y2-x5>=0
y2-x6>=0
y3-x7=0
3*x1-y1-y2-y3>=0
x1-y1<=0
x1-y2<=0
x1-y3<=0

Is there a more efficient way to tackle this?


texts: Understanding integer factorization is NP

texts: I can see that Integer factorization problem is in NP. I am looking for a simple intuition behind this. For example if we take the problem of sorting the complexity is $n\log n$ for merge/quick sort where $n$ is the number of objects to be sorted. Along that line if take $n$ as the number to be factorized, then factorization algorithm can be run in polynomial time (checking from 2 to $\sqrt{n}$). I understand this is not the case. Please give how to look it this problem compared to that of sorting problem.


texts:
Shouldn't I post this question on mathematics.stackexchange.com?

  Let be an airlaine company which has to affect its aircrew to several flights. We group som flights in subset, every flights of a subset have to be realised by the same aircrew according to the actual possibilites and labour regulations. We provide a list, as rich a way as possible, of those combinations. Let be $E_j$ the $j^{th}$ combination. We associate to $E_j$ a cost $c_j$ that take into account, for instance, the bonuses to aircrew for a time worked that would outreach th norms, etc...

  The problem is to determine the combinations such that all flights are covered and that the cost is the minimal one.

  I have to give a formulation of this problem as a linear programing problem.

The set of flights $V=\{v_1;...;v_m\}$

Let be
$x_j=
\begin{cases}
1 \mbox{ if the combination $E_j$ is taken}\\
0 \mbox{ else}
\end{cases}$

I don't understand the following formulation by my teacher.
\begin{cases}
\min &\sum_{j=1}^{m}c_jx_j\\
&\sum_{v_i \in E_j}x_j&\ge 1\\
\end{cases}

But I quite understand the one given by Vangelis Paschos in Combinatorial Optimization:

  An instance of the MIN WEIGHTED VERTEX COVER. An instance of this problem (given the incident matrix $A$, of dimension $m\times n$, of a gaph $G(V,E)$ of order $n$ with $|E|=m$ and a vector $\bar w$, of dimension $n$ of the costs of the edges $V$), can be expressed in terms of linear program in integers as

  $$\begin{cases} \min &\bar w.\bar x\\
&A.\bar x &\ge \bar 1\\
&\bar x \in \{0;1\}^n
\end{cases}$$

  such that $x_i=1$ if the vertex $v_i\in V$ is included in the solution $x_i = 0$ if it is not included. The block of $m$ constraints $A.\bar x \ge \bar 1$ expresses the fact that for each edge at least one of these extremes must be included in the solution.

But I don't quite understand this notation $\bar 1$

  The feasible solutions are all the transversals of $G$ and the optimum solution is a transversal of $G$ of minimum total weight, that is a transversal corresponding to a feasible vector consisting of a maximum number of 1.


texts: Finding all solutions to subset sum for integers with bounded weights

texts: Suppose I have the set of weights $W = \{w_1,w_2,\ldots,w_{50}\}$ where each $1 \le w_i \le 60$ is an integer.  I am interested in determining all subsets (not just one, and not just the number of them) of $W$ with a fixed sum $s$.  I realize this is obviously NP-hard, but are there some efficient ways (e.g. dynamic programming) to obtain this result for these relatively nice conditions (e.g. only 50 items, weights integer and bounded)?


texts: How do windows executables run on both AMD CPUs and Intel CPUs?

texts:
Do they contain instructions for both CPUs or do the CPUs have the same instruction set?
Assuming they weren't compiled to an intermediate language (although even then, I think the intermediate language compiler has one version for both CPUs).


texts: Reduction from Clique to IS degree at most 4

texts:
This is from the Algorithms textbook by Dasgupta,C. H.Papadimitriou,andU. V. Vazirani question 8.6 (b) that asks:

Edit:

And missing from the pic as @Nathaniel points out in his answer below:
"3SAT remains NP-complete even when restricted to formulas in which
each litteral appears at most twice".

My reduction from Clique:
Definition of clique: fully connected graph/subgraph
So given G=(V,E) and a goal g it returns a clique of size g fully connected.
The complement graph G’ would contain an IS of size g of the same vertices.
So given a graph G, with degree at most 4, as input to Clique, the largest possible clique would be of size 5 vertices per the  definition.  Let's assume g=5 as input to the Clique problem.
Make the complement graph G’ =(V, E’) where uv in E’ not in E and call ISdeg4 on G’ with g=5.
If there is an IS of size g=5 in G’, then those 5 vertices make up a clique in G so return that to Clique.
Else returns no which I can return to Clique.
ISdeg4 is in NP:
Returns a set of vertices which are an IS.
In O(n+m) I can check that none of the v's in the IS have an edge to another v in the IS.
So ISdeg4 can be used to solve Clique problems for G=(V,E) with degree at most 4.
Edit:
The above is not a solution since the reduction from Clique to ISDeg4 only solves a subset of Clique problems where an input G=(V,E) is at most degree 4.
Thus, I want to know if anyone has a reduction from a known NP-Complete graph problem rather than 3SAT-> IsDeg4 which I was able to understand after seeing the solution given by my teacher.


texts: Making 5-tuples out of their respective 4-tuples

texts:
Let's take integer numbers from [1..36]. We can generate 376992 different (order is not important) five-number-combinations like (1,3,5,7,12), etc. Such five-number-combinations always have five distinct (unique) numbers. Each such five-number-combination always contains 5 four-number-combinations (like (1,3,12,7), etc.). All 376992 different (unique) five-number-combinations have 58905 different (unique) four-number-combinations. All these four-number-combinations also have all (four) distinct numbers - being a subset of a set with unique numbers.

Five-number-combinations and four-number-combinations (tuple-4) always have 5 or 4 distinct (unique) numbers respectively. This is prohibited: (1,1,2,3,4) or (2,3,5,2)

Then I take at random approximately half of those 58905 different four-number-combinations - let's call them "unused 4-tuples".

Finally I need to generate all possible five-number-combinations each being such that it always consists of 5 unused four-number-combinations. That is all five four-number-combinations within such five-number-combination are from the "unused 4-tuples" set.

Direct (brute-force) algorithm is like this: I take a set of n=28000 unused 4-tuples, generate all combinations from that set by k=5 (binomial(n,k)) and then check that all five 4-tuples in such combination give exactly five numbers from [1..36] (say, I add individual numbers from every 4-tuple [out of every five 4-tuples] into a set and then check if the set contains exactly five numbers). Having checked all possible combinations (of five 4-tuples) I have solved my task.

The only problem is that binomial(30000,5) = 143368518402340005600  :)))

Could you think of some math trick to somehow sieve and shortcut that process, or maybe a tip to a more clever algorithm?


texts: The subset sum problem is not in P because the question is about lossy compressed data? Why not?

texts:
Where is there a gap or error in my reasoning?
The subset sum problem deals with a set of n numbers, which is the result of lossy compression of an array r of numbers (r = (2^n)-1).
The compression algorithm in brief:

check if the size of the set r +1 is a power of two. If not, terminate compression
check all combinations without repetition of size log2(r+1) if any of them can be decompressed (summing all possible subsets without empty subset) to the set r of numbers. If so, return the combination
if no suitable combination is found, terminate compression.

The subset sum problem is to check whether the set r of numbers (that is, the set of sums of subsets of the set n of numbers) contains the number you are looking for. To do this, you can represent the set r of numbers as an array and search it. Searching the array in the worst case requires checking each element, which is O(r) (for a decompressed set) or O(2^n) (for a compressed set). Faster ways such as binary search are known, but they require knowledge of the ordering of numbers, so that by checking one number we also gain knowledge of where to look for other numbers. Without knowing anything about the ordering of the numbers in the array, you can't search the array faster than linearly, because by checking the numbers one by one, you don't get any knowledge of where the number you're looking for might be.
Does the compressed set of n numbers have information about the ordering of the array of r numbers? No.
The number of possible orderings of a set r of numbers is r!, or ((2^n)-1)!, which is a number greater than n! Pigeonhole principle says that if we have 'a' objects that we put into b drawers and a > b then there must be at least one drawer where there will be at least two objects. According to this rule, the set of n numbers cannot contain explicit information about the ordering of the elements in the array r of numbers, because many orderings of the array r of numbers can be compressed into the same array of n numbers, with the same elements and their ordering, and we do not get any other information besides this set. The ways to generate combinations in the compression algorithm are many, by which we can consider that every ordering of an array r of numbers can be compressed into every possible ordering of a set of n numbers.
If the subset sum problem is in P, then there exists a search algorithm that will answer the subset sum problem in polynomial time calculated from the size of the compressed set of n numbers. From this, we can conclude that to find a number in an array r of numbers in faster than linear time, it is sufficient to subject the array to lossy compression rather than sorting. When we subject the sorted array r of numbers to compression, we retain the ability to search it in faster-than-linear time, despite the fact that the compression was lossy and as a result, we lost ordering knowledge and most of the content knowledge. The data can be reconstructed, but only by generating the sums of every possible subset and sorting them, since we know from principle pigeonhole that the original ordering knowledge has been lost and must be acquired anew.
Losing knowledge of the ordering of an array r of numbers ( and most of its contents) while still being able to search it in faster than linear time does not make sense, from which it follows that there is no algorithm that allows this, which means that the subset sum problem is not in P, and since SSP is in NP then P != NP.


texts: Given L is a regular language, prove that Perm(L) is Context-Free

texts:
Given a regular language $L$ defined over $\Sigma = \{0, 1\}$. We define a new language $$Perm(L) = \{w \mid \exists x \in L, w \in perm(x)\}, $$ where $perm(x)$ is the set of all permutations of the word $x$.
We have to show that $Perm(L)$ is context-free.
I have looked at the properties that neither CFL nor Regular languages are closed under permutation. Also, the problem comes with the following hint.
Hint: Build a PDA for $perm(L)$ which guesses a permutation of the input string and runs the DFA for $L$ on it, and uses the stack to check that it indeed guessed a valid permutation of the input string. The fact that the alphabet has only two symbols will be crucial for the latter check.
I am unable to use this hint to proceed further. Any help is appreciated!


texts: non-binary locality-sensitive hashing with random projections

texts:
I'm interested in using a random projection as a locality sensitive hash. In every example of this I've seen, it is suggested to pick a random hyperplane and produce a binary number corresponding to which side of the hyperplane a data point lies. I want to use locality sensitive hashing with a random projection, but I need to be able to produce more than just two possible indexes.

I'm wondering if I could make an LSH by binning data according to this strategy:

Initialize a d x k matrix, where d is the input data dimensionality and k is the number of hash indexes we want.
Project incoming data into k-dimensional space using this matrix.
Take the argmax of the new k-dimensional vector.  In other words, output the dimension that has the largest value.

If not, does anyone know of another technique? Thanks!


texts:
When defining a Turing Machine formally, you enumerate its states. But I don't understand what states a TM can be in. Reading, Writing, and moving the head are the only ones that come to mind.

Specifically, the turing I am trying to describe behaves like this:

    WHILE the symbol under the FH head is not $ DO
        IF this symbol is not marked 0 THEN write it on the tape
        ELSE write the symbol 1 on the tape
            Read the next symbol (which is a 0) and write a marked 0 on the tape
    Write $ on the tape

Where FH is the reading head which begins on the far left of the tape, and BH is the writing head which begins on the blank space after the last symbol on the tape. Once a cell is read or written into, the head in question moves one cell to the right.

The starting configuration for the TM is this: 100!0110\$ where the 0! indicates that the 0 is a marked symbol. The FH head begins on the first 1, and the BH head begins on the blank cell after the \$. The ending configuration for that TM with that input is then 100!0110\$1010!110\$

So, when describing this TM, what would its states be? Thanks!


texts: Give an NL-algorithm for complement of 2-SAT

texts:
Question1: What is the difference between 2SAT and the complement of 2SAT?

Question2: It is known that NL is contained in P, but what we know about P over NL? can be said that an algorithm that runs in P, uses NL space?

Information That I gather

I follow the Papadimitriou algorithm to solve 2-SAT with
Let give 2-SAT a graph of connected nodes according to the specifications contained literal and clauses where the information of the nodes and connections is a container in a CNF of 2 literals per clause, because of the problem need to be contained in NL we assume that we are only working to solve this in 1 writing tape and 1 only input tape to run the algorithm

    for i=0 repeat log2(n times)
      Choose Random initial assignment for every literal
         Repeat 2n^2
           -If
             The assignment satisfies all the paths in the sequence
             of clauses, Halt and report
           -else
             Pick arbitrary unsatisfied clauses and flip the value of its literals
     Report unsatisfiable

According to 2-SAT reachability one condition for the possibility of no reach, if one path of the graph where there are connected nodes with the same literal and one of them is a negation, then the graph doesn't have a satisfiable result, and that would be the case in the algorithm. This is the same case for a complement of 2SAT.

In the non-deterministic solution, the algorithm could give only a correct answer or a false negative depending on the condition of the arrangement of the clauses, but never retrieve a false positive because of the condition establish in the conditional operator.

With the else clause the algorithms cover different possible clauses fliping the literal where the condition was unsatisfied and trying new options.

The algorithm uses only memory to keep the counter running because the counter corresponds to the size of the input in Log2(n)*2n^2 space on the writing tape.

Also is prove that 2SAT correspond to NL and NL-complete and we know that NL=coNL


texts: Prove that A** = A*, where A is a language over Σ*

texts:
Let $\mathcal A$ be an arbitrary language over $\Sigma^*$

Proof.

To prove, $\mathcal A^{**} = \mathcal A^* $

$\mathcal A^{**} = \left( \mathcal A^0 \cup \mathcal A^1 \cup {...} \cup \mathcal A^n \right)^*$ by definition of Kleene Star

My idea is that Kleene star operation distributes over the union of languages but then, I dont know what to do next.

I need some directions.


texts: reference to model a network which nodes handle processing

texts:
does anybody have a basic reference (if it is possible) that explain how to mathematically model the state of a network. I assume that it goes like modeling a graph that is composed by nodes and edges. I need to handle the process of each node are doing.

What I have already in mind it is:
- each node can execute a set of process.
- the process changes the state of the node.
- each node has a set of states.

So, is it reasonable to say that I will create one graph for each node of my network? In each graph I will describe how all the states of a node will change.

Does anybody has a basic reference of a book that would help me? Currently, I am reading the book "Graph Databases, NEW OPPORTUNITIES FOR CONNECTED DATA".

Kind Regards,
Felipe


texts: Can any memory-less computer operation be represented in propositional logic?

texts:
Take any operation that is done by any type of computer (e.g. a cpu on a modern laptop), which doesn't use any type of temporary memory storage.

I.e. this computer operation computes a function $f(x)=y$, without using any form of memory storage.

  Q1: Is it possible for any arbitrary such $f$ to be represented by a formula $\phi(x,y)$ in propositional logic, such that $\phi(x,y) =True$ iff $f(x)=y$?

What if we relax the requirement that no temporary memory can be used?

EDIT: after reading the responses so far, perhaps it makes sense to phrase the question in the opposite way:

  Q1b: What restrictions on $f(x)$ are necessary and sufficient for it to be representable in propositional logic?


texts: Given a λ-term, can I decide which machine model I need to express it?

texts:
I am having a hard time figuring out the specific relationship, of various things in computability. So we have a hierarchy of machines, with a (real life) upper bound of Turing machines, moving on down to things like deterministic finite automata. We also have a hierarchy of grammars that the machines can implement. These grammars range from recursively enumerable down to things like regular grammars. By implement I mean be configured in such a way that they either accept a string or declare it not part of the language.

The lambda calculus has a grammar. This grammar can be expressed on a low class of machine. The lambda calculus itself though is Turing complete. Clearly the syntax of the lambda calculus has no relationship to the power classification.

While the full lambda calculus is Turing complete you can restrict it in certain ways so that the syntax is the same, but the calculus becomes no longer Turing complete. This is talked about in the Turner paper:

"https://uf-ias-2012.wikispaces.com/file/view/turner.pdf/401400700/turner.pdf".

You could restrict it more, and make it an even weaker machine, until nothing can be expressed. As the version of lambda calculus you are programming in becomes weaker, and weaker, fewer grammars could be implemented.

Noting that the syntax is the same: Given a string representing a lambda expression X. Depending on the content of X only certain classes of restricted lambda calculus (to un-restricted) may be able to execute it. If the expression X requires a Turing machine to implement then a machine restricted to a weaker lambda calculus would not be able to express it.

Is it possible to determine what class of machine is required to express a given lambda expression? Turner in his paper clearly shows that you can restrict the lambda calculus to not require a Turing machine. But just given the expression, can you determine the class of machine?


texts: How does left-factoring prevent backtracking?

texts:
I read that deterministic grammar helps in preventing backtracking.

Consider a grammar

$$A \rightarrow ab \mid ac \mid ad$$.

Here if input is "ad" then the compiler needs to check each of ab, ac .. and backtrack until it gets to last production.

To eliminate non determinism we modify the grammar as

$$A \rightarrow aB$$
$$B\rightarrow b\mid c\mid d$$

I don't understand how will this modified grammar prevent backtracking . If we again give the same input "ad" then in B production , it will again back track for b and c until it reaches d.

So how does left factoring actually solve this problem ?


texts: LP - Dual variable is zero implies primal constraint unnecessary?

texts:
Say I have a primal program P with n variables and c constraints.
Let's say that I have an optimal solution for the dual program D, in which the y1, the variable related to the first constraint in P, is zero.
Does that imply that I could run Simplex on P without the first constraint and get the same optimal solution as if ran Simplex with the first constraint?


texts: Shortest path from starting cell to all cells in the grid

texts:
I found an algorithm for finding the shortest path on grid between selected cell, to all cells on the grid, with $O(KN)$ where $K$ is the number of neighbor cells and $N$ is the number of cells.

How ever if that's true than it's better than A*, Floyd–Warshall and many others. So I probably mistaking some thing. Can you point me what.

Here is a pseudo code for my algorithm, the idea is to calculate simultaneously to all the directions.

The algorithm starts with the call to filter method

class MapFilter
{
    declare cellsMap, array of numbers with two dimensions, that represent a grid
    declare stack, a stack of MapFilter
    declare count of type number
    read input to map, array of Cells with two dimensions, that represent a grid
    read input to x ,y those are coordinates of starting node

    function filter(){
        initialize cellsMap with empty grid, all values are 0
        set count = 1
        set cellsMap[x][y] = 1;
        execute();
        while(stack is not empty){
            read length of the stack to length
            iterate over i from 0 to length{
                remove first element from stack and store it in mapFilter, instance of MapFilter
                mapFilter.execute()
            }
        }
    }

    function execute()
    {
        populate(x + 1, y);
        populate(x - 1, y);
        populate(x, y + 1);
        populate(x, y - 1);
    }

    function populate(x, y)
    {
        // Testing if the x,y cell is blocked by some way
        if( not isInMapRange(x,y) or
            cellsMap[x][y] not empty or{
            return;
        }

        set cellsMap[x][y] to count;
        addTask(x,y);
    }

    function isInMapRange(x,y){
        return x < cellsMap.length &&
            x >= 0 &&
            y < cellsMap[0].length &&
            y >= 0;
    }

    function addTask(x, y)
    {
        initialize mapFilter;

        set mapFilter.map = this.map
        set mapFilter.cellsMap = this.cellsMap
        set mapFilter.count = this.count + 1
        set mapFilter.x = x
        set mapFilter.y = y
        add mapFilter to stack
    }
}


texts: What is the correct term for a probabilistically complete algorithm?

texts:
I'm wondering what the correct term for an algorithm that is probabilistically complete is. An algorithm is probabilistically complete if the probability of finding a solution, should a solution exist, approaches one as the runtime goes to infinity.

A motion planner such as PRM will eventually find a solution if one exists, but cannot show that that no motion exists. This would be similar to an algorithm that semi-decides a problem, but the "yes" output is a trajectory, so it's not really a decision problem. Is there an accepted term for such algorithms? (Something like, PRM is semi-deciding)?


texts: Function that cannot be computed by a Boolean circuit of size $2^n/2n$

texts: Show that, for sufficiently large $n$, there is a function $f\colon\{0,1\}^n \to \{0,1\} $ that cannot be computed by a Boolean circuit with fan-in $2$ with $\frac{2^n}{2n}$ gates. Please give me a hint.


texts:
I am trying to build a bigram letter model.

I obtain a sequence of words in a form of ['hello','I','am','Johnny'].

Firstly, I lower all the words to obtain : ['hello','i','am','johnny'].

I am capable of building a bigram letter model, but I have read somewhere that you should provide some kind of empty strings / padding to the model.

Does anybody know why do you have to provide padding to the input data to build a proper language model? And how to use padding on this sample input to build letter model?

I was thinking about making a space in front of every word, but I am not convinced that this is the right solution - other options that I am considering are adding padding at the end of every sentence or after each sequence of 2 characters as this is a bigram letter model.


texts: Proof that recursive languages are closed under concatenation

texts: I can't figure out a proof that recursive languages are closed under concatenation. I know this is easy for most of the people but unfortunately my professor is not very good at explaining the material. If anybody can provide any hints on how to do it I would greatly appreciate it.


texts:
I have a formal language that describes digit production like

<digit> ::= 0|1|2|...|9

and I need to intruduce fraction to write decimals like 3.14 and so on

What did I do:

<frac> ::= <digit><frac> | .<digit><frac> | <digit>

I feel that the .<digit><frac> part is wrong, as every time we go this production we can substitute this part and get more than a single dot for the decimal part, which is wrong? What is the proper way to handle this?


texts: Algorithm for finding strongest connection for a user on social network

texts:
I am working on Problem 6-1 from MIT's Fall 2011 6.006 course. The problem reads as:

Problem 6-1. [30 points] I Can Haz Moar Frendz?

Alyssa P. Hacker is interning at RenBook (人书 / 人書 in Chinese), a burgeoning social network
website. She needs to implement a new friend suggestion feature. For two friends u and v (friendship is undirected), the EdgeRank ER(u, v) can be computed in constant time based on the interest
u shows in v (for example, how frequently u views v’s profile or comments on v’s wall). Assume
that EdgeRank is directional and asymmetric, and that its value falls in the range (0, 1). A user
u is connected to a user v if they are connected through some mutual friends, i.e., $u = u_0$ has a
friend $u_1$, who has a friend $u_2$, . . . , who has a friend $u_k = v$. The integer k is the vagueness of the
connection. Define the strength of such a connection to be
$$S(p) = \prod_{i=1}^kER(u_{i−1}, u_i)$$
For a given user s, Alyssa wants to have a way to rank potential friend suggestions according to
the strength of the connections s has with them. In addition, the vagueness of those connections
should not be more than k, a value Alyssa will decide later.

Help Alyssa by designing an algorithm that computes the strength of the strongest connection
between a given user s and every other user v to whom s is connected with vagueness at most
k, in O(kE + V) time (i.e., for every pair of s and v for v ∈ V\{s}, compute the strength of the
strongest connection between them with vagueness at most k). Assume that the network has |V|
users and |E| friend pairs. Analyze the running time of your algorithm. For partial credit, give a
slower but correct algorithm. You can describe your algorithm in words, pseudocode or both.

After reading the problem, the first intuition I got is to:

Do a BFS from the source node s and stop the BFS as soon as kth level is reached.
And, while doing the BFS, calculate and maintain the strength that each node encountered has with s
At the end, when the BFS stops after the k levels, we iterate the strengths stored, and find the one with maximum value.

Here is the (pseudo/Python)code for the same:
def find_strongest_connection(graph, source_node, k):
    nodes_discovered = deque()

    # source is already discovered
    strengths = {source_node: 1}
    parents, levels = {source_node: None}, {source_node: 0}
    nodes_discovered.append(source_node)

    while nodes_discovered:
        parent_node = nodes_discovered.popleft()

        current_level = levels[parent_node] + 1
        if current_level > k:
            break

        for current_node in graph.adj[parent_node]:
            if current_node not in levels:
                # current_node is now discovered
                strengths[current_node] = strengths[parent_node] * ER(parent_node, current_node)
                parents[current_node], levels[current_node] = parent_node, current_level
                nodes_discovered.append(current_node)

    strongest_connection, max_strength = None, -1
    for connection, strength in strengths.items():
        if strength > max_strength:
            max_strength = strength
            strongest_connection = connection

    return strongest_connection, max_strength

To me, this solution looks correct. But when I was going through the solutions provided by MIT for the problem set, I see they are first transforming the graph, and then applying the Bellman-Ford's algorithm. What I want to know is that am I missing something really basic in my understanding of the problem and the algorithm that I have come up with?
I am asking this because seeing the complex solution provided in the solution set is making me doubt my overly simple solution. Unfortunately, I cannot think of a case, where my solution would fail. If there is any issue with my algorithm, any hint would be much much appreciated.
PS: I am not a student looking for an answer to my homework. I am a full time working professional.


texts: is a while loop always an indefinite loop?

texts:
Building on this example and others found elsewhere we have two types of loops, definite and indefinite:

definite being a loop that has its number of iterations known before it is executed. E.g. a for loop:

for x in range(1,10):

and indefinite loops which don't have the number of iterations known before it is executed. E.g. this while loop:

while answer <> "Yes":
    answer = input("are you an idiot?")

I'm checking some teaching materials that have an example of a while loop that looks definite to me as by looking at the code you know exactly when it is going to end:

number = 1
while  number <= 10:
    print(number)
    number = number +1

Is this example a definite loop even though we have to do a little work to work out the for loop equivalent?


texts:
Sipser theorem 4.4*
$E_{DFA} = \{ \langle A \rangle \mid \text{A is a DFA and } L(A)=\emptyset\}$ is decidable.

I could not quite understand the solution, I'll quote it:

On input $\langle A \rangle$ where $A$ is a DFA:

Mark the start state of A

Repeat until no new states get marked:

Mark any state that has a transition coming into it from any state that is already marked.

If no accept state is marked, accept; otherwise, reject.

My question is, what does it mean to even 'mark' something in the encoding? how do we do this? The encoding is merely a word from $\{A,c\}$, how would you 'mark' states?


texts: What is the notation for bounding running time in worst case with concrete example resulting in that worst case running time

texts:
I know that Big O is used to bound worst case running time. So an algorithm with running time $O(n^5)$ means its running time in worse case is less than $n^5$ asymptotically.

Similarly, one can say that for example merge sort's running time is $O(n^2)$  which is correct. But we know that there is a better bound for it: $O(n\log n)$. Technically speaking, one can say that every polytime algorithm has running time $O(2^n)$. This is correct, but not useful.

So my question is: what is the notation used for the case of worst case running time such that there exists an input in which the worst case running time happens.

In the merge sort example, one cannot construct an input example so that merge sort would take $n^2$ comparisons, but one can construct an example that requires the number of comparisons being about $n\log n$.


texts: Does a recursive call reset to the beginning of the method if the call is in the middle?

texts: Or does it finish the method? Sorry for noob question.


texts: Language which is recursively enumerable but not recursive

texts: Can someone provide me with some examples of languages which are recursively enumerable but are not recursive. I know that there exist some languages which are not Recursive but recursively enumerable but couldn't find such examples anywhere.. :(


texts: which error is it - a semantic error or a link error?

texts:
I am having a simple doubt in C programming language.

In any simple C code snippet, if by mistake suppose i have written intmain() instead of main().

Then it represents what type of error ?

It will not be a lexical error as compiler will correctly make a token for it and it is also not a syntax error clearly.

I think it is a semantic error as in this phase compiler checks with the meaningful statements, scoping, binding, variable not declared, function not declared, any variable declared twice, etc.

But, on the other hand, I also think it as a linker error as in the semantic phase, it can throw a error that function intmain() is not declared and it is been directly used.

Can anyone make this crystal clear that what is the actual error ?


texts: Solve T(n)=T(√n)+ n using substitution method

texts:
I am confused how to solve this recurrence equn. after a particular step (step involving ? in the picture)

(Plz help me solve the question with same method which I have used and correct if any of the steps are wrong!)

Attached is what I have done so far..


texts: How to prove following two statements are equivalent in Hilbert System?

texts:
statement 1: $Γ$ is satisfiable implies $Γ$ is consistent.

statement 2: If $Γ$ derives $α$ then $Γ$ entails $α$.

I can easily prove statement 1 from 2 , but not 2 from 1 (without using strong completeness theorem).


texts: When and where did Remote Rendering Systems originate?

texts:
Remote rendering is system in which a server (on the cloud, usually) is performing rendering tasks (such as running a video game) and sends the rendering results to a remotely connected, thin device -- the client. This allows the user to run complex 3D rendering application without the need for specialized hardware and/or software.

I have read A Survey of Interactive Remote Rendering Systems, which claims that such systems arose early when computers were not powerful enough to run computationally intensive graphical applications. I have followed the source and read that too, however, neither mention a date nor company or application in which this approach first appears.

Does anyone here know a bit more or have a better idea of when Remote Rendering systems arose?


texts: Is there a search engine over Artificial Intelligence and Machine Learning -related sites?

texts:
Sometimes it is necessary to dig into Artificial Intelligence or specifically Machine Learning problems to make a research. Common googling (in my own experience) usually doesn't help much due to a lot of irrelevant or paid material among the results. Google Scholar in contrast is limited to scientific publications only, sometimes it is too narrow.

I wonder if there is a kind of dedicated search engine over AI- and ML-related sites?


texts: Why does a software video encoder create higher quality output than a hardware video encoder

texts:
It is said commonly that a software video encoder has creates higher quality output than hardware encoder. Higher quality here means higher picture quality at a given bit rate.

Hardware encoders are commonly for realtime usage and some are for mobile applications, then there are trade offs in hardware encoders to get realtime performance and have lower power.

Commonly what exactly is the trade off (e.g. which encoding algorithm parameter) in hardware encoder that makes it have lower quality than a software encoder?

Will simply changing some encoding parameter (and as a result more chip area and power consumption) make a hardware encoder have the same quality as a software encoder?

H.264/H.265 are considered.


texts:
I was trying to prove by induction that
$$
T(n) =      \begin{cases}
       1 &\quad\text{if } n\leq 1\\
       T\left(\lfloor\frac{n}{2}\rfloor\right) + n &\quad\text{if } n\gt1 \\
     \end{cases}
$$
is $\Omega(n)$ implying that $\exists c>0, \exists m\geq 0\,\,|\,\,T(n) \geq cn \,\,\forall n\geq m$

Base case : $T(1) \geq c1 \implies c \leq 1$

Now we shall assume that $T(k) = \Omega(k) \implies T(k) \geq ck \,\,\forall k < n$ and prove that $T(n) = \Omega(n)$.
$$
T(n) = T(\lfloor{\frac{n}{2}}\rfloor) + n \geq c\lfloor{\frac{n}{2}}\rfloor + n \geq c \frac{n}{2} -1 + n \geq n\left(\frac{c}{2} - \frac{1}{n} + 1\right) \geq^{?} cn\\
c \leq 2 - \frac{2}{n}
$$
So we have proved that $T(n) \geq c n$ in :

1) The base case for $c \leq 1$

2) The inductive step for $c \leq 2 - \frac{2}{n}$

Yet we have to find a value that satisfies them both for all $n\geq 1$, the book suggest such value is $c = 1$ which to me is not true since :

$$
1 \leq 1\\1\leq2 - \frac{2}{n}\implies 1 \leq 0 \text{  for n = 1}
$$
My guess would be $0$ but is not an acceptable value; So we just say its $\Omega(n)$ but for $n \gt 1$?Or how can we deal with it?


texts: Finding k-nearest neighbors to a set of nodes in a large graph

texts:
Given a large graph $G=(V,E)$, a set of nodes $S\subseteq V$, the problem is finding the $k$-nearest nodes in $V$ to the nodes in $S$.

Given a pair of nodes $(u,v)$, the distance $d(u,v)$ between $u$ and $v$ is defined as the length of the shortest path between them. Hence, the lower the distance is, the closer two nodes are.

The 1st nearest neighbor $n\in V$ to the set $S$ has the minimum sum of the distance to all the nodes in $S$.

Finding $n \in V$ to minimize $\Sigma_{s \in S}$  $d(s, n)$

I think solving a unique facility location problem with $S$ as the client nodes can be an answer for the problem when k=1. However, it may not provide a correct answer when k>1 since to the best of my knowledge, if the facilities are more than one, the clients are assumed to be served by their closest facility, so the distance of other facilities are not important if there exists a close facility to a subset of $S$ not all of them. However, I need a ranking of facilities while they consider the sum of the distance to all nodes in $S$ for all $k$ facilities.

Example: 1st facility is the closest one to all nodes in $S$, 2nd is farther than 1st to all in $S$, etc.


texts: Can the language of squares be described by a PEG?

texts:
I believe that they can't, but I couldn't find any existing framework for parsing expression grammars akin to the pumping lemma that would allow me to prove it.

The language I'm talking about is

$$\{ww\mid w\in\{a, b\}^*\} $$

Can you help me prove it, or find a PEG grammar that parses the language?


texts: How do you find set of keywords present in set of words in linear time or log time?

texts:
I am trying to optimize a program, where I need to know whether a given set of keywords present in the set of words. I believe using the dictionary is the only way to optimize it. Any other technique so that I can get better time complexity? The below python script is my version of the code, this works for a small sentence with a time complexity O(len(keywords)) +  O(frequency_table CONSTRUCTION TIME).
Space complexity is not a problem, but time.
def cover_test(keys, sentence):
    frequency_table = collections.Counter(sentence)
    count = 0
    for key in keys:
        if key in frequency_table:
            count += 1
    return count == len(keys)

cover_test("word1 word4".split(), "word2 word1 word3 word4".split())
# output
# True, because word1 and word4 is present in the sentense

examples of input

Set of words
['apple', 'green', 'horse', 'ink', 'ball', 'cat', 'dog', 'elephant', 'fun']
Set of keywords
['fun, 'green']

Output for the above input is True
Update: More clarifications:
The goal is to ensure that every word from the keys list is included in the sentence list, in linear or less time complexity.


texts:
My question is a bit on the philosophical side, and there is probably not one single 'correct' answer on this. Nonetheless, I'm curious to hear your opinion...

I'm currently designing a convolutional neural network to locate features in images taken by a microscope. These features are geometrically quite simple and similar to one another, with only minor contextual variations from image to image. When I look at modern general-purpose covnets, they often have tens of convolution/pooling layers, making them a bit heavy. I can imagine that one needs many layers of abstraction when detecting cars, cats, and cods all in once, which are very distinct from one another.

Returning now to my more specialist network: would it need as many conv/pool layers as a general-purpose covnet? Or should I consider a different strategy all together (like having more fully-connected nodes)?

EDIT: Based on the comments, I feel I should rephrase/clarify my question a bit. Recently I looked into the YOLO architecture, which seems to strike a nice balance between accuracy and speed. The original version of YOLO features 24 convolutional layers, and two fully-connected layers. When I ported this architecture into TensorFlow, I noticed my GPU was struggling memory-wise: TensorFlow would give numerous performance warnings related to an insufficient memory pool, and sometimes crash from running out of RAM on the GPU. YOLOv2 only has 9 convolutional layers, and has a smaller memory footprint.

In this paper it is claimed that YOLOv2 is more accurate than its bigger brother on various VOC test sets. However, this page says v2 actually performs a worse than its predecessor in terms of accuracy, because it has fewer layers. These contrasting claims made me wonder if more layers is really better in terms of accuracy.

Turning this question inside-out, one could ask if a deep, memory intensive architecture is really necessary if the problem is relatively simple (like detecting only a single object class, instead of one thousand), while maintaining good accuracy. Intuitively I'd say that the detection of objects defined by fewer features requires fewer layers, but when it comes to deep learning, intuition has failed me on several occasions already.

At present, I have yet to start training with either architecture, so I cannot directly perform experiments on my own input data and compare the outcomes. I had hoped there would be a general rule of thumb or general guidelines for a situation like this. The comments below seem to suggest there aren't. But perhaps after this clarification, someone could offer some more advice.


texts: Is there an efficient algorithm for WEAK-PARTITION?

texts:
Suppose that we are given a list of non-zero integers $(a_1,...,a_n)$ and we want to decide whether there exist $(x_1,...,x_n)$ such that

$x_1a_1 + x_2a_2 + ... + x_na_n = 0$,

$x_i$ $\in$ $\{-1,0,1\}$, with at least one $x_i \neq$ 0.

Note that this is not the same as PARTITION, where the restriction $x_i \in \{-1,1\}$ would give a solution. Of course we should also be aware that with $x_i \in \{0,1\}$ is the NP complete problem SUBSET-SUM. I don't see any obvious way of reducing SUBSET-SUM or PARTITION to this problem. For example, attempting to reduce a 0-1 problem to $\{-1,0,1\}$ problem by appending the list with negative elements appears to accomplish nothing.

The closest problem that I found was described this post, calling the problem WEAK-PARTITION. However, the link that the original poster provided is currently broken.

I would like to know whether there is an efficient (i.e. polynomial time) algorithm known for this problem and whether anyone knows of further references to this problem.


texts:
$L = \{y \in (a+b)^*  \mid  ||y|_a - |y|_b| \leq 10 \}$

Any idea? I have problem with this kind of task.


texts: Specialized Algorithm for Set-Cover with $k=3$

texts:
I know that the Set-cover problem with $n$ elements and a universe of size $N$ is NP complete.
Also, the problem is has parameterized complexity regarding the number of sets $k$ that should cover the whole universe:
There are only ${n \choose k}=\mathcal{O}(n^k)$ different combinations of $k$ subsets.

My specific problem is easily reducible to the set-cover problem with $k=3$.
My approach that iterates over all ${n \choose k}=\mathcal{O}(n^3)$ subsets does not perform well enough.

Is there any specialized algorithm for the 3-set-cover problem?
Ideally, I would like some parameterized algorithm or some potent preprocessing techniques that exploit $k=3$.


texts: Is it possible for a maximum weight edge of a cycle being included in MST?

texts:
Let C be a cycle in a simple connected weighted undirected graph. Let "e" be an edge of maximum weight on C
Which of the following is TRUE?

(A) No minimum weight spanning tree contains e.
(B) There exists a minimum-weight spanning tree not containing e.
(C) no shortest path, between any two vertices, can contain e.
(D) None

This was a question for which I gave the answer A because I thought using Kruskal's algo & since the maximum weight edge is lying on the cycle, we will always have an opportunity to select an edge with lesser weight.


texts:
I was solving some problem from past test, there was this question:
Use the closure property of regular language to show the language $L$ is not regular
$$L =\{ a^3 b^n c^{n-3}  \mid  n>3\} $$
I know how to solve it using Pumping Lemma, but how to solve it with closure property?
Also, I know that to prove that a language L is not regular using closure properties, the technique is to combine L with regular languages by operations that preserve regularity in order to obtain a language known to be not regular, but I can't figure out with whom to combine.
I saw some similar questions but didn't get ideas about how to do this one.
Any hints?
Thanks.


texts: Can a halting configurations of a Turing Machine has the same state of another configuration has?

texts:
At first, I believed since the state a halting configuration is at will be a halting state, whenever a configuration goes into that state, the TM halts.
Hence, there should not exist two configurations that appear at a different time that have the same current state.
However, after reading some introductions of the One-state Turing machine, I start getting confused about my initial conclusion since to my understanding, a one-state Turing machine will have its start state as accept state.
Can anyone explain this to me?
We use the 3rd edition of Sipser's Introduction of Computation as our textbook and here is the definition of a Turing machine from the book:

DEFINITION 3.3 A Turing machine is a 7-tuple, $(Q,Σ,Γ,δ,q_0,q_{\mathit{accept}},q_{\mathit{reject}})$, where $Q, Σ, Γ$ are all ﬁnite sets and

$Q$ is the set of states,

$Σ$ is the input alphabet not containing the blank symbol $␣$,

$Γ$ is the tape alphabet, where $␣ ∈Γ$ and $Σ⊆Γ$,

$δ\colon Q×Γ\to Q×Γ×\{L,R\}$ is the transition function,

$q_0 ∈Q$ is the start state,

$q_{\mathit{accept}} ∈Q$ is the accept state, and

$q_{\mathit{reject}} ∈Q$ is the reject state, where $q_{\mathit{reject}} \neq q_{\mathit{accept}}$.


texts:
I have a group of logical conditions and need to deduce values that would NOT satisfy them.  For example:

City != New York && Location = Museum
City = New York && Location = Store
City != New York && Location != Subway
Elevation = 100'

So some values that would NOT satisfy any of those conditions are:

City: New York, Location: Museum, Elevation: 110'
City: Moscow, Location: Subway, Elevation: 110'

I just need to derive values, any values, that will fail to satisfy all conditions.  (Application: Generating manual tests.)

It's easy to figure out values to violate any one condition, but I'm having trouble coming up with an algorithm to generate values that will violate them all.  I have all the logical conditions in a data format (JSON, e.g. { key: 'City', operator: '=', referenceValue = 'New York' }).

This solution worked for me, but I'm not making it an answer because it's not super-elegant and I'm not sure it would work in all cases.

Create a value hash for each key, populating it with all possible values for that key.
Each value for each key is marked ALLOWED initially, but can later be marked CONTINGENT or DISALLOWED. (I created a ValueDisposition class to manage this.)
Find relevant conditions for each key, and analyze their effect on values.  For example analyzing condition 4 above for elevation would mark 100' as DISALLOWED (because we are looking to find data that violate all the given conditions). Analyzing condition 2 above for City would mark New York as CONTINGENT because it is only a valid value if the contingent condition Location = Store is violated (I record contingent conditions in the ValueDisposition class as well).
Do a first pass finding an ALLOWED value for as many keys as possible.
Do a second pass on CONTINGENT values, violating the contingent conditions to derive acceptable value-sets (for example, with New York it's easy to violate Location = Store). I was able to do this easily for all of my condition-sets, but this could get challenging (requiring recursion?) if you had contingent conditions involving multiple keys.


texts: What is Round Robin's behavior when a process comes at the same time that the old process is swapped out?

texts:
Let's say there are two processes: p1 and p2, their arrival time and service time are 0,2 and 3,1 respectively.  The time quantum is 2s.

After excuting for two seconds, will the processor excute p2 or continue excuting p1?


texts: How can you see which points in the spectrum is from which pixel in the original image?

texts:
Take the image and spectrum below.
If I look at the spectrum, it just look like noise....
How to make sense of it intuitively?

Image:

Frequency spectrum of image (using Fourier Transform):


texts: Time estimation for successful brute force attack

texts:
If I have a password  =

"passwordPASSWORD"

and the time it takes to encrypt the password successfully is:

353259.545 nano seconds

is there a formula that can work out the time taken to successfully conduct a brute force attack on the password?
I was thinking:

AvrgTimeToEncrypt^PasswordType x PasswordLength ?


texts:
Let
$T(n):=\begin{cases} \frac{2+\log n}{1+\text{log}n}t(\lfloor\frac{n}{2}\rfloor) + \log ((n!)^{\log n}) & \text{if }n>1 \\
1 & \text{if }n=1
\end{cases}$

I need to prove that $t(n) \in O(n²)$, thus $t(n) \leq c\cdot n²$

I asked the question here and I got really great help last time, the thing is after I was shown last time that $f(n)=\log(n)\cdot\log(n!)$ is $\Theta(2\cdot\log(n)\cdot n) = \Theta(\log(n)\cdot n)$ I thought I could then use the master theorem

However since $a=\frac{2+\log n}{1+\log n}$ is NOT a constant I can not use the master theorem
but I thought that I could use an upper bound for $a$, since $\frac{2+\log n}{1+\log n} < 2 \quad\forall n$ and then use the master theorem for $a=2$, $b=2$. But am I allowed to use the master theorem after finding an upper bound for the non-constant $a$?

What would other ways be to show that $T(n) = O(n^2)$ ?


texts:
$T(n)=\sqrt{2T(n-1)}$
what will be the time complexity if $T(n)$ is given as this?
I tried substitution but no result was reached.


texts: Proving that the Bellman-Ford algorithm contains negative circuit

texts:
Let $D=(V,B), n=|V|$ be a directed graph. Then the graph contains a circuit of negative length from $s$ if and only if $f_n(v) \neq f_{n-1}(v),$ where $v \in V,$ and $f_k(v)=$min$\{l(P)|P$ is an $s-v$ walk traversing at most $k$ arcs }.

I do not understand what a $s-v$ walk means and what is the meaning of the function $f_n$.

Can somebody help me prove the two directions of the above statement  ? Many thanks.


texts: Subtyping relationship in a simple type system

texts:
This example is from Algebraic Subtyping, p. 14. Let's say we have a type system with just function types, $\bot$ and $\top$; propositions involving type variables are defined by quantification over ground types.

I understand why $$(\bot \rightarrow \top) \rightarrow \bot \leqslant (\alpha \rightarrow \bot) \sqcup \alpha$$ holds. But how do I convince myself that it no longer holds when the type system is extended with a more general function type $\tau_1 \xrightarrow{\circ} \tau_2$ (for example, a function with possible side effects)?

The specific counterexample given in the text is $\alpha = (\top \xrightarrow{\circ} \bot) \xrightarrow{\circ} \bot$. But I don't understand why it's so obvious that this is a counterexample.

Also, I don't understand how to check whether $\alpha = \bot \xrightarrow{\circ} \top$ is a (simpler) counterexample.


texts:
I am having a problem trying to solve a question on a past paper asking to design a security lattice. Here is the question:

  The AB model (Almost Biba) is a model for expressing integrity policies rather
      than confidentiality. It has the same setup as Bell-LaPadula, except that $L$ is now a set of
      integrity levels which express the degree of confidence we have in the integrity of
      subjects and objects. Subjects and data at higher integrity levels are considered
      to be more accurate or safe. The set of subjects and objects may also be different,
      for example, programs are naturally considered as subjects.

  Often, the set $L$ is actually a lattice of levels, with two operations: least
      upper bound $l_1 \vee l_2$ and greatest lower bound $l_1 \wedge l_2$, where $l_1, l_2 \in L$.

  i. Design an example integrity lattice for AB, by combining two degrees of
          data integrity dirty and clean and two means by which a piece of input
          may be received, website (external user input from a web site form) and
          dataentry (internal user input by trusted staff).

I have been looking for an explanation on how to build lattices but can't seem to find one on the internet or in textbooks. Can anyone point me in the right direction?


texts: Recommendation book to learn how computers work at a transistor level

texts: I would like to know your book recommendations / popular books to learn how computers perform operations, store memory, process your mouse input to open a program for example (maybe not that complicated) at transistor / logic gate level


texts:
This was the initial CFG (starting symbol is I):

I → aAB
A → BAb | ε | B
B → a | b | CD
C → ba
D → DD

And this its CNF:

X → a
X'→ b
I → XY
Y → AB | a | b | X'X
Y'→ BA | a | b | X'X
A → Y'X' | a | b | X'X
B → a | b | X'X

Is it correct?


texts: Proving reducibility of a language to another language

texts:
I am self-studying formal languages and want to solve an example problem. Given formal languages $A,B\subset\Sigma^*$ over an alphabet $\Sigma=\{a,b,c\}$ with
$$A=\{\omega\in\Sigma^*\vert\left|\omega_a\right|=\left|\omega_b\right|=\left|\omega_c\right|\}$$
and
$$B=\{a^ib^jc^k\vert i,j,k\in\mathbb{N}\}$$
where $\left|\omega_n\right|$ denotes the number of $n$s in the word $\omega\in\Sigma^*$, I want to prove that $A$ is reducible to $B$, i.e. that there exists a computable (total) function $f:\Sigma^*\rightarrow\Sigma^*$ for which it holds that $\omega\in A\iff f(x)\in B$ for all words $\omega\in\Sigma^*$.

I think a suitable function would be given by $f(\omega):=abca^{\vert\left|\omega_a\right|-\left|\omega_b\right|\vert}b^{\vert\left|\omega_b\right|-\left|\omega_c\right|\vert}$, for which the required equivalence obviously holds. But it is not clear to me how I would best prove that this function is (Turing-)computable. Do I have to produce an explicit Turing machine which takes a word $\omega$ as input and outputs $f(\omega)$, or is there a more straightforward way? Also, is there a way to intuitively see that this function is computable?


texts: Algorithm to calculate numbers of 10^x smaller than given one

texts:
I am struggling to create a smart algorithm. Currently I have produced one which is super-ugly and not efficient because I am casting numerics to strings back and forth, not really useful to share it here.

The point of algorithm is to get a number 10^x which is smaller than a given one.

Examples:

600 => 100
34.54 => 10
7.2 => 1
0.123 => 0.1

I am sure I am missing something. Is there any smart way of doing that?


texts:
So I have done part a) but I have no clue what I am supposed to do for part b), I have been trying for days to wrap my head around and even asked my fellow course mates, none of which seem to know themselves.

The way I understand it they give me automaton of

  a->b->c

But what do they mean about the next state a',b',c' automaton for which is not displayed.


texts: How can I take advantage of the capabilities of a cluster

texts:
I'm developing a model in C, and I need to run a couple of simulations (lengthy, and heavy ones). I seem to have a cluster at my disposal, but I'm not very familiar with the concept. I understand that there are different "nodes" ? My program is not designed to take advantage of this individually - it can't event take advantage of multiple processors, because the calculations have to be done in sequence. But I have to run multiple instances of the program, and I was hoping there'd be a way to run them on separate "nodes" (?) to avoid them having to share CPU time too much.

What I know : the cluster runs Red Hat Enterprise Linux for Servers 5.3.

Can anyone help?


texts: Precisely when and where was Feynman's Computer Heuristics lecture given?

texts: Feynman's Computer Heuristics lecture was apparently given at the Esalen Institute, Big Sur, California, in 1985.  But I have no formal evidence of this.  Has anyone ever cited this lecture that you can point out?


texts: Finding $k$ claws ($K_{1,3}$ bipartite graphs) in a graph?

texts: Usually questions deal with claw-free graphs, but suppose we are given a graph $G$ and there are $k$ vertex-disjoing claws in the graph, how can we derive a randomised algorithm using color coding to find them. My intuition is to approach this with $k$ colors, but not really sure how to start it. Could someone give me some hints and ideas on how to approach this?


texts: Confused about substitution in grammar in certain cases

texts:
To illustrate my confusion let's say I'm given this unambiguous grammar in BNF:

         S ::= T O x
         T ::= empty
         T ::= "if" E "then" T x "else" T
         O ::= empty
         O ::= "if" E "then" T O

Here is the corresponding derivation tree:

                                         S
                     ____________________|______________________
                    /                    |                      \
                   T                     O                       x
                   |         ____________|_________________
                 <empty>    / |  |             |           \
                           if E then           T            O
                                       ________|_______     |
                                      / |  |   | |  |  \ <empty>
                                     if E then T x else T
                                               |        |
                                            <empty>  <empty>

Why couldn't we have this:

                                         S
                     ____________________|______________________
                    /                    |                      \
                   T                     O                       x
                   |         ____________|_________________
                 <empty>    / |  |             |           \
                           if E then           T            O
                                       ________|_______     |
                                      / |  |   | |  |  \ <empty>
                                     if E then T x else T
                                               |        |
                                       ________|_______ \
                                      / |  |   | |  |  \ <empty>
                                     if E then T x else T

Why is the first T <empty>? What are the rules that govern how you substitute the definitions in the graph.


texts: Existence of a CFL $L$ such that $\sqrt{L}$ is not CFL

texts:
Does there exist a CFL L such that the language defined as $L' = \sqrt{L} = \{w | ww \in L\}$ is not CFL? I feel that there is no such $L$ but obviously, I am unable to prove it.
I am sorry but I have not made any mentionable progress with my attempts on this problem.
I would appreciate any hint to the proof or a language $L$ that could satisfy this.


texts: Confusion about the definition of the average-case running time of algorithms

texts:
In this lecture note,

  The average-case running time is defined by the expected value, over all inputs $X$ of a certain size, of the algorithm's running time for $X$:
  $$T_{\text{average-case}}(n) = E_{|X| = n}[T(X)] = \sum_{|X| = n} T(X) \cdot Pr[X].$$

This wiki article (Quicksort) gives an average-case time complexity analysis for Quicksort:

  When the input is a random permutation, the rank of the pivot is uniform random from $0$ to $n − 1$. Then the resulting parts of the partition have sizes $i$ and $n − i − 1$, and $i$ is uniform random from $0$ to $n − 1$. So, averaging over all possible splits and noting that the number of comparisons for the partition is $n − 1$, the average number of comparisons over all permutations of the input sequence can be estimated accurately by solving the recurrence relation:
  $$C(n) = n - 1 + \frac{1}{n} \sum_{i=0}^{n-1} (C(i)+C(n-i-1)).$$

My confusion is how does the average-case analysis for Quicksort fit the definition above? First, I would expect a term $\frac{1}{n!}$ (which is $Pr[X]$) in the recurrence. But, it is not the case. Second, the analysis above is on a random permutation and the averaging is done over all possible splits. How is this related to averaging over all possible inputs? Do I need another definition for average-case running time?


texts: distinction between $\textbf{P}^{\# \textbf{P}}$ and $\# \textbf{P}$-Complete

texts:
We know that $\# \textbf{P}$ is closed under polynomial sums, i.e., sum of polynomially many $\# \textbf{P}$ functions is still in $\# \textbf{P}$.

Functions in $\textbf{P}^{\# \textbf{P}}$ are those which make polynomially many (non-parallel) queries to an oracle for a $\# \textbf{P}$-Complete problem. So, the computational complexity of such problems must be a sum of polynomially many $\# \textbf{P}$ functions. Due to the closure property, this sum will be in $\# \textbf{P}$.

If the above is right, then:
What is the difference between the classes $\# \textbf{P}$-Complete and $P^{\# \textbf{P}}$ ?

Thanks.


texts: Algorithm for length of longest common subsequence

texts:
The case of multiple strings. A slight modification of the dynamic programming algorithm for two strings is used as a subroutine. Here is the pseudo code:

# The modified dynamic programming algorithm for longest common subsequence.
# Inputs: x, y - the strings
          xL, yL - their respective length vectors
lcs(x, xL, y, yL)
    u = |x|
    v = |y|
    T = 2-dimensional table with default value 0 for all elements.
    for i in 0..u-1
        for j in 0..v-1
            if x[i] == y[j]
                T[i, j] = T[i - 1, j - 1] + 1
            else
                T[i, j] = max(T[i - 1, j], T[i, j - 1])
            # limit the value of the table element by the length vectors:
            T[i, j] = min(T[i, j], xL[i], yL[j])
    # Take the element wise minimum of the vectors for each of the strings and the bottom row and right-most column respectively.
    return x, element-wise-minimum-of(xL, T[_, v - 1]), y, element-wise-minimum-of(yL, T[u - 1, _])

# Algorithm to compute the length of the longest common subsequence of multiple strings.
# Inputs: strings - a list of strings
mlcs(strings):
    if for any string x: |x| == 0
        return 0
    R = a dictionary indexed by a string x, where the value is initialized to be the length vector of x (initially [1,2,..,|x|]).
    N = initially a copy of R.
    while true
        for i in 0..|strings|
            for j in i + 1..|strings|
                x, y = strings[i], strings[j]
                _, xL, _, yL = lcs(x, R[x], y, R[y])
                R[x], R[y] = xL, yL
        if for every string x: N[x] is element wise equal to R[x]
            break
        else
            N[x] = R[x]
    return the last element of any of the vectors in R

What follows is an implementation in the python language.

import collections

def lcs(x, xL, y, yL):
    u = len(x)
    v = len(y)
    T = collections.defaultdict(int)
    for i in range(u):
        for j in range(v):
            if x[i] == y[j]:
                T[i, j] = T[i - 1, j - 1] + 1
            else:
                T[i, j] = max(T[i - 1, j], T[i, j - 1])
            T[i, j] = min(T[i, j], xL[i], yL[j])
    return (x, [min(xL[i], T[i, v - 1]) for i in range(u)]), (y, [min(yL[j], T[u - 1, j]) for j in range(v)])

def mlcs(strings):
    if any(len(x) == 0 for x in strings):
        return 0
    R = {x: list(range(1, len(x) + 1)) for x in strings}
    N = {x: R[x] for x in strings}
    while True:
        for i in range(len(strings)):
            for j in range(i + 1, len(strings)):
                x, y = strings[i], strings[j]
                (_, xL), (_, yL) = lcs(x, R[x], y, R[y])
                R[x] = xL
                R[y] = yL
        if all(all(N[x][i] == R[x][i] for i in range(len(x))) for x in strings):
            break
        else:
            for x in strings:
                N[x] = R[x][:]
    return R[strings[-1]][-1]

The idea is to initialize for each input string a vector which holds information for each position of that string about what is the maximum length of a LCS up to that position. These are updated each time a pair-wise LCS computation is done. This in turn is done for all pairs until all the vectors are stable (ie. don't change) between iterations.

So far testing gives me mixed results. The correct length at first seems to be produced pretty reliably, but when trying to use the function mlcs as an oracle in an algorithm for retrieving an actual longest sequence, sometimes the result is not what is expected. This may or may not indicate that there are cases for which an incorrect length is produced.

So on to the question: Is the idea of the length computing algorithm sound?


texts: What's the purpose of ANDing a bit mask with all bits set to a value?

texts:
I'm adapting an algorithm for calculating a CRC 16-bit CCITT (XModem) value from an ASCII input.  I've found some code here. I'm using the function the poster has in his question, but I've noticed at the bottom he does this:

calcrc = crc And &HFFFF

What's the purpose of applying such a bit mask that is all 1s to a value?  Doesn't that just return the value again?


texts: Count the number of ways numbers 1,2,…,n can be divided into two sets of equal sum

texts:
count the number of ways numbers 1,2,…,n can be divided into two sets of equal sum.

This is my recursive algorithm, what is wrong here?:

int f(int sum,int i){//sum is the current sum, i is the current indx (<=n)
    if(i>n){
        return ((2*sum)==(n*(n+1)/2));//ie sum==totalsum/2
    }
    int cnt=f(sum,i+1)+f(sum+i,i+1);//move to i+1 or add i to sum and then move to i+1
    return cnt;
}

For example, if n=7, there are four solutions:
{1,3,4,6} and {2,5,7}
{1,2,5,6} and {3,4,7}
{1,2,4,7} and {3,5,6}
{1,6,7} and {2,3,4,5}
ie f(0,1)=7

Answer is f(0,1) for any n (n is globally defined)

Thanks!


texts:
let us assume that:
 f is a grayscale image of size NxN, and F is the Fourier transform of f.

G is a 2Nx2N transform obtained by inserting 0 between every value in F:

What is the inverse transform of G?

solution:
so i have programmed it, and the picture will be 4 times bigger with the picture 4 times in it. g= [f f;f f]
can you please explain why this is the answer?


texts: Why is $L= \{ 0^n 1^n | n \geq 1 \}$ not regular language?

texts:
I'm looking for intuition about when a language is regular and when it is not. For example, consider:

$$ L = \{ 0^n 1^n \mid n \geq 1 \} = \{ 01, 0011, 000111, \ldots \}$$

which is not a regular language. Intuitively it seems a very simple language, there doesn't seem to be anything complicated going on. What is the difference between $L$ and a regular language like:

$$L' = \{ w \mid w \text{ does not contain } 11 \} = \{0,10\}^*\cdot (1 \mid \varepsilon).$$

I know how to prove that $L$ is not regular, using the Pumping Lemma. Here I am looking for intuition about what makes a language regular.


texts: Expected number of maximal cliques in $G(n,p)$

texts:
The $G(n,p)$ random graph model creates graphs with $n$ vertices and each possible edge exists independently with probability $p\in (0,1)$.

Much is known about the (expected) size of a largest clique in these graphs, and it has been shown that the expected number of maximal cliques of size $d$ is

$${n\choose d} p^{d \choose 2} (1-p^d)^{n-d}.$$

To find the expected number of maximal cliques,  just sum over all values of $d$ to get

$$\mu (G(n,p)) := \sum_{d=1}^n {n\choose d} p^{d \choose 2} (1-p^d)^{n-d}.$$

I'm interested in the asymptotic growth of $\mu (G(n,p))$ as a function $n$. For example, if $p$ is fixed, does $\mu$ grow polynomially in $n$?

A quasi-polynomial bound is not hard to show. Since the expected maximum clique size is roughly $\omega(G(n,p))\approx\frac{2 \log n}{\log(1/p)}$, the number of cliques (not necessarily maximal) is $O( {n \choose \omega(G(n,p))+1}) = O(n^{\omega(G(n,p))+1})=O(n^{\frac{2 \log n}{\log(1/p)}+1})$.


texts: What is the point of an active shape model in facial recognition?

texts:
From what I understood, the Active Shape Model (ASM) is used in facial recognition. I figured out how the ASM works but I don't get why we use it.

How this shape is suppose to be interpreted for facial recognition? Should it be compared directly to the database?

I have read many research papers about ASM and facial recognition but none of them explains the point of it.


texts: Why is the following language not context-free?

texts:
$L = \{a^n b^m | m \not= n^2 \}$
I guess I need to use Pumping Lemma for CFL in order to prove this. But I'm stuck.

Assuming that $ a^n b^m = uvxyz$, we know that $v$ or $y$ can not have both $a$ and $b$ symbols in them. Otherwise pumping would generate strings not of the form $a^i b^j$.

Hence both $v$ and $y$ must consist only of one kind of symbol each.
Beyond this I wonder what string in $L$ has to be chosen in order to pump and obtain something of the form $a^n b^{n^2}$.

Alternative idea : Assuming that $L$ is context-free, then I must have a PDA accepting it by final state. Can I say that this PDA can be adjusted* to accept $L'$ i.e., all $a^n b^{n^2}$ ? However I know that $L'$ is not a CFL. Hence, contradiction ?

*Adjusted = Make the non-final state on reading $a^n b^{n^2}$ as final and the rest as all non-final.


texts: Problems that provably require quadratic time

texts:
I'm looking for examples of problem which has a lower bound of $\Omega(|x|^2$) for input $x$.

The problem needs to have the following properties:

$\Omega(n^2)$ runtime proof for any algorithm - first priority is to have as simple as possible lower bound argument.
$O(n^2)$ algorithm, if possible, simple one as well.
Output size of $O(n)$ (or smaller). Obviously any problem which requires $\Omega(n^2)$ lengthed output required at least similar run time, but that's not what I'm looking for. Notice that any decision problem fits here.
(if possible) a "natural" problem. Without a formal definition, a problem any CS graduate would recognize is preferable.

I was recently asked about such problem but couldn't come up with a simple one. The first problem that came to mind was $3SUM$, which was conjuctured to be a $\Omega(n^2)$ runtime problem. This was not simple enough and furthermore, the conjucture was recently proven false :o.

Going to an extremely unnatural problem, I believe that the problem that gets as an input a deterministic TM and input $\langle M \rangle,x$, and outputs the position of the tape head after $(|M|+|x|)^2$ steps when it's running on $x$ probably answers the question.

If you absolutely need to, lets agree that we're using the single-tape TM model, although I prefer problems whose runtime is independent on the exact model (as long as it's a reasonable one).

So, can we find a simple (to prove), natural (well known) problem whose runtime is $\Theta(n^2)$?


texts:
The problem:

There are $N$ houses for sale. The $i$-th house costs $A_i$ dollars to buy.
You have a budget of $B$ dollars to spend.
What is the maximum number of houses you can buy?

There is an intuitive way to solve this problem in a greedy way: we must at first sort the house costs and then buy houses until we are out of money and it works.
and the proof is:

Let's prove the correctness of this greedy algorithm. Let the
solution produced by the greedy algorithm be $A = \{a_1, a_2, \ldots, a_k\}$ and
an optimal solution be $O = \{o_1, o_2, \ldots, o_m\}$.
If $O$ and $A$ are the same, we are done with the proof. Let's assume that
there is at least one element $o_j$ in $O$ that is not present in $A$.
Because we always take the smallest element from the original set, we
know that any element that is not in $A$ is greater than or equal to any
$a_i$ in $A$. We could replace $o_j$ with the absent element in $A$ without
worsening the solution, because there will always be element in $A$ that
is not in $O$. We then increased number of elements in common between $A$
and $O$, hence we can repeat this operation only finite number of times.
We could repeat this process until all the elements in $O$ are elements
in $A$. Therefore, $A$ is as good as any optimal solution.

I don't understand the proof and I have couple of questions:

What does it mean to replace $o_j$ with an absent element in $A$?
Why do we need to do it?

Could you explain this proof in a simpler way with examples?
You can see this problem here.


texts: What's the official name of "New" page replacement algorithm?

texts:
I am studying some page replacement algorithms.

I found an interesting algorithm called "New" algorithm.

From page 17 of this slide (https://web.stanford.edu/class/cs346/2015/notes/Lecture_One.pdf)

The algorithm guarantees that each relation has a working set by subdividing the buffer pools.

I want to read the published paper that presents this algorithm

But I failed to find it after spending multiple hours...
(The google cannot find it.. because of its name?)

Does any one know the related paper?


texts: Determining if a langage defined by a given context-free grammar is finite using the pumping lemma

texts:
Here is a question that I found into an old exam:

  Describe an algorithm that, given a context-free grammar $G$, can determine if the language $L(G)$ produced by $G$ is finite or infinite.
  Hint: use the pumping lemma.

While I found several possible solutions to the problem (mostly exploiting the presence or non-presence of cycles in the grammar or automata) none of them implies the use of the pumping lemma (that was given as hist).
For this reason I believe that none of the solutions that I found corresponds to the intended one.

Is there any way an algorithm could exploit the pumping lemma in order to solve this problem?


texts: Where can I find rules for source to source transformation optimization rules?

texts:
Upon reading  Do source code optimizers exist? I knew that such programs existed but the ones I have worked with use a set of rules to drive a transformation algorithm. Ira Baxter provided a link to the tools running the algorithms with his answer but what I was more after from the question was the rules. In the comments Ira noted the  Irvine Program Catalog.

Are there any more papers, sites, etc. that list such rules?

I will accept any answer but have a preference for rules used with functional languages.


texts:
In the paper, Paxos Made Simple, Lamport describes a round of Paxos as two phases: a $prepare$ phase, and an $accept$ phase. An instance of Paxos can have multiple rounds. Can a round have multiple proposers make proposals, or is it strictly one proposal per round?

In addition, I found a number of sources which indicate there are three phases in Paxos: an $accept$ phase, $propose$ phase and a $learning$ phase, in which a distinguished learner informs all other participants of the chosen value. For example: http://pdos.csail.mit.edu/6.824-2007/labs/lab-8.html

Which is true?

If we do require three phases, in which a distinguished learner informs all other participants of the chosen value, does Paxos then guarantee that all nodes agree on the chosen value? What about the minority of acceptors that did not accept the value? Does the distinguished learner inform them too?


texts: Is this a valid representation of a function in Lambda Calculus?

texts:
Let's say I want to define a function:

This function multiplies an input by two, adds one to this integer, then divides it by two in that order.

f represents the multiplication, g represents the addition, and h represents the division.

Could I represent this as λx.fxgh, when explicitly defined with parentheses is shown as λx.(((fx)g)h))?

I would think that is correct, because you evaluate the innermost function first, then move outwards treating each evaluated function on the inside as input for the next one, no?


texts: Coordinate descent for Lasso, Question about algorithm

texts:
I'm not sure why the algorithm computes $c_k$ with $\sum_{j \neq k} w_j x_{i, j}$. Why does one need to ignore the $k^{th}$ feature here? I'm not sure how this is derived. Is this the result of taking the gradient with respect to the $k^{th}$ feature?
Also what exactly is $a_k$ and $c_k$?


texts: What is the theory behind testing fixes for intermittent bugs?

texts:
I ask this question because I deal with alot of intermittent bugs and want to be able to answer the question "Can I be at least 95% sure that my changes to the code fix the bug?".  I've got some ideas on how one could formalize the problem, but I'm guessing that someone else has done this.

I'm particularly interested in theory where we do NOT already know a value of $p$ - the probability that a bug will hit.  This means we'll likely have to assume some distribution on $p$.

It seems like this should be a known thing, especially within TDD.  Some problems are just so hard that we have to rely on testing results.  Thanks for any direction you can give me.


texts: Find the intersection point between two sorted arrays with unknown lengths in lesser than O(n)

texts:
Two sorted arrays of positive integers, X[] and Y[] are given.But, the array sizes are unknown to us. We may assume that accessing any index beyond the last element of the array returns -1. The elements in each array are distinct but the two arrays may have common elements. An intersection point between the two arrays is an element common to both the arrays, i.e., p ( p>0 ) be an intersection point if there exists i,j such that X[i]=Y[j]=p
Given a positive integer q, how can we design an algorithm ( in pseudocode ) to check if q is an intersection point between X and Y in strictly less than O(n) time complexity.

 I proceeded by thinking of applying binary search on both the arrays X and Y, since they are sorted and trying to find if q exists in both of them. But not knowing the lengths leads me astray.

Could anyone please help me with this ?


texts: What's a general rule for this little lambda calculus identity?

texts:
I've been fiddling around with a project that does some normalization of lambda calculus(-like) expressions and I stumbled upon that

(λ λ ... λ n (n-1) ... 2 1)

(De Brujin notation) is just the identity. I've generalized this a little to realize I can do stuff like

(λ λ λ λ 4 2 1) = (λ λ 2)

So basically if you can identify some character in your expression which is just the variable index n, and all variable indices to the left of that point are greater than n, and to the right is just descending down the variable indices one at a time to index 1 then you can eliminate all the indices to the right of that character (including that character) and then eliminate the _λ_s from the head of the expression and decrease the remaining indices appropriately.

This feels too haphazard to be the simplest form of this identity though. There must be a cleaner way to express this, and possibly a more general rule.


texts: How can I verify a solution to Travelling Salesman Problem in polynomial time?

texts:
So, TSP (Travelling salesman problem) decision problem is NP complete.

But I do not understand how I can verify that a given solution to TSP is in fact optimal in polynomial time, given that there is no way to find the optimal solution in polynomial time (which is because the problem is not in P)?

Anything that might help me see that the verification can in fact be done in polynomial time?


texts: name matching algorithms from partial input

texts:
There are a lot of algorithms out there that solve this particular problem. My main problem is in trying to understand how they work; where to start. Most of the algorithms are academic in nature.

There is a master list of product names. We feed in an input file into the program with product names, but the names of the products may be partial or incomplete. We would need to match the correct product from the master list.

There are solutions like clustering algorithms, naive-bayes, etc. But I am looking at some working examples to actually understand the concept. Would want to review the computations step-by-step for a small model.


texts: Complexity of increasing the radius of a graph

texts:
Let $G(V,E)$ be a graph and each edge e∈E has a positive length $\ell_e$. The radius of the graph is $rad(G)=\min_{v∈V}\max_{u∈V}d(u,v)$ where $d(u,v)$ stands for the shortest path between $v$ and $u.$

Now let we are allowed to increase the edge lengths by total increasing equal to B so that the radius increases as much as possible.

1-What is the complexity of this problem? Is this problem NP-hard?

2- Which problem is suitable for reduction?


texts: Why is the type ∀t.t un-inhabited in System F?

texts:
How do you prove that there exists no term with the type $\forall t. t$ in System F?

I tried searching through Pierce's TAPL and Reynold's ToPL, but could not find anything. I suspect that the proof may involve some kind of model theoritic argument, but I fail to see where to start.


texts: Terminology for reducing runtime of an algorithm by using a property of the problem?

texts:
It is a very standard situation that we have a class of problems $P$, and a subclass $\tilde P\subset P$ which has a certain restricted property.

For example, $P$ could be the problem of searching through an arbitrary list of people for someone with height $1.8$ meters, while $\tilde P$ could be the same problem, except that it is known that the list is ordered by height.

Searching through an ordered list is far more efficient than through an arbitrary list.

My question is: what would be the term for an algorithm using/relying on a certain particular structure of the problem in order to run more efficiently than would be needed in the general case?

Or alternatively, what is the term for "omitting calculations" that are necessary to do in the general case but that can be omitted in the restricted problem case?


texts: If I have a DCFG G for some language over {0,1}* and a DCFG H for its complement, with disjoint non-terminals, and a (perhaps partially reduced) string, can they both have a handle for the string? So the right hand sides of these rules would consist of only terminals and one would be a (maybe proper) prefix of the other. I think it's possible but I'm not certain and can't quite show it.


texts: Which algorithm for counting the occurrences of a certain pattern (spots) in an image?

texts:
The Problem :

Finding the number of occurrences of a certain pattern (or shape) in an image. In my example, the problem is about finding the number of spots (in variety of sizes) in an image. See figure 1 below:

What I'm looking for here is an orientation. What class of algorithms can lead to a solution for this type of problems?


texts: I've proven my language undecidable what is left to prove it Turing equivalent?

texts:
Let us say that I have a computation model $A$.  Let us also say that I have shown that $A$ can be simulated by a Turing machine.

I have not been able to prove that $A$ can simulate a Turing machine. In fact in trying to do so I have shown that doing so would require proving a notable unproven conjecture in mathematics.  I have shown that $A$'s halting problem is decidable iff this unproven conjecture is false.

This means if I were to show $A$ to be Turing complete I would prove the conjecture.  However it does not mean that if I proved $A$ to not be Turing complete I would disprove the conjecture.  Since (to the best of my knowledge) a language can be Turing undecidable and still remain weaker than a Turing machine.

I would like to show that the language is Turing equivalent iff the conjecture is true, but I have run into a block getting anywhere.  Since I doubt I will prove a conjecture of this caliber it seems worthless to try and simulate a Turing machine in $A$, but I don't know any non-constructive ways of proving Turing completeness.

Is there any useful strategy I could employ or relevant theorem I could use here?

In case of curiosity the unsolved problem I am dealing with is the Skolem problem


texts: In multi criteria decision making, what notions are there to get a subset of the Pareto set?

texts:
In the multi criteria decision making context, let $\mathcal{A}$ be a set of alternatives or choices. Each alternative $\alpha\in \mathcal{A}$ is a vector of $k$ criteria $\alpha=(v_1,v_2,\dots,v_k)$. Let $\geq_1,\dots,\geq_k$ be a set of $k$ partial orders over $\mathcal{A}$.
For any two alternative $\alpha,\beta\in \mathcal{A}$,  $\alpha$ dominates $\beta$ $(\alpha\geq \beta)$ if and only if $\alpha\geq_i \beta$ for all $i\in\{1,2,\dots,k\}$.

An alternative $\alpha$ is said to be Pareto optimal if there is no alternative dominates it. That is, $\beta \not\geq \alpha$ for all $\beta\in \mathcal{A}$.
The Pareto set $S_{pareto}$ is the set of all Pareto optimal alternatives.

I am looking for different notions with which one can have a subset of $S_{pareto}$.
Are there other notions in the literature define a set $S$ which is guaranteed to be a subset of $S_{pareto}$?


texts: Would Schmidhuber's theories of everything be capable of performing hypercomputation?

texts:
Jürgen Schmidhuber pointed out that a simple explanation of the universe would be a Turing machine analogy programmed to execute all possible programs computing all possible histories for all types of computable physical laws. His work was based on Zuse's thesis.

This hypothesis would be inside the domain of Digital Physics, a group of hypothetical models that propose that the universe is analogous to a computer or an automata.

(https://en.wikipedia.org/wiki/Digital_physics)

In 2000, he expanded this work by combining Ray Solomonoff's theory of inductive inference with the assumption that quickly computable universes are more likely than others. This work on digital physics also led to limit-computable generalizations of algorithmic information or Kolmogorov complexity and the concept of Super Omegas, which are limit-computable numbers that are even more random (in a certain sense) than Gregory Chaitin's number of wisdom Omega.

So since Chaitin's constant (https://en.wikipedia.org/wiki/Chaitin%27s_constant) would allow hypercomputation if it existed in the pysics of the universe, would then Schmidhuber's hypothesis be able to perform hypercomputation?
Also, in the hytpercomputation wikipedia entry (https://en.wikipedia.org/wiki/Hypercomputation) it says (In "eventually correct" systems):

  A symbol sequence is computable in the limit if there is a finite, possibly non-halting program on a universal Turing machine that incrementally outputs every symbol of the sequence. This includes the dyadic expansion of π and of every other computable real, but still excludes all noncomputable reals. Traditional Turing machines cannot edit their previous outputs; generalized Turing machines, as defined by Jürgen Schmidhuber, can. He defines the constructively describable symbol sequences as those that have a finite, non-halting program running on a generalized Turing machine, such that any output symbol eventually converges; that is, it does not change any more after some finite initial time interval. Due to limitations first exhibited by Kurt Gödel (1931), it may be impossible to predict the convergence time itself by a halting program, otherwise the halting problem could be solved. Schmidhuber uses this approach to define the set of formally describable or constructively computable universes or constructive theories of everything. Generalized Turing machines can eventually converge to a correct solution of the halting problem by evaluating a Specker sequence.

And also, Super-recursive algorithms are closely related to hypercomputation, and super recursive algorithm is just one way of defining hypercomputation. In super-recursive algorithms wikipedia entry (https://en.wikipedia.org/wiki/Super-recursive_algorithm), Schmidhuber's model is included as a super-recursive algorithm-based model

So, knowing all of this, then, would Schmidhuber's hypothetical universes be based on hypercomputation?


texts: How to handle an undefined case with µ-recursive functions?

texts:
How to construct my proof and generally what should I aim to get when showing a function is $\mu$-recursive? Should I transform it in some of the basic functions using the given operators?

For example, how should I proceed with the following one:

$\phantom{AAAA}pred(x) = undef$, if $x = 0$
$\phantom{AAAA}pred(x) = x - 1$, if $x > 0$

How should I handle the $undef$-part?


texts:
my data's range is from 1 to 9 and I have two subsets of integers from this range.
the hash function takes each of this subsets and calculate product of these three integers and maps this set to the result of this multiplication.I want to know the probability of collision by this hash function with this two subsets of integers that they are from 1 to 9 and the size of each subset equals 3.


texts: Dynamic Shortest Path with Linear Programming

texts:
Consider a grid with $x=5$ columns, $y=5$ rows, and $T$ timesteps.

There are $N=2$ agents in this grid, which can move vertically or horizontally. The positions of each agent $x$ at timestep $t$ is denoted as $A_{xt}$. For this example, consider $A_{00}=1$ and $A_{10}=23$. The goal is to carry a ball from node $1$ to node $G=15$. Each agent can carry the ball or throw it at distance $k=2$ (measured in Manhattan distance). The shortest path is, in this case, for Agent $0$ to carry the ball until node $3$, while Agent $1$ moves to node $13$. Then, Agent $0$ throws the ball to Agent $1$, which kicks it to the goal node.

How can this be modeled? If agents cannot move without the ball (not a dynamic graph), the problem is fairly simple. Assume $X_{ijt}=1$ (an activated edge) when the ball is carried or is kicked from node $i$ to $j$ at timestep $t$, and all actions cost (or have weight) $1$. All nodes (except starting and goal nodes) must have the same amount of ball 'entrances' as 'exits'.

$ \sum X_{ijt_1} = \sum X_{jit_2}, \forall i,j,t_1,t_2$, where $t_1<t_2, d(i,j)=1$ (adjacent nodes) or $j=A_{xt}$ (passing towards an agent)

The entrance and exit nodes will have a single activated edge.

$ \sum X_{A_{00}j0} + \sum X_{A_{00}A_{x0}0} = 1, \forall j,x$, where $x\neq0, d(A_{00},j)=1, d(A_{00},A_{X0})\leq k$

$ \sum X_{iGT} = 1, \forall i$, where $d(i,G)\leq k$

However, if all agents can move at any given point, then the graph is dynamic, since the passes that can be performed are different in each timestep. I don't know how to model this. Before, because $A_{1t}$ was static until it got the ball, I could list all the restrictions a priori, but now, I cannot do it. I can create a set of restrictions based on $A_{xt} \forall x,t$, but I don't know how to then input this problem into a linear programming solver (for example, a simplex method).


texts: Why does NTIME consider the length of the longest computation?

texts:
In Sipser's textbook "Introduction to the Theory of Computation, Second Edition," he defines nondeterministic time complexity as follows:

  Let $N$ be a nondeterministic Turing machine that is a decider.  The running time of $N$ is the function $f : \mathbb{N} \rightarrow \mathbb{N}$, where $f(n)$ is the maximum number of steps that $N$ uses on any branch of its computation on any input of length $n$ [...].

Part of this definition says that the running time of the machine $N$ is the maximum number of steps taken by that machine on any branch.  Is there a reason that all branches are considered?  It seems like the length of the shortest accepting computation would be a better measure (assuming, of course, that the machine halts), since you would never need to run the machine any longer than this before you could conclude whether the machine was going to accept or not.


texts: Solving the min edge cover using the maximum matching algorithm

texts:
To solve an instance of an edge cover, we can use the maximum matching algorithm.
Edge Cover: an edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least one edge of the set [from Wikipedia].
Maximum matching: a matching or independent edge set in a graph is a set of edges without common vertices [from Wikipedia].
For example to find the min edge cover of the example below, we can:
1- Find a maximum matching.
2- Extending it greedily so that all vertices are covered.
The image below present this solution:

My question is why this reduction works, is there a proof for that result? or at least an intuition to help me undestand!
How can be sure that the final solution is the min edge cover of the graph and there is no other edge cover with size less than the founded solution.


texts:
$$L=\{uv\in\{0,1,2\}^*\mid u\in\{0,1\}^*,v\in\{1,2\}^*, \text{ and }u\text{ has the same number of 1s as }v\}.$$

Here is my attempt solution, but it is not completely correct, any hint is appreciated
(not sure how I can ensure that $u$ and $v$ to have the same number of 1).

\begin{align}
S &\rightarrow S_l \mid S \mid S_r\\
S_l &\rightarrow 0S_l \mid 1S_l \mid S_l0 \mid S_l1 \mid \varepsilon \\
S_r &\rightarrow 1S_r \mid 2S_r \mid S_r1 \mid S_r2 \mid \varepsilon
\end{align}


texts: 3-partition problem without the restriction to triplets

texts:
In the standard 3-partition problem, there are $3 m$ integers, their sum is $m T$, and they have to be partitioned into $m$ subsets of sum $T$ and size $3$.
Consider the variant without the restriction that the size is $3$ (but with the restriction that there are $m$ subsets with a sum of $T$). Are these problems computationally equivalent?
[NOTE: often there is an additional restriction that each input number is in $(T/4 , T/2)$; in this question there is no such restriction - the numbers in both variants can be any positive integers].
I found a reduction from the triplet-variant to the subset-variant: given an instance of the triplet-variant with target-sum $T$, construct an instance of the subset-variant by adding $2 T$ to each element and changing the target-sum to $7 T$. Every solution to the triplet-instance is also obviously a solution to the subset-instance. Conversely, in every solution to the subset-instance, each subset must have exactly 3 elements, since the sum of any 2-element subset is at most $6 T$ and the sum of every 4-element subset is at least $8 T$.
Is there a reduction in the opposite direction? Particularly, given an instance of the subset-variant, how can I construct an instance of the triplet-variant, that has a solution whenever the original instance has one?


texts: How to write a regular expression that excludes certain strings?

texts:
It's a homework problem.
Assume $\Sigma = \{a ,b\}$, I am asked to construct a regular expression that does not have both the substrings bba and abb.

My idea was: construct a regex that matches everything except bba, construct a regex that matches everything except abb and OR them together.

The first answer I thought of was $a^*b^*|b^*a^*$ and while it does technically guarantee that only one substring will be present at a time (if it is present), it is limiting in that it doesn't accept other perfectly valid strings like $aba$ or $ababa$. How would I go on about constructing such a regex specifically and generally how should I approach constructing regexes to be able to come up with correct regexes?


texts: Can any algorithm efficiently be implemented as a SIMT problem?

texts:
Many algorithms can be implemented more efficiently using SIMT instructions (e.g. CUDA) than using sequential instructions.

Excluding overhead due to hardware limitations (specifically, memory copy times when using a GPU) - are there algorithms whose efficiency can only be made worse in a SIMT model? By "efficiency," I mean here the total number of elementary operations / # parallel processing elements.

(Assume that each individual compute element in the SIMT model is (made to be) exactly as fast as the single compute element in the sequential model. Therefore, computing time is the same as the number of elementary operations.)

Asked another way, can any algorithm be made at least as efficient using SIMT instructions than it could using sequential instructions? Again, I'm purely talking about computing "time" here - not set up / memory copies (which are the typical reason why you wouldn't use a SIMT processor for a highly sequential problem AFAIK).