texts:
I'm just starting to learn about NP-completeness. While I understand that reducibility plays a key role in this, I'm astonished how few problems I've been able to find who's proof that they are NP-Complete is not based on reduction to an existing NP-Complete problem.

While I understand these proofs are perfectly valid, you loose insight into what makes a particular problem difficult if you have to trace logic through 3, 4, 5+ reductions.

Since NP-Complete is, by definition, an equivalence class, I should be able to start with any of them; however I can only seem to find is this general strategy.

Are there any other problems with direct proofs that they are NP-Complete other than Circuit-SAT and SAT?


texts: I have heard the quote "L is a trivial language" What does this mean and how do we relate this to Turing machines and complexity theory?


texts: How to exclude all points adjacent to a given point from the feasible region of IP

texts:
Consider a basic integer program such as:

$$\begin{align}
\min_x & \quad c^Tx \\
\text{s.t.} & \quad Ax \leq b \\
&\quad x_i \in \{-100,\ldots,100\}
\end{align}
$$

where $x \in \mathbb{Z}^n, A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R^m}$.

Say that I have a feasible point $y \in \mathbb{Z}^n \cap [-100,100]^n$ with the property that all points adjacent to $y$ cannot be optimal. In other words, given $y$, all points in the set:

$$\mathcal{A}(y) = \Big\{ z \in \mathbb{Z}^d ~\big|~ z_i = y_i \pm 1 \Big\}$$

could be excluded from the feasible region of the IP.

I am wondering if there is an elegant way to formulate constraints that will exclude all points that adjacent to $y$ from the feasible region.


texts: An algorithm for fitting a rectangle inside a polygon

texts:
I have a kind of cutting problem. There is an irregular polygon that doesn't have any holes and a list of standard sized of rectangular tiles and their values.

I want an efficient algorithm to find the single best valued tile that fit in this polygon; or an algorithm that just says if a single tile can fit inside the polygon. And it should run in deterministic time for irregular polygons with less than 100 vertices.

Please consider that you can rotate the polygon and tiles. Answers/hints for both convex and non-convex polygons are appreciated.


texts: Are link-cut trees ever used in practice, for max flow computation or other applications?

texts:
Many max flow algorithms that I commonly see implemented, Dinic's algorithm, push relabel, and others, can have their asymptotic time cost improved through the use of dynamic trees (also known as link-cut trees).

Push relabel runs in $O(V^2E)$ or $O(V^3)$ or $O(V^2\sqrt{E})$ normally, but with dynamic trees $O(VE \log(V^2/E))$
Dinic's algorithm runs in $O(V^2E)$, but with dynamic trees $O(VE\log(V))$

However, practical implementations of max-flow algorithms in most libraries don't seem to make use of this data structure.  Are dynamic trees ever used in practice for max flow computation? Or do they carry too much overhead to be useful for real world problem sizes?

Are there any other problem domains where link cut trees are used?

This question is related to a question that I asked on cstheory: Are any of the state of the art Maximum Flow algorithms practical?


texts:
For optimization problems, I found complexity classes analog to some classes for decision problems, e.g. PO and NPO, mirroring P and NP for decision problems in the sense that optimization problems in PO can be solved in polynomial time and verified in polynomial time, respectively.
Are there similar class definitions mirroring BPP and BQP, i.e. classes of optimization problems that could be solved with a probabilistic algorithm or on a quantum computer efficiently?


texts: Is this an unambiguous CFG that is not LR(k) for any k?

texts:
The grammar is this:
$$S  \rightarrow  a B c $$
$$B  \rightarrow  b B b $$
$$B  \rightarrow \epsilon $$
The LR(1) states that I worked out were these
$$(1)$$
$$S \rightarrow .aBc$$
$\\\\$
$$(2)$$
$$S \rightarrow a.Bc$$
$$B \rightarrow .bBb$$
$$B \rightarrow .\epsilon $$
$\\\\$
$$(3)$$
$$B \rightarrow b.Bb$$
$$B \rightarrow .bBb$$
$$B \rightarrow .\epsilon$$
$\\\\$
$$(4)$$
$$B \rightarrow \epsilon.$$
$\\\\$
$$(5)$$
$$B \rightarrow bB.b$$
$\\\\$
$$(6)$$
$$B \rightarrow bBb.$$
$\\\\$
$$(7)$$
$$S \rightarrow aB.c$$
$\\\\$
$$(8)$$
$$S \rightarrow aBc.$$
The trouble seems to come primarily from state (3). In state (3) there is an S-R conflict on the lookahead of b. Also I feel that it makes the entire grammar not belong to any LR since on any lookahead of b...b, the same S-R conflict will exist. Is my reasoning correct?


texts: Given a list of points on a sphere find the place for another point such that most space is covered?

texts:
Suppose I knew my current location as a geographical point (Lat/Lng) and had a standard radius to search (meters). Now given a list of previously searched geographical points as the centers of circles with the same standard radius that are nearby my point but do not encompass my point what would be a good algorithm for determining where to place the center of the new geographical point such that the circle around it covers the most area not covered by other circles while also containing my current geographical point?

I've already done some thinking and I thought perhaps something to do with the average of all the points would perhaps work, but it becomes tricky because the points are on a sphere instead of on a plane.

Of course because this is the real world we must take all distances as "sphere" distances instead of straight-line distances. An algorithm which uses straight line distance but can be substituted for sphere distance is also acceptable.

I'm sure there is a name for this problem, I just could not find a name so I figured I would ask here.


texts: Calculate the number of iterations in unusual nested loop

texts:
I am trying to calculate the number of iterations of a sequence of nested loops of the form:

\begin{equation}
N = \sum_{j=0}^{j_T} \sum_{k=0}^{j} \sum_{l=0}^{k} \sum_{n=n_0}^{n_T} 1
\end{equation}

where $j_T\ge 0$ and $n_T\ge 0$ are known constants.

For $n_0 = 0$ the case is trivial and can be calculated using the standard procedure (Sum number of times statement is executed in triple nested loop)

The problem is that in my case $n_0$ is given by a more complex expression:

$$ n_0 = \begin{cases}
0    &\text{ if } k-2l\lt0,\\
n_T  &\text{ if }k-2l\gt n_T,\\
k-2l &\text{ otherwise.}
\end{cases} $$

Basically, the initial value of $n$ in the last sum is $k-2l$, except when its value is lower/greater than the lower/greater limits of the sum, in which case it gets replaced by the corresponding extreme value of the interval (either $0$ or $n_T$).

Any ideas?


texts: How to prove a complete binary tree of depth N has $2^{N+1} - 1$ nodes?

texts:
Here is the description of a proof problem:

A complete binary tree of depth N is a binary tree in which every node on levels $0,1,2,...,N-1$ is a parent and has two children, and each node on level N is a leaf.

It's asking for proving binary tree of depth N has $2^{N+1} - 1$ nodes.

I am not really sure how to approach this proof. I tried to plug in some values in $D(N) = 2^{N+1} - 1$ just to play with the formula, I get $D(1) = 2^{1+1} - 1 = 3$,  $D(2) = 2^{2+1} - 1 = 7$, $D(3) = 2^{3+1} - 1 = 15$, and so on. I still did not see how these numbers relate to the descriptions given and how I would relate these values to given facts to build a proof.


texts: Size of address spaces (logical and physical)

texts:
Suppose a system in which addresses (physical and logical) occupy 32 bits, page size is 1024 bytes
(210), and physical memory is of size 32MB. How many frames are in physical memory? Is the logical
address space larger than physical memory? Explain.

The solution given is:

232 byte logical address space (assuming byte-addressable machine)

225 byte physical memory

210 byte pages

At one page per frame, there are 225/210 = 215 pages in physical memory. The logical memory address
space is larger than physical memory.

Can someone explain how to arrive at this solution?


texts:
I am trying some methods to solve the graph coloring problem with large data sets. I decided to start off with the total space search but to eliminate certain combinations that are same due to symmetry. So for instance, if we code the color by a natural number, graph coloring 1-2-1-1 is the same as the coloring 2-1-2-2.

I figured that all the colorings from the same symmetry group can be represented by their member which has all the colors first time appearing in the correct order. For instance in the graph 1-2-1-2-4-3 the appearances of colors is 1, 2, 4, 3 which is not in order. So the colorings 1-2-1-1, 2-1-2-2, 3-1-3-3 are all the same as 1-2-1-1 and I do not even allow the others in the search.

In the implementation I go node by node and if at some node in the search $\gamma$ colors appeared so far, I try out only colors $[1, \gamma + 1]$. I testes for some small cases but for larger cases since I am using some data set with best found solutions noted, it seems that better results are possible though I think I am doing the full space search with symmetry applied. My question is why is this happening and where does my solution method skip the combinations. I really tried hard and could not figure it out. It seems to me idea is fine.

Here is the pseudocode of my algorithm. A bit of clarification. Since I am using depth first I edit the original globally defined graph as a solution for each level.

Graph G
best_coloring

find_solution(curr_node = 0, gamma = 1):
  if curr_node == G.node_count:
    # base case
    if colors_used < colors_used(best_coloring):
      best_coloring = G
  else:
    for color in [1, gamma]:
      G.nodes[curr_node].color = color
      if is_coloring_ok(G):
        if color == gamma:
          next_gamma = gamma + 1
        else:
          next_gamma = gamma

        find_solution(curr_node + 1, next_gamma)


texts:
If there is a deadlock between the processes does that mean that there is starvation also?

My Thinking:
deadlock is no process using that resources , but starvation is like not giving chance to only that process so there is progress in starvation but not in deadlock
Is my thinking right?


texts:
Looking at the pumping lemma, I've noticed that in the string $xy^pz$, there seems to be no rule explicitly stated for $x$ and $z$. If I understand correctly, $x$ and $z$ are basically anything on the 2 sides of the string $y^p$ that we're pumping and thus can be anything in $L$.
Rule 2 & 3 of the pumping lemma are:

$|y| \geq 1$
$|xy| \leq p$

Since $|x| = 0$ and $|z| = 0$ seem to be allowed, as they only need to be of non-negative length, we shouldn't need $x$ in rule 2 and it can be rewritten as $1 \leq |y| \leq p$.
Are $x$ and $y$ not just a substitute for whatever are on the 2 sides of $y^p$ which we're pumping? Why is $x$ in rule 2 if it doesn't seem to make a difference? If $x$ is necessary, why is there no $|yz| \leq p$?


texts: Generalized Büchi Automata - Formal definition of a state appearing infinitely often?

texts:
I am studying generalized Büchi automata and I don't really understand when a state is considered to appear infinitely often. The definition I have is:

A state $s$ appears infinitely often if there exists an infinite set of points $i \in N$ such that the $i$th state of the execution is $s$.

But there's also an example which I think contradicts this definition.

According to the example, the language accepted by this automaton is the language where the string $ab$ appears infinitely often.

Why isn't it just $a$ appearing infinitely often? State 2 would be reached even if we only had $a$ as input. Which is wrong, the example or the definition? Or did I misunderstand the definition?


texts: Set of Turing machines $S$ such that any $A \in S$ halts on input the description of any $B \in S$

texts:
Does there exist a maximal set of Turing machines $S$ over the alphabet $\{0,1\}$ such that any $A \in S$ halts on input the description of any $B \in S$?

Take S to be the set of deciders. Then S satisfies the property, but is not maximal, because for example we can take:

The set of TMs which are not equal to 0 and which halt on input any string not equal to 0. (Assuming 0 is not a deciding TM.)
Where $A$ is any set of non-deciding Turing machines, the set of TMs which are not in $A$ and halt on input any string not in $A$.

Maybe we can construct such a set $S$ by infinite recursion or by Zorn's lemma, but I haven't been able to see how.

Edit: By maximal, I mean there is no $S' \supsetneq S$ satisfying this property.


texts: Use of Tabu search Algorithm for solving optimization problem

texts:
I am trying to solve a maximization problem using the Tabu search algorithm but there is no relevant code available on the internet. Any kind of sample code is highly appreciable.

My function is F(x)= x^3-60.x^2+90.x, 0 < x < 31


texts:
Consider the well-known language: $$L = \{\langle M,x,1^t \rangle \ \ |\ \text{$M$ accepts $x$ after $t$ steps}\}$$

I've encountered some technical problem while trying to show a logarithmic reduction from some $L'\in P$ (which will show completeness of $L$)

Basically, the reduction is: $$f(x) = \langle M_{L'},x,n^c\rangle $$

Where $n^c$ is the time it takes for $M_{L'}$ to decide some input, $x$.

At first everything seems legitimate, but...  How do we construct $M_{L'}$ at the first place?

In other words, do we have an "access" (as the reduction function) to the machine description?


texts: Let $L$={ $\alpha$ in {$a,b$}* | $\alpha$ has exactly two symbols b } .Prove that $L'$ = { $\alpha^n$ | $\alpha$ in $L$ ,$n \ge$0} is not context-free.I was thinking to prove it that way: Since $a^nba^nba^n$ is in $L$ then $a^{n^2}b^na^{n^2}b^na^{n^2}$ is in $L'$.Now I will use the pumping lemma for the language $L'$  .Is my approach for proving that is not CFL right?


texts: Derandomization of vertex cover algorithm

texts:
I have the following randomized-algorithm for the vertex cover problem. Let $B_0$ be the output set:

Fix some order $e_1, e_2,...,e_m$ over all edges in the edge set E of G, and set $B_0=∅$.

Add to $B_0$ all isolated vertices, i.e. the ones without any incident edges.

For every edge $e$ in $e_1,e_2,...,e_m$
if both endpoints of e are not contained in $B_0$, then
flip a fair coin deciding which of the endpoints to choose, and add this endpoint to $B_0$.

I have already proved that this algorithm has $E[|B_0|] \le 2|OPT|$.

Now I don't know how to apply the method of conditional expectations (defined here) to derandomize the algorithm in order to show that we can't obtain an efficient deterministic version and that gives the same result of the expected value found previously.
Can you show me to do this?


texts: Finding maximum rectangular frame in array of zeros and ones

texts:
I've recently come across a following problem. In a rectangular array of ones and zeros one has to find maximum non-degenerate rectangle whose sides are filled with ones. By "maximum" i mean any rectangle with maximum possible perimeter. By "non-degenerate" i mean that all sides consist of at least two cells. We do not care about the points inside the rectangle. The only requirement is that its sides consist of cells filled with ones.

I know how to solve a similar problem where one needs to find maximum rectangle totally filled with ones (i.e. not only its border, but its interior too). But with this problem i got stuck so any ideas will be highly appreciated. I believe that there is some smart $O(max(m,n)^3)$ solution but can't see it yet.

Thanks in advance.

P.S.
This is not a problem from an ongoing competition, hometask problem or an interview question. The problem originates from KPI-OPEN 2017 competition. You can find original statement here (problem F): http://kpi-open.kpi.ua/problemset/kpi_open_2017_2/eng.pdf

According to bounds on rectangle's size and time limitations there has to be at most cubic (or perhaps cubic-logarithmic) solution. As far as i know there were cubic solutions during the contest.

P.P.S.
There is an algorithm which precomputes for each cell how many cells there are to the left and above it which are filled with ones. Using such precomputation we can easily solve the problem in $O(max(m,n)^4)$ considering all possible rectangles. We just iterate through all possible cells for upper left corner of rectangle and through all possible cells for lower right corner. With the precomputation we might check in $O(1)$ that our rectangle is appropriate and if it is we just update the answer. Unfortunately such approach is to slow.


texts: Predicate calculus- meaning of the word "any"

texts:
In the following 2 statements -

1. Anyone who eats any pumpkin is a nutrition fanatic.
&forall x ((&exist y (PUMPKIN(y) &and EAT(x,y))) &rarr FANATIC(x))

2. Anyone who buys any pumpkin either carves it or eats it.
&forall x &forall y (PUMPKIN(y) &and BUY(x,y) &rarr CARVE(x,y) &or EAT(x,y))

In the first case any pumpkin is given by &exist and

in the second case any pumpkin is given by &forall

Why the second case is also not given by &exist?


texts: Should you use Genetic algorithm for an extremly large unstructured search space?

texts: My search space is discrete and in the order of $10^{1360}$, with a probably very complex fitness surface. Is it hopeless to attempt to use GA for such a problem? One fitness evaluation could take 1-3 minutes per candidate solution.


texts:
I have got confused in undressing the informal definition of LTL below: $$G(\phi \Longrightarrow\psi)\Longrightarrow(G\phi \Longrightarrow G\psi)$$

in many literatures I have seen implies is said as replies like for LHS we can say Always/Globally $\psi$ replies to $\phi$. is it correct?
Does the LHS implies the RHS if so what is the informal interpretation of the formula? (Alway $\psi$ replies to Always $\phi$) replies to (Always $\psi$ replies to $\phi$)


texts: The barbers paradox first order logic formalization

texts:
I tried to look on the site and while I found some similar questions, I did not find the first order logic formalization of the following sentence (the basic barber's paradox), so I wanted to ask if I got the right first order logic formalization of it, and I am sure others will benefit from this thread as well.

Sentence: there exists a barber who shaves all the people that don't shave themselves.

My attempt: this complicated sentence can be made simpler by inferring that "for all of those who does not shave themselves, are shaved by the barber"

And now it seems to be easier to substitute with variables so:

$$\exists x(\lnot S(x,x) \rightarrow S(b,x))$$

where $S(x,x)$ is shaving(verb), $x$ are the persons (who don't shave themselves), and $b$ is a shortcut for barber, so if a person does not shave himself, it can be inferred that he is shaved by the barber.


texts: Proving there is no polynomial algorithm for independent set

texts:
I need some guidance in an assignment I'm doing.

I'm at complete loss, he says the the MAXIMUM INDEPENDENT SET problem is NP-hard and then asks me to prove that there is no polynomial time for the same algorithm and it also guarantees that some inequality holds, which I also don't understand, since $A(G)$ returns the size of a maximal independent set in $G$ and $OBT(G)$ returns the size of an independent set of maximal size for $G$ but isn't the case that a graph could have multiple maximal independent sets? Let's assume that it returns the largest one which reduces the epression to $0 \le K$ which should always holds since $K$ is a natural number?

As for the hint given, I don't see how we can use $H$ if I understand it correctly, it says split $G$ into disjoint sets. Also it says for every instance $G$ which is confusing me.

When I asked the professor she was very reluctant to help me, so please any guidance is appreciated.

The full question:   .


texts: Monte Carlo Algorithms : Are there any problems where two opposite Monte Carlo algorithms could solve it?

texts:
I started reading on Probabilistic algorithms and Monte-Carlo algorithms. Since a Monte-Carlo can only give a certain answer for either True or False, I was wondering if it's conceivable that for the same problem, there exist two opposite Monte-Carlo Algorithms capable of giving a certain answer. (By opposite, I mean one would be sure when it's FALSE, and the other would be certain when it's TRUE)

For example : There exist a prime number test Monte-Carlo based algorithm that can check whether or not a number "n" is prime. If the answer is FALSE, then "n" is not a prime number (it is a composed number). However, if the answer were to be TRUE, then "n" COULD be prime (with a certain probability). To my knowledge, there is no efficient algorithm (Monte-Carlo) capable of saying with certainty if "n" is a prime number.


texts: Evolving expert systems with machine learning

texts: Expert systems seem to have been left at the wayside a little bit in the 21st century. In fact, expert-systems was not even a tag on this site (until I just created it). The traditional focus in expert systems has been on rule based systems and logical resolution via, for example, 2-SAT backward chaining. Have there been attempts to integrate modern machine learning with traditional expert systems theory?


texts: Checking disjointness between subsets of a poset

texts: If there is a poset $(P, \le)$ and two sets $X \subseteq P$ and $Y \subseteq P$, and we have a way $f : P^2 \to 2$ to efficiently compute for any $(x, y) \in P^2$ whether there exists a $z \in P$ such that $(x \le z) \wedge (y \le z)$, we want to return $\mathbf{T}$ if there exists a pair $(x, y) \in X \times Y$ such that $f(x, y) = 1$ and $\mathbf{F}$ otherwise, using the fewest possible number of calls to $f$ and $\le$.


texts: Partial order, total order, and version order in transaction histories

texts:
In Section 3.1.2 "Transaction Histories" of the PhD thesis by Atul Adya [1]:

  A history $H$ over a set of transactions consists of two parts: (1) a partial order of events $E$ that reflects the operations (e.g., read, write, abort, commit) of those transactions, and (2) a version order, $\ll$, that is a total order on committed object versions.

The author gives a comment on "the partial order of events" (Page 36):

"For convenience, we will present history events in our examples as a total order that is consistent with the partial order. Furthermore, wherever possible in our examples, we make this total order be consistent with the real-time ordering of events in a database system."

  Question 1: Why can we present the partial order of events as a total order of them? Because a partial order may imply multiple total orders consistent with it, which one to choose? Does the choice matter for later definitions and theorems?

Some comments on "the total version order" (Page 36) are as follows:

[Added (01-10-2015)] "The version order in a history $H$ can be different from the order of write or commit events in $H$. This flexibility is needed to allow certain optimistic and multi-version implementations where it is possible that a version $x_i$ is placed before version $x_j$ in the version order even though $x_i$ is installed in the committed state after $x_j$ is installed."

And,

"The system chooses the version order for each object."

  Question 2: What does it mean for the database system to choose the version order? And how? Is this implementation-dependent?

[1] Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions by Atul Adya, 1999


texts: A non-regular language satisfying the pumping lemma

texts:
I got a problem to solve, which is to demostrate that the language $L$, given by:

$L = \{ab^nc^n\mid n \geq 0\} \cup \{a^kw \mid k\geq 2 \wedge w \in \Sigma^*\}$

Satisfies the pumping lemma.
Is not regular.

For the question 1. I think it would suffice to demonstrate that for all $w \in L$, $w$ can be decomposed in the form $\alpha \beta \gamma$, where $|\beta| \neq 0$, and that every string $\alpha \beta^m \gamma \in L$, where $m \geq 0$, but after that I have no clear what I have to do, because I start thinking about cases, what if I have a string $w \in \{ab^nc^n\mid n \geq 0\}$... I should decompose it the way $\alpha = \epsilon, \beta = a$ and $\gamma = \text{the rest of the string}$ (because if we use $w = ab^0c^0 = a$, $\beta$ will have to be $a$, because we know that $\beta \neq \epsilon$), but in this case $\alpha \beta^m$ may not be in $L$, for example, if we choose $m = 0, \alpha \beta^m \gamma$ won't be in $L$, so I don't know what I'm doing wrong... perhaps I'm making mistakes in several steps.

Now, for the question 2. I don't even have an idea on how to start, if someone would help me I would really appreciate it


texts: House painting problem where the house row is split and converged back

texts:
I am trying to solve a house painting problem: There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x k cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs1 is the cost of painting house 1 with color 2, and so on... Find the minimum cost to paint all houses.

This can be solved with dynamic programming (see solution in link house painting). I am trying to solve a very similar problem, but my house row is splitting somewhere in the middle and converging (but sometimes it doesn't), as shown in the picture attached:

Above you can see the problems that I am facing... Can I solve those problems with dynamic programming ? Is there any other solution for those problems ?


texts: Page cache and its relationship to page table

texts: I was reading about the page cache Page cache - the cache in memory for files, but I couldn't find the answer to my question. Does the page table have anything to do with, or maintain any entries, for the page cache? My guess is no, despite the similar sounding name, as the page table only stores entries for text/code, stack, and heap segments for a process (i.e., virtual memory).


texts:
The question is: What is the smallest complexity class in which the following problem is contained: Given a graph with $n$ nodes, Is there independent set of size of at least $n-10$?

I have a little difficulty to understand the meaning of being in ${\sf L}$ and examine problems in a correct way for deciding if they are in ${\sf NL}$ or ${\sf L}$

First I know that for being in ${\sf NL}$ I need to provide a verifier for a Turing machine which uses only $O(\log n)$ space on its working tape- So I wonder- I can give as a verifier this set of nodes to be independent set as requested, but how does the checking work? Can it go to all the lists of the pointers to the neighbors of each node , and for every node to check whether all the other nodes in the set given as independent set is not on that list- Is this considered of not using any space and I only need to count the nodes in the list that fulfill the requirement and therefore use only $O(\log n)$ space? Is this correct? Is there a way to prove that the problem is in ${\sf L}$?


texts: Replace 1's with -1's and vice versa in a matix

texts: Assume that we have an anti-symmetric matrix that consists of 1's and -1's and 0's. All the elements of the main diagonal are 0 and each row and each column has exactly one 1, and one -1. Design an algorithm that replaces all 1's with -1's and vice versa only by swapping some rows and some columns.


texts: difference between two uncomputable functions

texts:
for $L1$ regular language, $L2$ some language, $L1$ \ $L2$ is regular, decidable. yet, the next transition function might not even be computable:

$F′=${$\,q:δ(q,w)∈F \, for\, some\, w∈ L2\,$}$.$

$F$ is the accepting states group of DFA accepting $L1$.
$F'$ is the accepting states group of DFA accepting $L1$ \ $L2$

$HALT\,=${$<M,w>|M\,is\, a\, TM\, and\, M\, halts\, on\, w\,$}

$
on (M,w):\,
return\, 1\, is\, M\, halts\, on\, w\,
\,
return\, 0\, else\,
$

this function is also well defined, but not computable.
We know that the halting problem isn't decidable. what is the difference? In both cases the functions are well defined, but the first case is decidable, and the second isn't.


texts:
Can a probabilistic Turing Machine compute an uncomputable number?

My question probably does not make sense, but, that being the case, is
there a reasonably simple formal explanation for it. I should add that
I am pretty much ignorant of probabilistic TM and randomized algorithms.
I looked at wikipedia, but may even have misunderstood what I read.

The reason I am asking that is that only the computable numbers can have their digits enumerated by a Turing Machine.

But with a probabilistic Turing Machine, I can enumerate any infinite
sequence of digits, hence also sequences corresponding to non
computable numbers.

Actually, since there are only countably many computable numbers,
while there are uncountably many reals that can have their digit
enumerated, I could say that my probabilistic Turing Machine can be
made to enumerate the digits of a non computable number with
probability 1.

I believe this can only be fallacious, but why? Is there a specific
provision in the definition of probabilistic TM that prevents that?

Actually, I run into this by thinking whether various computation models can be simulated by a deterministic TM, in question "Are nondeterministic algorithm and randomized algorithms algorithms on a deterministic Turing machine?". Another p[ossibly related question is "Are there any practical differences between a Turing machine with a PRNG and a probabilistic Turing machine?".


texts: What is the asymptotic behaviour of a sum of powers of three?

texts:
I'm more concerned with just finding big oh since that can be used to find big omega. I am also told I cannot use limits to find the answer.

I'm given:
$3+9+27+\dots+3^n$. My first assumption is that $3^n = \Theta(3^n)$. The method we're supposed to use goes something like this:

$3+9+27+\dots+3^n<3^n+3^n+\dots+3^n$

Or I think that's what we're supposed to do here. I'm not sure how to simplify a sequence of repeating $3^n$ in order to find a constant C.

Any help is appreciated.


texts: Is there evidence that using dynamic languages has an impact on productivity?

texts: I am wondering if there are any experiments that show the existence or the non-existence of a correlation between usage of a dynamic language (such as Python, Ruby, or even languages that run on the Java platform such as Groovy, Clojure) over a static language (such as C/C++), and the difference in the productivity.


texts:
Summary: According to Rice's theorem, everything is impossible. And yet, I do this supposedly impossible stuff all the time!

Of course, Rice's theorem doesn't simply say "everything is impossible". It says something rather more specific: "Every property of a computer program is non-computable."

(If you want to split hairs, every "non-trivial" property. That is, properties which all programs posses or no programs posses are trivially computable. But any other property is non-computable.)

That's what the theorem says, or appears to say. And presumably a great number of very smart people have carefully verified the correctness of this theorem. But it seems to completely defy logic! There are numerous properties of programs which are trivial to compute!! For example:

How many steps does a program execute before halting? To decide whether this number is finite or infinite is precisely the Halting Problem, which is non-computable. To decide whether this number is greater or less than some finite $n$ is trivial! Just run the program for up to $n$ steps and see if it halts or not. Easy!
Similarly, does the program use more or less than $n$ units of memory in its first $m$ execution steps? Trivially computable.
Does the program text mention a variable named $k$? A trivial textual analysis will reveal the answer.
Does the program invoke command $\sigma$? Again, scan the program text looking for that command name.

I can see plenty of properties that do look non-computable as well; e.g., how many additions does a complete run of the program perform? Well, that's nearly the same as asking how many steps the program performs, which is virtually the Halting Problem. But it looks like there are boat-loads of program properties which a really, really easy to compute. And yet, Rice's theorem insists that none of them are computable.

What am I missing here?


texts: single algorithm to work on both directed and undirected graph to detect cycles?

texts:
I have been trying to implement an algorithm to detect cycles (probably how many of them) in a directed and undirected graph. That is the code should apply for both directed and undirected graphs.

Using DFS or topological sort is mostly recommended in various posts. But largely, everything is addressed for undirected graph.

This link describes one approach for cycle detection. To my understanding this works for directed graphs.

This link has the code for cycle detection in undirected graphs. but I fail to understand how it ignores the back edge. That is it must ignore any cycles with two nodes, say D to C and C to D.
which means it must remember it parent as the DFS recurses. But the code does not seem take care of that.

Any suggestions welcome..


texts: Hard computational problem on special class of bipartite graphs

texts:
I am interested in the properties of a class of bipartite graphs $G(X \cup Y, E)$ where all nodes in $X$ are 3-regular, all nodes in $Y$ are 2-regular, and $|X|=|2Y/3|$. First, Is this a well known class of graphs? Secondly,

  Is there an example of intractable computational problem restricted to this class of bipartite graphs?


texts: Regular expression (ab U a)* to NFA with two states (Sipser)?

texts:
In the 3rd edition of Sipser's Introduction to the Theory of Computation (example 1.56, p.68), there is a step-by-step procedure to transform (ab U a)* into a NFA.
And then the text ends with: "In this example, the procedure gives an NFA with eight states, but the smallest equivalent NFA has only two states. Can you find it?"
Nope. I can't.
After a good deal of head scratching, I've convinced myself that it's not doable. But being a novice, I'm probably wrong.
Can anyone help? Thanks!


texts: Finding the total capacity of two communication channels

texts:
I have the transition matrices of two communication channels. I am able to find the capacity of each by performing an optimization calculation, however I need the total capacity of the two channels. The channels are not weakly symmetric so I don't think I am able to simply add the two capacities. I think what I need to do is perform the optimization calculation over the combined channels but I'm not sure how to do this. I think I need to construct a transition probability matrix but I'm not sure how to go about this. If anyone can give some advice on this I'd be grateful.

Thanks


texts:
My doubt is based on the relation between regular grammar and regular languges

$S \to Sa\ |\ a$ produces the regular language $a^+$ but this grammar is not type-3 grammar of Chomsky classification. So am I correct in stating that this is not a regular grammar even when it produces regular language?


texts: What is the appropriate term for the "string splitting" problem?

texts:
To be clear, I didn't hear of this in any particular venue, and so can't point you to one.

Two variants that I can bring you:

String spitting

  Given a string (sequence of elements), and a function that takes a substring and returns a score/penalty. Overall score is the product of scores of chosen split.

  Find the optimal way to split the string into consecutive, non-overlapping substring to maximize the score.

String folding

  Given the same as (1).

  Also given a function that takes two substring and an edge (head-head, head-tail, etc.) specifying how the substrings will connect, returns a score.

  Find the optimal way to "fold" the string. Any two "elbows" (or folding points) can be made to touch. No length limitations (substring length is not geometrically motivated).

I haven't been able to find mentions of "optimizing string splitting" online. So I'm doubting it might be more specialized than I'd thought.


texts: Single machine job scheduling (Greedy heuristic)

texts:
Here is a variation of a job-scheduling Problem.
Let $J = \{j_1,...j_n\}$ be a set of Jobs for $1 \leq i \leq n$. Given Job length $|j_i|\in \mathbb{N}$, deadline $f_i \in \mathbb{N}$, profit $p_i \ge 0$ and starting-time $s_i  \in \mathbb{N}$. I am looking for a greedy approximation factor given that the Job length may only be distinguished by factor k.

$$max_i|j_i| \leq k \cdot min_i|j_i|$$

The Greedy algorithm of this Problem is fairly stupid. Greedy takes a job with the biggest profit.  I created an example (3-Job-Scheduling):

Let $J = \{j_1,j_2,j_3\}$ with $|j_1| = 2, j_2 = j_3 = 1$ and

$s_1 = 0; s_2 = 0; s_3 = 1$,

$f_1 = 2;f_2 = 1; f_3 = 2$

$p_1 = w; p_2 = p_3 = (w-1)$

What I want to show is that Greedy gives us w while 2(w-1) is the optimal solution.

My question: Is this valid for n-Job-Scheduling (the general case). Is this the worst-case?

I can't think of anything worse. So I figured since the problem is a k-Matroid (is this a common term?) there will be a an approximation factor $\frac{1}{k-\epsilon}$ for  any $\epsilon > 0.$ I know this is not exactly a proof yet, but am I on the right way?

Thanks for your help!


texts:
I made a recurrence tree and guessed that solution to $T(n)=2T(n-2)+n$ is $O(2^{n/2})$ and I am now trying to prove this through substitution. These are my steps so far, but I can't get it to pass for some reason:

\begin{align}
T(n-2) &\leq c2^{(n-2)/2}\\
T(n) &= 2(c2^{(n-2)/2})+n\\
&\leq c2^{n/2} \quad (?)
\end{align}

But as far as I see, it can never add up, because it will always be greater than the $+n$ term and times $2$. Any help will be much appreciated.


texts: Writing linear programming constraint in a canonical form

texts:
I have a particular research problem that I'm formulating as a linear program. It's more or less an instance of the transportation problem, except there is one additional constraint that is proving difficult to translate into the canonical form required by LP solvers. The constraint is
$$
\sum\limits_{i'=i+1}^k \sum\limits_{j'=j-1}^1 x_{i' j'} + \sum\limits_{i'=i-1}^1 \sum\limits_{j'=j+1}^n x_{i' j'} \leq (k+1)(1-x_{ij})\,\forall i,j
$$

Is there a general method of converting these constraints into a form that a standard LP solver accepts? Thanks in advance for help or advice.


texts: Is it possible to create a chatbot that doesn't fall into an infinite loop under some restrictions?

texts:
Consider a chatbot that runs on a turing machine. It has some restrictions:

It must talk to itself 1 sentence at a time.
It is forced to use English words to reply. (so only around say 80 k different words to pick from)
A sentence cannot be longer than N words (say N=100)

Is it possible to create such a bot (computer program) such that it will not repeat itself over and over, i.e. fall into an infinite loop?

I think that yes, it's possible. For example the sequence: "Hello, how are you? > Good, and you? > Not so good, and you? > Good and you? > Good and you? > Good and you? > Not so good, and you? >..."

I could write the above as 10110111011110111110... where 1 represents "Good, and you?" and 0 represents "Not so good, and you?".

But a friend is telling me that the example does not work because "it's not a cycle, so it's not possible on a finite state machine".

Edit: I'm asked whether the TM can maintain state during inputs. My answer is "yes if a common household computer can, no otherwise."

Edit for the bounty: I'd like the answer to be clear on whether a common household computer can run such a program, i.e. a program that never cycles under the above restrictions.

Thus far, on one hand Anrej Bauer's answer explain that it's impossible. On the other hand, in the comments I am told by D.W. that "Or, to put it another way: yes, a common household computer can retain state if you invoke it in a way that allows retaining state; it can't retain state if you invoke it in a way that doesn't allow it to retain state." and by David Richerby that "Is the Turing machine allowed to maintain state between inputs? If so, you can implement your 10110111011110... sequence exactly as you describe.". Which would make the answer as "yes, it is possible even when the TM is a common household computer". This is why I am reluctant to accept the answer and bounty so far.

EDIT 2: To make the question well definied, I must pick whether I want the TM to retain state between inputs. Since it is possible to do so on a household computer with say Python as a programming language, I pick that yes, the TM can retain state between inputs.


texts:
From Wiki - Superscalar processor:

  (Line 1): superscalar processor is a CPU that implements a form of parallelism called instruction-level parallelism within a single processor. In contrast to a scalar processor that can execute at most one single instruction per clock cycle, a superscalar processor can execute more than one instruction during a clock cycle *by simultaneously dispatching multiple instructions* to different execution units on the processor.

  (Line 8): In Flynn's taxonomy, a single-core superscalar processor is classified as an *SISD* processor (Single Instruction stream, Single Data stream)

I understand ILP, which means two instructions executed at the same time. My problem is that: If one doesn't fetch two instructions simultaneously, how can it dispatch multiple instructions to different execution units...? Or I misunderstand the meaning of instruction stream, which it's single stream but one can fetch two instructions at the same time, why sounds so counter-intuitive?

From Wiki - SISD:

  (Line1): In computing, SISD (single instruction stream, single data stream) is a computer architecture in which a single uni-core processor, executes *a single instruction stream*, to operate on data stored in a single memory.


texts: Is it possible to make this grammar unambiguous? expr: ... | expr expr

texts:
I am writing a simple calculator in yacc / bison.

The grammar for an expression looks somewhat like this:

expr
: NUM
| expr '+' expr { $$ = $1 + $3; }
| expr '-' expr { $$ = $1 - $3; }
| expr '*' expr { $$ = $1 * $3; }
| expr '/' expr { $$ = $1 / $3; }
| '+' expr %prec '*' { $$ = $1; }
| '-' expr %prec '*' { $$ = $1; }
| '(' expr ')' { $$ = $2; }
| expr expr { $$ = $1 '*' $2; }
;

I have declared the precedence and associativity of the operators like this.

%left '+' '-'
%left '*' '/'
%nonassoc '('

The problem is with the last rule:

expr expr { $$ = $1 $2; }

I want this rule because I want to be able to write expressions like 5(3+4)(3-24) in my calculator.

Is it possible to make this grammar unambiguous?


texts: Are complexity classes equal in this case?

texts:
Let us assume we have a program of size $k$ that solves any instance of SAT of size $N < n$ in $poly(n)$ time. For every input of size $N \geq n$ the program is allowed not to solve it.

Then we might imagine an infinite sequence of programs of sizes $k_0 \leq k_1 \leq\ ...\ \leq k_i\leq\ ...$ which solves SAT up to the size $n_0<n_1<\ ...\ < n_i<\ ...$ in $poly(n):n<n_i$ time. And if an instance is solvable by $i^{th}$ program in $T_i(n)$ time, it's also solvable by $i+1^{th}$ program in at most $(1+1/\Omega(poly(n))T_i(n)$ time.

Also we assume the sequence is unbounded and no better sequence exists. $\forall m\in\mathbb N\ \exists i\in\mathbb N: k_i>m.$

Does the last statement mean $\mathsf{P\subsetneq NP}$? And what if we put other complexity classes and functions there?

P.S. I said time in first statement but regarding other complexity classes we might put space there too.


texts: How many times does a pair of numbers co-occur in a list?

texts:
Imagine you have N distinct people and that you have a record of where these people are, exactly M of these records to be exact.

For example

1,50,299
1,2,3,4,5,50,287
1,50,294

So you can see that 'person 1' is at the same place with 'person 50' three times. Here M = 3 obviously since there's only 3 lines. My question is given M rows, and a threshold value (i.e person A and B have been at the same place more than threshold times), what do you suggest the most efficient way of returning these co-occurrences?

So far I've built an N by N table, and looped through each row of M, incrementing table(N,X) every time N co occurs with X in a row. Obviously this is an awful approach and takes 0(MN^2) depending on how you implement. Any tips would be appreciated!


texts: Solving a problem with instance of size $n$ in $O(n)$

texts:
Today I read the following text in CLRS:

We say that an algorithm solves a concrete problem in time $O(T(n))$ if, when it is provided a problem
instance $i$ of length $n = |i|$, the algorithm can produce the solution in $O(T(n))$ time

It is ambiguous for me, because if we consider a problem in which a number $n$ is given and we have to print $1$ for $n$ times, and our input is the number $n$ in binary format, our input has a size of $O(lg(n))$, and since we do an action $n$ times, the algorithm runs in $O(n)$, and since $O(n) = O(2^{lg(n)})$, the algorithm is exponential.
What am I doing wrong here?


texts: Assign $m$ tasks to $n$ workers, with $m \geq n$

texts:
There are $n$ students that share the same apartment. At each evening, one of them must prepare dinner for everyone. There are $m$ evenings to schedule, with $m \geq n$, and you have to assign any singular evening to one student at a time.

In particular, student $i$ is disposed to accept cooking for $c_i$ evenings, with $1 \leq c_i \leq m$. Let $S$ be the global set of evenings (eg. $S=\{1,2,3,4,5\}$), for every student we define also $S_i \subseteq S$: you may assign evening $j$ to student $i$ only if $j \in S_i$.

So, given $m, n, c_i, S_i$, you have to define an algorithm that assigns each single evening to an available student.

I think a solution can be found using linear programming, although seems a little tricky. Let $x_{ij}$ be defined as follows:

$$
x_{ij} = \begin{cases} 1 & \hbox{if evening } j \hbox{ is assigned to student } i \\
0 & \hbox{otherwise}
\end{cases}
$$

Then you have such constraints. Student $i$ can accept a max. of $c_i$ evenings, so:
$$
\begin{array}{cr}
\sum_j x_{ij} \leq c_i & \hbox{ for every student } i \cr
\end{array}
$$
You have to ensure that every evening is assigned to a student only, then:
$$
\begin{array}{cr}
\sum_i x_{ij} = 1 & \hbox{ for every evening } j \cr
\end{array}
$$
Now a way to include $S_i$ in the constraints is required. Before doing it we define:
$$
 p_{ij} = \begin{cases}
1 & \hbox{if evening } j \notin S_i \\
0 & \hbox{otherwise}
\end{cases}
$$
So last constraints are:
$$
\begin{array}{cr}
\sum_j x_{ij} \cdot p_{ij} = 0 & \hbox{ for every student } i \cr
\end{array}
$$
Suppose you have $5$ evenings, with $S_i=\{2,4,5\}$. You'll have the constraint $x_{11} + x_{13} = 0$. Since it's a linear program, we have $x_{ij} \geq 0$ so the equivalence is satisfied only if terms are all zeros, i.e. those evenings ($1$ and $3$) are not assignable to that student.

I have some doubt with the objective function, that it should be the sum of every $x_{ij}$. Should we maximize or minimize, or are they the same for this model? We could also put a constraint to say that such sum must be equal to $m$ (the total amount of evenings to assign), but i think it's not mandatory since it's guaranteed by previous constraints. What do you think about?

Is there a better way to solve such problems?


texts: What are the differences between search problems, optimization problems, and decision problems?

texts: How do we differentiate these classes of problems?


texts:
I have been implementing  some neural networks  in MATLAB and recently I noticed a weird thing while implementing softmax derivative:

Setting the derivative to one, rather than using the actual derivative converges faster.

I have to admit that the derivative of softmax in particular confused me quite a bit, since the actual derivative requires the Jacobian as opposed to other activation functions that only depend on the input.
That is, for output vector of size nx1, the derivative of the activation function is also nx1 (see ReLU, tanh etc.) but for softmax is nxn.

Anyway, the simple case is to consider the diagonal of the Jacobian which is “out*(1-out)” as derived and proposed in a couple of sources around [1-3]. However setting the derivative to “1” shows faster convergence.

I am not fully sure to say how this phenomenon generalises but I tried with different settings, architectures and optimisers and the issue seems to persist.

I made an example of a 2x5x5x2 feedforward network with tanh in all but last layer, where I’ve used softmax, classifying a typical XOR problem using cross-entropy loss with ADAM optimizer.

Does anyone have any hunch why this would happen?

Refs:

1: https://eli.thegreenplace.net/2016/the-softmax-function-and-its-derivative/
2: https://math.stackexchange.com/questions/945871/derivative-of-softmax-loss-function
3: https://datascience.stackexchange.com/questions/29735/how-to-apply-the-gradient-of-softmax-in-backprop

P.S. I am aware that showing this behaviour in only one problem does not mean that it happens always, but in a couple of experiments I have done, this behaviour seems to be persistent


texts: Post Correspondence Problem - algorithm that solves the problem for a word with maximum K length

texts:
The question is as follows:

Let's observe the following Post correspondence problem.
Input: Two finite lists of words $A$ and $B$ and a natural number $k$.
Question: Is there any words correspondence with a length of $k$ at the maximum?
Describe an algorithm to solve the problem and analyze its runtime.

I really don't understand how to solve this problem. From my understanding, the Post correspondence problem is undecidable so how come we can describe an algorithm to solve this question?


texts: How to detect infinite loop exist in linear bounded automata (LBA)?

texts:
The following theorem from Michael Sipser's book "Introduction to the Theory of Computation" states:

  $A_{\textrm{LBA}}= \{ \langle M, w \rangle \mid \text{$M$ is an LBA that accepts string $w$} \}$.

  THEOREM: $A_{\mathrm{LBA}}$ is decidable.

On the proof part, it states:

  The idea for detecting when $M$ is looping is that as $M$ computes on $w$,
  it goes from configuration to configuration. If $M$ ever repeats a
  configuration, it would go on to repeat this configuration over and
  over again and thus be in a loop.

I do not understand this:
"If $M$ ever repeats a configuration, it would go on to repeat this configuration over and over again". What if $M$ only repeat one configuration, then halts?


texts: Which instruction yields atomicity in this expression that makes the result 2?

texts:
I am reading about atomicity and came across the following scenario

int x = y = z = 0;

Thread 1        Thread 2
---------       --------
x = y + z       y = 1
                z = 2

Which gives the following sets of output

$$\begin{array}{ccc}1&2&3\\
T1 : x = y + z&T2 : y = 1&T2 : y = 1\\T2 : y = 1&T2 : z = 2&T1 : x = y + z\\T2 : z = 2&T1 : x = y + z&T2 : z = 2\end{array}$$

Translating the $x=y+z$ expression to machine code gives

load r1; y
load r2; z
add r3; r1; r2
store r3;

However according to some notes I read going down the path of

T1 : load r1, y
T2 : y = 1
     z = 2
T1 : load r2, z
     add r3, r1, r
     store r3, x

I cannot seem to understand how the author came to result that $x=2$.

To me, based on the previous machine instructions the result should be 3, which I guess leads me to realize I am supposed to hit eureka (or a simple misread) and realize where the atomicity occurs. Could you explain the atomicity in this fairly simple statement that leads to the correct result?


texts: Is there a "natural" example of a total, computable but non-primitive recursive function?

texts: Every example of a total, computable but non-primitive recursive function seems to be explicitly constructed for proof theory, or in Godelian proofs of "what is the name of this book?" kind. But is there a non-primitive recursive function or algorithm that occurs naturally, like in physics or number theory or even in industry software?


texts: Show that an instance of PCP or MPCP has no solutions

texts:
I'm studying the Post Correspondence Problem (PCP) and understand the concept, although I have problems with proving how to show that an instance of a PCP or modified PCP has no solutions.

For instance, how could I show that the the instance $\ ((0,11,1), (001,1,11)) $ of an MPCP has no solutions? and what is the thought behind it?


texts: Finding median of three sorted array (the same length)

texts:
I think about following problem:
There are given three sorted arrays $A,B,C$ (each of them is length $n$).
Every array has distinct elements.
Find median of union $A,B,C$.

I consider following approach:
Let's consider $A_i, B_i, C_i$, where $i=n/2$. There are six cases - but I consider only one (rest of them is analogous). Let $A_i\le B_i\le C_i$:
Now we may dispse $1/3$ elements - $A[1...n/2]$ and $C[n/2 + 1... n]$.
Unfortunately I can't estimate time of run this algorithm.
I should solve recusrion equality: $T(n) = T(2/3n) + 1$
$(T(0) = T(1) = 1$, but I can't.

I am thinking about better algorithm.  Can you suggest something ?

Edit
I am goint to say more about this algorithm. The key idea is using Divide and conquer method. In each step we may dispose $\frac{1}{3}$ elements.   Lets $i = n/2$.   Let suppose that $A_i \le B_i \le C_i$ (rest of cases is analogous). Look at example:

In every case I dispose $1/3$ elements and get smaller problem.


texts: When retrieving values from a hash table with linear probing, how do we know if the wanted value had not been shifted?

texts: So, after a collision, a piece of information gets stored in the next bucket. When retrieving the value later with a key, how do we know it has not been shifted due to a collision and that we are in fact receiving the wrong value?


texts: I'm working with trees in a project where I need to test various tree-making algorithms and their outcome. A frequent quantity I look for is the number of branches of a tree. Is there a commonly used name for that aside "number of branches"?


texts: Is there a way to measure the maximum random bits of the outputs of a generator?

texts:
I want to give examples to explain want I want to know first. Let $G \colon s \mapsto G(s)$ be a PRG.

Let $F_{1} \colon s \mapsto G(s) \Vert b$, where $b = \bigoplus_{k = 1}^{|G(s)|} G(s)[k]$. Obviously, $F_{1}$ is not a PRG, since the last bit can be predicted. But if we remove the last bit, it is a pseudorandom string.

Let $F_{2} \colon s \mapsto G(s) \Vert G(s)$, $F_{2}$ cannot be PRG, too. but if only choose $|G(s)|$ bits properly, it can be pseudorandom.

So, if $F \colon \{0,1\}^l \to \{0,1\}^n$ is a polytime deterministic generator. Perhaps, $F$ is not a PRG, but $F$ may be closed to a PRG. Namely, there exists a compression algorithm $A \colon \{0,1\}^{n} \to \{0,1\}^m$, where $n \geq m > l$, such that $A \circ F$ is a PRG. Is it well-defined? Can we use something like $n - \min_{A} m$ to measure how is $F$ closed to PRGs? Is there a standard way to measure the maximum random bits of all the outputs of $F$?


texts: Is an undirected graph consisting only two connected vertices cyclic?

texts:
I have two questions:

Does acyclic/cyclic classification only apply to directed graphs?

If not, does the following undirected graph have any cycle?
A --- B


texts: Is this a standard representation of a 'space' character?

texts:
I recently came across a handwritten note with directions to push a string of text into a database. There was a strange character in the string I've never seen before, a lower case 'b' with a forward slash through it:

I asked the author about it and he said it was an old-school way of representing a space.

My question is whether or not this was a standard/widely used representation of a space character and if so, whether or not it's still commonly used.


texts: Is $\log{n}$ bounded from above by $n^{o(1)}$?

texts:
Let $O(n)$ be "Big-O" of $n$ and $o(n)$ be "Small-O" of $n$.

It is a well-known fact that $O(n \log{n}) \subset O(n^{1 + \epsilon})$ for any $\epsilon > 0$. Can we omit the $\epsilon$, and just type $O(n \log{n}) \subset O(n^{1 + o(1)})$?


texts: DAG: When adding an edge that would normally result in a cycle, is there an algorithm to split the graph instead?

texts:
Summary
I am using a DAG to compress a tree structure with many repeated nodes (the repeated nodes only very seldomly do not also have repeated edges out.)
Normally, when attempting to add an edge to a DAG that would cause a cycle, you instead detect the situation and abort.  I'm seeking an algorithm that will instead attempt to add the new edge anyway, modifying the graph such that it still represents the same tree, potentially partially decompressing parts of the graph in order to avoid the cycle.
Does an efficient algorithm to do this already exist?  I have been unable to find one in a perfunctory literature search, though I am not aware of the proper terminology for this operation, if one exists.
Simple Example

In this example, we are adding the edge F->C, which creates a cycle.  To break this cycle, we can split the E node into one version of E with C as a parent and one version of E with D as a parent (notated E'), similarly with F and C.
Slightly more complicated example

In this example we have several more cases. The offending edge from F to D is highlighted.  But there are several paths through the graph, some involving nodes upstream from D, some involving nodes downstream from D, and potentially some not involving D at all.
This graph is a compressed version of this tree:

where the highlighted copies of F are where placing D as a child is permissible. As you can see, these three nodes correspond to the three ways of reaching F' in the previous figure.
Motivating use case
In the game of Go, there is, in certain rulesets, the idea of superko, which forbids repetition of a previous board state.  Such positions are usually very rare in practice.  In order to efficiently search the game tree, we would want to take into account transpositions of sets of moves which leave the board the same, which is why a graph structure is useful, but in situations where a superko is possible the history of the position is also important, not just the current situation.  So while F->C would be a legal move normally, it is only a legal move in situations where C is not part of the node's history, i.e. we went through node D instead of node C.  So we would need to consider the cases separately.
Known Caveats
I am aware of the DAG cycle detection algorithm, and it seems like it might be easy to adapt this algorithm to perform this task, but I cannot seem to make it work. I am also aware that it is not always possible to split a graph in this manner to remove the cycle.


texts: Running an algorithm on data remotely and ensuring answer has not been tampered with

texts:
I´ve been thinking about this particular computing/crypto/database problem for years and I just want to know if there are already solutions to it. To be honest I don´t even know what field this problem belongs to exactly.

In a nutshell: person A has a list of data, another person (B) has an algorithm that gives each item on this list a score and then sums all these scores to provide an overall score for the whole list. How can we run the algorithm on the data list so that the data is kept extremely secure (preferably never leaving person A) but so that person B can be certain the algorithm ran properly and was not tampered with.

Here is an example: Anna and Bob live in a large village. Anna has a list on her computer of all the things she has done in the village, both good and bad. Bob has made a very simple scoring algorithm for such lists, which runs on each item on the list and gives it a score and then adds all these numbers up to give Anna a final score. This score lets Bob know how beneficial Anna is to the village community and is specific to Bobs opinion. (This is more than an example as this is actually the system I want to make)

However Anna does not want to give Bob her list, as then he has access to potentially embarrasing info in there (everyone has skeletons in thier closet). Bob however does not trust Anna to run his algorithms herself, as she may just lie and tell Bob the score was very high so that Bob is more likely to help her.

There are a few solutions I have already thought of, but all have problems:

A. Find a random person to take the data and run the algorithm and send the score back, but it may be difficult to ensure that this random person do not know Anna and try to help her or make a copy of the data and later try to trace it back and blackmail Anna.

B. Let Anna run the algorithm but somehow encode a check code into the scores, for example, instead of rating an event as 1 rate it as 1.0000000000797, in such a way that Bob can later use this as a checkcode to see if the given score is correct. However this check could also be misused by Bob to indicate what specific things Anna has done. Also I can imagine such a system would be trivial to reverse engineer so that Anna can give a false score with a correct checkcode, considering that Anna must have full access to Bob´s algorithm to run it.

C. The village creates a secure server to take such data and algorithms and run them together. However Anna and Bob both don´t really trust anyone enough to do this and not make a copy of the data or modify the scores, unless there is some fundamentally secure architecture for doing so. Also I would prefer this to be a P2P system.


texts:
I'm preparing an UML use case diagram for my following school project:
The main goal of the project is to design a software that eases the process of installing an
operating system in today's systems. Normally the users must download the distribution
that they think is most suitable for them, burn the downloaded image of the distribution (ISO)
to a removable media (USB), boot the removable media, and then start the installation process.
Since all these stages have many sub-steps, installing an operating system is not something
that most people can do easily.

It's an abstract subject and it's not expected to be something completely realistic whatsoever. So here's the Use Case Diagram that I was working on:

Visual Paradigm project
My question is: Is this usage correct? Do I have to fix/replace/add something?


texts: Count number of ways to place ones in an $M \times M$ matrix so that every row and column has $k$ ones?

texts:
On math.stackexchange, someone asked how to count the number of ways to place $1$'s into a $10 \times 10$ matrix so that every row and column has $5$ $1$'s.  Each element of the matrix must be either zero or one.

I came up with a recursive solution for an $N \times 10$ matrix.  Subproblems are indexed by the counts $c_k$ of how many columns have $k$ $1$'s, for $k =0, 1,2,3,4,5$. The counts $c_k$ have to satisfy $\sum_k c_k = 10$, and they also have to satisfy $\sum_k kc_k = 5N$ and $c_k = 0$ for $k > N$. The complexity of this algorithm basically boils down to how many distinct sets of valid indices $(c_k)_k$ there are.

For a $10 \times 10$ matrix I think this approach should work out nicely, but I worry the complexity might get prohibitively large if we wanted to count how many ways to get $M/2$ $1$'s in every row and column of an $M \times M$ matrix. So I'm wondering, is there a more efficient way to solve this counting problem?  In other words, a better way than solving for $N \times M$ in increasing order of $N$ and keeping track of subcases indexed by $(c_k)_k$ such that $\sum_k c_k = M$ and $\sum_k k c_k = NM/2$? Also, for my solution, can anybody work out a good bound for how many sub-cases I have as a function of $M$?


texts: Definition/properties of NFA extended transition function

texts:
I am trying to prove by induction that if

$$\hat\delta_d(q_0, w) = \hat\delta_n(q_0, w)$$

I know by practicing inductive proofs of the $\hat\delta$ for DFAs, that on the basis of the definition of $\hat\delta_d$

for any $q \in Q$, $\hat\delta(q, \epsilon) = q$
for any $q \in Q$ and $a \in $ the language of the DFA,  $\hat\delta(\delta(q, y), a)$
$\hat\delta(q, ax) = \hat\delta(q_1, x)$ where $a_1 = \delta(q,a)$

Does the extended transition function also have these properties? Does it have other definitions/properties?

For reference, $\hat\delta_d$ refers to the extended transition function of DFAs and $\hat\delta_n$ refers to the extended transition function of NFAs.


texts: Is List comprehension equivalent to composition of filter and map?

texts:
Wikipedia says

  A list comprehension is a syntactic construct available in some programming languages for creating a list based on existing lists. It
  follows the form of the mathematical set-builder notation (set
  comprehension) as distinct from the use of map and filter
  functions.

  A list comprehension has the same syntactic components to represent
  generation of a list in order from an input list or iterator:

  A variable representing members of an input list.
  An input list (or iterator).
  An optional predicate expression.
  And an output expression producing members of the output list from members of the input iterable that satisfy the predicate.

  The order of generation of members of the output list is based on the
  order of items in the input.

I think a list comprehension can be equivalently converted to combining a filter and a map in the following way:

"An optional predicate expression." corresponds to a filter
"an output expression producing members of the output list from members of the input iterable that satisfy the predicate" corresponds to a map

So are list comprehension  and  combination of filter and map  equivalent?

Thanks!


texts: Priority inversion in Hoare and Mesa monitors

texts: I understand the difference between Hoare and Mesa monitors. However I don't understand why priority inversion (when a lower priority process gets done before a higher priority process) is possible in the Hoare type but not possible in the Mesa type. Can someone explain this?


texts:
Lemma 2 in "Impossibility of Distributed Consensus with One Faulty Process" is as follows:

  LEMMA 2. P has a bivalent initial configuration.

They prove this by showing that the opposite assumption creates a contradiction. As part of that proof, they state:

  Let us call two initial configurations adjacent if they differ only in the initial value x, of a single process p. Any two initial configurations are joined by a chain of initial configurations, each adjacent to the next. Hence, there must exist a 0-valent initial configuration C0 adjacent to a 1-valent initial configuration C1.

In other words, there exists two "adjacent" sets of inputs that differ in only in the value of one of the inputs.

But if I use the output of a totally correct consensus protocol to ensure that the inputs are always either all 0 or all 1, the resulting two sets of inputs would not be "adjacent".

So it appears they implicitly assume that every combination of inputs must be possible. Why can they make this assumption?


texts: Run time of Dijkstra's compared to Kruskal's algorithm using union-find

texts:
I am dealing with the following statement:

  the run time for Dijkstra's on a connected undirected graph with positive edge weights using a binary heap is $\Theta$ of the run time for Kruskal's using union-find.

However, this is false and I fail to see why this is so. Dijkstra's algorithm when using binary heap is $O(|E|\log|V|)$. The same is true for Kruskal's algorithm as its complexity is $O(|E|\log|V|)$.

Hence, can someone reconcile this difference? Are there certain edge cases for when this isn't true, hence making this statement false?


texts: Different definitions of complexity class DP

texts:
I would like to know how different defintions of class DP (also written $D^p$) are equivalent (brief explanations would do). The following are the two definitions I see:

Difference between two NP problems; i.e.,  DP $:=\{A\setminus B\ :\ A,B\in NP\}$.
$\{L_1\cap L_2\ :\ L_1\in \text{NP},\ L_2\in \text{co-NP} \}$.

Complexity zoo gives the full form "Difference Polynomial-Time" for DP and states that it is equivalent to BH$_2$. They give Definition 3 above as the definition of BH$_2$. (So, according to complexity zoo, the two definitions are equivalent).
This answer says that the definition of DP changed over time. Is this true? If so, which definition is accepted nowadays? Is there a book or survey that explains the complexity class DP (at least as a section) ?
According to this source, NP $\subseteq$ DP. Doesn't that mean DP-hard problems are NP-hard and the other direction is wrong (the latter, unless there is a collapse in complexity classes)?


texts: Probability of arising of simple graph in configuration model

texts:
I am studying a configuration model building $d$-regular graphs and reading the following article:
The expansion of random regular graphs by David Ellis.
I am stuck on the following step:

Each simple labelled $d$-regular graph on $n$ vertices has the same probability of arising. Indeed, it is easy to see that a simple d-regular graph on $[n]$ arises from precisely $(d!)^n$ of the matchings.

Where does this $(d!)^n$ come from?


texts: Can we load the data on the bus on multiple registers at the same time?

texts:
So in the book that I'm reading it says at a time only the data of one register can be on the data bus and only one register can load the data. the first part i get but what about the second part?

why can't we just turn on the load parameter for both of the registers at the same time?

I'm studying for computer architecture and this is the bus that I'm talking about:

Computer

so can we transfer the data from one register to multiple registers with 1 clock?

like transfer the content of AC to PC and DR with one clock?(turn on the load parameters for both of DR and PC at the same time? why can't we do that?)


texts: What is the best algorithm to match a student's schedule with a tutor's schedule?

texts:
I am building an application (RoR framework) that can help to match a tutor and a student based on their subjects, budgets, locations and freetime. I have done the first three parts(subjects, budgets, locations). Now, I am getting stuck at the most difficult one which is freetime matching.

The student's sample freetime:

Monday: 7AM-8:30AM
Wednesday: 6AM-8AM
Friday: 9AM-10:30AM

Now I want to match this student with a list of tutors who have the freetime that can match with the student's freetime. In addition, each session between a student and a tutor must be 90 minutes.

For example, the following is the tutor's freetime:

Monday: 6AM-9AM => matches because both the student and tutor can start their session at 7AM, and when the session ends at 8:30AM, it is still in the range of the student's freetime and tutor's freetime.
Tuesday: 7AM-10AM => doesn't match, of course.
Wednesday: 7AM-9AM => doesn't match because both of them can start their session at 7AM, but when the session ends 8:30AM, the student's time is already over.
Friday: 10AM-11:30AM => matches, like the case in Monday.
=> Conclusion: this tutor doesn't match with the student since he just matches 2 out of 3 days with the student (Monday and Friday)

I tried to use Hash data structure to solve the problem.

student_freetime = { monday: { start_time: 7, end_time: 8.5 }, wednesday: { start_time: 6, end_time: 8 }, friday: { start_time: 9, end_time: 10.5 } }

tutor_freetime = { monday: { start_time: 6, end_time: 9 }, tuesday: { start_time: 7, end_time: 10 }, wednesday: { start_time: 7, end_time: 9 }, friday: { start_time: 10, end_time: 11.5 } }

However, I think this is a bad solution since I need to use loop and if many times.

Therefore, I have been searching for the best solution for this problem, and found some suggestions on using the Hopcroft–Karp algorithm on stackoverflow. However, I've never implemented graph related algorithm before, so I am not sure the Hopcroft–Karp algorithm is the best choice in my case. As I understand, to implement Hopcroft–Karp algorithm  first I need to create to have 2 sets of data. In this case, I think the first set would be the student's freetime in a particular day, and the second set would be the tutor's freetime in the same day. But at this step, I am wondering how can I match their time by using Hopcroft–Karp algorithm  as I pointed out above, their freetime can be different and still match as long as it satisfies the session's limit time (90 minutes).
I would be appreciated if anybody could give me some suggestions here or point me to the right resources/similar problems.


texts: Is it possible to create a regular language from an non regular language? (details inside)

texts:
I am wondering, is it is possible to create a regular language from a non regular language if we add or remove finite number of words from it?

say L is irregular, if we add or remove finite number of words can we create a regular language?

i might be mistaken, but since all regular languages are finite - if we add a finite amount to a non regular language - it still stays non regular, but if we substract, let's say a finite amount from infinity, it is still infinity.

so is it safe to say that in both cases a regular language cannot not be obtained by adding/substracting a finite amount of words?

i was told to ask this question here rather then in softwareengineering.

thank you very much for your help. really curious about that


texts: Is this a proof that SET COVER is not an NP-hard problem?

texts:
In this paper, Karpinski and Zelikovsky introduce the SET COVER and the $\epsilon$-DENSE SET COVER problems as follows:

  Set Cover Problem. Let $X = \{x_1, \ldots, x_k\}$ be a finite set and $P = \{p_1, \ldots, p_m\} \subseteq 2^X$ be a family of its
  subsets. Find minimum size sub-family $M$ of $P$ such that
  $X \subseteq \bigcup \{p \mid p \in M\}$.

  An instance of the set cover problem is $\epsilon$-dense if there is
  $\epsilon > 0$ such that any element of $X$ belongs to at least
  $\epsilon \, m$ sets from $P$. We show that the dense set cover
  problem can be approximated with the performance ratio $c \log k$ for
  any $c > 0$ though it is unlikely to be NP-hard.

In page 3, Lemma 2.1 implies—and Theorem 2.2 proves—that $\epsilon$-DENSE SET COVER is not NP-hard. But, since SET COVER is $\frac{1}{m}$-DENSE SET COVER (any element of $X$ belongs to at least 1 of the $m$ sets), would this mean that SET COVER is not NP-hard?


texts: Nodes reached with exactly $k$ steps in an undirected graph?

texts:
Given an undirected graph $G$ of $N$ nodes and a starting node $s$, I want to build, with dynamic programming, a table whose $(k, n)$-th entry is $1$ if node $n$ is reachable with exactly $k$ steps from node $s$.

Specifically, for the first row of the table, I set $(1, n)$ to 1 if node $n$ is connected to node $s$. Then for the second row, I set $(2, n)$ to 1 if node $n$ is connected to any of the nodes who have value $1$ in the first row. I can stop the construction whenever I have a repeated row. In other words, I want to build the table to the point where more rows will be redundant, as there are already exact copies of them up in the table. So $k$ should be expressed in terms of $N$.

I want to check if this table construction can be done in polynomial time.  I think it boils down to whether the number of rows is polynomially bounded. Is it so?

My intuition is yes, because in the worst case, where the $N$ nodes are serially connected one next to another, and starting node $s$ is at one end, I can still reach the other end with $N-1$ steps.


texts: Algorithm to find all 2-hop neighbors lists in a graph

texts:
Given a graph $G = (V,E)$, where $|V| = n$. What is a fast algorithm for generating the collection of all 2-hop neighborhood lists of all nodes in $V$.

Naively, you can do that in $O(n^3)$. With power of matrices, you can do that with $O(n^{2.8})$ using Strassen algorithm. You can do better than this using another matrix multiplication algorithm. Any better method ? Any Las Vegas algorithm ?


texts: Edge exchange property of two Minimum Spanning Trees

texts:
Given an undirected graph G with weight on its edges and 2 different minimal spanning trees(MSTs): T, T'
Then I want to prove the following:

For every edge e in T that's not in T', there is an edge e' in T'
that's not in T such that if we replace e with e' in T (let's call
it T_new) then it's still a minimal spanning tree of G.

I think I am too close for finding the right algorithm but stuck a little:

I have proved that weight(e) must be exactly equal to weight(e').

Since T is a tree, deleting e will result in 2 separated components, then for T_new to be a tree it must use one of the edges connecting two vertices from those different components.

But, I wasn't able to know which edge e' exactly will work. Plus I wasn't able to prove that always there is such an edge (I just found some requirements for e' that is must satisfy).
Some notes: I know Kruskal algorithm, and familiar with an algorithm in which we can paint some edges in yellow and request it to generate minimal spanning trees with maximum yellow edges (In other words from all found minimal spanning trees return the one with maximum number of yellow edges)


texts: Are different assignments allowed for the implication graph proof of 2-SAT being in P?

texts:
One proof for $2-SAT$ being in $P$ uses the implication graph, i.e. one creates 2 vertices per variable $a$, one for each possible literal ($a$ and $\neg a$). One then adds 2 arcs per clause $(a \lor b)$, one from $\neg a$ to $b$ and one from $\neg b$ to $a$, respectively representing the implications $\neg a \implies b$ and $\neg b \implies a$. Finally, (assuming a solution exists) one sorts the connected components in topological order and traverses these in reverse order. Now for the important part :
For every literal $a$ encountered, set variable $a = true$, and for every literal $\neg a$ encountered, set variable $a = false$.
Don't change variables already set. The resulting assignment is a solution.
My question is : Do other assignments work as well, as long as the underlying implications stay $true$ ? For example :
For every literal $a$ encountered, set variable $a = false$, and for every literal $\neg a$ encountered, set variable $a = true$.
since $false \implies false$, or even some combination :
For every literal $a$ encountered, if it points to some literal that equals $false$, set $a = false$, otherwise set it to either $false$ or $true$. For every literal $\neg a$ encountered, if it points to some literal that equals $false$, set $a = true$, otherwise set it to either $false$ or $true$.
since $true \implies true$, $false \implies true$, and $false \implies false$?


texts: Bits of memory address used for page number?

texts:
A $64$-bit computer has a virtual mem space of $2^{64}$ bytes and the computer also uses memory paging with size of $2^7$ $(128)$ bytes.

Work out the bits of the memory address which are used for the page number?

No. of bits of the memory address which are used for the offset?

Can someone explain how I would go about doing this ?


texts:
I try to solve exercise "on the power of double - logarithmic space" from the great textbook Computational Complexity by Oded Goldreich.
The goal is to show that the given set $S=\left \{ w_k \mid k \in \mathbb{N} \right \}$, where $w_k$ - concatenation of all $k$-bit long strings separated by *'s is not regular and yet it is decidable in double-logarithmic space. The exercise contains guidelines, and I would like to shed the light on few sentences from guidelines in order to solve the exercise.

In the guidelines it's mentioned that

  we can take advantage of of the *'s (in $w_i$) , the $i$th iteration
  can be implemented in space $O(\log i)$

The $i$th iteration is verifying whether $x = w_i$, which is really can be decided in $O(\log i)$ space, where $\log i$ can be used to note the position in $i$ long string, but the position in $x$ can be included in $O(\log i)$ or not?

  Furthermore, on input $x \notin S$, we halt and reject after at most
  $\log |x|$ iterations.

It means only $\log |x|$ $w$'s from the set S will be compared to $x$. Why it is actually so?

  Actually, it is slightly simpler to handle the related set
  $\left \{w_1**w_2**..**w_k \right \}$

Why it is actually so, and I would call it set, it is rather concatenated string.


texts: Multi Source/Sink Max Flow Alternative Reduction

texts:
When solving a multi source/sink max flow problem, the classic reduction to the single source/sink problem is to add a new source and sink node with infinite capacities that connect to/from the existing source/sink nodes.
I was curious about an alternate reduction. It is kind of silly buy I just wanted to sanity check it.
Is it possible to group all the source nodes into one big source node, with all the outgoing edges of the original source nodes now added to the mega source node. We can collapse repeated edges by adding up their capacities. A similar thing can be done for sink nodes.
Let's say I have a solution to the mega source/sink problem. You would have to keep track of which edges in the mega source/sink node correspond to which edges in the original sources/sinks, and choose the same corresponding flow for the original source nodes' edges. For two edges that you collapsed in the mega node by summing their capacities, you can just distribute the flow arbitrarily amongst the original source nodes (maintaining the capacity constraints).
Does this approach fail catastrophically or sound reasonable?


texts: Halting problem and simulation of intelligence

texts:
According to halting problem, there is no algorithm which can decide if another algorithm and its input will halt or not.
Suppose human intelligence can be simulated in a computer.
Also suppose than human can determine if an algorithm will halt for its input.

Then, the simulated brain, which is a program in a computer hence another algorithm, must be able to solve the halting problem which is impossible.

Then, either the human intelligence cannot be simulated in a computer or humans themselves cannot solve halting problem.

On the other hand simulation of brain as a collection of particles is doable at least in principle. Which leaves us with the only option which is human themselves cannot solve halting problem. Am I right?


texts: Optimizing greedy solution for choice game

texts:
Consider the following game: Two players choose numbers from a sequence of integers with even number of elements. The two can only choose from either the front or the end of the sequence. The purpose is to pick a series of numbers that form a sum greater than the opponent's. The first player always starts and tries to beat the second player, which chooses his numbers randomly. Develop a strategy with which the first player always wins. By winning we consider that the first player's sum is greater or at least equal to the second player's sum.

My solution (greedy): At each step, P1 chooses the greater number between the front and the end of the sequence. At the end Sum(P1) >= Sum(P2).

Example:

S: 4 5 3 1
P1: 4
P2: 5 or 1
P1: if P2 picks 1, then P1 picks 5 || if P2 picks 5, then P1 picks 3
P2: picks either 3 or 1, depends on P1's choice
Sum(P1) (= 9 or 7) >= Sum(P2) (= 6 or 4)

Problem: For certain sequences, the above greedy approach does not compute a greater sum for P1. For S: 1 2 80 3, if P1 will choose 3 as it is greater than 1. If P2 then picks 80, the game is lost for P1.

My take on this situation: We scan S for it's greatest numbers and compare them to the greatest sum of numbers chosen up to them and create a strategy for P1 so that he chooses the greater number/ numbers. In the example above we find that 80 > 3 +1 (possible sum up to it), so P1 will first choose 1. This way P2 will have to pick from 5 and 3. After P2 chooses, P1 picks 80 and wins.

Thoughts on this?


texts: Smallest Circuit for Square of Sparse Symmetric Matrix

texts:
I have an n by n symmetric matrix, and I would like to compute its square in as small a circuit complexity as possible. It's sparse: there are sqrt(n) nonzero entries in each row/column, so the input will be sparse by the output will be nearly a density of 1. A normal sparse multiplication algorithm would take O(n^2) time which is clearly optimal, but the circuit depth for any sparse representation I can think of is at least O(n^3). (The act of "accessing a given location in memory" is not efficient in circuits.)

Using a fast matrix multiplication method like Coppersmith Winograd would bring me to O(n^~2.4). I know I can use the symmetry to reduce by a constant factor, but I figure not more than that. I'm hoping that the fact that it's squaring (and not multiplying two different matrices) can reduce the exponent, but I don't know how -- I know that it can cut my work down a bit because the first iteration of C-W will have some identical results. I can't find any way to use the sparsity at all.

Numerical precision isn't an issue for me; the input is a 0-1 matrix.

In terms of practical purposes, I particularly care about n~3000, but am generally curious about asymptotically good answers too. (Just saying this to explain that very huge constant factors are a big negative for me.) Any references very much appreciated!


texts: Test cases for graph embeddability problem

texts:
Suppose that I have a polynomial-time algorithm to solve the graph embeddability problem.

$k$-embeddability problem :
Given an edge-weighted and undirected graph $G = (V,E)$, can we assign coordinates to each $v \in V$ in $k$-dimensions such that Euclidean distance between $u,v \in V$ is equal to the weight of the edge $\{u,v\}$?

And, suppose that I want to check if I have settled P vs. NP. The algorithm has 100% success rate when tested with random graphs.

However, I might be lucky while generating random data. Is there any finite set of test cases, such that if an algorithm solves each of them, that implies the algorithm is able to solve graph-embedding problem for all possible problem instances?

(I've already verified that the algorithm runs in polynomial time; now I just want to verify whether the algorithm is correct.)


texts:
Starting from this definition https://en.wikipedia.org/wiki/Boolean_algebra_%28structure%29#Definition, is the following a valid proof that $\neg 0 = 1$?

Instantiate a ∨ ¬a = 1 with a:=0 to get 0 ∨ ¬0 = 1
Then use pattern matching (and commutativity) against a ∨ 0 = a to get a = ¬0 on the LHS and a=1 on the RHS, thus ¬0 = 1.

To clarify the "pattern matching":
We have

0 ∨ ¬0 = 1
0 ∨ 1 = 1 (from 0 ∨ a = a)
0 ∨ 0 = 0 (also from from 0 ∨ a = a)

If there are only the two elements 0 and 1 available, ¬0 = 1 should follow from this. But then again, if it were not true that ¬0 = 1, we would have that ¬0 = 0, which wouldn't make too much sense...

Are there other/simpler proofs?


texts:
If we have the function $f : \mathbb{N}_0 \rightarrow \mathbb{N}$ with $f(n) = n^2$ and we look at the following representations of the sets $\mathcal{o}(f),\mathcal{O}(f),\Theta(f),\Omega(f),\omega(f) $:

Now I have to list all necessary statements which are proving that the illustration is correct.

The necessary statements are in my opinion:

\begin{align}
\Theta (f)&\subseteq \mathcal{O}(f) \\
\Theta (f)&\subseteq \Omega (f) \\
\Theta (f)&= \mathcal{O}(f) \cap  \Omega (f) \\
\omega (f)&\subseteq \Omega (f) \\
\hbox{o}(f)&\subseteq\mathcal{O}(f) \\
 \, \emptyset &=\, \omega (f) \cap \hbox{o}(f)
\end{align}
Now I have to proof two statements of my choice. But how to proof that in a formal correct way. (I understand the intuitive proofs but I don't know how to do it formally correctly.)

Hope somebody can help.


texts:
When doing the "inexact" analysis of the Merge Sort, the literature that I have seen usually consider that the input is an array with a even quantity of numbers and the recurrence relation is:

$T(n) = 2T(n/2) + \Theta(n)$

But how I can formally prove that even if I consider any input, the complexity stays the same? While looking in the answers to the exercise 4.3-5 of the book Introduction to Algorithms on this site, he mention the recurrence for the odd sized input is as follow:

$T(n) = T((n-1)/2) + T((n+1)/2) + \Theta(n)$

And justifies that:

  However, shifting the argument in $n.log(n)$ by a half will only change the value of the function by at most $\frac{1}{2}\frac{d}{dn}(n.log(n)) = \tfrac{log(n)}{2} + 1$, but this is $o(n)$ and so will be absorbed into the $\Theta(n)$ term.

But I did not understand his justification very well. Somebody could explain to me?

(Exercise 4.3-5: Show that $\Theta(n.log(n))$ is the solution to the "exact" recurrence for merge sort.)


texts: Scheduling tasks on a graph with assistance

texts:
This is a follow-up to a question that I recently posted here: Completing tasks on a graph. In that question, I posted the following:
Consider a graph $G = (V, E)$, where $V = \{0, 1, 2, \ldots, n\}$. The graph $G$ is complete, which means we can traverse $(i, j)$ for all $i, j \in V$. At each vertex $v \in V$, there is a task that we must complete. The task at vertex $v$ takes $q_v > 0$ minutes for $v \neq 0$, and we must complete all tasks. We start at Vertex $0$, and we have $q_0 = 0$.
It will obviously take us exactly $\sum_{i = 1}^{n} q_i$ total time for us to complete all of the tasks on our own  (it doesn't take any time to traverse the edges). However, suppose we have a single helper. We are allowed to dispatch the helper at any node (say $v$), and we can leave the node, go work on other tasks, and pick up the helper after $q_v$ minutes to drop it off at another node. A caveat is that the helper cannot move on its own; it must be picked up and dropped off.
Is there some sort of algorithm that allows one to find the best strategy (i.e., one that minimizes the total time) when we are allowed one helper?

As a summary, in the initial post, I asked for an approximation/heuristic that would allow me to minimize the total time spent completing all of the tasks with the assistance of a helper. Tom van der Zanden proposed an answer in which the longest job is always assigned to the helper, and they showed that this is an efficient polynomial-time approximation scheme for the makespan.
However, I now want to consider a slight variant of the problem. Most of the problem remains the same, but the following constraint is added: The helper cannot be dispatched at any node. Instead, there is a subset of vertices $S \subseteq V$ that is known to everyone at the start of problem, and the helper can only be dispatched at the vertices in this subset.
I looked at the extreme cases (i.e., $S = \emptyset$ and $S = V$). When $S = V$, the heuristic proposed in the previous post obviously works. When $S = \emptyset$, the total time taken is fixed since we cannot exercise the option to use a helper vehicle.
I was wondering whether there was an approximation scheme or heuristic that might be efficient in this general case.


texts: Subgraph isomorphism reduction from the Clique problem

texts:
I was trying to understand the Wikipedia proof for NP-completeness of subgraph isomorphism by reduction from the clique problem. It's really just one sentence:

  Let $H$ be the complete graph $K_k$; then, the answer to the subgraph isomorphism problem for $G$ and $H$ is equal to the answer to the clique problem for $G$ and $k$.

In the subgraph isomorphism problem, $G$ and $H$ are not constrained in any way (e.g., $H$ is not constrained to complete graphs). Yet, in the proof, Wikipedia just states "let $H$ be the complete graph $K_k$". It's not defined what $K_k$ represents or why $H$ suddenly becomes constrained to a complete graph.


texts: Fast algorithm for interpolating data from polar coordinates to cartesian coordinates

texts:
I have a set of solution nodes generated over a polar grid. I would like to convert / interpolate these solution nodes onto a Cartesian grid:

That is, using the image above, for each node in the Cartesian grid I would interpolate a value from the closest existing nodes (red).

Currently, my approach is to generate a kd-tree for the original solution nodes, then use a nearest-neighbor search to obtain the three closest nodes. I then use barycentric interpolation to obtain a value from these three points. The problem, however, is that my polar grid is much finer along the radial direction than it is in the azimuthal direction, which means that my nearest-neighbor search almost always selects points from the same radial. This has the result of creating "striations" in my new solution, instead of smoothly interpolating along the azimuthal direction (i.e., the results look no different than if I had simply mapped the nearest point to the "interpolated" point).

Unfortunately, I don't know how to achieve a better sampling without sacrificing the kd-tree and losing a lot of the speed improvements. Am I being thick-headed and missing an obvious solution? Or does anyone know a better way to approach this problem?


texts: Information gain vs Gini impurity, for Random Forest?

texts:
I was researching about the supervised algorithm called Random Forest, that made me begin to study about decision trees, and how to induce them from a set, in order to create several predictors.
My question comes at this point when we consider functions such as Information Gain or Gini impurity.

In order to use as splitting functions, both functions are very similar almost for the binary case, the only differences is that the first function has a maximum value of 1 whereas  the other one has a maximum of 0.5 for the binary case.
I would like to know in which cases it's is better to use one instead the another.  I would also really appreciate any intuitive explanation of this kind of conclusion.


texts: Union of infinitely many regular languages

texts:
I need to prove or disprove the following statement.

  If  $A_n ⊆ \Sigma^*$ is regular for each $n \in \mathbb{N}$ then $\bigcup\limits_{n=0}^{\infty} A_n$ is regular.

I know that if two languages are regular, then the union of the languages is also regular. I don't think that really applies to this problem, because it's the union of every $n \in \mathbb N$. Also, to help with my understanding with the definitions, is $A_n$ a language or an alphabet, since it's a subset of $\Sigma^*$?


texts:
I'm reading this article.

In particular I'm having some trouble trying to replicate the results of the first image in that article.

For x=9, the graph says that the probability is 0.20 aprox. But from my calculations I get something different. After some thought I think I may be misinterpreting the idea of the calculation.

First attempt: Doing the sum of a X -> Bin(1024, 1/29), calculating f(X=1)+...+f(X=1024). My calculation equals 0.86 which is not 0.20

Then I thought that maybe he was talking about just having 1 result with 9 leading zeros. This means that from the 1024 numbers, we can have only 1 success in any of the 1024 numbers. Which is 0.27... closer but far from 0.20.

What am doing wrong here?


texts: Practical algorithms for the disjoint paths problem

texts:
Given an undirected graph $G$ and two pairs of vertices $(s_1, t_1), (s_2, t_2)$, the disjoint paths problem (DPP) asks for two vertex-disjoint paths, one from $s_1$ to $t_1$ and the other from $s_2$ to $t_2$.

The problem has been shown to be in $P$ even for the generalization with $k$ disjoint paths, where $k$ is a constant [1, 2].

I'm interested in practical algorithms to solve this problem. The algorithm given in [1] runs in $\mathcal{O}(nm)$ but uses many case distinctions which makes it very cumbersome to implement.

Are there any known algorithms which are more practical to implement, even at the expense of a worse runtime guarantee?

I'm interested in application to 3D grid graphs, so results assuming planarity or low tree-width unfortunately do not help.

[1]: Shiloach, Y. (1980). A polynomial solution to the undirected two paths problem. Journal of the ACM (JACM), 27(3), 445-456.

[2]:  Robertson, N., & Seymour, P. D. (1995). Graph minors. XIII. The disjoint paths problem. Journal of combinatorial theory, Series B, 63(1), 65-110.


texts: I'm not sure if this is off-topic but I was thinking about the following: many modern (object-oriented) programming languages are very similar at their core, i.e. they share language features like iterative functions, classes, objects, inheritance, polymorphism etc. Has anyone ever attempted to create a "unifying" (maybe pseudo-code) language that captures all the features shared by those languages such that it would be easy to e.g. compile it to any of them?


texts: MOOC recommendations for learning algorithms based on topics covered in Daspupta, Papadimitriou & Vazirani

texts:
I would appreciate some advise/mentoring on self-study of algorithms. Based on my several years of work as a software developer (non CS background), I have some good grip on standard data structures (linked lists, stacks etc.) and basic sorting and searching algorithm characteristics (time/space complexity).
My goal of learning is to take my knowledge to next level (learning graph theory and advanced algorithm techniques such as dynamic and linear programming) to be able to use it in a variety of situations incl. AI and computationally complex domain problems.
So I purchased 2 books -- Algorithm Design Manual from Skiena and Algorithms by Dasgupta et al. I am aware of the usual advice of CLRS, but decided to skip it for now as my goal at this stage is not proofs.
Now my question is: even though I found the style of writing of Dasgupta book rather appealing, topic is often difficult for unguided, unsupervised learning.
Are there any recommendable online courses (free or otherwise) which would cover topics from Dasgupta book? In general, I found the topics covered in Stanford Algorithm specialization (coursera and edX) rather good, but any further options would be helpful!


texts: What graph data structure works fastest with Dijkstra's algorithm?

texts:
What data structure should I store my graph in to get the best performance from the Dijkstra algorithm?

Object-pointer? Adjacency list? Something else?

I want the lowest O(). Any other tips are appreciated too!