texts:
I'm putting together a primality tester for large numbers. When the numbers were smaller things were more straightforwards. I got refined it to a point where I could quickly test any number within the range of long long ints. I wanted to be able to test larger numbers. I've gotten it to read the numbers in as strings then convert to an array. I now have the issue of not knowing how to perform mod on arrays. (int*)mod(int) isn't too bad but (int*)mod(int*) is more complicated.

In short:

Is there a relationship between n%c and n%a,n%b where a+b=c
How do you take the mod of 2 sums where either sum would give you overload.


texts:
I do know what a "left-most-" and a "right-most derivation" is, but I stumble across the term "sentential form" and its specific differences "right-sentential form" as well as "left-sentential form" and I just don't understand what is meant with this term.

Is the concept "sentential form" so different from the concept "derivation" that it is necessary to "have" it" ?

Can some of you please explain?

Yours sincerely


texts: Why does higher-order abstract syntax need an inverse to define catamorphisms?

texts:
In the introduction to the colorfully-named Boxes Go Bananas: Encoding Higher-Order Abstract Syntax with Parametric Polymorphism, Washburn and Weirich describe a problem in traditional formulations of higher-order abstract syntax (HOAS):

  One obstacle preventing the widespread use of this technique is the difficulty in using elimination forms, such as catamorphisms, for datatypes containing functions. The general form of catamorphism for these datatypes requires that an inverse be simultaneously defined for every iteration. Unfortunately, many operations that we would like to define with catamorphisms require inverses that do not exist or are expensive to compute.

They go on to demonstrate this problem with a small example, in Haskell. They define the following datatypes to represent simple lambda terms with HOAS:

data Exp = Lam (Exp -> Exp) | App Exp Exp
data Value = Fn (Value -> Value)

Lam represents lambda terms, App represents function application, and Fn represents evaluated functions. They next attempt to define eval :: Exp -> Value, but this causes trouble, as it requires converting a function of type Exp -> Exp to one of type Value -> Value. Since Exp appears in both positive and negative positions, this requires functions from both Exp -> Value and Value -> Exp to define.

The remainder of the paper proposes a solution to that problem, but I am stuck on something else: I don’t understand why it’s a problem at all. Usually, in programming language papers, we define languages with grammars like the following one:

$$
\begin{align*}
v &::= \lambda x. e \\
e &::= v \thinspace | \thinspace e \thinspace e
\end{align*}
$$

If we define a big-step evaluation relation $e \Downarrow v$, we have no need to define some other “unevaluation” relation $v \Uparrow e$, as lambdas are already values, so $\lambda x.e \Downarrow \lambda x.e$, which is quite straightforward.

It seems to me that a natural translation of the above grammar to HOAS is different from the one Washburn and Weirich present. Specifically, I think it would look more like this:

data Exp = Lit Value | App Exp Exp
data Value = Fn (Value -> Exp)

Defining eval on this grammar is as simple as defining the usual big-step relation:

eval :: Exp -> Value
eval (Lit v) = v
eval (App e1 e2) = case eval e1 of
  Fn v -> eval (v (eval e2))

But this solution seems much too simple to be right. Boxes Go Bananas is a well-cited paper from reputable authors published at a reputable PL conference, so its solution surely must have some advantage over the one I presented above. My question, therefore, is simply this: what is that advantage? What am I missing?


texts:
I am currently learning about FPTAS and PTAS but do not understand what the definition of FPTAS.

  A fully polynomial time approximation scheme (FPTAS) for problem $X$ is an approximation scheme whose time complexity is polynomial in the input size and also polynomial in $1/\epsilon$.

In this explanation, what does the $\epsilon$ stand for?


texts: does godel's incompleteness theorem shed any light on dynamic vs typed languages?

texts:
I'm clojure user myself. I'm trying really hard to learn haskell and to better understand the type system. However, I feel that trying to 'type' everything is quite restrictive when the problem or the data is less defined.

I intuitively feel that godel's incompleteness theorem offers some insight into the typed/untyped debate. What are some simple problems that may trip up the typing system but not untyped ones?

According to http://en.wikipedia.org/wiki/Type_theory. "The types of type theory were invented by Bertrand Russell in response to his discovery that Gottlob Frege's version of naive set theory was afflicted with Russell's paradox. This theory of types features prominently in Whitehead and Russell's Principia Mathematica. It avoids Russell's paradox by first creating a hierarchy of types, then assigning each mathematical (and possibly other) entity to a type. Objects of a given type are built exclusively from objects of preceding types (those lower in the hierarchy), thus preventing loops."

Godel's theorem invalidated Principia Mathematica. What consequence does it have on Type Theory.


texts: Master theorem: what to do with constant in parenthesis?

texts:
In analysis of algorithms, we sometimes use the (unsimplified) Master Theorem for recurrence relations.
What should be done in the case that there is a constant factor in the numerator following T?
$$
T(n) = 2T\left(\frac{5n}{8}\right) + 1
$$
Does b simply equal $\frac{5}{8}$? This seems a contradiction to the Theorem.


texts: Decidability of a set containing first symbols of elements of a decidable set

texts:
Let's say we have an alphabet $\Sigma = \{a,b, \dots , z\}$

Set $A$ consists of words $x_i$ containing symbols from $\Sigma$ alphabet, which have this structure

$x_i := \alpha_i \beta_i$, where $\alpha_i$ is just 1 symbol from $\Sigma$ and $\beta_i \in \Sigma^{*}$ (can also be empty)

So the set A should look like this
$A = \{ \alpha_1 \beta_1, \alpha_2 \beta_2, \dots , \alpha_n \beta_n, \dots\}$

The question is:

If the set $A$ is decidable, then should also the set $B = \{ \alpha_1, \alpha_2, \dots , \alpha_n, \dots\}$ be decidable?

My thoughts..

For the set $A$, we have a total computable function $f(x_i)$ which gives an answer, whether a given input element contains in $A$ or not.
Now, when we shrink $x_i$-s and only leave $\alpha_i$ parts, we cannot use $f$ anymore. The only idea which came to my mind, is using this naive algorithm.

get input $\alpha_j$
for each $x_i \in A$
   if $\alpha_j$ is prefix of $x_i$
      return YES
return NO

And here, I guess, the problem is in for each statement. Here we enumerate all elements of the set $A$. For being able to do this, I guess we need to use some kind of mapping $\phi : \mathbb{N} \to \Sigma^{*}$ and then apply $f$ on the output to get all possible $x_i$-s. This algorithm may give a correct answer, but it also may give no answer (we will never reach to return NO). So my conclusion was B is not decidable (B is semi-decidable). But there might also be a 'better' algorithm?

..end of my thoughts.

I apologize if my thoughts are 100% wrong. That's how far I could reach.

Any help is much appreciated.


texts: Flynn's Taxonomy as a modern classification

texts: Flynn's Taxonomy was a classification of computer architectures published in 1966. Computing has changed a lot since then. Is this taxonomy still useful? What are some of its shortcomings for evaluating modern computing systems?


texts: How to check rapidly if an element is present in a large set of data

texts:
I am trying to harvest scientific publications data from different online sources like Core, PMC, arXiv etc. From these sources I keep the metadata of the articles (title, authors, abstract etc.) and the fulltext (only from the sources that provide it).

However, I dont want to harvest the same article's data from different sources. That is, I want to create a mechanism that will tell if an article that I am trying to harvest is present in the dataset of the articles that I already harvested.

The first thing I've tried was to see if the article (which I want to harvest) has a DOI and search in the collection of metadatas (that I already harvested) for that that DOI. If it is found there then this article was already harvested. This approach, though, is very time expensive given that I should do a serial search in a collection of ~10 millions articles metadata (in XML format) and the time would increase much more for the articles that don't have a DOI and I will have to compare other metadatas (like title, authors and date of publication).

def core_pmc_sim(core_article):
    if core_article.doi is not None:      #if the core article has a doi
        for xml_file in listdir('path_of_the_metadata_files'):  #parse all PMC xml metadata files
            for event, elem in ET.iterparse('path_of_the_metadata_files'+xml_file): #iterate through every tag in the xml
                if (elem.tag == 'hasDOI'):
                    print(xml_file, elem.text, core_article.doi)
                    if elem.text == core_article.doi:  # if PMC doi is equal to the core doi then the articles are the same
                        return True
                elem.clear()
    return False

What is the most rapid and memory-efficient way to achieve this?

(Whould a bloom filter be a good approach for this problem?)


texts: Finding a non-boundary, local optimum of a non-convex function over a convex feasible region

texts:
I have a reasonably smooth non-convex non-monotone function in high(ish) dimensional space, that I wish to find a local minimizer for, over a convex feasible region (the intersection of a ball with a set of halfspaces, so a "wedge" of the ball or a polytope), with the caveat that I want the minimizer to be away from the boundary of the feasible region.

Are there any sound ways, or even just good heuristics, for doing that?

Edit: If all minimizers (or regions looking like minimizers) are around the boundary, then is there a way to detect that?

One idea I had is to use barrier functions near the boundary and then just use gradient descent, but the barrier functions might create false local minima...

Thanks!


texts: Finding most likely tree over a semilattice

texts:
If I am not mistaken, then a semilattice defines a finite set of trees, for example spanning trees.

Now assume that each semilattice edge is annotated with a transition probability. In addition, let's assume that the probability of a tree over the semilattice is the product of the probabilities of all the edges that the tree uses.

How to find the most likely spanning tree, that is the most likely hypothesis how the nodes came to be? I am unsure whether this amounts to finding a maximum spanning tree of the semilattice.

I guess this has applications in probabilistic graphical models...


texts:
I have read many resources, but I cannot understand what the polynomial-time reduction is. In everywhere, this is explained with standard-pattern sentences.

Please can anyone explain it in detailed version ?


texts:
I was reading about dynamic programming and I understood that we should not be using dynamic programming approach if the optimal solution of a problem does not contain the optimal solution of the subproblem.

The Longest path problem is very clear example on this and I understood why.

But I am not able to find out any other problem which is similar to longest path problem, where the subproblems's solution cannot be used for solving the optimal solution of parent. Can some one guide me?


texts: Two regular languages over the same alphabet, regular or not regular?

texts:
TRUE or FALSE:
Let $L_1, L_2$ be any two regular languages over the same alphabet $\Sigma$, then the language $L=\{w\in\Sigma^* \mid w\in L_1 \text{ or } w\notin L_2\}$ is regular.

So we have to determine whether $L_1 \cup \overline{L_2}$ is regular or not.
Proof:
First attempt:
First we have to prove that a complement of a regular language is also regular: the complement of a language $L$ with respect to an alphabet $\Sigma$ such that $\Sigma^*$ is $\Sigma^*-L$. Since $\Sigma^*$ is surely regular the complement of a regular language is always regular.
Let's prove that the union of two regular languages is also regular: For example, let $\Sigma = \{a,b\}$. Assume $L_1 = \{a\}$ and $L_2 = \{b\}$ so they are regular language. Then the union: $\{a\} \cup \{b\} = \{ab\}$ is also regular. Since $\{a\}$ is regular , $\{a\}^*$ is also a regular language.
After these two proofs we can say that the statement above is True.
Second attempt:
A regular language is regular iff there is a finite state machine recognizing it. Let $L_1 = \{S_1,\Sigma,\delta_1,s_0^1, F_1\}$ and $L_2 = \{S_2,\Sigma,\delta_2,s_0^2, F_2\}$ be two automata. First we have to take the complement of $L_2$. The complement of $L_2$ is the set of states without the set of final states: $\overline{L_2} = \{S_2,\Sigma,\delta_2,s_0^2, S_2-F_2\}$. Then we can create the product automaton of the two languages which is: $L = \{S_1 \times S_2,\Sigma,\delta_1 \times \delta_2,s_0^1 \times s_0^2, F_1\ \times (S_2-F_2)\}$. The final states of the language $L = L_1 \cup \overline{L_2}$ is the set of states where $F_1$ or $S_2 - F_2$ is final. Since there exists a finite state machine that recognizes the language $L$, we can say that $L$ is a regular language.
Can somebody please correct me? Maybe I made a mistake.


texts: How can I show a problem is in the intersection of np and co-np using duality and Farkas-lemma?

texts:
Currently, I have a hard time to find out the solution to this problem:
Given a matrix $A \in Z^{m \times n}$, $b \in Z^m$, $c \in R^n$ and $\lambda \in  R$. Is there $x \in R^n$ with $Ax \leq b$ and $c^Tx \geq \lambda$?
I was able to show that the given problem is $NP$, but now I have to show it is in $NP \cap co-NP$ by using strong duality and Farkas lemma. I thought it would be enough to show, that given a no certificate $x$, I can calculate $c^Tx$ and compare it with $\lambda$ in polynomial time.
Edit:
We can assume, that all extreme points have polynomial size.


texts: What data structure to use for large scale DHCP server

texts:
What data structure would one use to keep a large number of IP addresses (v4 and v6, but not at the same time if that makes a difference), and I'm talking about millions, preferably hundreds of millions at a time for fast look-up.
The preference would be for fast look-up. Initial filling of the data structure is not too big of a concern. To have a small memory footprint is not also a big concern, but it would be nice to have that part as small as possible.
I was thinking in lines of using some sort of binary tree, but don't know if hash map would suffice...
Thanks in advance!


texts: Getting minimum DFA for regular expression (11)*+(111)*

texts:
(sorry beforehand I know putting scanned diagrams may seem not-so-professional but this problem is sticking for long and its interesting too)

The language corresponding to given regex seems to accepts all strings of 1's with length in multiple of 2 or 3 (i.e.4,6,8,9,10,12,...)

I prepared following NFA first:

Figure 1

Then I followed steps given here to prepare DFA.
First I prepared below table to get equivalent DFA steps:

Figure 2

Then I prepared below DFA, which seems to be quite correct.

Figure 3

Next to get equivalent states I followed table filling algorithm as explained [here]
(http://books.google.co.in/books?id=tzttuN4gsVgC&lpg=PP1&pg=PA144#v=onepage&q&f=false)
and formed below:

(cross between every intersecting column and row indicates two intersecting states are distinguishable / not equivalent)

Figure 4

But I dont get from above table how can I get below minimized DFA as given in the book solution:

Figure 5

So in the solution of the textbook, their is one less state (total 6) than my dfa in figure 3 (which has 7 states). I should be able to derive the same (equivalent 6-state dfa) from above triangular table.


texts: Fastest (fast enough to compute) algorithm for finding permutations

texts:
I have a set of letters, and a list of words, and I'd like to find all the possible "sentences" that can be built using the words from the list, while using up all the letters in the process. (A word can be used more than once.)
The maximum amount of words in a sentence is also given.

For example, my letters are {"a","a","a"}, and for the sake of simplicity, my words are {"a","aa","aaa"}, and I'm looking for sentences of maximum 3 words (cannot be more in this case anyway).

The order of the words in a sentence doesn't matter, so "a aa", and "aa a" would be considered duplicate sentences, so the output would be the following:

{"a a a", "a aa", "aaa"}

I need an algorithm that finds and lists these sentences (no matter how many there might be) for larger sets. Right now I have 9000 words, and 24 letters. (I know the amount of words is way too much, but let's just disregard that in this case.)

I'm really new to this kind of problem solving, and algorithms in general, so I tried several approaches on my own (and with the help of the internet) with obviously not much success.

The closest I could come up with was the following:

I assigned a prime to each character, and then each word would be the product of them, then considering the letters is together are also a "word", I could find out whether a word was a part of it with congruency, then after dividing the set of letters by word after word would eventually end up being 1, which means, I found a sentence.

So with this in mind, my approach was the following:

I start a sentence with each word, then then I find the next possible words for each one.
Then I take all the valid (now 2 word) sentences, and find a next word for each of them as well.
And I repeat this until I reached the maximum amount of words I'm looking for.

By "valid" sentences, I mean the ones that can be used in the next iteration, which means that their "letters" are not 1 (in which case no more words can be found, and the sentence is done), and a word was found in the previous iteration, no further validation takes place.

The problem with this is that it takes way too much time to be usable, e.g if I start with 3 words, for finding all the 3 word sentences in the worst case I would have to go through the list of words 3+3^2+3^3 times if I'm not mistaken, but I'm looking for sentences with a maximum of 6 words, and I'm supposed to start with a lot more words. Another problem is that with this approach I end up with duplicatons, and I'd need to filter the result in the end.

Are there any algorithms that are suitable for this kind of problem, or can it even be solved in polynomial time?

Thanks in advance


texts: difference between "addressable" and "address" in memory?

texts:
I'm struggle on this practice question from this site....

Calculate the number of bits required in the address for memory having
size of 16 GB. Assume the memory is 4-byte addressable.

MY QUESTION IS: what is the difference between an "address" and "the memory is 4 byte addressable"?
I understand an address would be its location in memory that is represented by bits, such as 2^n, where n is the number of bits in the address. But I'm confused about addressable in this question and how that's different than address
2^n * 4 bytes = 2^34
The solution is 32 bits


texts: What's the error-correcting capacity (randomly errors, or burst errors) of polar code?

texts:
Polar codes, invented by Arikan, with low encoding and decoding complexity. But the minimum distance of polar codes is not great. The normalized minimum distance goes to 0 with the block size. Yet, the existing decoding algorithms for polar codes can asymptotically achieve channel capacity.

Generally, a code with minimum distance $d$ can correct $\frac{d-1}{2}$ errors (random errors). And Polar code is also error-correcting code, I was wondering how many errors can it correct( e.g. A $[2048, 614]$ with $BEC(0.19)$ polar code.)? Much appreciated.


texts: Does the illumination color (red/blue/green) has any effect over the disparity map generated from a stereo image?

texts: I have a working model that creates a disparity map using stereoscopic image processing using opencv. I am thinking of improving the disparity map by using illumination and stuck with different options in the light colors. I want to know if the color of illumination has any influence over the disparity maps.


texts: What is considered arithmetic when dealing with bits?

texts:
In a recent homework question we were asked to implement a program that would use only bitwise operations. From our notes, this includes & | ^ ~ >> << and >>>. We are not allowed to use arithmetic operations, or loops.

Since immediately addition can be defined with the above accepted operators, what constitutes "arithmetic"? Would unary operations be allowed?

For example, I could define incrementation and decrementation using ~ and the unary -, and recursively call both until the decremented number reached 0, meaning both numbers were added (think addition in brainfuck). Is this arithmetic?


texts: Prove $L =\{0^{2^n}\mid n \geqslant 0\}$ is not context free

texts:
Here $0^j$ means $0$ repeated $j$ times e.g. $0^2$ is $00$. So to prove this I was asked to use the pumping lemma.
So let $m$ be the pumping length and assume $L$ is a CFL by contradiction. We can then pick a string of the form $w=0^{2^m}$
We know that $w=uvxyz$ where $|vxy| \leqslant m$ and $|vy| > 0$ and $uv^ixy^iz\in L$.
As the string is made of only zeros the only case we need to consider is : $vy = 0^j$, $j>0$.
If we take $i=2$ then we get $w'=uv^2xy^2z = 0^{2^m+j}$.
To show $w'\notin L$ we can show $2^{m}<2^m+j < 2^m$.
I'm not sure how to show this part though. I thought that as $j$ is $|vy|$ and $|vxy| \leqslant m$ then $|vy| \leqslant m$ but im not sure where to go from here.


texts: What are positive and negative circles in weighted digraph?

texts: I am going through Warshall and Floyd algorithms and I read that Floyd's algorithm does not hold if a graph has negative circle. I have not been able to fully figure out what  negative circle means. Therefore, I would like to know  more about positive and negative circles.


texts: Is there a word/name for the node(s) in a graph with the minimal cumulative path length to a set of other nodes?

texts:
In other words, given a graph with nodes $N=\{n_0,n_1,...,n_j\}$, and a set of nodes in the graph $M=\{n_a,n_b,...,n_k\}$ with $M\subseteq N$, I'm looking for what to call the node or nodes $n'$ which minimize:

$\sum_{m\in M}d_{min}(n',m)$

where $d_{min}(x,y)$ is the shortest distance from node $x$ to node $y$, as traditionally defined.

When $M=N$, this would be the node with the highest closeness centrality, but I'm interested in subgraphs.


texts: Calculating number of intersections of a horizontal line with line segments efficiently

texts:
I'm given an array $A = [a_1, a_2, ....a_n] $ using which I construct $n-1$ contiguous line segments by drawing a line from $(i,a_i)$ to $(i+1, a_{i+1})$.
Now, I'm given $q$ queries in the form of $x_1, x_2, y, l, r$ where $l$ and $r$ are the range for the array $A$ and the rest indicate a horizontal line segment $L$ from $(x_1, y)$ to $(x_2, y)$.
For each query, I want to find total intersections of $L$ and the segments in the range $l$ and $r$ in $O(q)$ or $O(q\log{n})$ complexity so that total computational complexity becomes: $O(n + q)$  or $O(n + q\log{n})$

I was able to arrive at a solution that works in $O(nq)$ which simply traverses each range and calculates whether $L$ intersects with the segments or not.
I believe, some pre-processing can be done on $A$ which can reduce the complexity.
Any leads will be appreciated!


texts: Algorithm to build tri-nodes in MapleStory

texts:
This problem is originated from the game MapleStory, where the player needs to build "tri-nodes" to enhance there skills, and each skill should appear in two different tri-nodes. For my character, kanna, I want to enhance 9 skills with 6 tri-nodes (2x9=3x6). After thinking a while for an optimal strategy, it seems to me that the problem isn't that easy. I henceforth abstracted it into an algorithm problem showing below. Please let me know if there is anything unclear in the problem description. Thanks.

A card is a tuple of three letters in [a,b,c,d,e,f,g,h,i], and the three letters within a card are different.
For example, (a,b,c) could be a card, but (a,a,c) can't be because there are two same elements.
We can take exactly 6 cards to acquire 3x6=18 letters, and we want each letter in [a..i] appears exactly twice. However, we cannot take two cards that share the same first element. For example, the following set of cards satisfy the requirement. Each letter appeared exactly two times, and the first elements of these cards are unique.
[(a,b,c)(b,c,a)(d,e,f)(e,f,d)(g,h,i)(h,g,i)]
For a deck of $n$ cards ($n$ can be any integer), if there is a set of 6 cards that satisfies the above requirement, we say that this deck is complete, otherwise we say it's incomplete.
Given a deck of cards,

(a) determine if the deck is complete.

if the deck is complete, find an algorithm to

(b) find a solution.
(c) find all solutions.

If the given deck is incomplete, the requirement cannot be satisfied with the cards in the deck. In such case, a randomly generated new card will be added into the deck. The new card is generated randomly, meaning that [a..i] are equally probable at each position of the card tuple (but still the three positions will be different). After adding a random card, if the deck is still incomplete, another new random card will be added again. As such, we can expect that as the number of cards -> $\infty$, the deck will eventually become complete.

(d) Find an algorithm to take $m$ cards ($m<6$) from the deck, such that

$m$ is as large as possible;
each letter appears at most twice;
it is possible to take $(6-m)$ new cards that may be added in the future to satisfy the requirement. List these new cards.

For example, the following deck is incomplete:
(a,b,c)(d,a,e)(f,d,c)(b,e,f)(g,c,b)
We cannot take all of them because there will be more than 2 b's and c's.
we can have two solutions:

(a,b,c)(d,a,e)(f,d,c)(b,e,f)

with the appearance count [a:2,b:2,c:2,d:2,e:2,f:2,g:0,h:0,i:0]
and the needs count [g:2,h:2,i:2]

(d,a,e)(f,d,c)(b,e,f)(g,c,b)
with the appearance count [a:1,b:2,c:2,d:2,e:2,f:2,g:1,h:0,i:0]
and the needs count [a:1,g:1,h:2,i:2]

For the former solution, we want the new cards, for example, (g,h,i)(h,g,i). For the latter one, we want the new cards, for example, (h,a,i)(i,g,h). The possibilities of getting the needed cards might be different.

(e) There might be multiple solutions for (d). Find one that has the maximum possibility to satisfy the requirement with fewest new cards.


texts:
I'm reading "Understanding Linux Kernel 3rd edition" and it starts talking about memory segments. It says that a logical address is:

  Included in the machine language instructions to specify the address
  of an oper- and or of an instruction. This type of address embodies
  the well-known 80 × 86 segmented architecture that forces MS-DOS and
  Windows programmers to divide their programs into segments. Each
  logical address consists of a segment and an offset (or displacement)
  that denotes the distance from the start of the seg- ment to the
  actual address.

Well, for a x86 architecture, the instructions must fit a register, that is, they must be int he 32-bits format.

The book says then that logical addresses are formed by the segment identifier (16 bits) and the offset, which is 32 bits. Since the logical address is included in the machine language instructions, it does not makes sense that it is formed by 16 bits + 32 bits. So I presume that's the following:

The kernel code is a bunch of instructions in the 32-bit format, that is, its either instructions or it points to 32-bit addresses. Obviously a machine instruction can't be of length 16+32, therefore what happens is that the kernel chooses a segment to work with, and then stores the segment selector in the register it wants, so all the addresses given by the offset will fall inside that segment. However, I see it as a redundant form of paging, and it does not make much sense. What if the segment is of length 1mb and the offset refers to a address much greater than that? It makes sense if the code refers to addresses near it, but I don't get the necessity of segmentation here.


texts:
I meet a problem. I can find a sub-optimal solution, but cannot find an optimal one and cannot prove its NPC hardness.

The problem can also be described as follows. Given a sequence $X=\{x_1,x_2,...,x_n\}$, a partial order $<$, where $x_i <x_j$ means that $x_i$ must be in front of $x_j$, and a new item $x_k$ as well as related statements $x_k<x_i$ for some $i$'s and $x_j<x_k$ for some $j$'s to be added to the partial order, how to find the least replacement solution to insert $x_k$ into the original sequence $X$ without violating the resulting partial order?

It can be ensured that the partial order forms no cycle such as $x_i<\cdots<x_j<\cdots <x_i$.


texts: Highest lower bound on an NP complete problem

texts: What is the highest time complexity lower bound that has been proven on any (non-contrived) NP complete problem?


texts: Distribute numbers 1,N on a grid as evenly as possible

texts:
I'm working on a complex engineering problem that I've essentially reduced to this problem:

I have a set of natural numbers $1,N$ and a grid (square or hexagonal) of exactly $N$ cells. I have to map each number to each cell so that the distribution (in a geometric sense) is as flat as possible. I'm still working on the definition of flat, but so far

The average of the numbers of a cell and its nearest neighbours must be as close to $N/2$ as possible, for every cell.
The average of the distance between a cell and each neighbour must be as large as possible.

If a cell has a number $n$ and its neighbour $m$ the distance between these neighbours is $min(|n-m|,N-|n-m|)$. It's essentially cyclical.

If $.$ represents a small number and # a large number I'm looking chessboard-like configurations like

.#.#.#.#
#.#.#.#.
.#.#.#.#

I need to find the best configuration (or a very good one) without using brute force.

Can you point me to some good algorithms that may be useful for this problem? I could only get above-average results on my own.

In my problem $N\approx~500$ and there is no runtime constraint.


texts: Hardness of approximation: what decision problem is hard exactly?

texts:
Just a question for personal comprehension.  Consider the following statement:

  It is NP-hard to approximate Set-Cover within a $(1 - \epsilon) \log n$ factor for any $0 < \epsilon < 1$.

Now, NP-hardness refers to decision problems.So what is NP-Hard exactly here ?

My guess is that the statement is equivalent to saying that the following problem is NP-hard (but I really ain't sure):

  Given a set cover instance $S$ and an integer $k$ with the guarantee that either $S$ admits a cover of size at most $k$, or $S$ has a cover of size at least $k \cdot (1 - \epsilon) \log n$, decide if $S$ has a cover of size at most $k$.

Note that I took set cover as an example, but my question is on problems that are said 'hard to approximate' in general.


texts: What Properties Matter For the Bound on Generalization Error of Hypothesis Set?

texts:
As I know, there are several upper bounds on the generalization error of hypothesis set with respect to sample complexity. For hypothesis space $V$, if the learning algorithm output the set of hypotheses that are consistent with the training data, i.e., $\sum\limits_{1 \leq i \leq n}{\frac{I[h(x_i) \not= y_i]}{n}} = 0$, the VC theory gives the bound on generalization error. If we consider the "margin" or confidence of classification, PAC Bayes theory gives tighter bounds on generalization error with margin incorporated.

My question is: what other properties or structure of the set of all possible hypotheses output by the learning algorithm matter for the bound on generalization errors? Name a few.


texts:
How do you union of two finite automata as well as establish the transition table for it. I'm unsure of how to properly union the two finite automata. I believe the transition table would look something like this:

state |  a  |  b  |  a,b

x1|  x2 |  x3 |
x2|     |     |  x3
x3|     |     |  x3
y1|  y2 |  y3 |
y2|     |     |  y3
y3|     |     |  y3

I'm to sure how to properly develop the FA for these two diagrams. I would appreciate any links or advice on how to go about this.


texts: The algorithm yields optimal ternary codes

texts:
Steps to build Huffman Tree
Input is array of unique characters along with their frequency of occurrences and output is Huffman Tree.

Create a leaf node for each unique character and build a min heap of all leaf nodes (Min Heap is used as a priority queue. The value of frequency field is used to compare two nodes in min heap. Initially, the least frequent character is at root)
Extract two nodes with the minimum frequency from the min heap.
Create a new internal node with frequency equal to the sum of the two nodes frequencies. Make the first extracted node as its left child and the other extracted node as its right child. Add this node to the min heap.
Repeat steps#2 and #3 until the heap contains only one node. The remaining node is the root node and the tree is complete.

If we would like to generalize the Huffman algorithm for coded words in ternary system (i.e. coded words using the symbols 0 , 1 and 2 ) I think that we could do it as follows.

Steps to build Huffman Tree
Input is array of unique characters along with their frequency of occurrences and output is Huffman Tree.

Create a leaf node for each unique character and build a min heap of all leaf nodes
Extract three nodes with the minimum frequency from the min heap.
Create a new internal node with frequency equal to the sum of the three nodes frequencies. Make the first extracted node as its left child, the second extracted node as its middle child and the third extracted node as its right child. Add this node to the min heap.
Repeat steps#2 and #3 until the heap contains only one node. The remaining node is the root node and the tree is complete.

How can we prove that the algorithm yields optimal ternary codes?


texts: Existence of particular/specialized halting oracles

texts:
It is known that there does not exists an oracle $H$ which given any pair $(M,I)$ where $M$ is a machine and $I$ is an input (possibly still a machine) to have $H(M(I)) = YES$ if $M(I)$ halts and $H(M(I)) = NO$ if $M(I)$ does not halt. This was proven by Turing. However, this can be shortly written as
$$ \not\exists H \hspace{0.5cm} \forall M,I \hspace{0.5cm} H(M(I)) = \begin{cases} YES, \hspace{0.3cm}M(I)  \text{  halts }\\ NO, \hspace{0.4cm} M(I) \text{ doesn not halt}\end{cases}$$
But is it possible to have the following:
$$ \forall M,I \hspace{0.5cm} \exists H_{M,I} \hspace{0.5cm} H_{M,I}(M(I)) = \begin{cases} YES, \hspace{0.3cm}M(I)  \text{  halts }\\ NO, \hspace{0.4cm} M(I) \text{ doesn not halt}\end{cases}$$


texts: Question about Dynamic Scoping example output

texts:
I'm trying to do a runtime stack on a simple code example that uses dynamic scoping. The code is this:

void g() {
  int r = 10;
  c = 2;
  b = a;
}

void f() {
  int b;
  b = a;
  a = a + 1;

  g();

  print a, b, c;
}

void main() {
  int a, b, c;
  a = 2;
  b = 4;
  c = 6;

  f();

  print a, b, c;
}

For the first print, I'm getting 3 3 2, which is correct. However, for the second print (in main) I'm getting 3 3 2 when the correct answer is 3 4 2.

I got 3 3 2 because the value of a is assigned to b which is 3 in function g(), which is called by f(). I don't see b being changed after that.

Appreciate the help!


texts:
I would like to design an algorithm to pack closed paths into a rectangle. An example of one of these paths is below:

The rectangle will have a fixed width, but the height will expand to accommodate the paths.

A Simple Approach I Already Tried:

Calculate the smallest rectangle that inscribes the path. (Results were later improved by rotating the path until its width was as small as possible). Pack the paths left to right, and if the remaining width is too small, expand the height and pack on the next row. This approach, however, loses optimizations with concavity. I want optimizations like this to be made:

But with the current approach I get this:

What type of algorithms can be used to optimize both concave and convex shape packing?

Edit:

Paths cannot overlap, be warped, or contain other paths (like a square in a square), but they can be rotated for optimal packing


texts: Why does the app I downloaded say that 1 in binary is 00110001?

texts: I've just started learning binary so mind me if I'm bad at this. I think that the binary for 1 ought to be just "1" but, when I key it in to an app I downloaded, the answer has extra 0s and 11s in it. Why?


texts: Is this language depending on P = NP recursive?

texts:
Nobody yet knows if ${\sf P}={\sf NP}$. Let us consider the following language

$$L = \begin{cases} (0+1)^* & \text{ if ${\sf P}$ = ${\sf NP}$} \\ \emptyset &\text{ otherwise}. \end{cases}$$

A language is said to be recursive if there exists any rule to determine whether a string belong to language or not. We have a rule here, but the rule itself depends upon an unknown equation. So can we say $L$ is recursive?


texts: How do I show this variant of the longest path problem is NP-hard?

texts:
The problem is as follows:

"Given a weighted graph G and a path p, show that p is the longest simple path in G."

I'm thinking a reduction from HAMPATH would work, but after 3 hours of racking my brain over this, I have no idea how to do it. What makes the reduction difficult is that I'd need to somehow "know" the path, since the input to this longest path variant requires the path along with the graph.

Any tips/hints/help would be appreciated.


texts:
I have two shapes in a 2D space, not necessarily convex, and I'd like to compare how similar they are. How can I define a robust distance metric to measure their similarity, and how can I compute it?

I am looking for a method which provides a short distance in case of:

scaling;
rotation;
perhaps local scaling or rotation.

I see two possible solutions:

transform the shapes into pixel-based matrices (bitmap) and compute a Levenshtein distance (but without enough robustness in the distance, in case of rotation for instance);
transform the shapes into graphs and try to define a distance between them.


texts: Finding an invalid walk order between two nodes when edges have traversal limits

texts:
Given an arbitrary connected graph with a start and goal node, with both directed and undirected edges, where each edge has a maximum number of times it may be traversed during a single traversal (at least 1, at most infinite):

Is it possible to confirm in O(n) time whether or not a walk (possibly with repeating edges and/or nodes) exists such that the walk stops at a node N before reaching the goal due to not being allowed to traverse any of N's edges additional times?

For clarification: I'm wondering if it's possible to traverse the graph in such a way that I end up at a node in the graph that no longer has a path to the goal node (due to the edges along those paths no longer allowing additional traversal). This assumes that at least one walk between start and goal existed when the traversal began.

Example: A graph with edges S~A, A~B, B~C, C~G, C~>A (S = start, G = goal).

If the edge B~C only allows the user to traverse it once, then a valid walk from S to G would be S, A, B, C, G. However, moving from C back to A would prevent the user from reaching the goal since C~>A is directed, and B~C has already been traversed the maximum number of times. I'm looking for a way to confirm the existance of such an invalid walk.


texts: What are good examples of computational theories for A.I. according to David Marr's Definition?

texts:
I was reading David Marr's "Artificial Intelligence-A Personal View" and he talks about "computational theory of AI" or what he laters labels as "Type 1" Theory. He provides the example of Chomsky's notion of "competence theory for English syntax as an example of what he means by that. However, with the current trend of deep learning and modern machine learning, that example seems quite different and very unfamiliar.

Is there a better example with more modern AI like machine learning (or deep learning)? Even if it were at least from 1 layer models like Support Vector Machine (SVM) or Radial Basis Functions Networks (RBFs), but something that was modern? What is an example of type 1 theory in modern AI?


texts:
I ave a a collection of lists of objects:

$a_1$ $a_2$ $a_3$...

$b_1$ $b_2$ $b_3$...

$c_1$ $c_2$ $c_3$..

I need to merge them into a minimal possible number of lists, each list must be as long as possible. The merge does as follows:

For every consequitve pair ($x_i$, $x_{i + 1}$) within the collection, if one or more subsequences ($x_i$, $y_j$, $y_{j + 1}$, ... $y_k$, $x_{i + 1}$) exists, substitute the pair with the longest said subsequence.

After all such substitutions are made, eliminate redundant lists as follows:

for every list $x_1$, $x_2$, ... $x_m$, if for each $j$ the subsequence ($x_j$, ... $x_{j + 1}$ exists in any other list, remove the whole list.

For example, this collection of two list of strings:

"a", "sheep", "grazing"
"a", "young", "white", "sheep"

Is to be merged into

"a", "young", "white", "sheep", grazing"

This is because the subsequence in the second line

"a", "young", "white", "sheep"

can be squeezed between "a" and "sheep" of the first line, while

"sheep", "grazing", end-of-line of the first line can be squeezed between "sheep", end-of-line of the second line.

Likewise, if there is a list A1, ... AN in one of the lines, and another line starts with AN or ends with A1, the substitution is to occur.

However,

"a", "lonely", "sheep", "grazing"
"a", "young", "white", "sheep"

can't be merged into one list, because we don't know whether "lonely" should go before or after "young", before or after "white", etc.

So this case is to be partially merged into

"a", "lonely", "sheep", "grazing"
"a", "young", "white", "sheep", "grazing"

Pseudocode welcome.


texts: Effect of increasing the capacity of an edge in a flow network with known max flow

texts:
I need your help with an exercise on Ford-Fulkerson.

Suppose you are given a flow network with capacities $(G,s,t)$ and you are also given the max flow $|f|$ in advance.
Now suppose you are given an arc $e$ in $G$ and suppose this arc's capacity is increased by one.
Give an efficent algorithm which returns true iff the increase of the capacity of the arc $e$ will allow an increase in the max flow.

I suppose we shouldn't run Ford-Fulkerson again but somehow use the given $|f|$… Any ideas how?


texts:
Given array $A[1..n]$, and black box, and a number $x$. we want to
find out a $i$ such that $A[i]=x$. Our black box have three inputs,
array $A$ and at most $k$ numbers from set $S=\{1,2,...,n\}$, and $x$.
Black box return true if there is $i\in k$ that $A[i]=x$. How we can
show that the number of times we use black box is $O(\frac{n}{k}+\log
k)$?

I think as follow: divide set $S$ to $k$ sets with size $\frac{n}{k}$ and then we use block at most $k$ times. Now if after $k^{th}$ the black box return true the on array $A$ we search an interval with size $k$. So the number of calls are $O(\frac{n}{k}+k)$. But the term $k$ contradict with $\log k$. Any help be appreciated.


texts: How to find the angle of an arc to draw graphic

texts:
I would like to draw an arc from a specific point to a goal point, during the process of drawing a larger path. I would like to do it using bezier curves, which aren't adequate for modeling circular arcs, but these equations found here seem to potentially estimate the arc pretty well (I can't tell if these equations correctly implement the circular arc using cubic Bezier curves (yet), but it seems like a good start). Here is the equations from that link.

start coordinate = {
  x: R,
  y: 0
}

control point 1 = {
  x: R,
  y: R * 4/3 * tan( phi / 4)
}

control point 2 = {
  x: R * ( cos(phi) + 4/3 * tan( phi/4 ) * sin(phi) ),
  y: R * ( sin(phi) - 4/3 * tan( phi/4 ) * cos(phi) ),
}

end coordinate = {
  x: R * cos(phi),
  y: R * sin(phi)
}

So let's say I start with a drawing of a path composed of some stuff, in this case just a few connected line segments (doesn't matter what they are):

Then what we want to do next, from the current point we left off at, is draw an arc. This is what that arc might look like:

You can see that there is a center where we can draw a radius, and a goal point where the arc ends (so it doesn't complete a whole circle).

My question is, how to determine the angle phi (in the equation above). That way I can use the equation. I am not sure what my current orientation is, if it is all relative to a global coordinate space or what. This is for traditional graphics. So need to figure that part out. Let's say it is a global coordinate space and not relative to the direction I moved along the path. Then this would be the angle:

I don't know, I'm already confused. So somehow I need to figure out some angle, which I'm not sure what to do. From there I think I could figure out the rest. Any help would be appreciated.

After the radius is found, then these equations above would take my simple circular arc, and turn it into a cubic Bezier equation so hopefully it could be drawn in an environment that only supports that and not arcs.


texts: How can we prove that in binary search, low – high ≤ 1

texts:
How can we prove that in binary search
$$\mathit{low} - \mathit{high} ≤ 1$$
Below is a sample algorithm for Binary Search.
while (low<=high) {
  int mid = low + (high-low)/2;
  if (data[mid]<value) low = mid+1;
  else if (data[mid]>value) high = mid-1;
  else return &data[mid];
}
return nullptr;

A good stranger told me that

typically you would want to avoid unprotected mid-1 and mid+1 for fear of over- and underflow and have a special case for when the difference between high and low is less than 2.

What I still want to know is a formal proof that $\mathit{low} - \mathit{high} ≤ 1$ provided that you started off with $\mathit{low} ≤ \mathit{high}$.
My idea so far has been to adapt the explanation on loop invariant here but I can assure you I haven't made any progress, yet.


texts: optimal lifted phylogenetic alignment - how to improve time complexity?

texts:
optimal lifted alignment - is a dynamic programming algorithm. Its input is a tree $T$ with $k$ strings assigned to its leaf nodes (their length is $n$).

The algorithm then assigns strings to the internal nodes s.t. the sum of distance (global alignment distance) on all the edges would be minimal, under the constraint that the string assigned to each node is one of the strings of its immediate children (hence the name "lifted").

The algorithm first computes distances $D$ between all pairs $O(k^2n^2)$. For each leaf node $v$ assigned $S_v$ we initialize: $d(S, v) = 0 | S = S_v$ and $d(S, v) = \infty | S \neq S_v$.

We then traverse post-order and for each internal node $v$, for each string $S$ assigned to one of its leaf descendants (all strings in its subtree) does $d(v,S) = \sum{\min(D(S,T) + d(w,T))}$ where $w$ are $v$'s immediate children. Overall = $O(k^2n^2 + k^3)$.

I've been told its possible to improve the complexity to $O(k^2n^2 + k^2)$ but I can't see how? Would appreciate any hint.


texts:
We know how DSU(Disjoint Set Union) can be used to find the connectivity between two users. However, I was wondering if it can be used with a Segment Tree.

Let me explain my idea further. Suppose we have $N$ people, numbered from $1$ to $N$. I have a list of input specifying if two people are friends or not. Running a DSU on the data will tell me if any two people are friends or not. Easy and simple up till here. Now, suppose I have some queries of type, ranges provided in the format $[l_1, r_1]$, $[l_2, r_2]$ up-to $[l_k, r_k]$. I need to answer on the union of these ranges if they all are friends or not.

Now what I thought: Using a bottom-up approach on a Segment Tree, I fill the nodes of the tree with either $0$ or $1$ denoting friends or not-friends. But then I thought that for a query like $[1, 3]$ and 1-based indexing on the Segment Tree, my query will pass as $[1]$ and $[2,3]$ on reaching the bottom of the tree. Now $[2,3]$ will directly return as the tree[node] value but the $[1]$ will pass on to my array that I have used for building the tree. Also, the array should contain a relation between $1$ and ($2, 3$) for proper working of the Tree. Here's when I can't really understand as to how to proceed further.

Maybe the entire idea is wrong and it doesn't really need Segment Trees, or maybe requires more than one Segment Trees. Any help here is appreciated.


texts:
In CMU's HoTT course, lecture 1, which can be found here: https://scs.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=0945cc7f-48b7-4803-81af-e7193a3f461d

At 33:52, Harper was giving parallel comparison between synthetic theories and analytic ones, and when he reached PL theory, he said Coq is analytic and said Coq only proves a language in its grammar but not the parser itself.

I have a strong desire to disagree somehow but I don't have a clear idea why I would want to do that. I believe that Coq is very synthetic, so are any other proof assistants based on dependent type theory, because all these languages do nothing but build programs. We can also express axiomatic algebra in Coq by using type classes for example, and concretize whenever suitable. This pattern is especially the case in Agda.

So my question is, was Harper right? If he's right, which part of my view causes my misunderstanding?


texts: Java, strong typing, covariance and contra-variance

texts:
While studying for a test in my OOP course, I came upon this question which had an answer I didn't really understand. The question is as follows (translated):

The programming language "Sava" is similar to Java in every way except in the following:

It's structurally typed
When overriding a method the argument can be contravariant and the return type can be covariant.

Given the following class and interface, is the following assignment legal?

  interface I{
    boolean equals(I i){…}
  }

  class C{
    boolean equals(C c){…}
  }

I i = new C();

The answer that was given to this question was:
The assignment isn't legal. The equals method in C changes the paramater in a covariant way and so it doesn't match the equals method in I.

At first I thought the professor forgot to add "Implements I" but the answer also stated the following:
Answers that refereed to the fact that C doesn't implement I weren't accepted because given that it's a Structurally Typed language it doesn't matter if it were a subtype.

I'm not sure I understand how we can refer to these methods as covariant / contravariant if there is no relation of subtyping between C and I.

Can anyone clear this up for me?


texts: Find least amount of combinations in multi-dimensional array (php). (Need help with school assignment)

texts:
I’ve got a computer science school assignment which I can’t solve for the past week and it’s driving me crazy!
I hope I’m posting this on the right board.

I need to find the least amount of combinations in “not-so complex” data in php. The answer of course doesn’t have to be in php. Anything helps!

PROBLEM DESCRIPTION:

We need to transport items with least possible vehicles.

There is a multi-dimensional array of items, each has assigned possible vehicles for transport and how much % the item occupies in that vehicle. I need to fit these items in as few vehicles as possible. We can’t fit more items in vehicle if they exceed 100%.

The array looks like this:

$items = [
    item1 => [
        vehicle1 => 50,
        vehicle2 => 30,
        vehicle3 => 60
        ],
    item2 => [
        vehicle2 => 60,
        ],
    item3 => [
        vehicle1 => 40,
        vehicle3 => 60,
        ]
]

So in the example above, just by looking at it, we can see we are going to need 2 vehicles.
item1 + item3 can go with vehcle1 only, because they don’t fit in vehicle3 (it would exceed 100%). Item2 can go only with vehicle2 only.The result in this example is at least 2 vehicles.

The data I wrote here as example is not static. To test my algorithm, there is going to be different data, so I can’t hardcore anything.

The answer doesn’t need to be specifically in php. If you have any idea how to solve this, anything will be huge help for me!

Thanks in advance.


texts: Is there a common unit of measurement for comparison of computing power used to solve mathematical puzzles?

texts:
I just wanted to make sure if I'm reasoning correctly. So, if two computers are solving the same mathematical puzzle i.e. SHA-256 function of Bitcoin (finding nonce that satisfies difficulty target), the computing power used by each of them can be compared in units of Gigahashes, Terahashes etc. and we know which one used more computing power in time.
But what if we wanted to compare computing power (herein called "CP") used by two computers in time t if those two computers were solving different hash functions (e.g. one SHA-256 and one SHA 3-512) or different mathematical functions altogether?
Could we then denominate computation power used by Computer 1 and 2 to reach a conclusion that in time t:
Computer's 1 CP > Computer's 2 CP
and by how much? And what would be that proper and best denominator (FLOPS, MIPS, IPS..)?


texts: Push-down automaton for a language with number of 1s double than 0s

texts:
This questions is taken from a complexity theory course.

  Design a push-down automaton that recognize $L = x \in \{0,1\}^* $
  such that $x$ contains a number of ones double than a number of zeros.

Example: x = 011011, 100011111, 011011110.

My approach

I tried to push on the stack a symbol "A" every time I read "0", than pop "A" from the stack when I read two consecutive "1" but this approach works not for every string $x$ in the language. Maybe the final PDA is non-deterministic. Any hints?


texts:
Suppose I have an $n\times n$ matrix. I would like to keep an $m\times m$ subblock undiagonized, while keeping the rest diagonized. Is there any algorithm for this?

More precisely, I mean using unitary matrix $U$ to realize

$$  U^* \pmatrix{ A & B \\ C & D }  U =  \pmatrix{A' & 0  \\ 0 & D'  }   $$ where submatrix $A'$ is diagonal, and $D' \approx D$.


texts: Representation of used space and free space in hard drives

texts:
I've read from this How data is physically stored in hard drives, that the North/South orientation of the magnetic medium represents data as 0 or 1 physically in the hard drive. Data is stored in binary, which means that it can be stored as either 0 or 1 in the hard drive. But what determines if that particular block of memory in the hard drive is "Used Space" or "Free Space".

In the OS, you can view how much memory is used, and how much is free.

Let's say i have a 1 TB hard drive. I stored 100 GB worth of data with the repeating pattern "1100 1100". This means that I have 100 GB of used space and 900 GB left of free space (does it?). How does it know that it is used or free? If both 1 and 0 can be used to represent the data in that block of memory, then what represents as a "Free Space"? What if i delete 50 GB of data? I'll have 50 GB more free space, but what represents this free space? And how is the data 1 or 0 of "Used Space" converted to "Free Space"?


texts: How does FDS (flat datacenter storage) make optimizations around locality unnecessary?

texts:
I was reading the following computer systems paper:

https://www.usenix.org/system/files/conference/osdi12/osdi12-final-75.pdf

And I was trying to understand why it claims that it does not need data locality for it be perform well.

Basically, in the abstract it says:

"...FDS multiplexes an application's large scale I/O across the available throughput and latency budget of every disk in a closer. FDS therefore makes many optimizations around data locality unnecessary."

What I was not sure was, why does multiplexing an applications I/O across the servers in the datacenter, make it unnecessary to have to optimize in terms of data locality?

Basically, as I read the paper they make a big deal that locality is something they don't need and that they can achieve the benefits of it without having servers being close to the clients they provide data access. The part I am not sure is, what is the crux of what makes them not depend on data locality? Is it the CLOS network? Is it because they don't serve clients around the world? Is it because their servers are all in one data center anyways and not scattered around the world? What is it that makes their performance be so amazing?

Paper Reference:

Title: Flat Datacenter Storage

Author(s): Edmund B. Nightingale, Jeremy Elson, Jinliang Fan, Owen Hofmann, Jon Howell, Yutaka Suzue

Institution(s): Microsoft Research, Univeristy of Texas at Austin


texts: TF IDF Spark values are small after cosine similarity

texts:
I am creating a software that computes the cosine similarity between 2 strings.

I am using Spark as I have to use Java. I created a Bag of words model and computed the cosine similarity successfully.

Feeding the same sentences to the software and substituting the bag of words model with a TF-IDF the similarity between sentences took a hit. Some similar sentences became not similar.

Example

"a b c"

"a a b c d"

Cosine similarity using Bag of words is 0.871

Cosine similarity using TF-IDF is 0

Is this behavior correct or am I doing something wrong?


texts: Introduction To Algorithms 3rd Edition MIT Press: Red Black Tree insertion error in pseudo-code?

texts:
I'm implementing the algorithm on page 316 of the book Introduction to Algorithms. When I look at the pseudo-code, I feel that there is something wrong between line 10 to 14. I feel it's missing a check. There is a YouTube video explaining this whole function (and it includes the pseudo-code plus line numbers): https://youtu.be/5IBxA-bZZH8?t=323

The thing is, I think that //case 2 needs its own check. The else if z == z.p.right is both meant for //case 2 and //case 3. However, the code from //case 2 shouldn't always fire. It should only fire when there is a triangle formation according to the YouTube video. In my implementation it always fires, even when it's a line.

So I feel the pseudo-code is wrong, it's also weird that it has an indentation, but I see no extra check.

Am I missing something?

Maybe superfluous, but I also typed the pseudo code given from the book here:

RB-INSERT-FIXUP(T, z)
  while  z.p.color == RED
    if  z.p == z.p.p.left
      y = z.p.p.right

      if y.color == RED
        z.p.color = BLACK   // case 1
        y.color = BLACK     // case 1
        z.p.p.color = RED   // case 1
        z = z.p.p           // case 1

      else if z == z.p.right
          z = z.p           // case 2
          LEFT-ROTATE(T, z) // case 2
        z.p.color = BLACK   // case 3
        z.p.p.color = RED   // case 3
        RIGHT-ROTATE(T, z.p.p) // case 3

    else (same as then clause with "right and "left" exchanged)

  T.root.color = BLACK


texts: Big Theta for finding combinations of arbitrarily sized subsets from n total elements

texts:
Given n elements, where the n elements are grouped into arbitrarily sized subsets, what is the Big Theta (tight bounds) of outputting all permutations of items from each subset?

Assume the elements are all unique.

For example:

n=2, `a b` there are two cases.
`(a), (b)` which has one permutation 1: `a, b`
`(a, b)` which has two permutations 1: `a`, 2: `b`

And then for a larger n:

n=3, `a b c` there are three cases.

3 subsets of 1 element: 1^3 permutations
`(a), (b), (c)` which has one combination 1: `a, b, c`

1 subset of 2 elements and 1 subset of 1 element: 2^1*1^1=2 permutations
`(a, b) (c)` which has two combinations 1: `ac`, 2: `bc`

1 subset of 3 elements: 3^1=3 permutations
`(a, b, c)` which has two combinations 1: `a`, 2: `b`, 3: `c`

Basically for a given n its the maximum value of S1*S2*S3... where S# is the size of subset #.

It's easy enough to demonstrate that big lambda is 2^(n/2).

And I think that 3^(n/3) may be a big omega.

I've been mulling this problem over for a little while now, if it's a known problem then I'd love to be pushed towards the right solution, but I've found that it's a bit difficult to search for.


texts: Method for Creating Any Unambiguous Grammar?

texts:
I'm in an undergraduate class where we're studying formal grammars right now. I asked my teacher if there was any known set of rules for creating context free grammars that

Was guaranteed to produce an unambiguous grammar.
Allows for the creation of any possible unambiguous grammar.

I am well aware that determining whether a grammar is ambiguous is undecidable. I'm not sure if the above stated idea is reducible to that, but after fiddling around with it a bit, I couldn't think of a method for making such a reduction. That said I'm really no expert at reductions or grammars. I tried googling for a while, but I only found pages about undecidability. Does anyone know?


texts: What are the requirements for a superset of P to be closed under karp reductions?

texts:
So today in our exercise session on complexity theory we discussed that P, NP, and BPP are closed under karp reduction. We also figured that the proofs could likely be expanded to straight generalizations of these three "classes of classes" (nondeterministic, deterministic, probabilistic) like EXPTIME.

This, to us, begged the question:

Suppose you have a class of languages $C\supseteq P$, what are neccessary (and sufficient?) conditions for $C$ to be closed under karp reduction?

Terminology:

A language $A$ is karp-reducible to another language $B$, written $A\leq_m B$ iff $\exists $deterministic poly-time turing machine $K_{A,B}:\forall x\in\{0,1\}^*: x\in A\iff K_{A,B}(x)\in B$ holds.
A class $C$ is closed under $\leq_m$ iff $\forall B,A\subseteq \{0,1\}^*: B\in C\land A\leq_m B\implies A\in C$ holds.


texts:
What are the largest classes which are low for EXP and NEXP?

For example: I am aware the class P, QP are low for EXP as well as NEXP. We also know that NP is not low for either of them.

Is class BPP low for EXP or NEXP? What is the largest oracle class we can provide to EXP (or NEXP) which doesn't increase its power?


texts: Is there a better-than-brute-force algorithm to generate a graph whose relation is string edit distance=1?

texts:
I'm interested in creating a graphs whose vertices are strings, and whose edges represent the relation of having an edit distance of 1 under a given string metric.

An obvious approach is to make all $\frac{n^2-n}{2}$ comparisons among the $n$ vertices, giving us $O(n^2)$ time complexity.

Excluding parallelizing the comparisons, is there a better algorithm in terms of time complexity?

I'm interested in string metrics where strings of different length are allowed.


texts:
I came across this description of Batch Interface:
"commands and directives are used to manage those commands that are entered into files and those files get executed. "

I would really appreciate if someone explains in detail what Batch Interface is and how it's different from Command Line Interface?


texts: min vertex cover to access k edges in a tree

texts:
I need to find the minimum number out of $N$ vertices on a tree with $N-1$ edges, so that at least $K$ edges of that tree are connected to these vertices.

For example, if $N=9$ and $K=6$ and we have this tree:

   Edges  |  Vertice #1  | Vertice #2
     1            1          2
     2            1          3
     3            1          4
     4            2          5
     5            2          6
     6            3          7
     7            4          8
     8            4          9

The right answer should be $\mathrm{min}=2$.

Any thoughts?


texts: Machine Learning: Identify Patterns in Time-Series Data

texts:
I work in renewable energy. My company gathers a lot of data from equipment. This typically includes process data (such as transformer temperature, line voltages, currents, etc.) and discrete alarms (e.g. breaker trip, inverter alarm values, transformer over temperature alarm). This is a rough example of what our data looks like (to be read as lines of csv):

timestamp, tag, value
5/25/2016 14:30:01, INVERTER_1.VOLTAGE_DC,
249.5
5/25/2016 14:30:06, INVERTER_1.VOLTAGE_DC, 250.1
5/25/2016 14:45:02, TRANSFORMER_1.TEMP_ALARM, 0
5/25/2016 14:45:15, TRANSFORMER_1.TEMP_ALARM, 1

I'd like to start performing some pattern analysis on this data at rest, not real-time (at least for now). I believe what I'd like to attempt is unsupervised feature learning, but I'm not entirely sure. It would be nice (I think) to apply machine learning to 1) identify any patterns that aren't obvious and 2) allow an algorithm to identify signatures of patterns in the data (e.g. all inverters on a single feeder lose communications when a breaker is open).

My initial question: Is this considered time-series data? In my research so far it seems that time-series data is referencing data that is a function of time. For most of my data, as a domain expert, I don't believe that defining functions for my data is useful for this analysis. Also, in my research, it seems as though time-series data refers to real-valued values and not discrete.

Any comments or relevant references would be helpful.


texts:
I'm refining my understanding of the connection between initial algebras and datatypes. This paper suggests that one could even represent the categories corresponding to datatypes definitions:

as follows:

Where $1$ is the terminal object of the category.

My question is, how can I justify that $1$ is the terminal object of the category? Do I have to postulate that any type has a unique morphism to $1$? This morphisms would be different that the datatype definitions which would not be nice...


texts: Find a permutation that maximize the minimum of $\frac{a_n}{a_{n-1}} + \frac{a_n}{a_{n+1}}$

texts:
Consider a sequence of $n$ positive real numbers $a_0,\ldots,a_{n-1}$. Let $S_n$ be the set of permutations on $\{0,\ldots,n-1\}$.

We are interested to find

$$
\max_{\pi\in S_n}\left( \min_{i=0}^{n-1}\left( \frac{a_{\pi(i)}}{a_{\pi(i-1)}} + \frac{a_{\pi(i)}}{a_{\pi(i+1)}}\right)\right)
$$

The addition and subtraction in $\pi$ is under mod n.

It might be easier to consider the more general problem, where $b_0,\ldots,b_{n-1}$ is a sequence of positive real numbers.

$$
\max_{\pi\in S_n}\left( \min_{i=0}^{n-1}\left( a_{\pi(i)}(b_{\pi(i-1)}+b_{\pi(i+1)} )\right)\right)
$$

Is this problem $NP$-hard? I feel this problem is $NP$-Hard but I don't see any obvious reductions.

The greedy approach: sort the numbers, then insert them one by one into the list such that it maximizes the minimum of the sum of quotients. Turns out to be not optimal.

Greedy Smallest First
[5, 4, 4] 1.8
[5, 5, 4, 4] 1.8
[5, 5, 5, 4, 4] 1.8
[5, 9, 5, 5, 4, 4] 1.5555555555555556
Greedy: [5, 9, 5, 5, 4, 4] 1.5555555555555556
Best: [4, 5, 4, 5, 9, 5] 1.6

Greedy Largest First
[5, 22, 20] 0.4772727272727273
[4, 5, 22, 20] 1
[4, 4, 5, 22, 20] 1.2
[4, 3, 4, 5, 22, 20] 1.4772727272727273

Greedy: [4, 3, 4, 5, 22, 20] 1.4772727272727273
Best: [3, 4, 5, 20, 22, 4] 1.5


texts: Translating the in-order index of a node in a complete, balanced binary tree into the level-order index

texts:
Consider the topmost part of a complete, balanced binary tree of all 64-bit numbers, exemplified here.
As highlighted by the lack of a 7*2^64/8 term it is not necessarily full, but it is always complete. The nodes are stored in numerical order (in-order) in a list of which I know the size, and I have the index (call it the in-order index) of a node in that sorted list.
I'm trying to get the index (call it level-order index) of that same node if the array was stored according to the breadth-first traversal order (level-order) of the tree instead. In the example, the tree root would have level-order index 0 and in-order index 3.
What I've found already is that the level-order index consists of two parts:

A base part which is the amount of nodes contained in the perfect tree above the level in which the node resides.
An offset part which is the amount of nodes to the left of this node in the level in which it is contained.

Summed together, they produce the level-order index.
I have no idea how to find either of these parts from the in-order index. Of course, it is possible by iterating the tree programmatically, but since the exact layout and contents of the entire tree are known simply from the amount of nodes that it contains, I was wondering whether a mathematical relation between these two indices holds. Does anyone have an idea?


texts: Why do we use different cost functions in machine learning?

texts:
In most machine learning applications, we use Maximum Likelihood Estimation to derive appropriate cost functions. For example, if we assume that our model $f(x;\theta)$ yields the mean of a multivariate normal distribution (i.e. $p(y|x;\theta) = \mathcal{N}(y;f(x;\theta),I)$), we will obtain the mean squared error (MSE) $$ MSE(\theta) = \sum_{i=1}^M || y_i - f(x_i ;\theta)||^2. $$
Similarly, if we suppose that $f$ models the parameter of a bernoulli-distribution (i.e. $p(y|x;\theta) = \mathrm{Be}(y;f(x;\theta))$), we get the cross-entropy-loss (CEL): $$ CEL(\theta) = -\sum_{i=1}^M y_i \log f(x_i;\theta)+(1-y_i) \log(1-f(x_i;\theta)).$$
Assuming that the model is powerful enough, we obtain

$f(x_i;\theta^*) = y_i$ for all $i=1,\dots,M$ iff
$\theta^* = \arg\min_{\theta \in \Theta} MSE(\theta)$ iff
$\theta^* = \arg\min_{\theta \in \Theta} CEL(\theta)$.

My question is: do we have any theoretical justifications on why we use different cost functions other than "it was derived using MLE"? For example, what exactly makes the CEL a better fit in certain scenarios than the MSE?
Edit: just to clarify a few points. If we make the assumption that our model is generally powerful enough (i.e. there is such a $\theta^*$ as described above), then why shouldn't we use the same cost function everywhere if the set of minimizers is the same?


texts:
Generating a Gray code representation of a binary number can be thought of as mapping one binary number onto another binary number. Therefore, $n$-bit Gray code is a permutation of $2^n$ elements.
What would be an efficient way to generate the corresponding permutation matrix (having sparsity 1)?
A brute-force solution would be to go through all the integers from $0$ to $2^{n-1}$, converting each of them from binary to Gray using smth like
def convert_gray(binary):
   binary = int(binary, 2)
   binary ^= (binary >> 1)
   return bin(binary)[2:]

considering each outcome as a binary, and filling the corresponding matrix entry.
I am wondering if there exists a faster and a more compact solution?


texts: Classification accuracy based on top 3 most likely classifications

texts:
My goal is to recommend jobs to job seekers based on their skill set.

Currently I'm using an SVM for this, which is outputting one prediction, e.g. "software engineer at Microsoft". However, consider this: how significantly different are the skill sets of a software engineer at Microsoft and a software engineer at IBM? Probably not significantly different. Indeed, by inspection of my data set I can confirm this. Hence, the SVM struggles to discriminate in situations like this, of which there are many in my data set, and my classification accuracy is about 50%.

So I had an idea.

In SK Learn, once you've trained some model, you can compute the probability a particular input X belongs to each class.

So for each input X in my test set, I took the the top 3 most likely classifications. Then I tested whether or not the correct label was in the top 3 predictions. If it was, then I considered the prediction to be correct. In doing so, the classification accuracy increased to over 80%.

So my question is: is this a valid approach to measuring classification accuracy? If it is, then does it have a name?

In my mind, it is valid given my intended application, which is to recommend a selection of jobs to a job seeker, which are relevant to their skill set.


texts: Transforming 3 SAT to Simultaneous In-Congruence Problem?

texts:
Garey and Jhonson mentions that a 3-SAT Problem can be transformed to another NP-Complete Problem - Simultaneous incongruences (AN2):

Given a collection $[(a_1,b_1),…,(a_n,b_n)]$ of ordered pairs of positive integers with $a_i≤b_i$ for $1≤i≤n$, is there an integer $x$ such that for all $i$, $x≢a_i(mod\ b_i)$?

But I am struggling with the transformation and not much clue how to go about it nor can find any literature on it. Thus, needed help with the transformation?


texts: substitution method - proving karatsuba algorithm is not O(n)

texts:
I want to prove that $T(n) \neq O(n)$ for the Karatsuba algorithm, which has the following recurrence:
$$ T(n) = \begin{cases} k_1, & \text{if $n$ = 1} \\
3T(n/2) + k_2n, & \text{if $n \gt$ 1} \end{cases} $$
where, $k_1$ and $k_2$ are constants, such that $k_1 \gt 0$ and $k_2 \in \mathbb R$.
So, to prove that $T(n) \neq O(n)$, I did the following:
Inductive hypothesis: $ \exists c, n_o \gt 0$ such that $ T(n) \leq cn \quad, \forall n \geq n_o $
Base case: at $n = 1$, we get the following constraint: $T(1) = k_1 \leq c $, which holds for $ c \geq k_1$
Inductive case: assuming that $T(n/2) \leq {cn\over2}$, we have
$$
\begin{align}
T(n) \quad &\leq 3({cn\over2}) + k_2n \\
&= cn + ({c\over2} + k_2)n \\
\end{align}
$$
But, for $cn + ({c\over2} + k_2)n \leq cn$ to hold, ${c\over2} + k_2 \leq 0 $. Although, this inequality doesn't hold for $k_2 \geq 0$ (since $c > 0$), it does hold if $ c \leq -2k_2$ and $k_2 < 0$.
Hence, I am having difficulty concluding that $T(n) \neq O(n)$. Is there anything wrong with the induction? And also, then how to prove that $T(n) \neq O(n)$?


texts: If L is not regular and is a proper subset of L1, does it follow that L1 is not regular?

texts: If $L$ is not regular and $ L \subset L_1$, does it follow that $L_1$ is not regular also? Can you please provide an explanation? Thanks in advance.


texts:
I have a search operation taking place on a server that essentially queries images using OpenCV against other images from a database. Since each image query operation is quite expensive computationally, I want to find a good way to sort the images in the database to compare them in a good order. I want the program to be more likely to find a good match early and less likely to have to try all the images in the database to get a match. I suspect there would be strong correlations between data about the user carrying out the search (such as his age, gender, location, etc...) and the likelihood of him searching for a particular image, taking into account the history of users who successfully searched for this image and their data.

I was thinking this could be achieved with a neural network, however, I haven't found anything online about doing such type of sorting with one. Maybe I could use some type of machine learning to create a score for each item in the database and then use conventional sorting. Could you kindly recommend what might be a good approach to this?


texts: What is an upper bound of T(n) = 2 T(3n/10) + T(4n/10) + n

texts:
if assume that T(n) = 2T(3n/10) + T(4n/10) + n <= cnlogn

T(n) <= 6cn/10 * log(3n/10) + 4cn/10 * log(4n/10) + n
= cn/10 * (6(log3 + logn - log10) + 4(log4 + logn - log10)) + n
= cn/10 * (10logn - 10log10 + 6log3 + 4log4) + n
= cnlogn - cn/10 * (10log10 - 6log3 - 4log4) + n <= cnlogn

because (10log10 - 6log3 - 4log4) > 0, there exists c that satisfy the equation.

I think it is the tight upperbound because I failed when I assumed the T(n)<=cn
so I think that upper bound of T(n) = O(nlogn)

am I doing right?


texts:
I was asked to sort several functions by their asymptotic growth. I was docked a couple points for incorrect ordering and the correct solution was never provided. For what it's worth, this assignment has already been graded, I'm just wondering where I went wrong.

(None $\sim$ indicates functions have similar asymptotic growth)

$1 \ll lg\:lg\:n \ll ln\:n \sim lg\:n \ll (lg\:n)^{2} \ll \sqrt{n} \sim \sqrt{2}^{lg\:n} \ll n \ll n\:lg\:n \ll n^{1+\epsilon} \ll n^{2}+lg\:n \ll n^{3} \ll n-n^{3}+7n^{5} \ll 2^{n-1} \sim 2^{n} \ll e^{n} \ll n!$


texts: Need help optimizing the loading of passengers on small airplanes

texts:
I work for a small non-profit that provides transportation for people who need medical treatment. We connect volunteer private pilots who fly people in their own (small) aircraft, typically 3-5 seats.

Several times each year, we provide flights for kids to go to special needs camps. In this scenario, we have a number of kids (say 20-30) going from multiple origins to one destination, and several pilots who have expressed an interest in flying one of the routes. We'd like to create an algorithm to optimize the loading and travel of each aircraft. The number of seats is a constraint, in other words, we can't have more passengers than there are seats. Optimizing loading would mean (I think) minimizing the difference between the airplane's load capability and the total weight of the passengers. A second factor would be how far the pilot would need to go out of their way to complete the trip, based on where the plane is based. For that, we can look at a multiple of the trip distance. So, if the plane is based at either the origin or the destination of the route, the multiple would be 1 (total distance divided by trip distance), whereas the multiple will grow the more they have to go out of their way.

I'm a programmer and not a mathematician, and I would love to have any guidance anyone is willing to provide as to an approach.


texts:
The following formulas are said to be defined in WS1S logic.

$Closed(Z, R) := ∀x ∀y(x ∈ Z ∧ R(x, y) → y ∈ Z)$
$(z_1, z_2) ∈ R^∗
:= ∀Z.(z_1 ∈ Z ∧ Closed(Z, R) → z_2 ∈ Z)$

However since WS1S formula requires bounded second order variables to be finite, I am not sure if the second formula is valid. $Z$ which is bounded here, can be an infinite subset of natural numbers. For example, when $R$ is a $succ$ relation.

There are no restrictions on $R$ stated in the reference.

In the paper Implementing WS1S via Finite Automata by James Glenn and William Gasarch :
$∀X∃Y ∀z(¬(z ∈ X) ∨ (z + 1 ∈ Y ))$ is stated to be a valid WS1S formula.
$∀x∃y(y < x)$ is stated as an invalid WS1S formula.

However if $X$ is finite in the first formula, $Y$ is infinite and hence I think this should not be a valid formula. In the second formula there are no second order variables and therefore it should be a valid formula. Please let me know what am I missing here.


texts: Given this transition system, for which states are these (very basic) LTL formulas fulfilled?

texts:
I missed a lot of lectures for this module due to surgery so I'm trying to teach it to myself now. This is the question I've been working on:

First of all, would I be correct in saying that the LTL formulas are b, c and e? CTL are a, d and f?

For (b) I'm guessing the answer is s1 and s3, since those are the only states with b in them.

Looking at (e), this says that the state must always contain b or a, so the answer is s1, s2, s3 and s4  (all states). Is this correct?

(c) is the one I can't get my head round. What exactly is it saying in english?

For now I'll just focus on the LTL stuff, so I just want to get b, e and c 100% correct. Any help is highly appreciated since I'm struggling a bit with this module.

Many thanks in advance!


texts: Are all possible programming languages a formal system?

texts:
Based on the Wikipedia page for a formal system, will all programming languages be contained within the following rules?

A finite set of of symbols.

(This seems obvious since the computer is a discrete machine with finite memory and therefore a finite number of ways to express a symbol.)

A grammar.
A set of axioms.
A set of inference rules.

Are all possible languages constrained by these rules? Is there a notable proof?

EDIT:

I've been somewhat convinced that my question may actually be: can programming languages be represented by something other than a formal system?


texts:
When we talk about DFA, we say that each new character from the input requires one memory access. What does that mean?

This is what I think about this. Please tell me is this right?
For example, I have a transition table stored for a certain regular expression in memory (RAM). Now, for each input character the CPU will fetch the whole transition table to find out the next state. In this way, we have just one memory access?


texts: Reduction from Vertex Cover to Dominating Set

texts:
I am trying to reduce the vertex cover (decision) problem to the dominating set (decision) problem in order to prove that the latter is NP-hard. After some research online, I found that many articles use a reduction that transforms the input for the vertex cover problem to an input for the dominating set problem by creating a triangle for each edge. Here is one of such articles (See question 7 in the link).

The question that I would like to ask is, if we drop isolated vertices in the input to the dominating set problem, then, we could easily find a counterexample to the reduction - Let the input to the vertex cover problem be a graph containing $N$ isolated nodes and parameter $k=N$. Now, the input to the dominating set problem will clearly be an empty graph with the parameter $k=N$. Now, there is a vertex cover of size $N$. But it is not a dominating set of the transformed graph (i.e. the answer to the vertex cover problem is yes but the answer to the dominating set cover problem is no).

How could I fix the reduction? Could someone please advise me?


texts: kPDA handling multiple epsilon transtions

texts:
I'm assigned to build a kPDA with 2 stacks that handles {w#w, where w is a string of (0,1)*}. I understand the # delineates the two strings, but I'm unsure of the logic when popping off stacks with epsilon. I asked my professor, verbally, if this works and he told me no, but I can't think of any other way.

EDIT: Here is the full machine:


texts: Algorithm for Items Best Fit/Arangement in a Box

texts:
I was looking for an algorithm that will give the best fit arrangement of package items in a box. For example given a large box and various items with multiple shapes(can be rectangle, square and so on and so forth), how will I arrange the items so that it will fit in the box? DO we have already an algorithm for that? If yes, what algorithm is it?

If no, I was thinking of making an algorithm for it.


texts: How can a problem be undecidable yet enumerable?

texts:
How can something be enumerable but be un-decidable ie, this states the halting set is un-decidable and enumerable. Enumerable means it can be computed, ie has the same cardinality as natural numbers and can be computed by a program with an output. But if thats the case it should be decidable. Or is decidability separated from computability?

Am I misunderstanding the intuition of the halting set?


texts: Simple algorithm to select separated points in closed intervals

texts:
Within the internal logic of a feature I'm working on, I've run into a need for a solution to essentially this problem:

$S$ is a finite union of $K \geq 1$ closed intervals,

$$S = [a_1,b_1] \cup \cdots \cup [a_K,b_K].$$

Select $N \geq 2$ points $x_i \in S$, maximizing the smallest difference between any pair of points:

$$\Delta = \min_{i \neq j} |x_i-x_j|.$$

In my case, the intervals are already disjoint and sorted ($a_1 \leq b_1 < a_2 \leq b_2 < \ldots  < a_K \leq b_K$), and solutions are only needed for "small" cases: $K$ and $N$ will both typically be 10 or smaller, and $K+N$ can never be more than 30.  Since the numbers are small, it's more important to have a simple and maintainable solution than one with the best possible asymptotic computational complexity, though it's probably good to avoid an exponential- or factorial-time solution if reasonable.

What is a straightforward and effective algorithm for this problem, given these limits on the interval and point counts?

I did notice this existing question about the same problem, but it's asking about asymptotic complexity and about the effects of having overlapping intervals vs. intervals already normalized to disjoint ones. (Also, it currently has no answers.) Since it mentions linear programming, distance constraints, and Bellman-Ford, I looked into those on Wikipedia. But not being very familiar with those topics, I didn't really see how the problem translates into a graph path optimization problem. And I suspect implementing this sort of algorithm might be more complicated than I really need in my case.

I have worked out how to reduce the problem from selecting real/rational values to selecting natural number parameters: If $C_i$ of the points are to be chosen from interval $[a_i,b_i]$, then

$$\sum_{i=1}^K C_i = N \\
\Delta = \min_{1 \leq i \leq j \leq K} \frac{b_j-a_i}{-1+\sum_{\ell=i}^j C_\ell},$$

ignoring the terms with denominator $0$ or $-1$.  And the point coordinates of a valid solution can be determined from knowing which of the ${K\choose 2}$ fractions in this $\Delta$ expression are exactly equal to $\Delta$.

So the dumbest brute force approach would be to find $\Delta$ for each of the ${{K+N-1}\choose{N}}$ possible partitions of $N$ into $K$ ordered buckets. One obvious improvement: $a_1$ and $b_K$ can always be two of the selected points. But that's probably way too many possibilities even with $N$ and $K$ just around 10.

It seems like some sort of "divide and conquer" strategy might be helpful, with splitting the sequence of intervals into two parts, deciding how many points in total to assign to each part, and solving those two subproblems, probably iteratively. But I haven't entirely determined the conditions that would make those subproblems produce valid answers to the larger problem.


texts: Find a regular grammar that generates words with even number of a's

texts:
I have a language $L$ = {$vabu$ | $v$,$u\in \{a,b\}^*$, $|vu|_a = 0$ $($mod $2)$$\}$

where $|vu|_a$ is number of $a$ in $vu$.

I came up with these rules:

$\sigma \rightarrow aa\sigma | ab\xi$

$\xi \rightarrow aa\xi | \epsilon$

This generates words in form: $(aa)^iab(aa)^j\epsilon$, but not all words in $L$ look like this.

How do I make sure that $b$s can be put anywhere in between $a$s in $v$ and $u$.

Edit: I think I found a solution.

$\sigma \rightarrow b\sigma$ | $a\alpha$ | $ab\gamma$

$\alpha \rightarrow b\alpha$ | $a\sigma$ | $ab\eta$

$\gamma \rightarrow b\gamma$ | $a\eta$ | $\epsilon$

$\eta \rightarrow b\eta$ | $a\gamma$


texts: How to modify Floyd-Warshall algorithm with space $O(V^2)$ with tracking actual path?

texts:
The Naive way to reduce space complexity of Floyd-Warshall algorithm is consider only $d_{ij}^{(k)}$ and $d_{ij}^{(k-1)}$ in each time.

But in this case, we can't track actual shortest path with knowledge only two $d$ tables. It requires whole table.

There is a nice solution: Johnson's algorithm reduce both time and space complexity. (Especailly space complexity is $O(V^2)$) .

But I want to know can we apply simliar trick to Floyd-Warshall algorithm  as Divide and Conquer trick in Sequence Alignment problem.

The crux part of Divide and Conquer trick in Sequence Alignment is 'we can reverse recursive relation into center'.

But in recursive relation in Floyd-Warshall algorithm, its recursive relation seems to be it has no such property.

Is there any other technique to apply such reducing space complexity that can track actual shortest path?

Edit: Also I want to retain time complexity $O(V^{(3+\epsilon)})$.


texts: Is a Turing Machine a Well-formed formula?

texts:
Today i wrote something about the bijection between turing machines and recursive functions. And i describe a Turing Machine as a Well-formed formula because it seems like a WFF to me.
But is it correct when we say that a Turing Machine is a WFF ?


texts: Decidability algorithm, whether substring belongs to L

texts:
It isn't very hard to decide if word belongs to language L. CYK algorithm should do here.

Occured thought, can CYK be modified to detect if all words of language L contain some specific subword?


texts: When are Dynamic and Lexical Scoping equivalent?

texts:
I am designing a small DSL and I know that implementing dynamic scoping (with a simple global stack) is easier then using full lexical scoping (each function needs its own scope/closure). What kind of features can be added that do not care how scope is implemented and what features would require a particular kind of scope implementation?

For example, if I have a very simple language that does not allow nested functions or function arguments I feel that both implementation choices are likely equivalent. On the other end of the spectrum, if I wanted to support returning inner functions then I'm pretty sure we would need to allow functions to save their own closures. However, I am not really sure what would happen in the middle if say, I alowed nested functions while not allowing them to be returned or if I allowed functions to be passed as arguments to other functions.


texts: Face recognition system with a sparse dataset

texts:
I have a dataset of 100 ID's, each ID with only a single unique face image. How can I develop an effective face recognition system to recognise only these faces?

I was thinking Deep Learning but the dataset is so sparse. It would be 100 classes each with a single data point (the image).


texts: When the stall is actually going to happen?

texts: Suppose in a 5 stage pipeline when the stall will actually happen if there is a RAW hazard? The stall will start after Instruction Fetch(IF) stage or Instruction decode(ID) stage? In few cases I see that the stall start after IF that is before executing ID and in multicycle pipeline, the stall starts after decode stage (ID). Can someone please clarify it?


texts: Construct a DFA with reduced states equivalent to 10 + (0 + 11)0*1

texts:
I have found this question in a book. I could convert it into its equivalent DFA. But the problem is with the "reduced state" part. I think the answer given in the book is wrong. What would be the DFA with its reduced states? I am giving the converting steps for reference:

The reduced DFA as given in the book:

So, what should the DFA with reduced states look like?


texts: Predict binary occupancy vector from history of vectors

texts:
I have a set of binary vectors where each vector represents one day of occupancy in a house and consists of 48 elements (each element for 30 minutes of the day). Each element can be 1 meaning that house was occupied and 0 for non occupied house.

My task is to predict the next day based on the history of the same days (Monday from history of Mondays etc.). So far I am using hamming distance to find 5 most similar days in the history and from them I calculate the probabilities of the occupancy as a mean of those 5 numbers. When the probability is higher than some X, in my case 0.4, I predict it to be occupied.

But there is definitely some more efficient way to do this, any algorithms that would capture the trend in the history?


texts: Simulating a probability of 1 of 2^N with less than N random bits

texts:
Say I need to simulate the following discrete distribution:

$$
  P(X = k) =
\begin{cases}
\frac{1}{2^N}, & \text{if $k = 1$} \\
1 - \frac{1}{2^N}, & \text{if $k = 0$}
\end{cases}
$$

The most obvious way is to draw $N$ random bits and check if all of them equals to $0$ (or $1$). However, information theory says

$$
\begin{align}
S & = - \sum_{i} P_i \log{P_i} \\
  & = - \frac{1}{2^N} \log{\frac{1}{2^N}} - \left(1 - \frac{1}{2^N}\right) \log{\left(1 - \frac{1}{2^N}\right)} \\
  & = \frac{1}{2^N} \log{2^N} + \left(1 - \frac{1}{2^N}\right) \log{\frac{2^N}{2^N - 1}} \\
  & \rightarrow 0
\end{align}
$$

So the minimum number of random bits required actually decreases as $N$ goes large. How is this possible?

Please assume that we are running on a computer where bits is your only source of randomness, so you can't just tose a biased coin.


texts: Prove that characteristic function $f_w$ in write protected input turing machine behave as a 2FSA

texts:
Write protected input turing machine is a single-tape TM that cannot write on the input portion of the tape. I almost prove that these TMs can only recognize regular languages but i have a problem in one of my steps.
In one step of proof i define a characteristic function $f_w$  such that for any $q \in Q, f_w(q)=q’$ implies that if TM $M$ is at state $q$ just before going back to input portion, the next time that going out from the input portion will change $M$ in satate $q’$ unless we halt inside the input portion.
Now what i need to prove is that for any two string $w_1$ and $w_2$ if for every $q \in Q$ we have the same value for $f_{w_1}(q)$ and $f_{w_2}(q)$ then for every $z \in \Sigma^*$ we have $f_{w_1z}(q)=f_{w_2z}(q)$
It is sensible for me and i have some idea to prove this , one of my idea is that if i can prove for every $f_w(q)$ there is a 2FSA then appending one character to $w$ leads us to a same equivalance class.
Am i in the right path ?


texts: Is it standard for VMs to run *= computationallyHeavyFunction() if the left hand side is 0?

texts:
What is the standard way for VMs to deal with 0 *= computationallyHeavyFunction()? Given that once the VM sees that left hand factor is 0, it would know that the result of computationallyHeavyFunction() would not matter, is it standard for VMs to still compute computationallyHeavyFunction() or do they tend to omit that computation and just evaluate as 0?

Edit: After answer, I think I misphrased the question. I'll rephrase a bit and replace computationallyHeavyFunction() that has unknown factors. If VMs see 0 * (1-1/veryLargeNumber)^anotherVeryLargeNumber, do they tend to not compute right factor? Assuming they rely on squaring algorithm, quite computation heavy with O(log2(anotherVeryLargeNumber)).


texts: The  address bus(of cpu) is connected to a digital decoder inside the memory which sets 1 pin logic high and activates the read/write operation of the memory let's say DRAM. Is the data bus(of cpu) connected directly to the bit line of the DRAM(columns) or are there some in between steps?


texts: Double ended queue data abstraction and axioms

texts:
I am trying to show the data abstraction for a double ended queue along with the axioms. A double ended queue is a queue where items can be added to and remove from either end of the queue.  I have already got the abstraction and axioms for a normal queue but looking at it, it looks to me like it would also work for a double ended queue. If this isn't the case what changes need to be made to make it work for a double ended queue?

Specification Queue:
Provides: Queue
Other abstractions used: Item, Boolean

Operations: NewQ: -> Queue
AddQ: Queue, Item -> Queue
RearQ: Queue -> Queue
FrontQ: Queue -> Item
IsEmptyQ: Queue -> Boolean

Axioms:
RearQ(NewQ) := NewQ
RearQ(AddQ(q, i)) := If IsEmptyQ(q) then NewQ
           otherwise AddQ(RearQ(q), i)
FrontQ(NewQ) := Error
FrontQ(AddQ(q, i)) := If IsEmptyQ(q) then i
           otherwise FrontQ(q)
IsEmptyQ(NewQ) :- True
IsEmptyQ(AddQ(q, i)) := False

Where:
   i is of type Item,
   q is of type Queue


texts:
In the Peterson Algorithm for mutual exclusion an implicit assumption is that the operations with the shared global variables happen atomically.

To me, this is not a superficial assumption , cause it's another mutual exclusion issue .
In which way we make the operations with the shared global variables happen atomically ?


texts: Find unambiguous grammar for an ambiguous grammar

texts:
Hi I want to find an unambiguous grammar for a known ambiguous one, and the production is like this:

S->bA|aB
A->a|aS|bAA
B->b|bS|aBB

I have found the string to prove this grammar is ambiguous: bbaaba. I wonder whether it is doable to convert the grammar into unambiguous. I have approached it from this perspective: in the above counter-example, the difference shows up when we have AA in the list, then whether we are changing the first A to contain S or the second will make the next step different. So I think maybe I can restrict A to go only via the first or the second A and hence eliminate the ambiguity, like this:

S->bA|aB
A->a|aS|baA|baSA
B->b|bS|abB|abSB

I'm not sure whether my approach or answer is correct or not. I understand there is no algo for this kind of conversion, but are there any kind of 'common steps' for getting the unambiguous grammar?


texts: Doubt over the index value used in dynamic programming

texts:
I was going through Count All Palindromic Subsequence in a given String where I've to count all the palindromic subsequence of a given string.

After seeing the brute force(recursive solution), I went through the dynamic programming technique but the index values used surprised me.

for (int L=2; L<=N; L++)
{
    for (int i=0; i<N; i++)
    {
        int k = L+i-1;
        if (str[i] == str[k])
            cps[i][k] = cps[i][k-1] +
                        cps[i+1][k] + 1;
        else
            cps[i][k] = cps[i][k-1] +
                        cps[i+1][k] -
                        cps[i+1][k-1];
    }
}

In the above code snippet,

if(str[i] == str[k])
    cps[i][k] = cps[i][k-1] + cps[i+1][k] + 1;

whereas in the code for brute force approach the same thing works using:

Else if (str[i] == str[j])
    return   countPS(i+1, j) + countPS(i, j-1) + 1;

I agree with what has been used in the brute force but Shouldn't the code following the DP approach be written as:

if(str[i] == str[k])
    cps[i][k] = cps[i-1][k] + cps[i][k+1] + 1;

because in the brute-force approach if we are computing for CountPS(i,j) then for str[i]==str[j] case, we need to compute countPS(i+1,j) and countPS(i,j-1) which in on translating to DP approach should mean that
we need to compute cps[i-1][j] and cps[i][j+1].

But, it isn't like what I'm thinking.

Where am I going wrong in understanding the code?