texts: Why Minimum circuit size problem is important?

texts:
Given a truth table, find the smallest size circuit computing it. Recently it was shown that for multiple output function the problem MSCP (Minimum Size Circuit Problem) is NP-Complete. The article is available online see.

Question: What will be the impact of this problem? or I am not able to follow why this problem MSCP is so important?

I didn't read the article completely, only the introduction part, it seem to me that problem is related to many other problems of interest.


texts: Prove a network is a feedforward network if and only if the numbering of its cells satisfy these conditions

texts:
Undergraduate math student here attempting to understand neural networks. Picked up a text on sale, "Neural Network Learning and Expert Systems" (Gallant), and I'm just starting on the exercises for chapter 1.

The full question is:

Prove that a network is a feedforward network if and only if its cells are numbered in a way such that:

all $p$ input cells are numbered from $1$ to $p$.
whenever cell $u_j$ is connected to cell $u_i$, then $j < i$.

The definition of a feedforward network, according to Gallant, is a directed network such that there are no cycles between any nodes.

I'm confused for a few reasons.

This sounds like I'll need at least a basic understanding of graph theory, which I don't have. Any quick and dirty resources that should cover what I need for this kind of material? I don't even know how to represent a network like this mathematically.
I'm used to the numbering of things being pretty arbitrary, for example, numbering basis vectors in a set just to differentiate between them. I don't really have an intuitive idea for why the numbering of input cells is a factor in deciding if a network has directed cycles or not.

Thanks in advance.


texts:
How can I show that the expected pairwise square euclidean distance between points in $X$ is $Θ(d)$?

Where $X$ is a $(x_1,...x_n)$ of points generated uniformly at random in the unit, d is d-dimensional cube , $x=(x(1),...x(d))$ the generic point has its -th component $x(i)$ chosen uniformly at random in$ [0,1] $independently of other components and points.

$\Theta(d)$ represent the largest possible distance is d.

I try to reconduct this problem to Bertrand Paradox but i dont think is right. Maybe I that show that $E(||x−y||2)=Θ(d)$ , because is a hint but i dont know how.

i m following this path: https://stats.stackexchange.com/questions/22488/probability-that-uniformly-random-points-in-a-rectangle-have-euclidean-distance

but is different to my point.

Thanks.


texts: Segment-tree construction: do we recurse into both children?

texts:
This question is about segment-tree as described in this Wikipedia article.

When constructing the tree (inserting the new input-interval), if the input-interval doesn't contain the node-interval we have to recurse into node's child, where child-interval intersects input-interval.

But what if both children-intervals intersect input interval? Should I recurse into both children-nodes?


texts: Proof for Minimum number of insertions to convert a string to a palindrome

texts:
For the problem "Find the minimum number of insertions to convert a string $S$ to a palindrome", a recurrence relation usually given is:

$$
c[i,j] = \begin{cases} c[i+1,j-1] & \text{if } S[i] = S[j], \\ \min(c[i+1,j],c[i,j-1]) + 1 & \text{otherwise}. \end{cases}
$$

(where $c[i,j]$ denotes the minimum insertions for the substring of $S$ beginning with index $i$ and ending with $j$).

But how do we (formally) prove the correctness of that relation? I tried to use the "cut-and-paste" method, but wasn't sure how to apply it here (to either the first or second line of the recurrence relation).


texts: How do I apply the Pumping Lemma to prove that this language is not regular?

texts:
I am trying to teach myself Automata theory. I have hard time with the Pumping Lemma, so I am trying to work through examples. I stumbled upon this example, but it doesn't have steps how to solve it.
I would appreciate a clear explanation of how I would use the Pumping Lemma to prove that this language S is not regular:
$$
S = \{va^{7|v|}\text{ | }v \in \{a,b\}^*\}
$$
|v| = length of v
How do I use the Pumping Lemma to show that S is not regular?
Thanks.


texts: Left recursion and left factoring -- which one goes first?

texts:
if I have a grammar having a production that contains both left recursion and left factoring like

$\qquad \displaystyle F \to FBa \mid cDS \mid c$

which one has priority, left recursion or left factoring?


texts: Approximation of minimum bandwidth on binary trees

texts:
Minimum bandwidth problem is to a find an ordering of graph nodes on integer line that minimizes the largest distance between any two adjacent nodes.

The decision problem is NP-complete even for binary trees. Complexity Results for Bandwidth Minimization. Garey, Graham, Johnson and Knuth, SIAM J. Appl. Math., Vol. 34, No.3, 1978.

What is the best known efficient approximability result for computing minimum bandwidth on binary trees? What is best known conditional hardness of approximation result?


texts: Could program verification techniques prevent bugs of the genre of Heartbleed from occurring?

texts:
On the matter of the Heartbleed bug, Bruce Schneier wrote in his Crypto-Gram of 15th April:
'"Catastrophic" is the right word. On the scale of 1 to 10, this is an 11.' I read several years ago that a kernel of a certain operating system has been rigorously verified with a modern program verification system. Could hence bugs of the genre of Heartbleed be prevented from occurring via application of program verification techniques today or is this yet unrealistic or even principally impossible?


texts: All-to-All Broadcast on a Balanced Binary tree

texts:
Can somebody please suggest some procedure for All-to-All broadcast on a balanced binary tree?

Assume that only the leaves of the tree contain nodes, and that an exchange of two m-word messages between any two nodes connected by bidirectional channels takes time ts + twmk if the communication channel (or a part of it) is shared by k simultaneous messages.

Should I use Scatter technique on it, i.e, All-to-Personalized Communication?


texts: Decomposition of a bipartite graph into complete bipartite graphs by adding the smallest number of edges

texts:
A bipartite graph $G$ and an integer $K$ is given. I want to decompose $G$ into $K$ complete bipartite graphs by adding the smallest number of edges.

Below is an example of decomposition when $K=2$. The red line indicates an added edge.

Is there any good (approximation) algorithms?


texts: Randomize List with guaranteed Index Change

texts:
I usually post on Stackoverflow, but I got stuck with a problem which I think fits better here and I hope someone can help me. The task ist pretty simple:
Shuffle/Randomize an array/list
conditions:

each Index has to change; an Item which was at index 0 before the shuffle has to be at an index != 0 after the shuffle
all possible resulting permutations which satisfy the first condition should be distributed equally

I am unable to find a satisfying solution. Brute force (shuffling the array with Fisher-Yates until first condition is met) obviously works but is not a solution I am looking for. Brute Force with an array with four elements resulted in following number of permutations (which is roughly distributed equally) for one million tries: [111467, 111172, 111497, 111047, 111114, 111053, 110699, 110655, 111296]
Another thing I tried was something like this:

iterate through the array object by object and randomly choose a new index for the object
the randomly chosen index must not have been chosen before and must not be same as the original index
if the last element would fall on its original index, swap the last element with a random other element

Using this approach, the distribution looks really bad: [74166, 110734, 83581, 129486, 83210, 101904, 111305, 111235, 194379].
In theory, there must be a better solution than brute force but unfortunately everybody I asked so far (including google) didn't have a solution, or just had another non uniform solution comparable to my second approach.
Can anyone help me please? I would appreciate it a lot.


texts: Applying Shannon Entropy to data storage

texts: I know Shannon Entropy is defined for messages. When it's said the size of a file stored in a HDD is 1 MB, are we talking about the Shannon Entropy? If so, how do we extend the definition to static information (not flowing like messages)? If not, how come they have the same unit, i.e. bits?


texts: How isolate the last bit work on teory Binary Indexed Trees

texts:
I'm learning about the Binary Indexed Trees, and I understand how it works, but I'm interested in the theory that there is behind!
In particular, I don't understand what is meant the following definition on TopCoder

The algorithms for BIT require extracting the last bit of a number, so we need an efficient way of doing that. Let num be an integer. We will now show how to isolate the last bit of num. In binary notation num can be represented as a1b, where a represents binary digits before the last bit and b represents zeroes after the last bit.

My first question what is mean a1b?
In addition, I don't understand what is mean this definition

Integer -num is equal to (a1b)¯ + 1 = a¯0b¯ + 1. b consists of all zeroes, so b¯ consists of all ones. Finally we have

-num = (a1b)¯ + 1 = a¯0b¯ + 1 = a¯0(0…0)¯ + 1 = ¯0(1…1) + 1 = a¯1(0…0) = a¯1b.

Someone can help me?


texts: Can a 2-way set associative mapping have just one set?

texts:
Though unintuitive, can a 2-way set associative mapping have only one set. For e.g., Cache size 8 bytes, block size 4 bytes and main memory size as 16 bytes. Here the number of cache lines are 2 and given 2 way set associative the set count is only 1. Can I map the 4 blocks (0,1,2 and 3) in the main memory to a 2-way set associative mapping?

If I can, what would be the set index? Since the set size is 1 = 20. is set index always 0. [in CPU OS simulator, it is not throwing any error when I try to set the cache and block size and mapping as 2-way]


texts:
Is next time complexity sub-exponential?

$O(2^{N^{LOG2(1.5)}}/8)$

unformatted: O((2^N)^LOG2(1.5))/8) just in case I didn't format it properly.


texts: Incomputable sets of low degree vs Rices theorem?

texts:
I have heard that there are sets that are not computable, but are lower in degree than the halting problem.
How does this not contradict Rice's theorem? Are there any concrete examples of such sets?


texts:
I'm trying to understand what a compiler intrinsic function is. I did find a wiki article but I'm still kind of fuzzy on what it is exactly. If someone could provide a few concrete examples that would definitely clarify the issue.

Any help is appreciated.


texts:
I have been confusing a bit about these relationship:

Given A polynomial reducible to B

1/ If A is NP hard, what is the hardness of B?

2/ If B is NP hard, what is the hardness of A?

3/ If A has polynomial algorithm, how is B?

4/ If B has polynomial algorithm, how is A?

Since "B is as hard as A", then for 1/, we can say B is also NP Hard. However, I'm not sure about the reverse order. In 2/, there is not enough evidence to conclude the hardness of A

Also, for 4/ If B has poly algorithm, then A also has a poly algorithm. I'm thinking 3/ is also similar, since A is reducible to B and B as hard as A, if A has poly algorithm so does B.

Can someone please verify this? Thanks very much


texts: Prove with pumping lemma that the language { $a^n b^n b^m a^m | n ≠ m $ } is not context free

texts:
I'm having a trouble proving it to be non-context-free.
For example, if I take w = $a^k b^k b^{k+1} a^{k+1}$, it would be problematic if the partition of $vxy$ with $|v| = |y|$ was in the $ b^{k+1} a^{k+1} $ part as I can't get it to be equal with $k$ or make the amount of $a$s and $b$s different.
We are also allowed to use Ogden's Lemma.


texts:
The Clique problem takes a graph $G = (V,E)$ and an integer $k$ and asks if $G$ contains a clique of size $k$. (A clique is a set of vertices such that every pair of vertices in the set is adjacent.) The Independent-Set problem takes a graph $G’ = (V’,E’)$ and an integer $k’$ and asks if $G’$ contains an independent set of size $k’$. (An independent set is a set of vertices such that no pair of vertices in the set is adjacent.)

Give a polynomial time algorithm that, given a graph $G$ and an integer $k$ produces a graph $G’$ and an integer $k’$ such that $G$ has a clique of size $k$ if and only if $G’$ has an independent set of size $k’$. Justify your answer.
Use 1. to prove that the Independent-Set problem is NP-Complete given that the Clique problem is NP-Complete.


texts:
Please help me to prove:

If $f, g ∶ \mathbb{N} \rightarrow \mathbb{N}$ and $f$ and $g$ are increasing $(f(n+1)>f(n),g(n+1)>g(n)$).

Need to prove $g=O(f)$ or $f=O(g)$.

Thanks


texts:
I will try to give the motivation behind this problem and later the math formality.
Given a grayscale image (1 Channel - M by N Matrix).
Someone marks some pixels as anchors.
Now, you need to interpolate the other pixels (Which are not anchors) by minimizing a given cost function s.t. the end result is an image which has the original image values at the anchors and interpolated values else were s.t. it minimizes the cost function.

Given an $M$ by $N$ matrix (A 1 channel image for that matter) $ I $.

Subset of the elements (Pixels) in the matrix are marked as reference and their location is a group marked as $ S $.

The optimization cost function is given by:

$$ \sum_{\mathbf{r}} \left( E(\mathbf{r}) - \sum_{\mathbf{s} \in N(\mathbf{r})} {w}_{\mathbf{rs}} E(\mathbf{s}) \right)^2, \text{ s.t. }  \forall p \in S \; E(\mathbf{p}) = I(\mathbf{p})\,, $$

where a bold letter $ \mathbf{p}, \mathbf{r}, \mathbf{s} $ means an element (Pixel) location.

The group $ N(r) $ is the neighborhood of $ \mathbf{r} $, which is size $ k $ namely, a $ k  $ by $ k $ rectangle where $ \mathbf{r} $ is in the middle.

The weights $ {w}_{\mathbf{rs}} $ are defined as following:

$$ {w}_{\mathbf{rs}} \propto \exp\left(-\frac{(I(\mathbf{r}) - I(\mathbf{s}))^2}{2\sigma^2_r} \right )\ \ \text{ s.t. } \sum_{\mathbf{s} \in N(\mathbf{r})} w_{\mathbf{rs}} = 1\,. $$

Namely, the weights are normalized to 1 within the neighborhood. The variance is calculated on the matrix $ I $ in the neighborhood (You can assume it is given).

So the problem is to find a matrix $ E $ which is equal to $ I $ on all reference points and interpolates other places by bringing the cost function to minimum.

It looks like a weighted least squares per neighborhood (The inner brackets).

I couldn't formalize it (For the whole matrix) a way that can be easily calculated and solved in e.g. MATLAB.
Is there a way to formalize it as classic Weighted LS problem?
Or any other form which using the classic tools will bring solution (Get the interpolated matrix)?

Could any one help with that?

P.S.
I tried using the Weighted LS per neighborhood disregarding the rest didn't yield the expected results (Obviously).
Tried it just to see how far the real solution is from this naive solution.


texts: What is the Curry-Howard analogue for linear logics?

texts:
As defined by Wikipedia,

  (The Curry-Howard correspondence) is a generalization of a syntactic analogy between systems of formal logic and computational calculi that was first discovered by the American mathematician Haskell Curry and logician William Alvin Howard.

Related to it is the λ-cube, which is a graphical representation of the possible axes of refinement from simple types to the calculus of constructions, which has a logical interpretation:

As far as I know, the Curry-Howard correspondence is a connection between type theory and classical logics. My question is: is there any analogue correspondence between type systems and linear logics?


texts: Understanding the notation and concept behind March Tests

texts:
Some background on my question:

I have done some research into March Tests that are essentially access patterns for DRAM.

One example of these march tests in the MATS+ algorithm shown below with (I think) O(n) complexity:

MATS+: {⇕ (w0); ⇑(r0, w1); ⇓(r1)}

Steps for algorithm:

1) Write a 0 in either up or down addressing order.

2) Read a 0 and Write a 1 in up addressing order.

3) Read a 1 in down addressing order.

My Question:

My question is concerned with step 1) which is represented as ⇕ (w0) in my notation. If this step can be either up or down addressing order, what determines the direction of the addressing order? Does it simply mean two variants can exist for this algorithm that start with up addressing and down addressing order? Thanks in advance for any light shed on this.

I am also not clear on what is actual meant by up addressing and down addressing order. Is it the traversal direction of the DRAM cell or the memory?


texts: Given $m$ operations of coloring. What is color of $i$-th ball ?

texts:
There are given $n$ balls. Their indexes: $\{1,...,n\}$.
Initially all of them are painted in $green$. (other possible color in my problem is $red$).
It is possible to paint interval of balls in color $red$ or $green$, for example $paint([a,b], green)$ - ball in given interval will be paint in green.

What's more, there are given $m\ge n$ operations of painting. After executing all $m$ painting our task is answer to question: What is color of ball $i$, where $i\in \{1,...,n\}$.

I can solve it by simple simulation coloring - I use BST interval tree. Hence, I get $O(m\lg n)$.

I am think about faster solution. It is my problem, indeed. It is easy to see that good idea is process operations in reverse order (from $m$ to $1$).  Have you any idea ?


texts: Efficient algorithm for factorizing symbolic sum of products

texts:
Given a sum of flat symbolic products like $axc + byc + ayc + bxc$, how can I efficiently factorize it as a product of sums like $(a+x)(b+y)c$? For my problem, the products are not commutative -- it's more like a sum-of-tuples becoming a tuple-of-sums.
What have I tried:
So far, I have this Prolog program (run in Swish). It is not able to handle a case with more than two terms in a sum, tough.
% factor(Sum, Product)
% Common factor (from left or right).
factor(T*X+T*Y, T*F) :-
  factor(X+Y, F).
factor(X*T+Y*T, F*T) :-
  factor(X+Y, F).

% No common factor (from left or right), recurse into sub-expressions
factor(T1*X+T2*Y, (T1*A+T2*B)*C) :-
  factor(X, A*C),
  factor(Y, B*C).
factor(X*T1+Y*T2, C*(A*T1+B*T2)) :-
  factor(X, C*A),
  factor(Y, C*B).

% Base case, no factorization.
factor(T, T).

I've also tried an imperative implementation that firsts sorts the terms, then factor pairs that have a single different term. It does n passes on the list of products, where n is the maximum size of the product:
Pass #1:
a*x*c + a*y*c + b*x*c + b*y*c
 \        /
 a*(x+y)*c

 a*(x+y)*c + b*x*c + b*y*c
      \       /
     differ by more
    than one element

 a*(x+y)*c + b*x*c + b*y*c
                \      /
               b*(x+y)*c

 Pass #2:
 a*(x+y)*c + b*(x+y)*c
     \           /
     (a+b)*(x+y)*c

This implementation, on the other hand, can't factorize terms that have just one term in common, like a*x*c + b*y*c = (a*x+b*y)*c. The full code can be run in this Repl.it; please let me know if it should be in the body of the question.
Context: I'm implementing a static type analyser that derives the concrete types of a generic function from its calls. So, a function a -> b -> Bool that is called with Int -> Int -> Bool and Str -> Str -> Bool would have type (Int -> Int)|(Str -> Str) -> Bool.


texts: Can I use the following method to prove an algorithm is correct?

texts:
I'm trying to show that a solution I have obtained via an algorithm is correct. The way I plan on doing this is first by showing that an optimal solution does indeed exist. Then, I plan on showing that every other solution that is not the solution provided by my algorithm cannot be optimal. Finally, I show that the solution I have cannot be improved in the same way as any other solution.

Is this enough to show that my algorithm is optimal? In this case I am avoiding doing an "exchange argument" a la greedy algorithms. In fact, I don't really prove anything about how my solution is an improvement of the other ones, but simply that all of the other ones can be improved, and given that an optimal solution exists, the one I have must be it because it cannot be improved in the same way that the other ones can.


texts: Over the alphabet {a,b,c,d}, how would i construct a NFA that only accepts strings that end with a letter that is already part of the string?

texts:
I've been trying to create a NFA that accepts strings that end with a letter that exists in the string. For example abcdb, cbdd, acac etc. while strings like abc aacd etc are not accepted since the last letter wasnt in the string before the last letter was read. I only seem to be able to create a NFA that accepts a subset of the language. What is the right way to go about it? I'm very lost.

This is my try at a 2 letter alphabet but i feel like for a 4 letter alphabet the NFA is going to be huge. Is there a methodology I'm completely missing or do I just use brute force?


texts: Is it possible to implement dependent types by any object oriented language supporting inheritance and classes?

texts: When I was reading Agda tutorial, I noticed resemblance between dependent type declarations and class definitions which I've been primarily used to work with. I'm not totally sure how much sense this questions makes, but what is the real practical difference between types and classes? Could we very well use object oriented approach to define types, and thus construct proofing system similar to Agda by any language supporting class and object construction?


texts:
I was reading CFG's and PDA's. I need to understand one basic point in that.I have solved some questions on final state acceptance by PDA.But in every answer,the string always end with epsilon(means that there is always a transition when string ends which by reading epsilon takes to final state and mostly it invloves checking that current stack TOP is same as initial symbol).

Do we assume that there is some end of string marker in PDA?I have not seen such thing in DFA/NFA.If the string ends,then there is no need to read epsillon in that,but what is the requirement for this in PDA?Or does this depends on the problem in context?


texts: If $R,F \cap R, F \cap \overline{R}$ are regular, is $F$ regular?

texts:
Let $R \in REG$. Is it true that if $F\cap R \in REG$ and
$F \cap \overline{R} \in REG$ then $F \in REG$?

I took $R = \Sigma^{\ast}$ and because $F\cap R \in REG$, $F$ must be regular. Is this the right approach?


texts:
Here's the problem: I have some $n$ ordered containers, each with $m$ slots. I have $p$ temporary slots that I can use to move items between containers. Sorting within containers is not costly, however moving items between containers is, so the more temporary slots that can be used to move items between containers, the better.
More succinctly:

There are $n$ containers with $m$ indices.
There is an always-accessible container with $p$ indices.
The $p$-container starts empty.
Only one $n$-container can be opened at a time.
Switching which $n$-container is opened is costly, and should be minimized.
Swapping items between the opened $n$-container and the $p$-container has the same cost as any normal swap. I.e. there is no additional cost for swapping items between the temporary container and the opened container.

Take this in the case of sorting Minecraft chests: this gives $m=p=27$. You can only open one chest at a time, but you can move items however you want between that chest and your inventory.
I want to sort my chests so that it's easier to find things. Strategies such as Bubble Sort and Selection Sort could work, but they would take a long time as they wouldn't take advantage of all 27 temporary spaces. Is there a sorting algorithm that's memorizable and executable by a human to efficiently sort between containers?


texts: Looking for a succinct dynamic sorted dictionary

texts:
I was digging through research articles to find a data structure that solves the dynamic sorted dictionary problem (representing any subset $S$ of a universe $U = \{0, \ldots, u\}$ with member/predecessor/successor queries), but sadly I was able to find none. I did find succinct solutions to the following problems:

Dynamic non-sorted dictionary
Dynamic indexable bitvector (which is no good if the universe, say $[2^{64} - 1]$ is too big to store), not to mention storing a simple set, $\{u\}$ uses up the maximum amount of space
Static indexable dictionaries

Dynamic succinct sorted/indexable dictionaries, however, do not seem to exist. (I do not actually need indexable dictionaries, just sorted ones with predecessor/successor queries, but it looks like this isn't really any easier to solve, either.)

What are some viable succinct data structures for solving this problem? Time bounds are not too important as long as they're not overly large (like $O(|U|)$). If there's no such data structure (yet), what is the second best option? Exponential search trees? Dynamic fusion trees? Multiple underlying data structures based on sparseness? (I prefer data structures with worst-time operation guarantees to those with amortized ones.)


texts: pseudocode to split number value to array of numbers

texts: How to write a pseudocode to split a number value to array of numbers? Let's say the number value is 12345. I need to convert it into [1,2,3,4,5].


texts: An operational semantics for lambda-calculus normal order evaluation strategy

texts:
TAPL book, page 56 reads:

  Under the normal order strategy, the leftmost, outermost redex is
  always reduced first.

I understand this as a restriction of the full beta-reduction evaluation strategy, whose reduction rules are given as follows:

$$\frac{t_1 \to t_1'}{t_1 t_2 \to t_1' t_2}$$

$$\frac{t_2 \to t_2'}{t_1 t_2 \to t_1 t_2'}$$

$$\frac{t_1 \to t_1'}{λx. t_1 \to λx. t_1'}$$

$$\frac{(λx. t_1) t_2}{[x \to t_2] t_1}$$

My question is how to transform these rules so that the normal order strategy condition holds.


texts: Matching of two weighted graphs allowing one-to-many mapping

texts:
I am looking for a heuristic for a graph matching problem as follows.

Given two graphs: $A$ (consisting of nodes $a_i$) and $B$ (consisting of nodes $b_i$). Typically the size of $B$ is larger than that of $A$.

Each node and edge in two graphs has weight. The task is to match graph $A$ to graph $B$, i.e., find a set of nodes and links in $B$ to map each node and link of $A$, such as the host node/link in $B$ has larger weight than the corresponding node/link of $A$.

The following figure illustrates two possible cases (or solution) of mapping (matching):

Case 1: One-to-one mapping: Each node or edge of $A$ needs only one node or link of $B$ to map. Here the nodes $a_1, a_2, a_3$ are mapped on to $b_1, b_2, b_3$, and the edges $a_1a_2, a_2a_3$ are mapped onto $b_1b_2$ and $b_2b_3$ respectively.

Constraints are satisfied: For nodes: $b_1 > a_1$, $b_2 > a_2$, $b_3 > a_3$. For edges: $b_1b_2 > a_1a_2$ and $b_2b_3 > a_2a_3$.

Case 2: One-to-many mapping: One needs more than 1 node/edge of $B$ to host a node/edge of $A$. In the example, $a_1$ is mapped on to $b_1$ and $b_4$, $a_2, a_3$ are mapped onto $b_2, b_3$. For the edges: $a_1a_2$ is mapped onto $b_1b_2$ and $b_4b_2$, and $a_2a_3$ is mapped onto $b_2b_3$.

Constraints are satisfied: For nodes: $b_1 + b_4 = 11 > a_1$, $b_2 > a_2$, $b_3 > a_3$. For edges: $b_1b_2 + b_4b_2 = 8 > a_1a_2$ and $b_2b_3 > a_2a_3$.

Heuristics for Case 1 have been well studied, e.g., using eigendecomposition to solve the Weighted Graph Matching Problem (WGMP). Nevertheless, I could not find an appropriate algorithm to find a solution as in Case 2. Any suggestions?


texts: How is the computational power of a human brain comparing to a turing machine?

texts:
This seems related to these questions at a glance:

What are some problems which are easily solved by human brain but which would take more time computers?

What would show a human mind is/is not reducible to a Turing machine?

But not quite, I am not asking about "time", but power. Also, I am not interested in the turing test. That said, my question can also be expressed as two parts:

Is there a language, which cannot be recognized by any turing machine, that can be recognized by a human?
Is there a language, which cannot be decided by any turing machine, that can be decided by a human?

And vice versa. The "language" I am talking about is the "mathematical" language, not only a "human" or "programming" language:

$$L \subseteq \Sigma^*$$

Since this is a question about computational power, I would make the following assumptions:

Human do not make mistakes
(here I mean mistakes like copying the wrong character or computing arithmetics incorrectly, typical human errors)
There is no space limit (turing machine gets infinite tape, you get infinite medium to write)
There are no time constraints
However, the recognition/decision must be achieved within finite time.
And of course, in finite space

Please give an example if you have an answer. Remember, this is a theoretical question, so practical issues are not in concern.

EDIT 1

OK, as someone pointed out, I will add the following assumptions.

Human is probably not easy to define in precise mathematical words, so let's just assume "you".

About a human recognizing a string in a language, I am talking about performing the same task the turing machine is "programmed" to do. Say, given a string, whether you (a human) can recognize it when it conforms to a set of rules, or decide whether it conforms to a set of rules or not. I am not sure if I can make the point clear enough...

EDIT 2

OK, to clarify, this is a question about model of computation, so yes, like André Souza Lemos mensioned, I am talking about "given a word $w$ and a language $L$, is sentence $w\in L$ decidable". I am not talking about a physical computer.

EDIT 3

OK, this is another idea I came up with. Does model of computation theory include inputs that are volatile by itself? That is, the input changes itself? That is probably not the "language recognition" problem though...


texts:
Say i have cropped an image and have hidden some part of it, like shown below

Is it possible for anyone to download this image and able to decipher what the hidden text is?


texts:
Let $G$ be multipartite directed weighted graph with $k$ independent sets (we will call
them "layers"). We select exactly one node from each layer and form the induced subgraph $H_k$. That is, $H_k$ has exactly $k$ nodes (one from each layer) and contains all edges from $G$ that have both endpoints in $H_k$.

Our goal is to find $H_k$ such that the total weight of all of its edges is minimized:
$$\min_{H_k \subset G}\sum_{e \in H_k} weight(e)$$

(you can assume that the graph is connected, so a solution always exists)

Case #1: Graph is flat

To better illustrate the problem I will give some examples. Consider a
special case where all edges in $G$ are from layer $i$ to layer $i+1$:

This problem can be easily solved, by adding 2 new nodes entry and exit
to $G$. Then we add edges with $0$ weight from entry to every node in layer #1 and from every node in layer #$k$ to exit. Finally the solution to our problem is the shortest path from entry to exit.

In our example, the minimum weight 4-induced subgraph will be:
$A_3, B_1, C_1, D_1$, with total weight $20$.

Case #2: Graph has backward edges

In this case, we allow a layer to have backward edges; that is, a layer $i$ can have edges to any layer $j$ as long as $i \ne j$. For instance, consider
the graph from the previous example, but this time add some backward edges
(with blue color):

Unfortunately, the previous approach does not work anymore, as the previous
approach will give us the same solution $A_3, B_1, C_1, D_1$ with a total
weight of $70$, but the minimum subgraph is $A_3, B_2, C_1, D_2$ with total
weight $34$

Case #3: Re-define the problem

Clearly, the introduction of "layers" can make the analysis hard. So, we can
redefine the problem without requiring $G$ to be multipartite.
That is, instead of having layers,
we add an edge with $\infty$ weight between every pair on the same layer. Then
the minimum weight k-induced subgraph $H_k$, cannot have two nodes from the
same layer, as this would imply that $H_k$ contains an edge with $\infty$ weight.
Back in our example, the previous graph becomes:

The case #3 is NP-hard

Unfortunately in the general case this problem is NP-hard (because it is an optimization problem), as there is a reduction from k-clique:

Let $R$ be an undirected unweighted graph that we want to check whether it has a $k$-clique. That is, we want to check whether $clique(R,k)$ is True or
not. Thus, we create a new directed graph $R\space'$ as follows:

$R\space'$ contains all the nodes from $R$
$\forall$ edge $(u,v)\in R$, we add the edges $(u,v)$ and $(v,u)$ in
$R\space'$ with $weight = 1$
$\forall$ edge $(u,v)\notin R$, we add the edges $(u,v)$ and $(v,u)$ in
$R\space'$ with $weight = \infty$

Then we find the minimum weight k-induced subgraph $H_k$ in $R'$. It is true that:

$$\sum_{e \in H_k} weight(e) < \infty \Leftrightarrow clique(R,k) = True$$
$:\Rightarrow$
If the total edge weight of $H_k$ is not $\infty$, this implies that for every
pair of nodes in $H_k$, there is an edge with weight $1$ in $R\space'$ and thus
an edge in $R$. This by definition means that the nodes of  $H_k$ form a k-clique
in $R$.
Otherwise (the total edge weight of $H_k$ is $\infty$) it means that it does not
exist a set of $k$ nodes in $R\space'$ that has all edge weights $< \infty$.

$:\Leftarrow$
If $R$ has a k-clique, then there will be a set of $k$ nodes that are fully connected. This set of nodes will have no edge with $\infty$ weight in
$R\space'$. Thus, these nodes will form an induced subgraph of $R\space'$
and the total weight will be smaller than $\infty$.

(proof is not formal; I just describe the general idea)

The Question

Although the problem that I described is NP-hard (assuming that my analysis
is correct), I want to find an approximation algorithm (along with a proof) that
can give me a solution that is at most $n$ times worse than optimal (obviously
we want $n$ to be as small as possible).

There is also a paper that solves a similar problem, but I don not know
if that helps.


texts: What are the practical use of weak semaphores?

texts:
Weak semaphores are often defined as

  if a process (or thread), say p1, performs a V operation and some
  other process is waiting on that semaphore, then the first process
  (i.e. p1) is not allowed to immediately perform another P operation on
  that semaphore. Instead, one of the waiting processes must be given
  its turn.

Further, while a single weak-semaphore cannot guarantee starvation-freedom, using few of them can actually guarantee starvation-freedom.
Can anyone mention any practical use of such weak-semaphores!

ǂThe quoted section is from the paper "An Efficient Solution to the Mutual Exclusion Problem Using Weak Semaphores" by S. A. Friedberg and G. L. Peterson, with a bit of embellishment


texts: Knowledge Vault - Please explain the local closed world assumption

texts:
Background

I'm currently reading a paper on the google knowledge vault here : http://www.cs.cmu.edu/~nlao/publication/2014.kdd.pdf.

I'm having trouble with the Local Closed World Assumption (LCWA).

My understanding of LCWA in layman's terms :

a) If a candidate triple has the same value as contained in its knowledge base then it's labelled as true.
b) If a candidate triple has a different value than contained in the knowledge base, it is labelled as false.
c) If the subject and predicate are not in the knowledge base, the triple is thrown out from the test and training set.

Problem with my understanding

In Section 3.1, LCWA is used to create a labelled training set for text extractors. According to my understanding of LCWA,triples with new predicates or subjects would fall into c) and would not be used to create and train extractors.

Question

Is my understanding of LCWA correct?
If so how are new facts extracted if c) causes those triples to be thrown out?

Explanation from section 2.2 of the paper

Explanation of LCWA:

  Define O(s, p) as the set
  of existing object values for a given s and p. This set will
  be a singleton for functional (single-valued) predicates such
  as place of birth, but can have multiple values for general
  relations, such as children; of course, the set can also be
  empty. Now, given a candidate triple (s, p, o), we assign
  its label as follows: if (s, p, o) ∈ O(s, p), we say the triple
  is correct; if (s, p, o) 6∈ O(s, p), but |O(s, p)| > 0, we say
  the triple is incorrect (because we assume the KB is locally
  complete for this subject-predicate pair); if O(s, p) is empty,
  we do not label the triple, and we throw it out of our training
  / test set.


texts:
I tried to solve if a grammar is ambiguous or not.
I know that I have to find a word that can be generate by two different leftmost derivations.
Is there any algorithm to find a word that, if the grammar is ambiguous, can be generated by two different trees?
This question is different.


texts: Acquiring the necessary background for research

texts: I'm starting my mater's thesis in computer science. I'm interested in computational Origami (algorithms mainly); I've read a little about the subject and I'm worried because I lack some of the knowledge that I think is necessary to do research in that area. But still I'd like to start and want to ask: which is better an approach: learn the necessary background as I go and wheneve a necessity pops up or learn it first and then start. I have 4 to 5 months to finish my thesis.


texts: Time Complexity when loop variable depend upon outer loop variable

texts:
What is the time complexity of the following piece of code in worst case?

s=0;
for(i=1;i<=n;++i){

   for(j=1;j<=i*i;j++){

       for(k=1;k<=j and j%i==0;k++)     /*  k<=j  and j%i==0 */
           s++;

   }
}

Each loop depend on the outer loop variable.How to proceed in such case?
Innermost loop will run only sometimes.How to evaluate this case?

For every increment of i middle loop runs for i^2 times and for every iteration of middle loop,I think innermost loop iterates for i times. Middle loop run for j=1 to i^2 and j%i!=0 is in i cases and for other i cases j%i=0. As inner loop run for j%i==0 it would be iterated i times.
Now as innermost loop run for i times,middle loop run for i^2 times and outer loop run for i times , I think complexity would be n^4

For every i of outer loop, innermost loop run for $i(i^2+i)/2$ times.Evaluating a summation over $i(i^2+i)/2$ for i=1 to n will get me a polynomial of degree four. So its complexity should be $O(n^4)$.Am I correct?


texts: In SAT, do we require an assignment for arbitrary variables?

texts:
I am reading about the Satisfiability Problem, in page (5) the author gives the following example :

$(P \lor Q \lor R) \wedge
(\bar{P} \lor Q \lor \bar{R}) \wedge
(P \lor \bar{Q} \lor S) \wedge
(\bar{P} \lor \bar{R} \lor \bar{S})$

A satisfying assignement is $: P,Q,\bar{R},\bar{S}$.

A different assignments is $P,\bar{R}$ to satisfy the four caluses. This means that $Q,S$ can be set arbitrarily to $True$ or $False$.

Do we require an assignment for all variables or we only reqiure to set variables that satisfy the input (i.e. $P,\bar{R}$ discluding $Q,S$) ?

Does that mean that the satisfying assignment of $P,\bar{R}$ is more efficient than $P,Q,\bar{R},\bar{S}$ given that it uses less variables ? Is there any resources to read about it ?

Also, given that $P,\bar{R}$ satisfy the input, does that mean that we can disclude $Q,S$ from the original Boolean Formula ?


texts: Turing machines that return to the same configuration

texts: Last year I took a course on Theory of Computation. One of the questions made a reference to a Turing machine as a "Potato" (the course was root vegetable themed). A Turing machine is a Potato if on any input it either a) halts or b) reaches a configuration that it has already been in. I'm currently a TA for this course now, and none of the former TAs or even the professor know that this type of Turing machine is actually called, or even if there is such a name for one. Can anyone cite any papers that used this type of Turing machine and know what it is called outside the context of this course.


texts:
Consider a valid string with bitwise operations (AND, OR, XOR), and also placeholders $X$, where each $X$ stands for an arbitrary number from $\{0,1\}$. There are $n$ many $X$s, so there are $2^n$ possible sequences. How many out of the
  $2^n$ strings have value $0$? How many have value $1$?

My approach to this problem was, I assumed that the interpretation of strings is done by associating left-to-right (that is, $0 \oplus 1 \land 0$ means $(0 \oplus 1) \land 0$).
I will use $\lor,\land,\oplus$ for OR, AND, XOR.

Let $s$ be an arbitrary string with $n$ many $X$s that evaluates to 0, and let $t$ be an arbitrary string with $n$ many $X$s that evaluates to 1.

Then, the strings with $n+1$ many $X$s that evaluate to $1$ are:
$$ t \lor 0, s \lor 1, t \lor 1, t \land 1, s \oplus 1, t \oplus 0. $$
The ones that evaluate to 0 are:
$$ s\lor 0, s\land 1, s\land 0, t\land 0, s\oplus 0, t\oplus 1. $$

Fixing a sequence of operations, let $S(n)$ be the number of strings with $n$ many $X$s that evaluate to 0 with the given operations, and let $T(n)$ be the number that evaluate to 1.

Denote the $i$'th operation by $O_i$.
Then, just counting the combinations in the previous paragraph for each operator, I get the following recurrence relations:
$$
\begin{align}
&S(1)=T(1)=1 \\
&S(n+1),T(n+1) =
\begin{cases}
S(n), S(n)+2T(n) & \text{if } O_{n+1}=\lor \\
2S(n)+T(n), T(n) & \text{if } O_{n+1}=\land \\
S(n)+T(n), S(n)+T(n) & \text{if } O_{n+1}=\oplus
\end{cases}
\end{align}
$$

  What should I do if my assumption was wrong, that is, if the sequence could contain parentheses, e.g. $(X \lor (X \oplus X))$?


texts: Merging $k$ sorted lists in $O(n\log k)$ time

texts:
This question is based on a solution of Laura Toma to a question from CLRS (#6 on the sheet).

Question: Give an $O(n\lg k)$-time algorithm to merge $k$ sorted lists into one sorted list, where $n$ is the total number of elements in all the input lists. (Hint: use a min-heap for $k$-way merging.)

Solution: The straightforward solution is to pick the smallest of the top elements in each list, repeatedly. This takes $k − 1$ comparisons per element, in total $O(k · n)$.
As the hint suggests, the idea for the “improved” solution is to keep the smallest element from each list in a heap; each element is augmented with the index of the lists where it comes from. We can perform a DeleteMin on the heap to find and delete the smallest element and insert the next element from the corresponding list.
Analysis: It takes $O(k)$ to build the heap; for every element, it takes $O(\lg k)$ to DeleteMin and $O(\lg k)$ to insert the next one from the same list. In total it takes $O(k + n \lg k) = O(n \lg k)$.

So I understand everything that's going on here. I just have one little question about this part:

$$O(k+n\lg k)=O(n\lg k)$$

The solution states:

  It takes $O(k)$ to build the heap; for every element, it takes $O(\lg k)$ to DeleteMin and $O(\lg k)$ to insert the next one from the same list. In total it takes $O(k + n \lg k) = O(n \lg k)$.

So in my head I want to do something like this:

$$O(k+n(2\lg k))=O(k+n\lg k)=O(n\lg k)$$

Is this also correct since there are two instances of $O(n\lg k)$? Is the solution just skipping over that one part assuming it's trivial?


texts: Time complexity of removing a vertex from a graph represented as collection of adjacency lists

texts:
I'm trying to reason about the time complexity of removing a vertex from a graph represented as an adjacency list, which has $n$ vertices and $e$ edges. It is a directed graph, and the list associated to any particular vertex $v_i$ contains the vertices directly reachable from $v_i$ (i.e. the edges with origin $v_i$).
Let's assume that the graph is represented as a hash map, which pairs a certain vertex with its adjacency list, which is a linked list. Iterating over a linked list of $m$ elements has a time complexity of $O(m)$, and deleting a node of the list as one iterates over it has constant complexity $O(1)$.
In order to remove a vertex $v_d$ I would need to:

Remove the pair with key $v_d$ from the hash map (which is $O(1)$).
Iterate over the adjacency lists of the rest of the vertices, removing any occurrence of $v_d$.

The second step would mean iterating over each vertex $v_i$ in the key set of the hash map (~$n$ vertices, after having removed one), and for each vertex $v_i$ iterate over its adjacency list, which is of length $e_i$.
Now, it is clear that $\displaystyle\sum_{i=1}^{n} e_i = e$, so my first thought is that the time complexity of the second step is $O(e)$, and so is the total cost of removing a vertex in this situation. Note how this is independent of the number of vertices in the graph.
However, I'm thinking about the case in which there are no edges at all. In that case, step two still requires iterating over the whole list of vertices, so I'm lead to believe that the number of vertices has to play some role inthe time complexity of the method.
What is the actual time complexity in this set up and how can you reconcile the two (apparently contradictory) conclusions I've reached?


texts: Showing Regular Languages are closed under removal of rightmost character

texts:
"Show that if L is a regular language without the empty string, then the language in which the rightmost symbol of every string in is removed is also regular."

I tried going by closure properties of regular languages but got nowhere.. I said L' = {x| y is in L and xa = y, for some a in the alphabet} and didn't really know where to go from there... I also tried to argue that since L is a regular language, it can be expressed by some regex..and I wanted to show by cases that we can form a new regex by omitting the last unit of regex? But that seemed flawed. I also tried creating a skeleton dfa for L and just changing the set of accepting states to the states that transition into the previous final states.. I feel like there is a gap in my knowledge and would really appreciate it if someone could not only help me figure out the solution but also give me some advice on how to approach such problems and fill the gaps in my knowledge!


texts: Are there decidable non-trivial properties of a LBA's accepted language?

texts:
The halting problem and therefore the acceptance problem are decidable for LBAs, but are the infinite extensions of these problems decidable?
Given a LBA, can you decide whether there exists an input on which the LBA halts?
Given a LBA, can you decide whether the LBA accepts a certain non-empty, non-finite language?


texts: Checking whether all integers appear exactly once

texts:
Let $\texttt{a[]}$ be a finite array. We want to check whether every number between $\texttt {min(a[])}$ and $\texttt {max(a[])}$ appears exactly once.

An obvious solution is sorting the array in time $O(n\log(n))$ and go through the sorted array in linear time and check that $\texttt{a[k+1] == a[k]+1}$ for $0\leq\texttt{k} < \texttt{length(a)-1}$.

The total complexity of this would be again $O(n\log(n))$. Is there a better way to do this?


texts: Multi-processing cpu utilization estimate

texts:
I find a formula on my book to estimate cpu utilization under multi-processing.

$ U = 1 - P^n $

U: cpu utilization
P: cpu idle

I want to know why or how to proof.

Edit:

The book is about operating system, not in english.

This may be like https://stackoverflow.com/questions/20328619/calculate-cpu-utilization/20328695?noredirect=1#comment88673153_20328695

I get an answer that is

  it's just basic probability theory


texts: Find the index of minimum number that is greater than key given of a sorted array, does these two functions return same result?

texts:
Give an array of integer has been sorted (non-decreasing order), we need find the index of minimum number number that is greater than key given, I wrote two functions, they're identical except the return lines.

int minimum_index_greater(int *a, int lo, int hi, int key) {
    int left = lo - 1;
    int right = hi + 1;

    while (left + 1 < right) {
        int mid = (left + right) / 2;

        if (a[mid] > key) right = mid;
        else              left = mid;
    }

    return right;    -------> function 1
    return left + 1; -------> function 2
}

The first question is any of them is correct (return the right value) ?

The second question is, I suppose two functions are the same in this situation, they return the same value in every case. And I pretty sure about that.  Am i right or not ? please explain.

P/S : When I solve a problem on Sphere Online Judge. I need to find this value and solve the problem, use function 1, I got 97.72/100 point (which I have no idea why isn't it 100), use function 2, I only got 94.44. So I guess the problem is here


texts: Hausdorff distance between two binary images according to distance maps

texts:
I want to compute the Hausdorff distance between two (very large) binary images X and Y, which is:

$$H(X,Y) = \max\left\{\,h(X,Y), h(Y,X)\right\}\!$$

with

$$h(X,Y) = \sup_{x \in X} \inf_{y \in Y} d(x,y)$$

$d$ being the euclidean distance (or any kind of distance, as it doesn't matter).

The naive algorithm for $h$, comparing each pixel of $X$ to each pixel of $Y$, leading to a complexity of $O(X*Y)$, is way too slow.

I have read many papers saying it is possible to compute the Hausdorff distance in $O(X+Y)$ by first calculating the distance map (distance transform) of $X$ and $Y$.

I can easily compute these distance maps, but I don't see how they can lead to the Hausdorff distance, and I did not manage to find the algorithm in any of these papers.

So the question is, does anyone know how to compute the Hausdorff distance of two images according to their distance map ?


texts: Total Number of Bits Needed to Represent a List of N elements

texts:
This is an excerpt from the algorithms textbook How to Think About Algorithms by Jeff Edmonds (This book is a gem by the way).

I get his conclusion about Merge/Quick/Heap sorts having $O(NlogN)$ operations with respect to $N$, the number of elements in the input list, and at the same time they are linear in the context that they need $O(n)$ opertaions with respect to the number of bits needed to represent the input list. Different models of computation and a good way to describe one algorithm under different models.

But my question is in the line

  Assuming that the $N$ numbers to be sorted are distinct, each needs $logN$ bits to be represented, for a total of $n = \Theta(NlogN)$ bits.

My understanding of this was that with $N$ distinct numbers, we need word size $w = \theta(logN)$, as defined in CLRS. We want the word size to be able to at least index into $N$ different elements but not so big that we can put everything in one word. Also, with $N$ distinct elements, we need $\Omega(logN)$ bits to represent the largest number. Assuming each word will fit in $w$, Edmonds' claim that $n = \theta(NlogN)$ bits made sense. Please correct me if my analysis is wrong up to here.

But when I try to apply this to counting sort, something doesn't seem right. With $N$ again the number of elements in the input and $k$ the value of the maximum element in the list, the running time is $O(N + k)$. Counting sort is linear with respect to $N$, the number of elements in the input, when $k = O(N)$. Using this constraint to represent the input as the total number of bits $n$, I think $n = O(Nlogk) = O(NlogN)$.

So with in the RAM model of computation, how can I express the run-time of counting sort with respect to $n$ bits? Merge/quick/heap sorts had time complexity $O(n)$ with respect to $n$ bits, as was expressed cleanly by Edmonds. I am not sure how to do something similar for counting sort, and maybe possibly for radix sort using counting sort as a subroutine. Any idea how to do this in the two cases when $k = \Theta(N)$ and when this condition is not present? I am suspecting the former will give some kind of polynomial time with respect to $n$ and the latter exponential (hence pseudo-polynomial) time with respect to $n$ bits, but have trouble expressing the mathematics...


texts: Why is it so difficult to eliminate dead loops?

texts:
I recently came across an issue where my compiler was not able to eliminate some "obviously" dead code - it was a function that returned nothing, with no side effects, and a cursory analysis of the code revealed that it would obviously terminate.

Investigating this further, I found it was extremely easy to write very short programs for which basically every major compiler will emit a bunch of dead code. (Side note - it's worse when using a C++ compiler - AFAIU 'forward progress' is guaranteed so even infinite loops should be able to be removed!)

// when m <= 0 this will never enter the loop, so will terminate
// when n >= m, j will be incremented each time through the loop until
// j == m, so the loop will terminate
void naught(int n, int m) {
    int i = 0, j = 0;
    while(j < m) {
        if (i < n) {
            i++;
            j++;
        }
    }
}

// each two loop iterations the value of i gets incremented by 3, and
// then decremented by 1. eventually it will be greater than or equal
// to the value of n and so the loop will terminate. We can ignore
// overflow since it is undefined; a language with unbounded integer
// types would also terminate.
void zip(int n) {
    int i=0;
    while (i < n) {
        if (i % 2 == 0)
            i += 3;
        else
            i--;
    }
}

// each time through the loop the value of i is increased; so it will
// terminate. same comments about undefined behaviour / unbounded types
// apply here
void nothing(int n) {
    int i=2;
    while (i < n) {
        i *= i;
    }
}

// on the first iteration through the loop i becomes equal to n + 1,
// so it will terminate. ditto on undef / unbounded
void zilch(int n) {
    int i=0;
    while (i < n) {
        i += (n / (i + 1)) + 1;
    }
}

// if i <= 0 we never enter the loop. otherwise, on the first iteration,
// i gets divided by i + 1 which equals zero from rounding.
// ditto on undef / unbounded
void nada(int n) {
    int i=n;
    while (i > 0) {
        i /= i + 1;
    }
}

Is there some fundamental reason that compilers fail in these simple cases? This lack of optimization does not seem to be compiler-specific, or language specific, so I thought it might be because of lack of research (hence posting here). Has there been much research in this area? When a compiler sees the snippets above, what are the obstacles in its way that prevent it from removing the code?

To my human brain, the "obvious" thing to do would be to work out where the loops terminate and where not, and replace the entire thing with a simple if statement. If optimizing for C++, I would immediately remove all the loops since forward progress is guaranteed. Why can't the compiler do the same?

Edit:

Maybe I should have been more clear in my question; I am aware that the problem is undecidable in general, but to me these seem like relatively "easy" examples (especially in a C++ compiler, where AFAIU they should all be able to be removed). Optimization in general is an undecidable problem but it has not stopped optimizers from being written. I am interested whether there has been any research in this area.


texts: An efficient algorithm to find a shortest cycle including a specific vertex

texts:
We wish to find shortest cycle (if any cycle exists) that includes a special vertex $v$.

We know if we run DFS on an undirected graph, back edges show us that there exists at least one cycle.

This answer on SO explains why neither BFS or DFS work. However, I still think that DFS could be helpful in finding a minimun such cycle. Is there a way to make it work?


texts: Was there a phase in Machine Learning timeline when researchers thought some Neural Networks could not be trained?

texts:
I was talking to a professor who made a comment to my question.

  Me: So much of quality literature around this topic ( IP Protection
  for Neural Weights) emanated in 1990-1991, I'm truly at loss to
  understand what went wrong. Why did everyone suddenly stop worrying
  about this topic?

  Prof: I think AI was starved of training data and what training data
  there was demonstrated that, depending on the architecture of the
  Neural Network ("NN"), there would be some NN's that could not be
  trained. They would essentially oscillate and never reach equilibrium.
  That is where the "Deep Learning" approach solved the problem -- and
  allowed AI/NN to move forward.

Fascinating. I looked up and indeed Deep Learning pushed forward in 2000 after it was introduced for Artificial Neural Networks by Igor Aizenberg and colleagues in 2000.

I want to collect research papers/ opinions around this point. Was AI/NN really bottlenecked until 2000 (Advent of Deep Learning)? What spurred the exponential growth in this domain?


texts: Does Google's PageRank count as a sorting algorithm?

texts: Is it correct to assume that PageRank is a sorting algorithm or does it fall in any other category?


texts:
In A simplified NP-complete MAXSAT problem, a reduction is given from Min Vertex Cover to MAX-2SAT by replacing each each vertex $x_i$ by a single-variable clause, and each edge by a two-variable clause:

\begin{align}
 \Phi = \left(\bigwedge_{i=1}^n x_i\right) \wedge \left(\bigwedge_{\lbrace i,j\rbrace \in E} (\overline{x}_i \vee \overline{x}_j)\right)
\end{align}

This basically makes sense to me, because the QUBO version of Vertex Cover is to maximize:
\begin{align}
L = \sum_{i=1}^N x_i -  \sum_{\lbrace i,j\rbrace \in E} x_ix_i
\end{align}
and QUBO can be converted to MAX-2SAT quite simply.

However, I would to know how the reverse transformation works.

How do you go from MAX-2SAT to Vertex Cover?

I don't actually know if this is an unsolved problem or not, but I figure it shouldn't be since they are both NP-Complete. Would it be as simple/tedious as trying to force an arbitrary MAX-2SAT instance into the same form as $\Phi$? I don't know if that can be done though.


texts: UML Use Case: How do we visualize Exception? (e.g.: Withdraw limit)

texts:
I want to learn UML. First Use-case diagrams.
Now I have a situation for an ATM with withdraw limit of 10k and I don't know how to implement this in my diagram.
I have found this definition for extends arrows
Extends     A different use case handles exceptions from the basic use case. The arrow points from the extended to the basic use case.
Is the extends I have used the correct way to implement such exceptions as limits?
My try for this is the seen diagram.


texts: Matrix Representation for logical gates?

texts:
I have been trying to find if there are other matrix type representations logical circuits, in the example below, $$\begin{bmatrix} 1 & 0\\ 1 & 1\\ \end{bmatrix} \equiv \, \, \Rightarrow$$ where:

$$ \begin{bmatrix} X, \  \neg X  \end{bmatrix}\begin{bmatrix} 1 & 0\\ 1 & 1\\ \end{bmatrix} \begin{bmatrix} Y \\ \neg Y \\ \end{bmatrix} = \begin{bmatrix} X \oplus \neg X, \ 0 \oplus \neg X \end{bmatrix} \begin{bmatrix} Y \\ \neg Y \\ \end{bmatrix} = \begin{bmatrix} 1, \ \neg X \end{bmatrix} \begin{bmatrix} Y \\ \neg Y \\ \end{bmatrix}$$ $$ = Y \oplus (\neg X \neg Y) = X \Rightarrow Y$$

Note that the juxtaposition of two variables without an operator corresponds to conjunction i.e. $XY = X \wedge Y$ and of course $1 \wedge X = X$ and $0 \wedge X = 0$ and are written accordingly. Actually all of the propositional logical operators can be done with a unique binary $2 \times 2$ matrix - it is fascinating.


texts:
The exercises in a textbook I studied asks about the best case for Shell sort. I have scribbled a derivation for the same along the margins almost two years ago. Basically I don't know if this was my own derivation or one copied from an authoritative source.

I have elaborated upon the same below. Could you let me know if the reasoning is right here?

The least number of comparisons occur when the data is completely sorted.
For a particular value of the increment, say, $h_i$, each of the $h_i$ sub-sequences require at most one less comparison than the number of elements in the sub-sequence(as insertion sort is used) which is,${N \over h_i} - 1$ ,where N is the total number of data items.
For the given data in this situation $h_i \times \left (N \over h_i - 1 \right ) = N - h_i$ number of comparisons are needed as there are $h_i$ sub-sequences.
If the increment sequence selected is has $k$ increments(such that $h_k = 1$), the total number of comparisons required would be $C(N) \ge (N - h_i) + (N - h_2) + ... + (N - h_k) = kN - \sum h_i = O(N)$


texts: Do online quantile estimation algorithms that support deletions exist?

texts:
There are several online quantile estimation algorithms, but I haven't seen any that supports deletions (i.e. unobserve elements observed in the past). Are there any such known algorithms?

To motivate my question: I'd like to maintain some quantile estimation data structure from the start of time (t0) and take a snapshot of it at t1 and t2. Given the two snapshots, I want to estimate the quantiles for the values observed in [t1,t2] by subtracting the snapshot taking at t1, from the snapshot taken at t2 (i.e. delete all observations in the interval [t0,t1]).


texts: Membership problem for context sensitive languages PSPACE-complete

texts:
I have read that the membership problem for CSL is PSPACE-complete but I couldn't find the proof anywhere. So I tried it myself.

Let's mark the membership problem for CSL as MEM.
First I have to proof that $ MEM \in PSPACE $.
This should be easy, just take Turing Machine that generate words from L in lexicographic order and check if any is the same as the input word w. We can stop with the Turing machine when we reach length w+1.

Seccond, make a reduction from some PSPACE language. Quantified Boolean formula problem (QBF) seems to be suitable for this reduction. I have seen how to make a reduction from MEM to QBF but here I need the opposite. If I had a word w, I could make a formula based on the configuration I must go through to get w and all those configurations would mean true for the QBF. The representation could be just going from the binary code to some formulas.

But when going from the opposite direction, I don't know how to make CSL work from any given formula.


texts:
The syntax STLC is usually written:

$e ::= x |\lambda x : \tau . e|(e \space e)|c$

However, the application rule appears to accept all expressions on the left hand side. Shouldn't the application rule be written:

$(\lambda x : \tau . e \space e : \tau)$ ?

The only time an application makes sense both intuitively and type-wise is by reducing and abstraction by replacing its variable with an expression. All other cases would be:

$(x \space e)$ makes no sense. By the time application can take place x will be substituted with its bound expression. By this logic it will be either an abstraction, as labeled okay above or something else, discussed below

$(c \space e)$ again, you can't apply to a value.

$((e \space e) \space e)$ this is not an issue because applications resolve to an expression, and following that recursive logic it will resolve to one of the aforementioned cases.


texts: Attribute Selection for minimum number of clusters

texts:
I have a table consisting of some headers $P, Q, R, S$ (shown in blue in Table 1). According to the headers, the column $T$ is populated using some predefined logic.

Now, any of the headers $P,Q,R,S$ may be wildcarded to match all values.
The aim to to compress the table using wildcards so that column $T$ is not affected.

As shown in Table 2, Table 3 and Table 4, choosing a combination of fields as key (shown in orange) and wildcarding the rest can be used to compress the table.

However, the choice of key (combination of header fields which are not wildcarded) affects the size of the compressed table.

Given a table, my aim is to automatically detect which combination of headers will yield the smallest table size (compressed) while not affecting column $T$.

So this problem can be split in two parts :
 1. Given that you have to have $k$ header fields in the key, what combination will yield smallest table size?
 2. What would be the optimal value of $k$?

Note: If case of conflict arising in column $T$ from using wildcards, a non-wildcarded row must be placed above it. (E.g. see Table 4, rows 3 and 4)

So what are some good approaches towards solving this problem? Other than iterating over all combinations and choosing the best? Any help in this regard is appreciated.


texts:
I'm having trouble finding materials on what 'finger search' is, in the context of a red black tree.

Even Wikipedia has a very short page about that, could you refer me or explain what kind of search is that.


texts:
If any problem P is NP complete then if there is a polynomial time reduction of P to another problem R then what can we say about R.Is it NP-hard or NP complete ?
From Theory of computation of Hopcroft,Ullman theorem 10.4 it says it would be NP complete but there some times when i see that it is NP-Hard in some other reference . is there any condition when it is NP Hard or NP Complete .Or i misunderstood the theorem .


texts: Recover a matrix with minimum number of queries

texts: Alice has a matrix $A \in \{0,1\}^{n \times m}$ such that the sum of each row is $1$. Bob tries to find the indices of the ones (he knows that the sum of each row is $1$). The type of questions Bob can ask Alice is: "Does $\sum a_{i,j} = 0$" for some subset $\{a_{i,j}\}$ of size $n$. How fast (i.e. minimum questions) can Bob recover the ones (even with high probability)?


texts: Are the outcomes of the maximum shifts function fixed regardless of our choice of axiomatic system?

texts:
It is known that there is a $748$-state Turing machine that halts if and only if $\mathsf{ZF}$ is inconsistent. So by Gödel's second incompleteness, $\mathsf{ZF}$ cannot find what $S(748)$ exactly is, where $S$ is the maximum shifts function (Also known as the "Frantic Frog").
I'm rather confused by this fact. As $S$ is well-defined, that should mean that regardless of what axiomatic system we use, the exact value of $S(748)$ always stays the same. We just need a stronger axiomatic system to find $S(748)$, like $\mathsf{ZFC}$, $\mathsf{ZFC+CH}$, or $\mathsf{ZFC+(V=L)}$.
If $\mathsf{ZFC}$ and $\mathsf{ZF¬C}$ entailed $S(748)$ to be different numbers, since Axiom of Choice is independent to $\mathsf{ZF}$, it would be concluded that $\mathsf{ZF}$ was inconsistent at the first place. So far, is my understanding correct?


texts: Quick and space-efficient way to find whether two sets intersect

texts:
I hope you can help me -

Given a lot of sets containing integers,
I'd like for any two sets, to quickly (i.e. O(1)) ask whether they intersect.
Note that I don't need the exact intersection, rather just a yes/no answer.
Also, I am fine with some false-positives.
Also, the representation of the sets should be space-efficient (i.e. less than the set-size).

Ideally, I'd also like to (infrequently) update the sets.

My requirements make me think of Bloom Filters, which 1)represent sets efficiently, 2)allow O(1) containment-test and 3) have some false-positives. Unfortunately it they don't apply to two-set-intersection.

Any ideas? Thanks!

(Just FYI, the sets are subsets of ids of adjacent edges from a huge graph)


texts:
Regarding CPU cache, if the CPU does not find the data it needs in the cache, I understand it then looks for it in the main memory (RAM). (Let's assume we have only one level of cache in order to keep this question as simple as possible.)

My question is this: if the data is found in main memory, what happens? Does the processor use this data directly, or is the data loaded into the cache and then read from there?


texts: What do you call a greedy algorithm that solves a combinatorial problem by optimizing the best k>1 choices altogether?

texts:
Suppose you have a problem which goal is to find the permutation of some set $S$ given in input that minimizes an objective function $f$ (for example the Traveling Salesman problem).

A trivial algorithm $E(S)$ that find the exact solution enumerates all the permutations and outputs the one that minimizes $f$. Its time complexity is $O(n!)$ where $n$ is the size of $S$.

A trivial greedy algorithm $G(S)$ that finds an approximation of the solution is:

out[0] = select a good starting item from S according to some heuristic h_1.
S = S - {out[0]}
for i=1 to n-1 do:
    out[i] = select the next best element using some heuristic h_2
    S = S - {out[i]}
return out

Where $h_1$ and $h_2$ are two heuristics. Its complexity in time is $O(n^2)$ assuming that $h_2$ runs in constant time.

Sometimes I mix the two techniques (enumeration and greedy) by selecting at each step the best $k$ items (instead of the best one) and enumerating all their permutations to find the one that locally minimizes $f$. Then I choose the best $k$ items among the remaining $n-k$ items and so on.

Here is the pseudocode (assuming $n$ is a multiple of $k$):

for i in 0 to n/k do:
    X = select the best k items of S according to some heuristic h
    S = S - X
    out[i*k ... (i+1)*k-1] = E(X)
return out

Where $E(X)$ is algorithm that find the exact solution applied on a subset $X \subset S$ rather than on the whole $S$.
This last algorithm finds an approximate solution and has a time complexity of $O(\frac{n}{k}(n \log k + k! ))$ assuming that $h$ can be computed in constant time. This complexity can be comparable to $O(n^2)$ if $k$ is small although according to my experience the performances can be way better than the greedy approach.

I don't think I invented this kind of optimization technique: do you know its name? Can you please include some theoretical references?

I know for sure it is not beam search, because beam search never mixes the best $k$ solutions found at each step.

Thank you.


texts: How do I efficiently checking if a string matches any substring in a collection

texts:
I have a collection of substrings

"this" "is" "a" "antelope"

I need to look at any given string and answer the question "Are any of the given substrings in this string"

So my input string might be

"issue"

Which would be a match because "is" is a substring of "issue"

My first stab at this, I incorrectly turned my collection of substrings into a trie.  That got me nowhere fast as it answered the inverse "is the input string a substring of the given collection".

Is there some algorithm or data structure I can transform my collection into to efficiently answer this question?  I mean, I could do the simple brute force "check the input against every substring" method, but it seems like there is a better way.

In my given example, I would expect that "antelope" would never be checked because "a" covers every case that antelope would. I may even expect that "is" would remove "this" since every case that "this" would find a match "is" would as well.  So it seems like eliminating longer substrings with shorter ones would yield some better performance.

I'm rambling... Anything I should be looking into?


texts: Finding a value in a sorted array in log R time, R is the number of distinct elements

texts: The standard binary search algorithm gives log N time, where N is the total number of elements in the array. When the array has duplicates, I don't see how you could detect those duplicates ahead of time. (Iterating through the array takes N time, which is too much.) Consequently how do you improve the performance from log N to log R?


texts: The Entropy of the phrase "Eile Mit Weile"

texts:
I want to calculate the Entropy of the phrase "Eile mit Weile". I found the probability of each letter as the following

$$P(e)=\frac{4}{12}$$
$$P(i)=\frac{3}{12}$$
$$P(l)=\frac{2}{12}$$
$$P(m)=\frac{1}{12}$$
$$P(t)=\frac{1}{12}$$
$$P(w)=\frac{1}{12}$$

Then I used the formula for entropy
$$H(p_1,...,p_k)=-\sum_{i=1}^{k}p_i\log_2(p_i)$$
$$H(p_1,...,p_k)=-(\frac{4}{12}\log_2(\frac{4}{12})+\frac{3}{12}\log_2(\frac{3}{12})+\frac{2}{12}\log_2(\frac{2}{12})+\frac{1}{12}\log_2(\frac{1}{12})+\frac{1}{12}\log_2(\frac{1}{12})+\frac{1}{12}\log_2(\frac{1}{12}))≈2.355388542 \ Bits$$
But the correct answer is $1.63263$ Bits. I've made a mistake somewhere but can't figure out what I did wrong.


texts: Need clarification regarding certificates of coNP problems

texts:
NOTE: this is not an attempt to prove $NP \neq coNP$

There is one thing I have never been able to completely digest about the certificates of problems in $coNP$ and I would very much appreciate a definitive clarification from this community.

Let's focus on the subset sum problem ($SUBSUM$), now we all know that this problem is in $NP$ since,
to accept language membership, a Prover $P_v$ can emit a certificate which a verifier $V_r$ can check in polynomial time. Up to here no problem. The complement of this problem ($\overline{SUBSUM}$) is in $coNP$ which means that
we do not know if there is a succinct (ie polynomial) certificate to decide the language.
If such a certificate does not exist, then $NP \neq coNP$
and therefore $P \neq NP$.
What I don't understand is this:

If I have (for example) a set $S$ of integers and the number $0$ as an input and I ask:
Prove me that $\forall s \in S \space\space\lnot SUBSUM$, ie $\nexists$ a subset of $S$ such that the sum of its element give $0$ as a result (this is  $\overline{SUBSUM}$, the complement of the subset problem).
How can a certificate exist for this problem whose verification is in $P$? I mean, i need to prove it for all the subset so the search space must be the powerset of $S$. If $|S|=n$ then $\mathcal{|P(S)|}=2^n$. So if the prover, for example, produce a $2^{n/3}$ certificate, this means that I systematically leave out $2^{ \frac{2}{3}n}$ subsets.
What I don't completely understand and for which I need clarification is why this argument is not accepted as evidence that $NP$ is not closed under complement.


texts: Computability of Kolmogorov Complexity of Turing-Incomplete language

texts:
I am trying to determine whether Kolmogorov complexity is computable for a specific language. I am certain this given language is not Turing-Complete. The language is defined as follows:
$A;B \text{ - executes instructions A and B one after the other.}$
$!x_i! \text{ - sets variable } x_i \text{ to the value }2.$
$\{x_i\} \text{ - doubles the value of the variable }x_i$
$[x_i] \text{ - halves the value of the variable } x_i \text{ and rounds it up.}$
$"w" \text{ - prints the string } w \in \{a,b,...,z,A,B...,Z\}$
$\lambda(x_i,A) \text{ - executes instruction } A \text{ exactly } x_i \text{ times, regardless of later changes to } x_i$
Specifically, I need to know whether the Kolmogorov Complexity relative to this language is generally computable. The program which computes this complexity may be written in a Turing-Complete language.
I understand that for any Turing-Complete language, the Kolmogorov complexity is not computable. This language here does lack the ability to create an infinte loop, though, and as such is less than Turing-complete. I am not feeling any intuition arising from this observation though. I'd assume that, this language being weaker, the Kolmogorov complexity may be computable now. Yet I can not find a proof for this. Giving an algorithm that fulfills this task appears overly complicated. The use of this language seems like a special case of the more general computability of the Kolmogorov complexity and as such, I can't derive from the attributes of the general case if the general case is not computable. This may still be.
I am not finding any ground to stand on with this problem and would welcome any tips and pointers towards a solution. Can we deduce anything else from this language than what I have mentioned so far? Does it's lower power relative to Turing-complete languages help us with this situation?


texts: Logic behind choosing the exponent bias as $2^7 -1$ instead of $2^7$ in $32$ bits IEEE-754 floating point representation

texts:
The $\text{IEEE-754}$ uses $32$ bits to represent single precision floating point numbers. The partitions of the register are as follows:
        Biased
 sign  Exponent  Mantissa
+-----+--------+---------+
|1 bit| 8 bits | 23 bits |
+-----+--------+---------+

Now in general $8$ bits can represent $2's$ complement numbers in the range $-2^7$ to $2^7 -1$. Now the bias is added to aid in comparison purposes. In general to make the entire range non negative we can add a bias of $2^7$ to the exponent so that the range becomes $0$ to $2^8 -1$. But again the IEEE uses implicit normalization of mantissa as a result of which we need explicit representation of $0$ or $\pm \infty$. So biased exponent $E'=0$ or $255$ is reserved for this purpose.
So we have,
$$1 \leq E' \leq 254$$
$$\implies 1 \leq E+127 \leq 254$$
$$ ,\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\text{(where E is the actual exponent)}$$
$$\implies -126 \leq E \leq 127$$
But had we used a bias of $128$ instead of $127$ then after reserving $E'=0 \text{ or } 255$
We would have got $$ -127 \leq E \leq 126$$
So my question is, Is there any technical reason for choosing $2^7-1$ instead of $2^7$ or it is just a convention followed by IEEE? Because using the bias of $128$ we could as well allow the required reservation for the special numbers, I see that the only difference comes in the range of the exponent, which shall become $[-127,126]$ instead of $[-126, 127]$


texts: What is known about the equidistribution properties of Philox pseudo random number generator?

texts:
I want to evaluate the usefulness of Philox pseudo random number generator for drawing multidimensional random vectors. What is known about the equidistribution properties of Philox?

I read the Philox paper but it does not contain any information about its equidistribution properties.


texts: Clarification for a class of Turing machine problems

texts:
So say I have a task like this:

  Construct a Turing machine transforming the word u to the word v byt
  removing all the sequences of form "ba" from the word u. Input
  alphabet = {a,b,c}.

  Example: for IN cabbaacba, OUT cac.

And my problem always is: can I leave blank characters in place of "ba" sequences in tasks like this so that in the end, I have something like $ca \Phi \Phi \Phi \Phi c \Phi \Phi$ on the tape or do I have to work on the tape in such a way that I end up with, for example "cac", written consecutively, without blanks?


texts:
I already know how to find the MST of a connected graph. This MST will have the least total weight and will connect all nodes in the graph.
However, this is a problem I have to deal with:

Given a weighted graph $G=\{V,E\}$ and one of its subgraph $H$. Find a subset $E'$ of $E$ such that

If we clear out every edge outside of $E'$, $H$ is still connected.

The total weight of $E'$ is lowest possible.

Note that $E'$ may contain edges that don't join two vertices in $H$, and any two vertices in $H$ may not necessarily be joined by an edge.

It is little different from the MST problem.
Firstly I thought that I only have to run MST algorithm in $H$, but I later found that this only work if any two vertices of $H$ is joined by an edge, not a series of edges.
How can I solve this problem? Thanks in advance.


texts: How to show that a $\log_2(x)$ is a recursive function?

texts:
I have a problem for the comprehension of how to prove that a function $ \log_2 : \mathbb{N} \rightarrow \mathbb{N}$ defined as:
$$\log_2 (x)= \begin{cases}
y  & \text{if $x=2^y$} \newline
\bot & \text{otherwise}
\end{cases}$$
is recursive.
I think that I need to use minimization operator but I don't know how to do that.


texts: Are all adjacency matrices represented by 0 and 1s?

texts: Are there any cases when adjacency matrix should have entries other than 0 and 1?


texts: Algorithm to recognize Strongly Regular Graph (SRG)

texts: I am looking for an algorithm to determine whether a graph is  Strongly Regular Graph (SRG) or not.


texts: Given languages A,B and C, each with alphabet Σ, define A/B/C as:

texts:
Given languages A,B and C, each with alphabet Σ, define A/B/C as

A/B/C = { w∈Σ* | ∃u ∈ B and ∃v ∈ C; such that wuv ∈ A }.
Prove that if A is context-free, and B and C are regular, then A/B/C is context-free.


texts:
I'm trying to show  that for every $L \in RE $ , there is    $L\leq_m HALT$.

can you tell if my reduction is true?

The reduction, while  getting input $x\in L$,

builds a T.M machine D, that upon some input   $x_1$, D is running M on $x$,
if M halted on x, D accepts and the reduction  returns $<M,x>$.

otherwise, D is doing what M does: loop.

does it a correct reduction? thanks.


texts:
I'm trying to construct the small-step semantic rules involving the for-loops, but I can't find anything about it in the literature (only about while-loops).

I was wondering if anyone could help me out with this? This is a first attempt, where $s$ represents a statement and $e$ an expression:

$\quad \displaystyle\sigma, \text{for } s_1 \, e_1 \, e_2 \, s_2 \, \rightarrow \, \sigma, \text{if } e_1 \text{ then (} s_2 ; \, e_2; \, \text{for } s_1 \, e_1 \, e_2 \, s_2 \text{ ) else } skip$

Where $\sigma$ is a local value store, $s_1$ is for example $i = 0$, $e_1$ could equal $i < 4$ and $e_2$ $i=i+1$.


texts: Finding the distance to the nearest neighbor for each point in a set of points in $R^n$

texts: I have a list of points in $R^n$, and for each point I want to find the Euclidean distance to the nearest other point in the list. I don't need to know the coordinates of the nearest neighbor; I only need the distance. The naive approach would be to compare each point to every other, resulting in quadratic running time. Are there any better approaches?


texts:
Lets say for simplicity sakes I have a simple balanced binary tree of height h  and I am doing Depth First Search. I generally do the following skeletons:

def dfs(node root):
    //Pre actions
    if not node:
        return

    dfs(node.left)
    dfs(node.right)

    // Post actions

Now when I look at this code I know its worst case asymptotic bound is O(n). But perhaps I can do better in some cases. So I want to ask a few things and see if you guys agree:

If the last level of the tree is very sparse. We will still make all those recursive calls when node->left and node-> right is null. these will be $2^h$ checks. Would I be correct in arguing that we should place an additional check in the pre conditions check to avoid at least some of those $2^h$ extra calls?

`

if not node.left and not node.right:
    return

or go even further and add an additional check:

 if not node.right.left and not node.right.left:
     // Do some book keeping
     return
 if not node.left.left and not node.left.right:
     // Do some book keeping
     return

IOW is it legit to argue that in cases where the last level is mostly empty, calling dfs recursively is less(much less in certain languages?) performant vs doing the above additional checks at that last level and though we will still be worst case O(n) time bound(we visit everything), we can be better in such cases?

Do compiler optimizations render my point (1) moot in certain cases. What are those cases?


texts: What is the set of operations of a Turing machine?

texts:
From https://en.wikipedia.org/wiki/Abstract_machine

  A typical abstract machine consists of a definition in terms of
  input, output, and the set of allowable operations used to turn
  the former into the latter.

  The best-known example is the Turing
  machine.

In a Turing machine, what is its set of operations?
Is $\delta$ in the following definition of a Turing machine an
operation? (If yes, then there is only one operation in a Turing machine?) Thanks.

From https://en.wikipedia.org/wiki/Turing_machine

  a (one-tape) Turing machine can be formally defined as a 7-tuple $M=  \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle$ where

  $Q$ is a finite, non-empty set of states

  $\Gamma$ is a finite, non-empty set of tape alphabet symbols

  $b \in \Gamma$ is the blank symbol (the only symbol allowed to occur
  on the tape infinitely often at any step during the computation)

  $\Sigma\subseteq\Gamma\setminus\{b\}$ is the set of input symbols

  $q_0 \in Q$ is the initial state

  $F \subseteq Q$ is the set of final or accepting states.

  $\delta: (Q \setminus F) \times \Gamma \rightarrow Q \times \Gamma
     \times \{L,R\}$ is a partial function called the transition function,
  where L is left shift, R is right shift.


texts: On relation between FFT and polynomial multiplication

texts:
Is it known that if polynomial multiplication of degree $n$ polynomials and coefficient size bounded by $M$ can be done in $O(n)$ arithmetic operations on $O(\log n+\log M)$ bit sized words then $FFT$ of length $n$ vectors with entries bound by $M$ can also be done in $O(n)$ arithmetic operations on $O(\log n+\log M)$ bit sized words?

Note that the converse is trivial since polynomial multiplication reduces to $FFT$.


texts: Calculating the time complexity of an arithmetic progression

texts:
Can someone help me calculate the time complexity of the algorithm?

I have an array and I want to check if it's sorted or not I start in the middle of it and I check the numbers first to the right and after that, I check it to the left.

I check it with a variable and that variable increases by 1 every time so it starts with 1 for the right and 1 for the left then 2 then 3, until I reach the end in both ways.

So that's why I thought its an arithmetic progression but I am not sure how to calculate it, and what formula to use.


texts: Show that the Halting problem is reducible to its complement

texts:
HALT$_{TM}$ is the set of all machine-input pairs $<M,w> $ where $M$
  halts on input $w$

  The complement of HALT$_{TM}$ is the set of all machine-input pairs
  $<M,w> $ where $M$ doesn't halt on input $w$

  Show that HALT$_{TM}$ is turing reducible to its complement, and
  explain why it's impossible for it to me many-one reducible.

Regarding the Turing reduction, I've made reduction proofs using using A$_{TM}$ and HALT$_{TM}$ but this doesn't make sense to me intuitively.

I understand the concept of many-one reduction using the Oracle, but have difficulty applying it, not being given any examples to work with.

I'd hugely appreciate it if someone could help me approach the above question, I'm more concerned with the approach rather than the answer, as I've an exam tomorrow!

Thanks a lot.


texts: How to answer the following queries on a tree?

texts:
Given a tree of "N" nodes(each node has been assigned a value A[i],node-"1" is the root of the tree), and a constant "K" , we have Q queries of the following type : [w]
(which means find the lowest valued node in the sub-tree of [w] , only considering those nodes in the sub-tree of [w] which have a depth less than equal to K) .
Example :
Value of nodes of tree :
A[1] = 10
A[2] = 20
A[3] = 30
A[4] = 40
A[5] = 50
A[6] = 60
Edges of tree : [1-2],
[2-3],
[3-4],
[4-5],
[4-6].
K=2.
Query-1 : [w]=1 . All nodes in subtree of [w] : (1,2,3,4,5,6) , now, all nodes in sub-tree of [w] having depth less than equal to K : (1,2) . Hence , minimum(A[1],A[2])=min(10,20)=10 is the answer .
Query-2 : [w]=4 . All nodes in subtree of [w] : (4,5,6) , now, all nodes in sub-tree of [w] having depth less than equal to K : (4,5,6). Hence , minimum(A[4],A[5],A[6]) = min(40,50,60)=40 is the answer .


texts:
While I was reading about Base & Bounds memory protection mechanism, I noticed the use of the abbreviation RTU as indicated in the slide below:

However I didn't know what it means.
So after searching for 'RTU', I found only this article on Wikipedia; But I'm not sure whether it matches the term.
Does anyone have any idea?


texts: decidability about intersection of regular language and context free language

texts:
Is "Given a CFL L and a regular language R, is intersection of L and R an empty set?" decidable? What if we replace L with the complement of L? One of them is decidable and the other is not. For the one that is decidable, give an algorithm. For the other, give an undecidability proof.

For the first part "Given a CFL L and a regular language R, is intersection of L and R an empty set?", I have the following idea. I think it is decidable because an intersection of context-free language and regular language is context-free, and then we can build context-free grammar G from the langauge. For a given CFG G, checking whether the language(G) is empty or not is decidable.

But I have one thing that I'm not sure of. For given context-free language, how can a Turing machine build context-free grammar? As far as I know, there is no known procedure for doing this. If there is no general procedure for building context-free grammar, I think the above proof is invalid.

But I read a proof of theorem "Every context-free language is decidable" from Sipser textbook, and the proof says that for any arbitrary CFL A, we build a grammar G that recognizes A, and we have to include this description of G into our machine. I guess this could work because CFL is fixed, but the above machine needs to take any arbitrary CFL L and regular language R.


texts: Connection between castability and convexity

texts:
I am wondering if there are any connection between convex polygon and castable object? What can we say about castability of the object if we know that the object is convex polygon and vice versa.
Let's gather together few basic things that we have to know.

The object is castable if it can removed from the mold.
The polyhedron P can be removed from its mold by a translation in direction $\vec{d}$  if and only if $\vec{d}$ makes an angle of at  least $90^{\circ}$ with the outward normal of all ordinary facets of P.

For a arbitrary object testing for castability has time complexity $O(n^2)$. In my opinion, for a convex polygon if could be improved to linear time, because for every new top facet we should test that the vector $\vec{d}$ makes an angle at least $90^{\circ}$ with outward normal not of all but only of two adjacent ordinary facets of P.
If this is true at least we have improvement in testing for castability in case of convex polygon.
We else can we state about castability and convexity. Especially interesting to know, if castability tells us something about convexity.


texts:
What is the link between the language defined by the Turing Machine and the algorithm that the Turing machine implements?

I.e. What is the link between the language and the algorithm


texts:
It is often stated that nondeterministic Turing machines cannot recognize any more languages than ordinary Turing machines. In particular, it is stated that there is no NTM that can take as input a DTM/input string and state whether that DTM will halt.

Is this proven, or is this an assumption under the same banner as the Church-Turing thesis?

If it is proven, does anyone have any citations for this in the literature?


texts:
I read one of those popular papers on cubical type theory, but no wonder I could only see formulas and diagrams without being able to recognize them at all.

So here's what I want. I want a deep enough explanation of what composition, Kan filling and gluing have to do with homotopy type theory. I don't expect there could be an ELI (insert age) for it but instead define the word dummy in the title as someone having some basic understanding of HoTT and category theory (perhaps, but not necessarily optionally).


texts: Why is it that in a butterfly network, there is a unique path from the input to the output?

texts:
Consider the a butterfly network as defined on the following OCW notes on page 208. An explantation of it can also be found on the following page.

I was wondering if someone had a proof or an intuition on why there is a unique path from each input to each output on a butterfly network.


texts: Enumerate all greedy choices of maximum independent set

texts:
Following what is stated in the question Why is greedy algorithm not finding maximum independent set of a graph?,
I have the following question:

Even enumerating and testing all possible choices of the greedy algorithm (namely, when there are two possible choices, test both) and verifying which returns the highest value, can it return an approximate result? (ignoring the computational cost)


texts: Can somebody please help me understand ways I can attempt to find two functions f(x) and g(x) in which f(x) is in big O of g(x) but not big theta of g(x). I get that this is asking me to prove that f(x) isn't in big omega of g(x) but I really don't know where to start with this one. I tried to look for scenerios where there wouldn't be any positive constants. However, I had trouble doing that.


texts: Can/Do multiple processes run simultaneously on a multi-core system?

texts:
I understand context switches and threading on a single core system, but I'm trying to understand what happens in a multi-core system. I know multiple threads from the same process can run simultaneously in a multi-core system. However, can multiple processes run simultaneously in such a system as well?

In other words, in a dual core processor:
 - How many processes can run simultaneously(without context switching) if all processes are single threaded?
 - How many processes can run simultaneously if there are 2 processes and both are multi-threaded?


texts: How to split the array into two subarrays with the smallest sum difference?

texts:
Given

An array of elements, all elements are positive (unsorted, but sorting is not a problem if required)

The objective:

To create two subarrays, so that abs(sum(array_1) - sum(array_2)) is the smallest possible

The order of elements in the subarrays and the amount of elements don't matter but all elements should be used
E.g.

Input: Starting Array = {5, 8, 13, 27, 14} Result: 3  - smallest possible
difference in sums

Explanation:

First subarray = {5, 13, 14}
Second subarray = {8, 27}
Difference in sums: abs((5+13+14)-(8+27)) = 3 = min

I have a guess that it's something connected to the binary search but I have no clue what is being "binary seached" and what to connect it to.


texts: By that, I don't mean what is needed to make an operating system. I know that OSes are built on top of kernels and whatnot. But what I mean is, it wasn't like anyone could just "program" the OS like any other software, right? Was an assembler first built? and then a C compiler on top of that? It's a chicken-egg problem I can't seem to find the answer to.


texts: I'm trying to solve the recurrence relation T(n) = 3T(n-1) + n and I think the answer is O(n^3) because each new node spawns three child nodes in the recurrence tree. Is this correct? And, in terms of the recurrence tree, is there a more mathematical way to approach it?


texts:
I have been coding and testing Neural Networks for a while but as of now I have only used IMAGE datasets. (i.e. I have M training images and N testing images).

Some datasets are video datasets. The UCSD Peds dataset for example has the following variants:

Peds 1: 34 training videos (of 200 frames each) and 36 testing videos (of 200 frames each)
Peds 2: 16 training videos (of varying number of frames) and 12 testing videos (of varying number of frames)

So basically, in this case, I have M SETS of training images and N SETS of testing images.

I know the inputs to a neural network is arbitrary and anything can be fed, but I do not really understand how to feed a set of videos.

Will we merge all the 34 x 200 = 6800 training frames together and 36 x 200 = 7200 testing frames together and use the resulting set just like we use MNIST, etc?

How do we feed a set of training videos to a neural network?

What if I want to detect anomalies in the test videos? For example a neural network is trained using videos from UCSD dataset involving only pedestrians. And tested on videos which also have cars and bikes. So these cars and bikes are anomalies.

I'd want to classify an entire video on whether it contains just normal elements or some anomalous elements as well.


texts: Given an undirected graph, find an orientation such that every vertex has out-degree at least 3

texts:
Given an undirected graph $G=(V,E)$, describe an algorithm that computes an orientation of $E$ such that each vertex has out-degree at least 3.

I know how to check if a vertex $v$ has at least $k$ edge-disjoint paths to any other vertex (using Ford-Fulkerson), so I thought I may use that for $k=3$.
Would appreciate your help :)


texts: Greedy algorithm: Minimizing the maximum of a list

texts:
Given a list $L$ of positive integers, assuming you can only modify the list by "splitting" its numbers a finite number $n$ of times. Write an algorithm which minimize the maximum of the last generated list.

By "splitting" a number $x$ I mean deleting $x$ from $L$ and adding to $L$ two positive numbers $\alpha,\beta$ verifying $\alpha+\beta=x$. We can only do this $n$ times.

My try was taking the two greatest elements of $L$, $\alpha$ (the maximum) and $\beta$ (the other), then I split $\alpha$ into $c=\min(\alpha/\beta+1,n+1)$ equal parts (the last part will be $\frac{\alpha}{(\alpha/\beta+1)}+\alpha\text{mod}(\alpha/\beta+1)$). So I spend $c$ of the hability.

Then I repeat the process until I run out of the hability or $\beta=1$, so then y take $c=\min(\alpha/\beta+1,n+1)-1$.

I know my try is not correct, as the list $(10, 4, 9)$ for $n=4$ is a counterexample. Any idea?

I'm not looking for efficiency details (it can be achieved working with heaps), only for correctness.


texts: How to justify the choice of using a specific metaheuristic?

texts:
For a problem how to justify the use of a metaheuristic upon another?
For exemple for scheduling problem, could the same heuristic be efficient for different variants of the problem?
What are the parameters that influence the choice of a metaheuristic?


texts: Are there algorithms or circuits that can implement addition without the need for carry flags

texts:
Let two numbers $x,y$ be represented in some digit form (binary, octal, ...): $(x_1 x_2 x_3 \ldots)$ and $(y_1 y_2 y_3 \ldots)$.

Can we add those numbers such that we do not need to carry over: $x_i = x_i+y_i + c(x_{i-1},y_{i-1})$ where $c(x_{i-1},y_{i-1})$ is the carry value of $x_{i-1}$ and $y_{i-1}$.

Are there $O(1)$ step circuit implementations of addition that exist? Are they practical?

In other words, is addition inherently recursive over the number of digits?