texts: Integer programming to MAX-SAT translation

texts:
Reading A Comparison of Methods for Solving MAX-SAT
Problems, I can see that a MAX-SAT problem can be translated to an integer programming (IP) problem.

Definition of MAX-SAT [Wikipedia]:

  The maximum satisfiability problem
  (MAX-SAT) is the problem of determining the maximum number of clauses,
  of a given Boolean formula in conjunctive normal form, that can be
  made true by an assignment of truth values to the variables of the
  formula.

Definition of integer programming [Wikipedia]:

  An integer programming problem is a mathematical optimization or
  feasibility program in which some or all of the variables are
  restricted to be integers

Is there a similar translation backwards? Given an IP problem that can be translated to a MAX-SAT.

The MAX-SAT problem is NP-hard [2] and Integer programming is NP-complete [3].
technically it might not be very suitable to solve a (in principle) simpler problem using a formulation which is (in principle) harder to solve. But it will be great to understand the encoding both ways. My motivation is to compare MAX-SAT solvers with IP solvers.

More precisely given an IP problem like:
$$x_1 + x_{2} + \neg x_3 \leq 1 \\
  \neg x_1 + x_4 + x_3 \leq 1 \\
   ... $$

with total n inequalities/equations and each $x_i \in \mathbb{B}$. Such that maximize as many as equations (from total n). Encode it as a MAX-SAT problem.

First Attempt:
Each inequality encodes AtMostOne of the complement of the variables (or AtleastN-1 of the original IP inequality). But representing AtMostOne in CNF will create multiple clauses and destroys the possible use of direct MAX-SAT.


texts: Enumerating all set covers when knowing one set at least

texts:
I have an index taking as keys values from the power set $P(S)$ of a set $S$, except for $\emptyset$ and $S$.

Then I have a query $Q=(s, k)$, where $s \in P(S) - \{\emptyset \cup S\}$ and $ 1 < k \le |S|$.

The result of the query is the set of covers $R$ of $S$; $\forall r \in R,  |r| \le k$.

So for instance, if $S = \{a, b, c, d\}$ and $Q=( \{a,b\}, 3 )$, $R$ should return all covers of $S$ formed by $\{a, b\}$ and $k = (3 - 1 = ) 2$ or less other subsets of $P(S) - \{\emptyset \cup S\}$, namely: $R = \{$
$$ \{a,b\} , \{c\} , \{d\}$$
$$ \{a,b\} , \{c, d\} $$
$$ \{a,b\} , \{a, c, d\} $$
$$ \{a,b\} , \{b, c, d\} $$
$\}$

I want to know if there is an efficient algorithm that can give me all of these combinations of covers.

In other words, I want to know if there is an efficient way to get all covers formed by at most $k$ elements, where I only know 1 element out of k.


texts: Deriving the Sobel equations from derivatives

texts: Many sites give the Sobel operators as the convolution mask for smoothing an image. However, I haven't found a single site that describes how you can derive the operators from partial first derivatives. If anyone can explain the derivation, I would highly appreciate it.


texts: Where is the second face in a graph with 3 nodes?

texts:
I understand that to work out the number of faces of a connected planar graph, you use Euler's formula F = A - N + 2, where A is the number of arcs and N is the number of nodes.

For a triangle node (3 arcs and 3 nodes), the number of faces would therefore be 3 - 3 + 2 = 2.

But I can't count two faces, only one (the triangle itself). Where is the second face, or where have I misunderstood?


texts: Calculate the average length of the linked lists in a hash table

texts:
I am learning hash tables, and I would like to know how to determine the average length of the linked lists.

For example: A hash table holds about 10,000 employee records. Each record is indexed by the 2-character initials of the employee name, transformed into integers using the mapping: A=01, B=02, C=03, and Z=26. On average no more than 8 comparisons is made every time a search is requested.

How would you determine determine the actual average length of the linked lists, in the hash table, that is pointed to by the hash value slots?


texts: What is the name of visiting an array starting at first element, then last element, then second, then last but one, then third, etc

texts:
For example if I have an array

[0, 1, 2, 3, 4, ..., n]

and I want to iterate over it in an order like

[0, n, 1, n - 1, 2, n - 2, ..., n // 2]

how it can be called? Is there a general name for this?


texts: Understanding facts about regular languages, finite sets and subsets of regular languages

texts:
I am aware of following two facts related to two concepts: regular languages and finite sets:

  Regular languages are not closed under subset and proper subset operations.
  It is decidable whether given regular language is finite or not.

However I feel these facts are quite insufficient to prove whether following statements are true or false:

If all proper subsets of $L$ are regular, then $L$ is regular.
If all finite subsets of $L$ are regular, then $L$ is regular.
If a proper subset of $L$ is not regular, then $L$ is not regular.
Subsets of finite sets are always regular.

I feel 3 is false, as regular languages are not closed under proper subset operation. Right?

But I am unsure of the other points. What facts I am missing to answer above statements true or false?


texts: How does RAM is shared in multi core environment?

texts:
I learnt that multi core processors have more than one processing units( i.e. the main executing units ALU etc.) and they are better at performance. I want to know how they share Physical memory. I'll take following example to make my question clearer - Say, There is a memory location M in physical memory and Two threads T1 and T2 running on different cores. Is it possible for T1 and T2 to access M at the same instance of time or do they have to wait for one other to complete access i.e. do they share the same memory bus so that they have to wait, for one another or Can they read M at same instance of time from two different memory buses? If former is the case, There is not much performance gain right, as they have to wait for memory bus to be free?

Summarising, Are memory operations independent of other cores or each core can only make a physical memory access when memory bus is free?


texts:
Are type variables really only used in mathematical conversation about types? i.e. are type variables (meta-variables that only contain the type classification label) only exist in proofs for types but not in real programming languages? At least is this true for monomorphic types? i.e. I can't actually define:

$$ \texttt{ let id x = x }: \tau$$

unless the type $\tau$ has already been defined or is built in? i.e. type variables only exist for symbolic manipulation of type proofs for humans (at least for monomorphism).

Extra thoughts:

I am trying to understand how one defines the identity function $\texttt{let id x = x}$ in monomorphic type systems. I believe the motivation for polymorphism is to allow to apply the same syntactic definition of a function to different data types that are NOT the same, like: $\texttt{id 2}$ and $\texttt{id true}$ without the type checker freaking out at us when it tries to run those (if the language is dynamically typed...I guess in static the compiler would complain at the first instance of the identity function being applied to the wrong type when we try to compile it to usable code).

So to my understanding, if we define types as a set of possible data values, so say $\texttt{int}$ defines the set of all integers. Then the set $Set_{int \to int}$ is the set of all functions that can map integers to integers. But if we have $Set_{\forall \alpha .  \alpha \to \alpha}$ and we consider the identity function corresponding to both sets so $id_{\forall \alpha . \alpha \to \alpha} \in Set_{\forall \alpha .  \alpha \to \alpha}$  and $id_{int} \in Set_{int \to int}$ then when both identity functions are applied to integers they will behave exactly the same BUT they are not the same function (because they are not the same data value, the data value for one is identity on only integers while the other is give me any type and I will act like its corresponding identity. So in particular $Set_{\alpha \to \alpha} = Set_{int \to int} \cup \dots \cup Set_{string \to string}$ (i.e. the identity $id_{\alpha \to \alpha}$ is just the identity function for a specific type but not actually a function that is able to process ANY type, its one and in this case this is why the for all is important).

So my question is, is $id_{\forall \alpha . \alpha \to \alpha} \in Set_{\alpha \to \alpha}$? I guess I am trying to clarify the dots ... What does it cover? Perhaps it depends on the context of how the types are formally defined? If the $\alpha$ stands for type variables, but type variables are only allowed to be monomorphic by definition (i.e. say the type constructor for the meta-langauge is recursive but only in the monomorphism where we can't introduce the forall quantifier) then the $id_{\forall \alpha . \alpha \to \alpha} \not\in Set_{\alpha \to \alpha}$. But if the recursive definition for polymorphic types is recursive at the polymorphic step then perhaps $id_{\forall \alpha . \alpha \to \alpha} \in Set_{\alpha \to \alpha}$ is true? Actually I don't think so...

Context: CS 421

Related:

What does $ \forall \alpha_1, \dots , \alpha_n . \tau $ mean formally as a type?
What is the difference between $ \alpha \to \alpha $ vs $ \forall \alpha. \alpha \to \alpha$?


texts: Shamos-Hoey Line segment intersection runtime

texts:
In the Shamos-Hoey algorithm for finding whether or not any two of $n$ line segments intersect, which is available at this site: http://geomalgorithms.com/a09-_intersect-3.html, there is use of "nearest line above" and "nearest line below". The algorithm is supposed to run in time $O(n\log n)$. Here is their pseudocode:

Initialize event queue EQ = all segment endpoints;
Sort EQ by increasing x and y;
Initialize sweep line SL to be empty;

While (EQ is nonempty) {
    Let E = the next event from EQ;
    If (E is a left endpoint) {
        Let segE = E's segment;
        Add segE to SL;
        Let segA = the segment Above segE in SL;
        Let segB = the segment Below segE in SL;
        If (I = Intersect( segE with segA) exists)
            return TRUE;   // an Intersect Exists
        If (I = Intersect( segE with segB) exists)
            return TRUE;   // an Intersect Exists
    }
    Else {  // E is a right endpoint
        Let segE = E's segment;
        Let segA = the segment above segE in SL;
        Let segB = the segment below segE in SL;
        Delete segE from SL;
        If (I = Intersect( segA with segB) exists)
            return TRUE;   // an Intersect Exists
    }
    remove E from EQ;
}
return FALSE;      // No  Intersections

If one studies the C++ code provided at the bottom of the webpage, we see that this is simply a "next" and "previous" in a BST, however, I can't seem to tell which information is being used as the BST key.

My issue is the following: if we are considering all $y$-values at the current $x$-value of the sweep line, this is not merely a check for next or previous endpoint value in a BST, and can not take $O(\log n)$ time. However, if we are checking per endpoint coordinate, this could not possibly be correct, since the following situation would lead to an incorrect execution:

The algorithm should find that $B$ and $C$ intersection on insertion of $B$ into the search tree ("SweepLine" / "SL") while sweeping. However, if we are ordering by endpoint coordinates, $A$ is $B$'s previous, $C$ is not, and this would run into problems.


texts: Can someone tell a formal definition for this problem: k-disjoint triangle?

texts:
k-disjoint triangle
"We consider the NP-complete problem of deciding whether an input graph on n vertices has k vertex-disjoint copies of a fixed graph H. "
The above definition is the best I could find online. Nowhere could I find an clear formal definition.

What does it mean to be vertex disjoint exactly?
How to prove k-disjoint vertex is NP hard?


texts: Introduction to type theory for a beginner?

texts:
I'm interested to read about type theory, but I'm quite a beginner. I know what sets are and how to work with them, but I don't have a deep understanding of set theory. I don't really understand the motivation behind type theory, other than that it was first developed to solve the problems with naive set theory.

I'm mainly interested in type theory because I heard it relates to proof theory (which I also don't understand well). I'm also not a mathematician or computer science by education.

Is there a good resource for beginners that introduces type theory, motivates it, shows how its different from set theory, why that's relevant, and shows how it can be used? I'd be satisfied if I have a thorough understanding of the general idea without understanding more advanced stuff.


texts: Query all bounding boxes which contain a point

texts:
I'm looking for the most efficient spatial-indexing data-structure for storing and querying bounding boxes which contain individual points. The points represent 2D coordinates on a grid, while the bounding boxes represent regions of the grid. The bounding boxes may vary greatly in size, and multiple bounding boxes may overlap a single point. Both points and bounding boxes are stored as signed integers.

For example, in the diagram below, if I were to query points $B$ and $C$, I'd expect a single bounding box in return. However, if I query point $A$, I'd expect an array containing both bounding boxes in return.

--------
| B  ============
|    |A|        |
-----|--     C  |
     ============

I'm not concerned with insert/remove efficient for adding bounding-boxes to the structure as all bounding-boxes are added to the structure during a one-time initialization. My main concern is efficient look-ups for finding which bounding boxes contain a point, as such queries will be made frequently.

My initial thought is to use a quadtree, and to test all objects contained in a particular node to see if they contain the point being queried. However, I'm wondering: is there a better data-structure I could use to implement this behavior with?


texts: Is there a known algorithm for computing the n-th Turing machine directly?

texts:
Let us define a Turing machine by a machine description that is a string of symbols produced by some numerical encoding. For example, a Turing machine $M_1$ can be represented by 9,900,599 ([0 0 halt], where halt = 5 and the start and end of an instruction is 99). A standard enumeration consists of all possible Turing machines.

If given a number $n$, is there a known algorithm out there for producing the $n$th Turing machine ($M_n$) in the standard enumeration?


texts: Lower bound for matrix determinant algorithm

texts:
I have the an algorithm for computing a matrix determinant:
$$\ det(A) = \sum_{i=1}^n (-1)^{i-1} \cdot A_{i1} \cdot det(A_{-i,-1})$$
Where $\ A_{-i,-1} $ is the matrix $\ A $ without the row $\ 1 $ and column $\ i $
Drawing the recurrence tree, I see each level $\ k $ has $\ \frac{(n-1)!}{(n-k)!} $ nodes. So I think the upper bound for this algorithm to be $\ O(n!) $ because the height of the tree is $\ n $ and the row sum of each level is the same as number of nodes. How can I set lower bound using recurrence tree? I've found this answer where the lower bound of such arithmetic operation in a matrix is set to be $\ \Omega(n^3) $ though , can not understand why?


texts: Can finding a witness be NP-hard even if we already know there is one?

texts:
The common examples of NP-hard problems (clique, 3-SAT, vertex cover, etc.) are of the type where we don't know whether the answer is "yes" or "no" beforehand.

Suppose that we have a problem in which the we know the answer is yes, furthermore we can verify a witness in polynomial time.

Can we then always find a witness in polynomial time?  Or can this "search problem" be NP-hard?


texts: Testing whether an arbitrary proof is circular?

texts:
I was thinking about proofs and ran into an interesting observation. So proofs are equivalent to programs via the Curry-Howard Isomorphism, and circular proofs correspond to infinite recursion. But we know from the halting problem that in general testing whether an arbitrary program recurses forever is undecidable. By Curry-Howard, does that mean there is no "proof checker" that can determine if a proof uses circular reasoning?

I've always thought that proofs are supposed to be composed of easily-checkable steps (which correspond to applications of inference rules), and checking all the steps gives you confidence that the conclusion follows. But now I'm wondering: maybe it is actually impossible to write such a proof checker, because there is no way for it to get around the halting problem and detect circular reasoning?


texts:
I'm looking for the name of the following concept.

Given a monoid $(M,\oplus)$, and a finite set of generators $x_1,\ldots,x_n$. The generators are the alphabets.

We define the regular expression on the words formed by the generators. We treat those words just like strings.

For words $x$ and $y$, we write $x\equiv y$ if $x$ and $y$ represent the same element in $M$.

If $R$ is a regular expression, we define $L(R)$ to be the set of strings matched by $R$ and $L_M(R)$ as

$$L_M(R) = \{w'|w'\equiv w,w\in L(R)\}$$.

I'm interested to know if there exist known literature on $L_M(R)$.

Many problems related to $L_M(R)$ are undecidable, because the word problem on $M$ might be undecidable. I wonder if $M$ has a decidable word problem, does it imply we can decide if $L_M(R)=L_M(R')$ for 2 regular expressions $R$ and $R'$.


texts:
I'm having some difficulty understanding ip addresses. Let's say:

Question Info:

private subnet 192.168.0.0/24

IP addresses 212.201.49.1-5

Now, a host 192.168.0.2:1234 retrieves a web page from the web server at 42.35.12.33.

Then, host 192.168.0.5:1234 retrieves a web page from the web server at 100.12.45.11

Answer Part:

Now, I have this information for first the request part:

internal

192.168.0.2:1234 (src)

42.35.12.33:80 (dest)

external:

212.201.49.1:1234 (src)

43.35.12.33:80 (dest)

Where does 80 come from at the end of dest?

Now, for the second request, the src address of external is 212.201.49.2:1234.

Why is it 2.1234? In the 3rd one, it was 1 again.


texts: What algorithm to use to generate random path of given length

texts: I have a map size of 8 x 8 cells with no obstacles. I should generate random path from start cell to the end cell with given length. Path can move up/down/left/right directions but not cross itself. What algorithm I can use to do this?


texts: Number selection algorithm (to fill up total amount)

texts:
I'm trying to create an algorithm in SQL(syntax doesn't really matter) that will read the results table that consists of 2 columns:
number (1,4,15,30...etc) and it's quantity(1,2,3,4,5...) like:

number qty
3     5
7     3
15    2
30    9

and then creates a resultset based on how many of these numbers can fit within a certain value, maximum number of numbers(sorry for tautology) should be used, but numbers should be used in such way that they are utilize value most efficiently (leaving least amount of leftover space).

Sample for value = 87

number    qty
3         5   (87-15 = 72 leftover)
7         3   (51 leftover)
15        2   (21 leftover) - not efficient

number    qty
3         5   (72 leftover)
7         3   (51 leftover)
15        1   (36 leftover)
30        1   (6 leftover) - better but probably not the best


texts: How to show that $\log (n!) = \Omega(n\log n)$ using Stirling's approximation?

texts:
Using Stirling's approximation, we have $\log_{2} (n!) = n\log_{2} n - (log_{2} e)n + O(log_{2}n)$. Most lecture notes I have come across say that $ n\log_{2} n - (log_{2} e)n + O(log_{2}n) = \Omega (n\log_{2} n)$. Can someone give a rigorous proof of the last line using the basic definitions of big-O and big-Omega?

Thank you in advance.

P.S. There are similar posts on this and I know some other proofs of  $\log (n!) = \Omega(n\log n)$ with or without using Stirling's approximation. I don't have any problem with $\log (n!) = \Omega(n\log n)$. It's just that I can't see why $ n\log_{2} n - (log_{2} e)n + O(log_{2}n) $ is $ \Omega (n\log_{2} n)$.


texts: Abstract algebra and programming languages

texts:
Quite often, I stumble upon abstract algebra concepts like initial algebra, free algebra, and similar while reading papers on programming languages. For instance, in papers on algebraic data types, monads, separation logic, models of polymorphic lambda calculus, etc.

Where can I find materials that will introduce me to such concepts, i.e., ones that are related to programming languages and logics? Hopefully, the number of such materials would be small.


texts: Clarifications on polynomial reducibility for problems in P and NP-complete

texts:
Can I always increase the complexity of a problem via polynomial reduction? (in which case 'reduction' is really a misnomer) For example, if I have a classic P problem (say, finding the smallest element in an array, by iterating through and making comparisons with the smallest value found thus far), what would be a corresponding problem in NP-complete (obtained via polynomial reduction)? Or, would it be possible to polynomially reduce a constant time (worst case) algorithm into a polynomial time algorithm (basically performing unnecessary executions for all n of the input for nothing)?

As a side request, I'm looking for a basic reference that deals with how one problem (in P or NP-complete) can be reduced (in polynomial time) to a problem in (P or NP-complete). Most of the things I found online are beyond scope or vague. I'm looking for an easy way to figure out whether a certain Problem A (in P or NP-complete) can be polynomially reduced to a Problem B (in P or NP-complete).


texts: Computing losing positions in modified Wythoff's game efficiently

texts:
Wythoff's game is as follows: there are two players $A$ and $B$ ( $A$ being the first player ) and there are $2$ piles of stones. When his turn a player can remove one or more stones from anyone pile or same number of stones from both the piles. A player unable to make a move loses. Also it is assumed that both the players play optimally.

As mentioned in the link the losing configurations $(n_k,m_k)$ ( $n_k$ stones in one pile and $m_k$ stones in another ) are given by
$$ n_k = \lfloor( k*\phi) \rfloor$$
$$ m_k = \lfloor( k*\phi^2) \rfloor$$
where $k$ is any natural number ( and $n_k \le m_k$ ) and $\phi=\frac{1+\sqrt{5}}{2}$. For example $\{1,2\}$ ( two stones in one pile and one stone in another ) is a losing position.

Modification to Wythoff's game"

In this modified game instead of ${\it2}$ piles there are ${\it 3}$ piles. And when his turn a player can move one or more stones from anyone pile or same number of stones from any $2$ piles or same number of stones from all the $3$ piles.
How do I compute the losing positions for this modified game efficiently ? The inefficient way of course is to find the grundy number of each  configuration $\{a,b,c\}$. This method is inefficient because I want to calculate  number of losing positions given that number of stones in each pile can be between $1$ and $1000$.

This is a project Euler question ( stone game ). I would appreciate hints
only.


texts: Minimum words in a string given a dictionary

texts:
The question is: Given a dictionary consisting of a set of words and a string: find the minimum number of words the string can be split into. If the string can not be decomposed into a list of words return -1.

I tried finding the longest prefix and proceeding but that doesn't seem to work. I searched this question online and found a similar stack exchange question but I believe that the solution provided is wrong. It looks like this person is finding the longest suffix and proceeding but this approach doesn't work. Link to similar question

The reason this doesn't work is because: Suppose the dictionary is:{i,iiiiface,facebook,book} and input instance is 'iiiiifacebook'. The given solution would select 'facebook' and then continue to select 5 'i's' making a total of 6 words when infact the optimal solution is: (book,iiiiface,i) which is just 3 words. Please correct me if I'm wrong.

Please help me find the optimal (DP) solution to this problem.


texts:
When I read about the Church-Turing thesis it seems to be a common claim that "physical reality is Turing-computable." What is the basis for this claim? Are there any theoretical results along these lines?

For context, I am a researcher who works on physical simulations, so of course I'm aware that many partial differential equations (PDEs) that would arise in nature (e.g. the heat equation, wave equation, etc) can be approximated by numerical methods like finite elements, and that for many PDEs a solution can be estimated to arbitrary accuracy given enough computation (by decreasing the space and time step sizes).

However, I also know that proving convergence of finite element methods is notoriously difficult for PDEs of any appreciable complexity, even "easy" PDEs like the mean curvature flow that describes the shape of a soap film. I also know that many "Zeno-type" situations arise in practice in physical systems, such as Euler's disk or inelastic collapse. Is there reason to believe that the solutions to all PDEs, or at least all PDEs that would arise in nature, are Turing-computable?


texts: Check if adding an edge to a DAG results in a cycle

texts:
On the begining: It is a programming contest problem, but not from on-going one. Unfortunatelly, I can't provide any link to this task, because it is not publically available. It was from one of the Polish local programming contest in 2011 organised by Warsaw School of Computer Science.

I have a graph with $V$ $(1 \le V \le 5 \cdot 10^5)$ vertices without edges and a list of $E$ $(1 \le E \le 5 \cdot 10^5)$ directed edges. On the $i$-th second $i$-th edge is being added to a graph. I want to know after which second there will be a cycle in a graph.

The most obvious solution would be to perform DFS after adding each edge, but it would take $O((V + E)^2)$ time. Another solution would be to keep the graph topologically sorted and when adding an edge, I could place it in such a way so that it will not disturb topological ordering. This would take at most $O(V^2)$ time. I did some research on Google and it seems that this is the fastest online algorithm.

As I know all the edges beforehand I can use offline algorithm. The fastest offline algorithm I can think of is binary search. If after $k$-th second graph contains a cycle then obviously it will have a cycle at any other second $l \ge k$. So I can do binary search to find smallest $k$ by performing DFS $O(\log E)$ times, each of them taking $O(V + E)$ time, so the total complexity of this solution would be $O((V + E) \log E)$.

It is quite fast, but I wonder if there exist any faster offline algorithm. One thing I can think of is giving for each edge weight equal to the time when this edge was added to a graph. Then the task would be equivalent to finding a cycle with minimal maximum edge weight. I don't know if it leads to anywhere.


texts: Minimize the maximum component of a sum of vectors

texts:
I'd like to learn something about this optimization problem: For given non-negative whole numbers $a_{i,j,k}$,
find a function $f$ minimizing the expression

$$\max_k \sum_i a_{i,f(i),k}$$

An example using a different formulation might make it clearer:
You're given a set of sets of vectors like

{
    {(3, 0, 0, 0, 0), (1, 0, 2, 0, 0)},
    {(0, 1, 0, 0, 0), (0, 0, 0, 1, 0)},
    {(0, 0, 0, 2, 0), (0, 1, 0, 1, 0)}
}

Choose one vector from each set, so that the maximum component of their sum is minimal.
For example, you may choose

(1, 0, 2, 0, 0) + (0, 1, 0, 0, 0) + (0, 1, 0, 1, 0) = (1, 1, 2, 1, 0)

with the maximum component equal to 2, which is clearly optimal here.

I'm curious if this is a well-known problem and what problem-specific approximate solution methods are available. It should be fast and easy to program (no ILP solver, etc.). No exact solution is needed as it's only an approximation of the real problem.

I see that I should have added some details about the problem instances I'm interested in:

$i \in \{0, 1, \ldots, 63\}$, i.e., there're always 64 rows (when written as in the above example).
$j \in \{0, 1\}$, i.e., there're only 2 vectors per row.
$k \in \{0, 1, \ldots, N-1\}$ where $N$ (the vector length) is between 10 and 1000.

Moreover, on each row the sum of the elements of all vectors is the same, i.e.,

$$\forall i, j, j':\quad \sum_k a_{i,j,k} = \sum_k a_{i,j',k}$$

and the sum of the elements of the sum vector is less than its length, i.e.,

$$\sum_k \sum_i a_{i,f(i),k} < N$$


texts:
What is the easiest and the most straightforward way to find whether a given language is decidable?

For example, how do we know if the following languages are decidable or not?

`Binary representation of all prime numbers`
`{ empty string(eps) }`


texts: Why is it that if we assume the Church-Turing thesis to be true, then human language must be recursive if the brain is finite?

texts:
I was reading "Why Only Us" by Chomsky and Berwick, and it said:

  If one subscribes to the Church-Turing thesis along with the
  assumption that the brain is finite, then there is no way out: we
  require some notion of recursion to adequately describe such
  phenomena.

I find this sentence confusing. What does the Church-Turing thesis have to do with recursion and the human brain? If anything, it seems obviously false to me because the Church-Turing thesis talks about computable things that require a Turing Machine, which in turn obviously requires an infinite tape.  The brain obviously doesn't have this since the brain is finite, unless we somehow assume the brain can always "get a new piece of paper to write on". But even if that was resolved, what does recursion have to do with this, and how is any of this related to language?


texts: Is there a way to incrementally degrade the quality of a PRNG?

texts:
I have an application that depends on a random number generator to perform.  The application might be sensitive to the quality of the random numbers, but I don't know for sure.  I'd like to test this, and if it is, what the degree of sensitivity is.

I've currently got a xorshift1024* PRNG plugged in.  It's fast and I can directly inject a full 1024 bit state.

I need to be able to degrade it in a controlled fashion, ranging from it's high quality native mode to something quite bad.  By quite bad, I mean something far far worse than a simple linear congruential generator.  I'm not interested in slowly changing it's output distribution from uniform to say, normal.  I just want to be able to make it (technically) crappier and crappier.

I have the sense that this might be a common requirement in other testing applications, so there might be a best practice methodology.  At this point my only alternative is to switch off the generator entirely.

Is there a way to incrementally degrade the quality of my PRNG?


texts: Does the order matter in the adjacency matrix?

texts: I have nodes a, b , c,d,N, and e in an adjacency matrix. If I follow the order as a,b,c,d,N,and,e , I get 100010(the question does not matter because I'm asking about the order) for b.But if I follow the order a,b,c,N,d,and e, I get 100100 which was done by my TA in the class. Does the order really matter? If so then is there a way to find order from the adjacency graphs?


texts: Convergence of Conjugate gradient method

texts:
I have implemented my own matrix library in Java to solve fluid simulations.
So I have also implemented the conjugate gradient method and I got a little bit confused.

What I have done to test my CG-method is the following:

Generate M, a $n\times n$ matrix, initialized with values between 0 and 1 (exclusive)
Calculate $A = M \cdot M^T$ (which must be symmetric positive definite)
Calculate the conjugate gradient and display the residuum and the actual distance to the target (I used cholesky to solve the equation and get an exact solution).

My results have been the following (n = 10):

residuum:                               actual distance:
0.9199326513658944                      72.7313310733776
0.7300075150837726                      72.24654586114522
1.2209457036576696                      69.71996519380937
2.062353336085214                       50.76028746131138
0.5685046122325719                      44.90515825964432
0.6994645262755821                      43.72541529795878
0.6572329365491988                      33.37442078957705
1.0192100131027082                      18.410526779358293
1.0808876324653045                      4.531060524696579
0.19130828691828886                     4.436357203678213
3.423483345725764E-10                   1.8117326798071072E-10

  Why does the actual distance always decrease but the residuum does not?
  Why is the distance so big to begin with? Is there a way to scale the Matrix or the vector to reduce A) the amount of steps required B) reduces the distance?


texts: Running time of a function $P$ calling itself via $P(P(n/2))$

texts:
int P(int n)
{
  if (n==1)
    return 1;
  else
    return P(P(n/2));
}

How will this function P(P(n/2)) be executed and what will be the recurrence relation for this code?
Original image with the code


texts: How CPU know which process generated an interrupt?

texts:
When a computer OS supports multi-program, it needs to have a scheduling algorithm to handle which process will be run by the cpu.

If a process is in state 'blocked' waiting for IO, the scheduling causes another process to be taken by the cpu while the process in state 'blocked' is waiting for a response I/O. In this situation, when the process returns to state 'ready' and then runs, how does the cpu know which process to run and where it was stopped ?


texts: Shortest distance between a point in A and a point in B

texts:
Given two sets $A$ and $B$ each containing $n$ disjoint points
  in the plane, compute the shortest distance between a point in $A$ and a point in $B$, i.e., $\min \space \{\mbox{ } \text{dist}(p, q) \mbox{ } | \mbox{ } p \in A \land q \in B \space \} $.

I am not sure if I am right, but this problem very similar to problems that can be solved by linear programming in computational geometry. However, the reduction to LP is not straightforward. Also my problem looks related to finding the thinnest stip between two sets of points which obviously can be solved by LP in $O(n)$ in 2-dimensional space.


texts: Finite automaton whose alphabet is $\mathbb{N}$

texts:
Is it possible to have a finite automaton where $\Sigma = \mathbb{N}$? Why or why not?

I think it is possible to have a set of all natural numbers, however I'm not sure why.


texts: Are all instructions eventually converted to zero-operand instructions?

texts:
Recently, my demonstrator said that all instructions are eventually converted to zero-operand instructions just before they get executed. yet another demonstrator said that this "doesn't make any sense", and I don't know who to believe; none of them really gave any logical arguments.

So, I want to know is any of them right at all? I tried searching for the answer but I didn't find anything.


texts:
I wonder what's the time complexity of the following selection problem I found while thinking of a string-matching problem.

[Assuming operations on integers take $O(1)$ time]

We are Given $m$ sets, with $n$ integer numbers each. We want to select exactly one integer from each set, to make a set S, such that $~ l = \max(S) - \min(S)~$ is minimized.

For example, n = 4, m = 3:

$S_1 = \{1, 43, 71, 101\}$

$S_2 = \{18, 53, 80, 107\}$

$S_3 = \{3, 16, 51, 208\}$

Now

$~S = \{43, 53, 51\}$

has one number from each set and

$~l = \max(S) - \min(S) = 53 - 43 = 10 ~$

wich is the minimum possible value of $l$ (I think).

First thing I tried was a reduction to the set cover problem, but I wasn't able to find one.


texts: motivation and idea of defining non-deterministic Turing machine

texts:
This is a very basic question but I spent some time reading and find no answer. I am not computer science majored but have read some basic algorithm stuff, for example, some basic sorting algorithms and I also have some basic knowledge of how computers operate. However, I am really interested in the idea of a Turing machine, especially the non-deterministic one.

I have read Wiki about the definitions of a Turing machine (and watched some youtube videos) and I sort of accept that, although I really feel that this is a huge jump from an algorithm to an abstract machine. From my understanding (you are more than welcome to correct me):

A Turing machine is a machine performing works specified on a cookery book (algorithm).
The pages of the cookery book represent the "states" of your machine and each page contains a table saying that which state and which cell your machine will move to given the alphabet the machine read and your current state. (NB. This is not a function but a partial function because it is possible that the machine stops.)
So, to guess the idea and motivation of defining an abstract Turing machine, I imagine that the algorithm corresponds to the partial map, the memory of the computer corresponds to the (infinitely long) tape and what's finally on the tape is the answer to the question you wanna solve.

So, Turing machine looks like a machine to realize any algorithm to solve problems. One just "translates" any algorithm to a set of mysterious simple rules (i.e. the partial function) and let the machine do the laboring job and then we get the solution.

In this respect, Turing machine is always deterministic, because algorithms are deterministic. It tells you what to do next precisely. This is no uncertainty. Turing machine is just a machine to realize any algorithm.

OK, This is very abstract and I sort of accept it. However, then I read something called non-deterministic Turing machine (NTM) and then I was knocked down. A NTM is pretty much similar to a Turing machine except that the partial function is now replaced by a "relation". That is, it is a one-to-multiple map and it is no longer a (partial) function.

Could someone explain to me why we need such multiple options? I would never expect to encounter something uncertainty in the implementation of an algorithm. It is like telling the machine: you first do A, then if you find yourself in a state B and find the data is now B' then you choose for yourself one of the 10 allowed next steps?

Are NTM's corresponding to a set of algorithms that need uncertainty? for example the generation of random numbers? If no, why do we need to allow multiple choices for a Turing machine?

Any help will be appreciated!

update From the linked post, it looks like the introduction of NTM naturally leads to a class of "problems" (not algorithms because a problem can be solved by several algorithms with different efficiencies) called NP problems. Forgive me that I still feel that every step is such a huge jump... Could someone close the gaps a little bit? thanks a lot!

Motivated by @reinierpost's answer, I found this explanation of NP problems on CMI website. The example problem is to choose 100 students from 400 candidates subject to some constraint that some pairs of students cannot be included. In this case, I can imagine that a Turing machine trying to solve this may naturally equip itself with a cloning ability such that it is able to generate the solution with multiple choices in the steps. Then, as long as some choices or branches of the NTM work, the machine finds the solution(s). In this sense, an NTM looks like a multi-threading parallelization to save time?


texts: When you install an OS on a piece of hardware such as a Macbook, what is happening logically? In other words, how does the software "talk" to the hardware? Is it the same logical process with every OS and every piece of hardware, or is this process different for each OS and each piece of hardware?


texts: Is process address space part of Process Control Block(PCB)?

texts:
I recently read about the process address space and PCB and trying to link them together. I don't find much literature on their relation.

Is the process address space a part of the PCB data structure?


texts: How can I show that the Cook-Levin theorem does not relativize?

texts:
The following is an exercise which I am stuck at ( source: Sanjeev Arora and Boaz Barak; its not homework ) :

  Show that there is an oracle $A$ and a language $L \in NP^A$ such that $L$ is not polynomial-time reducible to 3SAT even when the machine computing the reduction is allowed access to $A$.

What I tried was, take $A$ to be the oracle to halting problem and let $L=\{1^n | \;\exists \; \langle M,w \rangle \; \text{s.t.} \; |\langle M,w \rangle|=n \; \text{ and Turing machine M halts on w} \} $.
With this assignment I ensure $L \in NP^{A}$ and $L$ is not polynomial reducible to 3SAT if oracle is not provided to the machine carrying out reduction. Although to map an instance $1^n$ I would have to search through $2^n$ strings even if oracle is provided to the reduction machine. But this does not seem like a proof for absence of polynomial reduction in this case. Is there a way to prove it using the same example ? Is there a simpler example ?


texts: Name for "confluence unless both sides are normal"

texts:
I am looking for a name for the property $\mathbf{?_2}$ (and for that, it is sufficient to find a name for the property $\mathbf{?_1}$ since "Uniform" could then be added in front of it).

Confluence : If $t_1\leftarrow^* t \rightarrow ^* t_2$, then one of the following is true:

There is $t'$ such that $t_1\rightarrow^* t' \leftarrow^* t_2$.

Uniform confluence : If $t_1\leftarrow t \rightarrow t_2$, then one of the following is true:

There is $t'$ such that $t_1\rightarrow t' \leftarrow t_2$;
$t_1=t_2$.

$\mathbf{?_1}$ : If $t_1\leftarrow^* t \rightarrow^* t_2$, then one of the following is true:

There is $t'$ such that $t_1\rightarrow^* t' \leftarrow^* t_2$;
Both $t_1$ and $t_2$ are strongly normalising.

$\mathbf{?_2}$ : If $t_1\leftarrow t \rightarrow t_2$, then one of the following is true:

There is $t'$ such that $t_1\rightarrow t' \leftarrow t_2$;
$t_1=t_2$;
Both $t_1$ and $t_2$ are normal forms.

One way this property arises, is if you have two rewriting systems $S_1=(X_1,\rightarrow_1)$ and $S_2=(X_2,\rightarrow_2)$ and then look at  $S=(X_1\times X_2, \rightarrow)$ where $(x_1,x_2)\rightarrow (x_1',x_2')$ iff $x_1\rightarrow_1 x_1'$ and $x_2\rightarrow_2 x_2'$ (i.e. you reduce in parallel in both components). Then if both $S_1$ and $S_2$ are confluent (resp. uniformly confluent), $S$ is $\mathbf{?_1}$ (resp. $\mathbf{?_2}$).

For a minimal example, take $X_1=\{u,l,r,d\}$ (up, left, right, down) with $u\rightarrow_1l$, $u\rightarrow_1r$, $l\rightarrow_1d$ and $r\rightarrow_1d$ (i.e. $\rightarrow_1$ only moves downwards) , and $X_2=\{0,1\}$ with $0\rightarrow_2 1$. The pair $(l,1)\leftarrow (u,0)\rightarrow (r,1)$ can not be closed because $1$ is normal so that the system is not confluent.


texts:
Is it true or false that for running a dfs on an undirected graph G with a simple cycle than this cycle will have exactly one back edge?

Looks to me likes its true ,is it?


texts: Given a trie with word occurrences (frequency), how can we sort the words( both ascending and descending) on the basis of their frequency?


texts: How does the MMU map multi-channel setups

texts:
Given that the MMU does all the memory translations and etcetera, how does it maps a system consisted of multiple RAM chips?
Are their spaces concatenated (e.g Chip 1 + Chip 2)? If so, how does that works given ASLR?


texts: How to calculate image gradient with respect to homogeneous coordinate vector?

texts:
I want to use the direct method of computing the homography between two images to estimate the plane parameters (normal and depth [= distance from camera]) of a 3D plane.
If we have two images of the same 3D plane, then we know that the same point in the images is related by a homography. If one camera is placed at the origin, the homography is given by
$$^{2}H_1=\,^2R_1-\frac{tn^T}{d}$$
where R is the rotation between cameras (3x3 matrix), t is the translation (3 vec), n is the plane normal and d is the distance to the camera. (see here)
Since the homography tells us for an image point in one image where the corresponding image point in the other image is (as long as we stay on the 3D plane), we can write
$$I_1((\,^2R_1-\frac{tn^T}{d})x)=I_2(x)$$
where x is a homogeneous coordinate vector, e.g. (a,b,1). This equation should hold if the baseline between the images is not too big and lighting conditions are similar between images.
If we have a fixed stereo camera, we know R and t and can minimize the following function to get the plane orientation n and distance from the camera d:
$$F = I_1((\,^2R_1-\frac{tn^T}{d})x)-I_2(x)$$
Now if I take the partial derivative of F squared according to d and n, it results in
$$\frac{\partial F}{\partial d} = 2F\;\nabla I_1\;\frac{tn^T}{d^2}x$$
$$\frac{\partial F}{\partial n_i} = -2F\;\nabla I_1\;tx_i$$
The problem is the occurence of gradient of I_1. Simply from a number-of-dimensions-analysis, it must be a 3-vector, i.e. the image gradient with respect to homogeneous coordinates. How do I calculate it?
I thought about simply truncating the image gradient to the "true" gradient, i.e. 2-vector and considering the following vector given by the term $$\frac{tn^T}{d^2}x$$ to be a homogeneous vector, which can also be converted to a 2-vector. The problem here is that this term sometimes evaluates to values where the "z-component" of x is 0 and cannot be converted to a 2 vector, so I guess I must stick with the homogeneous representation.


texts: Are there are problems in NP that have been shown to be not NP-complete but it is still not known if they are in P or not?

texts:
I am not talking about NP-indeterminate class because those problems have to be shown to not exist either in P or NP-complete class and existence of such problems proves P!=NP. I am interested to know if we are half-way there i.e. problems that have been proven to be not NP-complete but are in NP but we don't know if they are in P as well.

What about such problems whose deterministic polynomial solution was found only recently? Was primality testing such a problem?

I would appreciate if the answers are given for someone like me who only has a high level understanding of computational complexity theory.


texts:
I am recently thinking about proving the undecidability of some problem. This problem has been formalized in Coq and by staring at it, people including me think "for sure" this is undecidable. "For sure" is a good source for surprises so I think I should try to prove it, probably formally.

But then I recall MLTT is compatible with LEM, and now my brain is in a loop:

To prove that theory is undecidable, I have to show that

forall x y ... z, ~({P x y ... z} + {~P x y ... z})

where x y ... z are the parameters. Namely, it's not true that we can decide the problem for all inputs.

On the other hand, LEM claims that for all P x y ... z we can obtain either witness or refutation, and its compatibility with type theory just says the falsehood is not provable. This means MLTT and others are just not able to express computability problems. Therefore, I am wondering can formal systems encode computability at all, or it's just I am mistaken? Is there anyone actually tried to formally prove undecidability in formal systems like Coq?

Even though I am using Coq, but since the compatibility is from MLTT, so I guess LEM does not have to live in Prop.

Apologies if I am being stupid for the moment but I think my brain is in a serious loop now.


texts: How to solve the feasibility problem in 0-1 integer programs?

texts:
I have an NP-hard 0-1 integer program that I need to solve. The issue with this problem is that even finding a feasible solution (ignoring the objective function) is NP-hard.

Let us look at two examples to illustrate my problem. On the one hand, the knapsack problem is an NP-hard problem which is defined as follows:

$$
    \begin{align*}\tag{$\mathit{P}_1$}
      & {\underset{\mathbf{ x }}{\text{maximize}}}
      & & \sum_{j=1}^nv_jx_j\\[3pt]
      & \text{subject to}
      & & \sum_{j=1}^{n} w_jx_j \leqslant\mathit{W},\\[3pt]
      & & & x_j \in\{0, 1\}, \forall\, j.
    \end{align*}
$$
However, finding a feasible solution to the knapsack problem is not NP-hard. In other words, find $x_j\in\{0, 1\}$ for $j=1,\ldots, n$ such that $\sum_{j=1}^{n} w_jx_j \leqslant\mathit{W}$ is easy.

On the other hand, the variable-sized bin packing problem is also NP-hard and is given by the following 0-1 integer program:

$$
    \begin{align*}\tag{$\mathit{P}_2$}
      & {\underset{\mathbf{ x }, \mathbf{ y }}{\text{minimize}}}
      & & \sum_{j=1}^ny_j\\[3pt]
      & \text{subject to}
      & & \sum_{i=1}^{m} a_ix_{ij} \leqslant\mathit{V}_jy_j,\forall\, j\\[3pt]
      & & & \sum_{j=1}^n x_{ij}=1, \forall\, i.\\[3pt]
      & & & x_{ij}, y_j \in\{0, 1\}, \forall\, i, j.
    \end{align*}
$$
However, finding a binary variables $x_{ij}$ for $i=1\ldots,m$ and $j=1,\ldots,n$ seems to be as hard as finding a solution to the bin packing problem.

In fact, if I apply the first-fit algorithm to the following instance of bin packing: two bins with capacities $V_1=3$ and $V_2=4$, respectively, and three items with values $a_1=2$, $a_2=2$ and $a_3=3$. The first-fit algorithm (if it processes the items in the order $a_1$, $a_2$ and $a_3$ will put item 1 into bin 1, item 2 into bin 2 and there is no bin left (i.e., $n=2$). Hence, the first-fit algorithm should output error or something since it cannot assign all items to the $n$ bins. Clearly, the optimal assignment can be items 1 and 2 into bin 2 and item 3 into bin 1. How to solve this issue with the greedy first-fit algorithm?

In general, if I have a 0-1 integer program that is hard to check its feasibility, how to design an algorithm that makes few errors? For example, for the bin packing problem, all the papers I found are not interested in finding feasibility but they are trying to the solve the problem when it is feasible.  In many practical cases we cannot pack all the items in $n$ bins using our greedy approaches (even though the optimal algorithm can).

Any suggestions where to find solutions to feasibility of 0-1 integer programs?


texts: Question about the formal proof of the inorder traversing

texts:
In Don Knuth's famous series of books, The Art of Computer Programming, section 2.3.1, he describes an algorithm to traverse binary tree in inorder, making use of an auxiliary stack:

T1 [Initialize.] Set stack $\rm A$ empty and set the link variable $\rm P\gets T$
T2 [$\rm P=\Lambda$?] If $\rm P=\Lambda$, go to step T4.
T3 [Stack$\rm \;\Leftarrow P$] (Now $\rm P$ points to a nonempty binary tree that is to be traversed.) push the value of $\rm P$ onto stack $\rm A$, then set $\rm P\gets LLINK(P)$
T4 [$\rm P\Leftarrow Stack$] If stack $\rm A$ is empty, the algorithm terminates; otherwise pop the top of $\rm A$ to $\rm P$.
T5 [Visit $\rm P$] Visit $\rm NODE(P)$. Then set $\rm P\gets RLINK(P)$ and return to step T2.

We can plot a flow chart of the algorithm. In the succeeding paragraph, he gives a formal proof of the algorithm:

Starting at step T2 with $\rm P$ a pointer to a binary tree of $n$ nodes and with the stack $\rm A$ containing $\rm A[1]\dotsc A[m]$ for some $m\ge 0$, the procedure of steps T2-T5 will traverse the binary tree in question, in inorder, and will then arrive at step T4 with stack $\rm A$ returned to its original value $\rm A[1]\dotsc A[m]$.

However, as far as I know, such a formal proof is quite different from the general method described in section 1.2.1:

for each box in the flow chart, that if an assertion attached to any arrow leading into the box is true before the operation in that box is performed, then all of the assertions on relevant arrows leading away from the box are true after the operation.

In fact, such a method is somewhat equivalent to Hoare logic, which is used to formally check the validity of algorithms.
Can we turn the statement mentioned to prove the traversing algorithm into a schema of Hoare logic, or the assertion-attachment of a flow chart?
Thanks!


texts: Picking an $m$ which minimises the sum $\sum_{i=1}^{i=n} |x_i-m|$ where $x_i$ is an element of the list $[x_1,x_2,...,x_n]$

texts:
I've got the following problem:

Tommy has a toy consisting of wooden posts and in each move he can either hit one post (which decreases its height by 1) or pull out a post (which increases its height by one). Tommy wants to set all poles to the same height but he must do that using minimal ammount of moves. How many moves must be made?

An input is a list $[x_1,x_2,...,x_n]$ where $x_i$ is a starting height of pole number $i$.

Mathematically speaking we must find an $m$ which minimises the sum $\sum_{i=1}^{i=n} |x_i-m|$ where $x_i$ is an element of the list $[x_1,x_2,...,x_n]$ and then all we need to do is to calculate this sum. But how to find such an $m$? And if I have a candidate for $m$, how to prove that I am right?


texts:
I am given a connected graph. I have to construct a spanning tree from the graph, that has minimum diameter.

However, I looked for the solution, and the solution goes like this.

If the diameter of the tree is even, then it must have a center node. Then we try to find the center node by finding all pair shortest path first, and then trying to check every node if it can be a center or not. We do this the following way.

Lets say the current vertex we are checking is called v.

If the two most farthest vertex from v is x and y, and they have the same distance from the vertex  v then v is a potential center of a diameter. Then we store ans = dis[v][x] + dis[v][y]. We find the minimum of such node v for which dis[v][x] + dis[v][y] is minimum. Here, dis[v][x] means the distance from v to x.

To avoid the diameter being odd, we introduce new vertex in every edges.

For example if there is an edge like 1-2 then we introduce a new vertex ( let's say 3 ) and the edge 1-2 becomes 1-3 and 3-2.

What I need is a proof of this solution.  Why are we taking the minimum of dis[v][x] + dis[v][y]? How does this guarantees the minimum diameter?

Also, the solution mentioned if the diameter isn't even, then you might want to check the most distanced vertex from v being x and y and as the diameter is odd, |dis[v][x] - dis[v][y]| = 1 this check will not provide a correct answer.

What I am searching for is a formal proof of this.

The problem is listed in UVa Online Judge, Here's the link:

http://uva.onlinejudge.org/external/108/10805.pdf

The solution I found is this:

https://yuting-zhang.github.io/uva/2016/12/21/UVa-10805.html


texts: Challenging exercises for proof correctness

texts:
I would like to know where I can find challenging exercises that ask to prove the correctness of an algorithm.

The invariant of most of the exercises I’ve found on the internet are quite easy (factorial, binomial coefficients...).

That’s why I was wondering if there exist a book or some online ressources where I can find challenging proof correctness’s exercises ?

Thank you !


texts: If graph isomorphism is in P, is then P = NP?

texts:
I think that, since graph isomorphism is not known to be $\textbf{NP}$-complete, we can not reduce all problems in $\textbf{NP}$ to it, and therefore the implication does not hold.

Additionally, in the accepted answer to this question it is stated, that a proof that graph isomorphism is not $\textbf{NP}$-complete would prove $\textbf{P} \neq \textbf{NP}$. Why?


texts: Can many threads run in a parallel in many-to-one model?

texts:
The book I am reading suggests that in a many-to-one multi-threading model, the threads are unable to run in parallel in a multi-core system.
I am thinking this is not the case because if we have many-to-one means that multiple user threads are mapped to one kernel thread. However, there might be many kernel threads running in a multi-core system . Am I right ?
The threads sharing the same kernel thread might not be able to run in parallel among themselves but when a thread is accessing on kernel thread, another user thread, not sharing the same kernel can be accessing its own kernel thread. So there will still be some user threads that running in parallel in the system.


texts: Worst-case sparse graphs for Hopcroft-Karp Algorithm

texts:
Of large sparse biparite graphs (say degree 4) with N verticies, roughly speaking, which of them cause the worst case running time of the Hopcroft-Karp algorithm? What is their general structure and architecture, and why does it cause a problem?

Further, in many implementations the DFS part is implemented using recursion, eg from Wikipedia:

function DFS (v)
    if v != NIL
        for each u in Adj[v]
            if Dist[ Pair_G2[u] ] == Dist[v] + 1
                if DFS(Pair_G2[u]) == true
                    Pair_G2[u] = v
                    Pair_G1[v] = u
                    return true
        Dist[v] = ∞
        return false
    return true

What is the approximate maximum depth of the recursion in the worst case?


texts: How to balance the inflow and outflow of each vertex in a bipartite graph?

texts:
I have a situation where in a group of people, every person is trading with multiple people and giving them some money. It can be visualised as a directed bipartite graph with L and R as the total set of people. A directed edge from l to r means l gave r some money with weight w which is the weight of the edge. Now I'm an auditing firm and want to make sure that the total amount given out by a person should be as close as possible to the amount received by him. I can limit each such transaction (implying I can reduce the weight of any edge in the graph). What is the best way to solve this approximately with the minimum restrictions required (in terms of actual amount)?

Ex. if

a -> 10 -> b
b -> 10 -> c
c -> 5  -> a

can be limited to

a -> 5 -> b
b -> 5 -> c
c -> 5 -> a

by reducing 10 units of transactions


texts: Algorithm for comparing object dates and types

texts:
I'm looking for a good / efficient algorithm to compare classes of driver licences (or any type of similar objects) and their dates, so that they do not overlap and come in certain order.

eg. We have G1, G2, G, M, etc.

I need to make sure all instances of G1 do not overlap, G1 comes before G2 and does not overlap, and G comes after both, and M is unrelated (there can also be multiple instances of each type, in which case they must not overlap either).

I'm looking to do this without a monster class of if/else statements that no one can ever read.


texts:
I've been trying to wrap my head around the following question for ages, its part of my revision for the upcoming end of year exam, however I fail to see how there is a link from the number to the letter, how will one cycle from 1 to a and iterate to get there? if that makes any sense! We were told that when estimating execution time of a loop, it is likely to be the number of times the loop executes, so therefor a list of length n would take approximately n units of time to execute, that makes sense, its just the cycle from 1-a, then 1-b? like, how many iterations will the loop run to get from 1 to a? it just confuses me! anyhow here it is as on the practice paper:

z := 0
for i from 1 to a
  for j from 1 to b
    for k from 1 to c
      z := z + a*b*c

• How long does it take to compute the k-loop?

• How long does it take to compute the j-loop?

• How long does it take to compute the i-loop?

• How long does it take to compute the algorithm?


texts: Regular expression for binary words with 1 in the middle

texts:
Given the alphabet $\{0,1\}$, generate a regular expression with the following language: $$ \{w\in \Sigma^* \mid w \text{ has odd length and its middle symbol is }1\}. $$

I'm having trouble finding a solution for this regular expression. I think it's impossible because you need to have an even amount of 1's and 0's on both sides of the middle 1. You also would need to have the same amount of 1's and 0's on both sides. Since a regular expression has limited memory, would that make this regular expression impossible?


texts: Given that A reduces to B in $O(n^2)$ and B is solvable in $O(n^3)$, solve A

texts:
Suppose a problem A reduce to problem B and reduction is done in $O(n^2)$ time.
If problem B is solved in $O(n^3)$ time then what about the time complexity of problem A?

Approach:
A is reduced to B . Here reduction is done at polynomial time.
Here B is solved in polynomial time.  So A should also be in polynomial time.
Now A can not be harder than B, So I think A can be $O(n^3)$ or $O(n^2)$.  But logically if I reduced A to B and if B is $O(n^3)$ then it makes no sense for A to be $O(n^2)$, else why would I reduce it to higher complexity? So A is $O(n^3)$.
But my doubt is,  we say while reduction that A can not be harder than B then how can we decide whether it is $O(n^2)$ or $O(n^3)$.
Or is this argument only valid for P, NP classes of problem when I say A can not be harder than B or B must be at least as hard as A?
Answer given is "A is $O(n^3)$",  but why can't it be $O(n^2)$ as "A can not be harder than B" but can be of equal complexity? Or is reducibility just an argument for complexity classes?
Explain if possible how reduction actually works, and why I couldn't apply it to my problem.


texts: What Is the Complexity Class of Deciding Whether a Problem Is in NP? Is It Decidable?

texts:
Title says it all, but to clarify:

Define a problem, called $IsInNP$, as follows:

  Given a Turing Machine $M$ that always halts, $IsInNP$ is the problem of deciding if the problem that $M$ recognizes is in $NP$.

What is the complexity class of $IsInNP$? Is it even decidable? Is the answer the same for any other complexity class, like $NP$-hard? And are those questions even sensible to ask?

By the way, I am aware that the class $NP$ is not enumerable, but since I do not quite understand enumerability and it seems that recursively enumerable problems can be decidable, I do not know if that means that deciding whether a problem is in $NP$, or any other complexity class, is decidable.

Also, I am aware of Rice's Theorem, and I believe it can be interpreted as saying that deciding whether a problem is in $NP$ is undecidable, but I am not certain.

Bonus question if the above questions are sensible: given a property $S$ that only $NP$ problems possess, does the above also mean that deciding whether a problem decided by a Turing Machine $M_2$ has property $S$ is in the same complexity class as $IsInNP$?


texts: How are lamport timestamps useful in practice?

texts:
I am reading Lamport's paper titled Time, clocks, and the ordering of events in a distributed system

I understand what's in there more or less, but I am confused whether Lamport timestamps on their own are useful in practice since just by looking at the logical timestamps, we can't say anything about which happened before what. It seems to me that Lamport timestamps on their own aren't useful, and we need to extend them to something like vector clocks to be useful in practice. Am I missing any details?


texts: How does Earley parsing using an automaton work?

texts:
As described in this paper, you can use an pre-computed automaton to speed up an Earley parse.  I'm not interested in the rigorous proof of this, but just how the basic algorithm works so that I can implement it.  Understanding this paper on my own would take a long long time, and I don't think it's justified for this algorithm because it seems simple enough, but the paper is accademic and is required to be over my head, so they didn't write it for a reader like me.

For instance, what does a transition labeled with a variable in the automaton mean?  How does this thing work?


texts: Finding the most frequent element assuming $\Theta(n)$ frequency

texts:
We know [Ben-Or 1983] that deciding whether all elements in an array are distinct requires $\Theta(n \log(n))$ time; and this problem reduces to finding the most frequent element, so it takes $\Theta(n \log(n))$ time to find the most frequent element (assuming the domain of the array elements is not small).
But what happens when you know that there's an element with frequency at least $\alpha \cdot n$? Can you then decide the problem, or determine what the element is, in linear time (in $n$, not necessarily in $1/\alpha$) and deterministically?


texts: Show that the string $( [ ) ]$ is not in a Dyck language

texts:
I think I understand why the string $( [ ) ]$ is not in a Dyck language.

In my words,

D2* is all the dyck words of 2 parentheses.

From the definiton of $D2*$, every words must have exactly 2 pairs correctly nested pairs of parentheses.

All the words of the language are given by

$\sum = { (1, )1, (2, )2 } $

The alphabet consisting of 2 kinds of left and right parentheses.

The language is given by the following grammar :

Terminal set is $\sum$
Start variable is not in terminal set
$ S -> \big( \epsilon | SS | (i S )i \big)$ for all i > 1

But the form of that word is $(i (j )i )j$  which fails to match the definition.

But I'm having trouble writing a formal proof on that.


texts: Show that the OR of n variables cannot be expressed as a polynomial over Fp of degree less than n

texts:
Here is a question from Computational Complexity by Arora and Barak:

Show that representing OR of $n$ variables $x_1,x_2,\dots,x_n$ exactly over a polynomial in $GF(q)$ requires degree exactly $n$.
(This is Exercise 6 in the chapter on circuit lower bounds.)

How do I approach this problem?


texts: Worst Case for AVL Tree Balancing after Deletion

texts:
After deleting a node in an AVL tree, self-balancing (zig-zag rotation or the left-right balancing) maintains O(logn) time that is not guaranteed in other unbalanced trees (like BST).
The Balancing operation is said to be O(logn).
What is the worst case for balancing? (I guess it will require balancing at every node all the way up till the root)
Any specific type of tree providing the worst case?


texts: Anagram sorting with inversion count oracle

texts:
Given a permutation $P$ of an unknown array $U$ of length $N$ and a function $f(Q)$ that calculates the minumum number of swaps between consecutive elements of array $Q$ to reach $U$, what is the minimum number of invocations of $f$ to discover $U$, worst case?

An upper bound of $N$ invocations is at hand:

Calculate $F(P)$, then for each $i,2\le i\le N$ move $P_i$ to the start of array $P$,  then calculate $f(P)$ to discover the correct position of $P_i$ in subarray $P_{1...i}$. Being a little more careful, we can spare the last calculation of $f(P)$ since having $P_{1...N-1}$ ordered and knowing $f(P)$ is enough to calculate the correct position of $P_N$.

This yields the upper bound of $N-1$ invocations

For an array with length $2$, is clear that we need at least one invocation so this is a tight bound.

Question: For a sufficiently large $N$, is it possible to do less than $N-1$ invocations of $f$ in the worst case?.

Asymptotically, since the possible outputs of $f$ are $0...N(N-1)/2$ by the pidgeonhole principle we need at least $O(\log_{N(N-1)/2}(N!))=O(\log_N(N!))=O(N)$ (by Stirling's approximation) invocations to discover the array $P$. So this prompts a second question:

Question: For a sufficiently large $N$, is it possible to do less than $c\times N$ invocations of $f$ for some constant $c<1$ in the worst case?.


texts: Pizza commercial claim of 34 million combinations

texts:
A pizza commercial claims that you can combine their ingredients to 34 million different combinations. I didn't believe it, so I dusted off my rusty combinatorics skills and tried to figure it out.  Here's what I have so far:
From the online ordering site I got the choices

crust (4 types, choose 1)
size  (4 types, choose 1) some crusts are limited to a certain size - not accounting for that, but would like to.
cheese (5 types, choose 1)
sauce  (4 types, choose 1)
sauce level (3 types, choose 1)
meats (9 types, choose up to 9)
non-meats (15 types, choose up to 15)

So I figured this was a combination problem (order is not important) and not an n choose k problem, null is allowed for anything but crust and crust, size, cheese, sauce and sauce level would all be choose only one. Meats and non-meats $2^?$? So that would be:

crust  $\binom{4}{1}=4$
size  $\binom{4}{1}=4$
cheese $\binom{5}{1}=5$
sauce  $\binom{4}{1}=4$
sauce level $\binom{3}{1}=3$
meats $2^9 = 512$
non-meats $2^{15} = 32768$

At this point I'm stuck, how do I combine these to arrive at the total number of possible combinations?

I found this site helpful.

ETA:
If I don't account for the limitations on crust size - some crusts are only available in certain sizes - there are over 16 billion; 16,106,127,360 combinations available, so they were off by quite a bit.


texts: Why are bottom-up selector matching algorithms more efficient?

texts:
Most implementations of CSS-like selectors (that is, patterns that may match paths in a tree) seem to use a bottom-up approach. That is, for each node in the tree, they check for a match against the rightmost element of the selector pattern. If the node matches, they search up its ancestors checking for a match against the second-to-rightmost element of the selector pattern, and so on.

My question is, why is this more efficient than starting from the top and working down (left-to-right in the selector pattern)? In both approaches it seems like you have to examine every path, and  both approaches can benefit from short-circuiting.


texts: P, Q, ((P→Q)→R) ⊢ R using only modus ponens

texts:
Can $R$ be inferred from $P$, $Q$, and $(P \to Q) \to R$ using only modus ponens?
My understanding is that it can, as shown below, but I was told this was incorrect.

Proof of ${P, Q, (P \to Q) \to R} \vdash R$ using modus ponens:

P, Q, (P->Q)->R  : Given
Q, (Q)->R        : By Modus Ponens
R                : By Modus Ponens


texts: Do polynomial reduction functions work both ways?

texts:
For example to prove 3-Sat ≤p Independent Set do I just have to prove this theorem:

Theorem- Formula F is satisfiable IFF graph has an independent set.

If I have to prove it this way does this also mean that Independent Set ≤p 3-Sat as well since the theorem goes both ways?


texts: On an AVL tree insertion/deletion, which nodes have their height changed and why?

texts: I've begun learning about AVL trees. It seems that the assertion with this data structure is that with every insertion/deletion, the only nodes whose height changes are nodes on the path towards the root (from the inserted/deleted node). How exactly is this 'proved'? I've gone through many examples and it would appear to hold true, but I haven't seen a convincing proof/explanation from any of the texts I have read.


texts:
I'm learning about CRC and Hamming distance and I have three questions.
Lets say we have binary code described by ($+$ refers to sum modulo $2$):

\begin{alignat*}{1}
a_1 &+ a_2 &+ a_3 &+ a_4 &+ a_5 &= 0\\
a_6 &+ a_7 &+ a_8 &+ a_9 &+ a_{10} &= 0\\
a_1 &+ a_6 &+ a_{11} &&&= 0\\
a_2 &+ a_7 &+ a_{12} &&&= 0\\
a_3 &+ a_8 &+ a_{13} &&&= 0\\
a_4 &+ a_9 &+ a_{14} &&&= 0\\
a_5 &+ a_{10} &+ a_{15} &&&= 0
\end{alignat*}
We received: $11011\ 01010\ 10111$

So if I would like to check minimal Hamming distance, then I should compare each codeword with others, right?

$\begin{pmatrix}
1&1&1&1&1& & & & & & & & & & \\
 & & & & &1&1&1&1&1& & & & & \\
1& & & & &1& & & & &1& & & & \\
 &1& & & & &1& & & & &1& & & \\
 & &1& & & & &1& & & & &1& & \\
 & & &1& & & & &1& & & & &1& \\
 & & & &1& & & & &1& & & & &1\\
\end{pmatrix}$

I have done so, and minimal Hamming distance $ = 6$. Is there any faster method?

Second question: how many distortions causing undetectable errors? Is there any formula for that?
And last one, how to compute redundancy using above information. I'm using formula: $ R = \dfrac{n-k}{n}$. In above example $n=15$, but I don't understand how to obtain $k$.


texts:
I am looking for an easy and introductory paper on the proof of Courcelle's Theorem. I am also interested in its connection to parameterized complexity regarding the treewidth.

I am only a beginner in this field.

Any suggestions?


texts: Complexity of "Fast Poisson Disk Sampling in Arbitrary Dimensions"

texts:
I came across the paper Fast Poisson Disk Sampling in Arbitrary Dimensions which gives an algorithm for generating Poisson disk points in $\mathbb{R}^n$.
It's claimed that the algorithm is linear time. However, I wonder if this assumes the dimension n is constant.

My understanding of the analysis is that to generate $N$ points requires $2N-1$ iterations, and each iteration is constant time.
I agree with the $2N-1$ iterations, but I'm not sure about each iteration being constant time.

In each iteration, they sample a small constant $k$ points, and then check whether or not these points are near to any of the previously generated points using a background grid to assist. However, isn't the number of neighboring cells to check exponential in $n$?
It seems like the runtime of the given algorithm using the background grid should be something like $k N \exp(n)$, (or $kN^2$ if you just check the other points directly).

Have I misinterpreted the algorithm or the analysis? I get that for a fixed $N$ it will be constant (assuming $k$ is constant). Is that the standard assumption when saying an algorithm is "linear time"? To me this seems a bit misleading because they mention dimension in the title.
If you go to high enough dimension and use the "constant time" algorithm, the constant will be exponential in $n$ which means the algorithm is not "fast" in "arbitrary dimensions".

As an afterthought, does it even make sense for $k$ to be constant. If you don't increase $k$ exponentially with $n$ then the "density" (number of points per volume) of the points will go to zero (although this is more of a "modeling" choice than an analysis choice).


texts: On $1$-way functions and formalizing my intuitions about them

texts:
Let $a: \{0, 1\}^* \to \{0, 1\}^*$ be a $1$-way function and $b: \{0, 1\}^* \to \{0, 1\}^*$ be a $1$-way permutation.

Now, it makes intuitive sense to me that $a \circ b$ should be a $1$-way function, but I am having problems formalizing this. What would a rigorous proof of this look like? Or are my intuitions wrong and this is simply not a true statement?


texts: $\mathsf{PP}$ compared to $\mathsf{\#P}$

texts: Since know that $\mathsf{TC^0\subsetneq PP}$, I wonder if we also know that $\mathsf{TC^0\subsetneq\#P}$? I understand that $\mathsf{\#P}$ is in counting hierarchy.


texts: Number of $1$'s in a Kolmogorov-random number

texts:
The problem I'm trying to tackle is to show that for a Kolmogorov-random number of length $n$, the amount of $1$'s in its binary representation is greater than $n/4$.

My only idea so far, is to use a Turing machine that takes indices of $1$'s as an argument and produces a binary sequence accordingly. Then, for instance, we could say the amount of ones is at least $\sqrt n$ as (roughly) $C_U(n)\leq \sqrt n\log n < n$ for $n$ large enough (each index is at most of length $\log n$).
But this doesn't allow us to infer there are more than $n/4$ ones.

Is there any other way to generate some given number that would prove the statement in question?


texts: How do I tell if $G$ is a forest in log-space?

texts:
How does to prove that language
$$\textbf{X} = \{G \mid\text{ all connected connected components in $G$ are trees}\} \in \textbf{L}\,?$$ I know how to prove that language of undirected trees is in $\textbf{L}$ but I don't know what to do next.


texts:
I've run into a problem concerning epsilon transitions and removing them. Specifically, it is to do with the picture seen in this post. My problem is that I am unsure of what to do with q1. I've already attempted to solve it but I don't know if it's correct.
Should it just sit there still with no inputs going to it essentially making it a dead state? What should its loop be that was once an epsilon loop?

Thanks, all help appreciated!


texts: Subset-Sum Problem Variant with Changing Target Sum - NP Complete?

texts:
Is the Subset-Sum Problem (SSP) with a changing target sum (which is dependent on the chosen subset) also NP-complete? If so, how would I reduce SSP to this or prove that it is NP-complete in another way?

This is the last step on a larger problem I'm working on and greatly appreciate the help!


texts: occur-check, does nominal unification has it?

texts:
In unification, there is a "occur-check".  Such as $X = a \, X$ fails to find a substitution for $X$ since it appears on right hand side too.
The first-order unification, higher-order unification all have occur-check.

the paper nominal unification described a kind of unification based on nominal concepts. But I did not mention "occur-check" at all.

So, I am thinking why? does it has occur-check?


texts: Theoretical CS and Math - self-study recommendations

texts:
I am a non-CS grad and my field of study is unrelated to CS. However, as part of a larger plan to become a computer scientist, I want to obtain a solid background in theoretical computer science and math as it relates to CS. I did a plenty of research and selected the following best/really good books on the topic of CS and math and would like to ask for your opinions on:

Completeness of topics covered (please recommend anything I've missed)
Overlap of material covered / overkill area (please recommend books that should be removed from the list)
Order to study the books (I listed in the order that I think they should be studied)

The list feels excessively long, so I would appreciate recommendations to remove some books, without the loss of the core knowledge require for CS.

So, the books are:

Mathematician's Delight by W. W. Sawyer
How to Prove It: A Structured Approach by Daniel J. Velleman
How to Solve It: A New Aspect of Mathematical Method by G. Polya
An Introduction to Functional Programming Through Lambda Calculus by Greg Michaelson
Foundations of Computer Science by Al Aho and Jeff Ullman (http://i.stanford.edu/~ullman/focs.html)
Concrete Mathematics: A Foundation for Computer Science by Graham, Knuth, and Patashnik
Introduction to the Theory of Computation by Michael Sipser
Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
Computational Complexity: A Conceptual Perspective by Oded Goldreich
Computational Complexity: A Modern Approach by Sanjeev Arora, Boaz Barak
A Course in Combinatorics by J. H. van Lint, R. M. Wilson
Computability: An Introduction to Recursive Function Theory by Nigel Cutland
Computers and Intractability: A Guide to the Theory of NP-Completeness by M.R. Garey, D.S. Johnson
Theory of Recursive Functions and Effective Computability by Hartley Rogers
Inequalities by G.H. Hardy, J. E. Littlewood, G. Polya
Mathematical Logic: A Course With Exercises (Part I): Propositional Calculus, Bookean Algebras, Predicate Calculus by René Cori, Daniel Lascar
Mathematical Logic: A Course With Exercises (Part II): Recursion Theory, Godel's Theorems, Set Theory, Model Theory by René Cori, Daniel Lascar


texts:
Given an integer sequence $\{ a_1, a_2, \ldots, a_N  \}$ that has length $N$ and a fixed integer $M\leq N$, the problem is to find a subset $A =\{i_1, \dots, i_M\} \subseteq [N]$ with $1 \leq i_1 \lt i_1 \lt \dots \lt i_M \leq N$ such that

$\qquad \displaystyle \sum_{j=1}^M j \cdot a_{i_j}$

is maximized.

For instance, if the given sequence is $-50; 100; -20; 40; 30$ and $M = 2$, the best weighted sum arises when we choose positions 2 and 4.

So that we get a value $1 \cdot 100 + 2 \cdot 40 = 180$.

On the other hand, if the given sequence is $10; 50; 20$ and $M$ is again 2, the best option is to choose positions 1 and 2 that we get a value $1 \cdot 10 + 2 \cdot 50 = 110$.

To me it looks similar to the maximum subarray problem, but I can think of many examples in which the maximum subarray is not the best solution.

Is this problem an instance of a well studied problem? What is the best algorithm to solve it?

This question was inspired by this StackOverflow question.


texts: Do we need visited flags when applying BFS on a tree?

texts:
Do we need visited boolean flags when applying BFS on a tree ?

/**
 * Traverse the grap as BFS
 *
 * @param {String}   $vertex              the key of the source vertex
 * @param {Function} $getAdjacentCallback to get the adjacent verticies
 * @param {Funcrion} $visitCallback       called when a vertex is visisted for the first time
 */
function bfs($vertex, $getAdjacentCallback, $visitCallback) {

  $visited = [];
  $queue = new SplQueue();
  $queue->enqueue($vertex);

  while(!$queue->isEmpty()) {

    $currentVertex = $queue->dequeue();

    // Is unvisited
    if (!isset($visited[$currentVertex])) {
      $visited[$currentVertex] = true;
      $visitCallback($currentVertex);
    }

    // Foreach adjacent vertices, find one of the unvisited adjacent vertcies if any
    foreach ($getAdjacentCallback($currentVertex) as $adjacentVertex) {

      // Is unvisited
      if (!isset($visited[$adjacentVertex])) {
        $queue->enqueue($adjacentVertex);
      }

    }

  }

}


texts: Learning automata for degree constrained minimum spanning tree problem

texts:
I'm trying to understand the algorithm described in "Degree constrained minimum spanning tree problem: a learning automata approach" (Javad Akbari Torkestani, The Journal of Supercomputing; April 2013, Volume 64, Issue 1, pp 226–249).

Given a undirected graph $G = (V, E)$, a weight function $w: E \rightarrow R$ and a value $d \ge 2$, the algorithm finds a spanning tree where each vertex has degree $\le d$ and try to minimize the weight of the spanning tree.

It's seems that for a complete graph the algorithm always create trees that are paths, it is weird since creating only paths does not explore the search space well. Considering that the algorithm find good trees it must do a good exploration of the search space. Note that all graphs in the test set used to
evaluate the algorithm are complete.

Consider for example a complete graph with 5 vertices $(v_1, v_2, v_3, v_4, v_5)$. Suppose the algorithm chooses the root $v_1$ and first action is $v_2$ (that is, the $(v_1, v_2)$ edge). In the second iteration, $i = 2$, $A_2$ actions are update (line 6) to avoid cycles, so $A_2 = \{v_3, v_4, v_5\}$. Suppose that the action $v_3$ is selected, so the edge $(v_2, v_3)$ is added to the three. In the next iteration $i = 3$, and $A_3$ is update to $A_3 = \{v_4, v_5\}$, and so on, producing a path. In my understating, a path will always be produced independently of which vertex is chosen in each iteration, this is because the lines 23-24 (and 18-20) will not be executed for a complete graph. What I'm missing here?

I implemented the algorithm and it always produces paths. The results does not match the results in the paper...

The question is: how can the algorithm produce a tree that is not a path if the input graph is complete?

The algorithm description is in section 3.2. Here is a overview of the algorithm followed by the pseudo-code:

  In this paper, a decentralized learning automata-based heuristic is presented to find a near optimal solution to the DCMST problem. In this method, each graph vertex is equipped with a learning automaton selecting its incident edges as the actions. This algorithm is composed of several stages and at each stage it constructs a degree-constrained spanning tree at random. To avoid the formation of a cycle, LACT uses variable action-set learning automaton and temporarily removes the actions corresponding to the already selected edges. LACT starts the tree construction process at the root node and each vertex randomly selects one of its incident edges, if any. The selected edge is penalized if its weight is greater than the minimum weight selected by the given vertex so far. It is rewarded otherwise. The vertex at the other end of the selected edge continues the tree construction process and this is repeated until a degree-constrained spanning tree is formed subject to the degree constraint. Each vertex locally decides on the optimality of its selected edges. As the proposed algorithm proceeds, for each vertex, the choice probability of the minimum weight incident edge converges to one. The convergence of the proposed algorithm to the optimal (or ε-optimal) solution is theoretically proved.


texts: What is the most efficent single-source shorthest path algorithm in unweighted directed grid graph?

texts:
As regards the topic.
Here is an example of such a graph:


texts: Is the language of words with as many a's in the first as b's in the second part context-free?

texts:
Is $L = \{ W_1W_2 \mid W_1,W_2 \in (a+b)^* , N_a(W_1) = N_b(W_2)\}$ context free? Can we construct an NPDA for the language?

There is a book here that claims $L$ is not CF (without any elaboration), but I think we can construct a NPDA that accepts the language. My guess is we can construct the language with an NPDA where after reading some $a$ and $b$ and pushing $A$ for each $a$ into the stack, makes a guess to jump to a new state and consumes the pushed $A$ with each $b$.


texts:
What is the space complexity of function $f(x) = \sum_{i=1}^x g(i)$ where g(n) is O(n)?

Is it O(n) because the maximum stack size is n, or is it O($n^2$) because there are $n(n+1)/2$ memory references?


texts: General application of principal component analysis to machine learning

texts: Ive written an essay on dimension reduction via pca ( im in high school so this took me a while.. the application im looking for shouldnt be too crazy either ). I would now like to elaborate on its utility in machine learning. I was thinking of looking at how dimension reduction of data results in improved classification outcomes, but im not sure if this viable, and I am open to anything really. Suggestions?


texts: What are the pros and cons of context-oriented programming (COP)?

texts:
I have started reading about COP, but can't really get a grip of it. What I understand is that you use layers to let the software dynmically adapt depending on the context, and this would result in less code duplication.

But other than that, what are the advantages of COP (what can I do with COP that would be hard to do otherwise)? And what are the disadvantages?


texts:
I think PRIME (is the given number a prime number?) is a good example a decision problem.  Therefore, when I'm trying to explain reduction, I'd like to give an example of a problem that is related to PRIME.

What are decision problems that can be reduced to PRIME, and how do these reductions look like?

What are decision problems that PRIME can reduce to, and how do these reductions look like?


texts: How does quicksort with 3-way partitioning ~ $(2 ln 2) NH$ become linear time complexity with many duplicated keys?

texts:
From Algorithms 4th:

  Quicksort with 3-way partitioning uses ~$(2\ln 2)NH$ compares to sort $N$ items, where $H$ is the Shannon entropy, defined from the frequencies of key values.

$ H = -(p_{1}\log_{2}{p_1} + p_{2}\log_{2}{p_2} + .... + p_{k}\log_{2}{p_k}) $

  Given $N$ keys with $k$ distinct key values, for each $i$ from $1$ to $k$ define $f_{i}$ to be frequency of occurrence of the $i$-th key value and $p_{i}$ to be $f_{i} / N$, the probability that the $i$-th key value is found when a random entry of the array is sampled.

How does $(2 \ln 2)NH$ become linear when there are many duplicated keys?

So does it mean that I need to prove:

$H$ is a constant (or should I say have a upperbound ?), and not related to $N$, when there are many duplicated keys.


texts: What is the connection between finite automata and logic (sequential calculus)?

texts:
Languages recognized by finite automata are exactly those definable
by sentences of the sequential calculus, and also exactly those
definable by rational expressions (also called regular expressions)

Howard Straubing, Pascal Weil. An introduction to finite automata and their connection to logic. Deepak D’Souza, Priti Shankar. Modern applications of automata theory, World Scientific, pp.3-43, 2012, IISc Research Monographs. hal-00541028v2
Can you please explain, what is the connection between finite automata and sequential calculus (logic)?


texts: Why F-bounded polymorphism and F-bounded quantification are called, well, F-bounded

texts:
It's claimed in Wikipedia that:

  F-bounded quantification or recursively bounded quantification,
  introduced in 1989, allows for more precise typing of functions that
  are applied on recursive types. A recursive type is one that includes
  a function that uses it as a type for some argument or its return
  value

Here's the article which Wikipedia refers to, and F-bounded quantification is introduced in that article in following fashion:

  F-bounded  quantification  is  a  natural  extension  of bounded
  quantification  that  seems particularly  useful in  connection  with
  recursive  types.

My question is - why though it's F-bounded, what does "F" stands for in this particular context?


texts: Global indexing of shared nodes in parallel

texts:
Consider a tiling of quadrilaterals in 2D that provide complete coverage of a particular region.  N quadrilaterals are distributed across many parallel threads, typically in a way to keep groups of quadrilaterals together.  In each quadrilateral we distribute np nodes, with some nodes located along the boundary of the quadrilateral.  This gives rise to a 2D indexing of nodes (i,j) where i=1,..,N is the quadrilateral index and j=1,..,np is the local index of the node within that quadrilateral.

We now wish to develop a map from (i,j) to a global index of nodes that accounts for coincident nodes that may exist along the boundary of the quadrilaterals (e.g., see attached image of two quadrilaterals with three shared nodes -- np=9 but global index goes from 1..15).  In serial, a simple algorithm would be as follows:

let k = 1
let X = map from local index (i,j) to global index k
for each quadrilateral i
  for each node j in quadrilateral i
    if (i,j) is coincident with a node (i',j')->k' in X
      assign index k' to (i,j)
    else
      assign index k to (i,j) in X
      k = k + 1

In parallel, only elements of this map that are associated with quadrilaterals on the local thread need to be stored.  We can further assume that each thread has complete knowledge of the quadrilateral indices and nodes of its own quadrilaterals and those quadrilaterals and nodes that are spatially adjacent.

So the question is:  Is there a parallel algorithm that performs better than the serial algorithm above?


texts:
According to this link:

  Polynomial Time Approximation Scheme (PTAS) is a type of approximate
  algorithms that provide user to control over accuracy which is a
  desirable feature. These algorithms take an additional parameter ε > 0
  and provide a solution that is (1 + ε) approximate for minimization
  and (1 – ε) for maximization. For example consider a minimization
  problem, if ε is 0.5, then the solution provided by the PTAS algorithm
  is 1.5 approximate. The running time of PTAS must be polynomial in
  terms of n, however, it can be exponential in terms of ε.

  In PTAS algorithms, the exponent of the polynomial can increase
  dramatically as ε reduces, for example if the runtime is O(n(1/ε)!)
  which is a problem. There is a stricter scheme, Fully Polynomial Time
  Approximation Scheme (FPTAS). In FPTAS, algorithm need to polynomial
  in both the problem size n and 1/ε.

What I dont understand is the second paragraph stated above. Can someone explain to me whats the difference between FPTAS from PTAS? Can you enlighten me about exponent of the polynomial can increase dramatically as ε reduces and algorithm need to polynomial in both the problem size n and 1/ε. ? I really dont get it. Please help.


texts: VC dimension of only the rim of a unit disk

texts:
Suppose we have an origin centered circle, ie $x^2 + y^2 =1$, so it's in $\mathbb{R}^2$ (2D). It will be classified as 1 if it lies only on this arc, and will be labeled 0 otherwise. What is the VC dimension?

I think the answer is 2. Any two points can be shattered $(++, -+, +-, --)$. But if we have three points $\{(x_1,y_1),\dots,(x_3,y_3)\}$ that all have the label 1, with radius $r_1 = r_2 = 1$, and $r_3 = 0$, it is impossible to shatter them. Is my intuition correct?

Or can I construct the sample points to my liking (to get the maximum VC dim) so that only the positive labels will be on the rim (have some combination of $x_i^2 + y_i^2 = 1$), and have 0 labels to not lie on the rim, therefore have infinite VC dimension?


texts: Help comparing relative error for different parenthesizations of addition

texts:
I am given two functions:
$ fl(fl(x+y)+z) $ and $ fl(x+fl(y+z)) $ and asked to derive their relative error. Then, given a set of conditions:

a) $ x < y < x $

b) $ x > 0, y < 0, z > 0 $

c) $ x < 0, y > 0, z < 0 $

determine which parenthesization has less relative error.

After some algebra I determined the following relative errors where

$ \epsilon_1 = RE(fl(x+y)),\ \epsilon_2 = RE(fl(fl(x+y)+z) $

$ \epsilon_3 = RE(fl(y+z)),\ \epsilon_4 = RE(fl(x+fl(y+z)) $

$$
\left| \epsilon_2 + \frac{(x+y)}{(x + y + z)}\epsilon_1 \right| \ \text{and}\
\ \left| \epsilon_4 + \frac{(y+z)}{(x + y + z)}\epsilon_3 \right|
$$

I determined that for the case $ x < y < z,\ fl(fl(x + y) + z $ has less relative error. With the largest variable, $ z $ in the denominator alone, as $ z \rightarrow \infty $ the coefficient of $ \epsilon_1 $ would approach $ 0 $.

But for $ x > 0, y < 0, z > 0 $ I'm struggling to generalize anything. I don't see how a conclusion can be drawn without an ordering between $z$ and $x$. And what about when $ y = x + z $? Although this case is independent of the relative parenthesizations. And similarly for the case $ x < 0, y > 0, z < 0 $.


texts:
I have an algorithm with worst-case time complexity in  $\mathcal O (\binom{k}{p-1})$, where $k$ is a parameter and $p$ is the input size of that algorithm. I further have determined that $p-1 \leq k $.
I need an argument which shows that the runtime complexity is solely a function of its parameter $k$, i.e. that the input size $p$ does not matter for runtime complexity.
My own argument goes as follows:
$$ \binom{k}{p-1} = \frac{k!}{(p-1)!(k-(p-1))!} \leq k!$$
Where the first equality follows from the definition of the binomial coefficient and the second inequality follows from the observation that both  $(p-1)!$ and $(k-(p-1))!$ are greater than or equal to $1$.
Thus the algorithm runs in $\mathcal O (k!)$, which is a not a function of $p$ as required.
Is this argument correct or am I missing something?
Maybe I am overcomplicating things and there is a faster / better argument?


texts:
This question seems to be causing a lot of debate and I'm wondering whether my working is correct.

A computer with a single cache (access time 20ns) and main memory (access
time 500ns) also uses the hard disk (average access time 0.01ms) for virtual
memory using paging. If it is found that the cache hit rate is 95% and the page
fault rate is 1%
Calculate the effective (average) access time (EAT) of this system for a
sequential access system.  (a) 73.5ns. (b) 55ns. (c) 50ns. (d) 74.75ns.

My working was as follows: (0.95x20) + 0.05 (0.01(10000+500+20) + 0.99(500+20))
Leading me to an answer of 50 being C), however others have seem to have chosen D) as their answer
Any help would be appreciated.


texts: Metrics for measuring and scoring automated “code analysis”?

texts:
I am writing various "program analysis" (aka static code analysis) algorithms.

I am looking for ideas for metrics to measure how well my algorithms "understand the code".

Some ideas i have so far :

classic points-to analysis - ability to determine (during compile time) pointer aliases and allocation sites

early object release - ability to predict when an object can be released (both in the context of explicit java references, or implicit C++ object usage)

I hope to find complex metrics, where the score can be improved by running deeper and longer algorithms on the source code.


texts: Express a "complex" IF-Statement to Linear Programming

texts:
In our current project we need to model the following if-statement in linear programming:

If T1 < b < T2 then z = s else z = 0

where T1 and T2 are two integer values (e.g. T1 = 10 and T2 = 100) and s is also an integer value (e.g. 5).

We already know how to model a simpler if-statement with for example A > 0 but we can not figure out how to model an if-statement with a condition t1 < b < t2.

Can someone help us?

Here is a little more detailed explanation of the problem:

In our problem we have several different ranges, each range with a lower and an upper bound, and for each of these steps we have to multiply another value to a variable (lets call this variable k and the result of this multiplication z). For example we have the following range and if-statements:

Ranges:
0   - 10 : 0
11  - 100: 9
101 - 200: 8.5
201 - 300: 8

IF-Statements
if 0   < b < 10  then z = k * 0
if 11  < b < 100 then z = k * 9
if 101 < b < 200 then z = k * 8.5
if 201 < b < 300 then z = k * 8

The lower and the upper bounds as well as the multiplication values are constants and known upfront. The rest (i.e. b, z, k) are integer variables for which we don't know the exact upper bound (lower bound is 0), but we know that they will not get too big. So, we are able to define M values for the M technique.

We already figured out how to do an if-statement like the following (T1 and T2 are the thresholds of the ranges from above, e.g. T1=0 & T2=10):

if T1 < b then z = k * something

and

if b < T2 then z = k * something

For this we transform T1 < b to 0 < b - T1 and b < T2 to 0 < T2 - b and then we use the way described here.

But we are stuck at how we can do the:

0 < b - T1 && b < T2 to 0 < T2 - b

The whole problem is a mixed integer linear programming problem, because we have also boolean decision variables and integer values like for example b.