texts: Where to start on SJF Cpu schedualing homework problem?

texts:
So the question is;

For the following three jobs:
P1: 10 (3,2,5); P2: 4 (2,2); P3: 16 (2,3,5,6)
Execute the three jobs using Exp Ave Alpha =0.6, default=2

I know the formula to get the exponential average for a process is

Pn+1 = (alpha) * Tn + (1-alpha * Pn)

I am basically confused at where to start. Obviously, the value .6 gets plugged in for the alpha, but where does the 2 go in the formula? And with each iteration is N increased? Where do the first time quantum for each process (3, 2, 2) go into the equation?

I have searched all over the web for an explanation, but every video I see on SJF has a gant chart and is given arrival time and looks nothing like this problem.


texts: Maximum connected cell length containing two different numbers

texts:
Suppose we are given an $n\times m$ matrix $M$ of positive integers. The adjacent cells of a particular cell is the up, down, left and right cells. Like for cell $M[i][j]$ the adjacent cells are $M[i-1][j]$, $M[i+1][j]$, $M[i][j-1]$ and $M[i][j+1]$ respectively.

An area is a set of cells such that for each pair of cells $(u_0,v)$ in the area, there is a sequence of cells $u_1,\ldots,u_k$ in the area such that $u_{i+1}$ is an adjacent cell of $u_i$ and $u_k$ is an adjacent cell of $v$. The problem is to find out a maximum area (i.e. an area with maximum number of cells) of this matrix which contains exactly two different numbers.

For an example: $$M=\begin{bmatrix}5&3&2&5&5\\2&1&2&5&3\\6&1&5&2&5\\5&2&5&3&5\\4&6&8&9&6\end{bmatrix},$$
Here the maximum area contains 10 cells. And the area is:
$$\begin{bmatrix}*&*&2&5&5\\*&*&2&5&*\\*&*&5&2&*\\5&2&5&*&*\\*&*&*&*&*\end{bmatrix}.$$
What is the most efficient way to find the maximum area?


texts:
I am practicing for an exam and one of the exercises is:

  Find an example sequence where FFD (offline) performs better than BFD (offline).

Intuitively I would say no such sequence exists as the sequence is sorted, but I have not managed to find a counterexample or proof.


texts: Can you verify a word's position in an enumeration faster than performing the enumeration?

texts:
Pt 1. Given as input the tuple: (word (from an r.e. language we fix), natural number)--does there exist a verifier, that runs faster than simply enumerating that language, that can accept if the word is in the position of the natural number in an enumeration by an enumerator, and reject if it is not (choosing any enumerator you want for the set that makes this possible)?

I suspect the answer is no. In that case...

Pt 2. Is there a way to get around this by adding a "tagging" function to an enumerator for the language, so that a verifier can be given something like (word#tag, natural number) so that it almost immediately knows, from the tag, if the word is in the position of the natural number in that enumeration? AND IT CAN'T BE FOOLED! Of course you can stick a natural number onto a word, but how can you do this so the verifier can BE SURE you aren't lying...?

clarification from the comments on the question:

The question is basically: can you manufacture an enumerator for any enumerable language so that it includes extra data that the verifier can use to quickly determine what position it was in the enumeration, ie: can such an enumerator be constructed for any enumerable language?

Any ideas? :)


texts: When it is said an algorithm runs in exponential time, is it meant it has complexity $O(2^n)$, or $2^{O(n)}$?

texts:
Also, are they equivalent or are they different?

Examples of algorithms/Turing Machines that run in complexity of one but not the other would be much appreciated.


texts:
I'm learning about language metatheory and type systems, and am using coq to formalize my study.  One of the things I'd like to do is examine type systems that include dependent types, which I understand is very involved: being able to rely on coq would be invaluable.

Since this type system feature (and other, simpler ones) brings the expressive power of my studied system closer to coq's own, I worry that I might run into a bootstrapping problem that might not reveal itself until much later.  Perhaps someone here can address my fears before I set out.

Can coq express its own metatheory?  If not, can it still express simpler systems that include common forms of dependent typing?


texts: Is there an efficient algorithm for this vertex cycle cover problem?

texts:
I've been trying to find an algorithm to find a maximum vertex cycle cover of a directed graph $G$ — that is, a set of disjoint cycles which contain all the vertices in $G$, with as many cycles as possible (we don't consider individual vertices cycles here). I know that the problem of finding a minimum vertex cycle cover, as well as finding a vertex cycle cover with exactly $k$ cycles is NP-complete. But what about the maximum case?

While I'd find an answer to this interesting in general, the graphs I want to use this for are actually quite constrained by their construction, so maybe even if the problem is NP-complete there might be a polynomial solution for these specific instances.

We have a list of integers $L$, elements $l_i$ and we'll use $S$, elements $s_i$ to refer to $L$ after sorting it. As an example:

$$
  L = (1, 3, 2, 5, 0, 7, 4, 2, 6, 0, 8, 1)\\
  S = (0, 0, 1, 1, 2, 2, 3, 4, 5, 6, 7, 8)
$$

The vertices of the graph will be identified with pairs $(n, i)$ such that $l_i = n$ and $s_i \neq n$. The graph has a directed edge $(n, i) \rightarrow (m, j)$ if and only if $s_j = n$. (A cycle in this graph corresponds to a set of values which can be cyclically permuted such that they'll end up in their sorted position.)

The above example would yield the following graph (using 1-based indices):

One thing that doesn't work is the greedy approach of repeatedly removing the smallest cycle (as this example shows).

Note that this problem is (if I didn't make any mistakes) equivalent to asking how many swaps you need to sort a given list. (Which is what inspired looking into this problem in the first place.)

After some pointers from Juho's answer and a bit more sifting through literature, I've come across the assignment problem which seems very closely related. However, the assignment problem is formulated in terms of a weighted bipartite graph and so far I have not been able to find a way to choose edges and weights to reduce this problem to it. If we wanted to formulate the problem here in terms of minimising a weight function, then an intuitive approach would be to say that the weight of each cycle is $|C|-1$ where $|C|$ is the number of edges (or vertices) in the cycle. (Of course this is equivalent to just setting the weight to $-1$.) That is, the weight depends on the size of the cycle, not the particular edges it includes. But maybe this gives someone another idea for how to reduce the problem.

It also appears that bounding the size of the cycles makes the problem APX-hard for general graphs. This doesn't necessarily imply that the same is true for task of maximising the number of cycles, nor for the specific graphs under consideration here, but it seems to be sufficiently closely related that it could be important.

In summary: Can a maximum vertex disjoint cycle cover be found for the graphs constructed from the above process?

As two asides, I'd also be interested in whether the maximum vertex disjoint cycle cover also has an efficient solution for arbitrary graphs that admit at least one cycle cover (which will probably fall out as an answer to the main question), or whether just determining the number of cycles in the maximum cover (as opposed to the actual edges contained in each) makes the problem any simpler. I'm happy to post these as separate questions if people think they deserve full-fledged answers on their own.


texts: How is heap memory allocated to a process?

texts:
I want to better understand how OS provides heap memory to a process. Here by heap memory I mean the memory allocated dynamically, say by call to malloc.

When a process is newly created, does OS reserve some heap memory for it?
If a process calls malloc, does OS associate a "Page" (from paging concept) with process and then return some portion from that page? And so do later calls to malloc try to provide memory from this page, and if not possible OS associates another page from RAM(or virtual memory)?


texts: Have block edit distances been computed on large code bases?

texts:
There is an enormous mass of source code in this world, and I think it's safe to say that most of this source code was once copied from elsewhere, then modified. There is a decent chance of the (small, incremental) modifications having been made traceable in some kind of version control repository, but the (larger-scale) copying of source code usually isn't traceable in this way.

It would be nice to make it easy to detect it anyway.

As far as I can see, the reason it isn't is ultimately that our paradigm for looking at changes is modelled after diff: we compute changes as a collection of per-character insertions and deletions, disregarding the possibility of using block edit operations such as copy, cut, and paste.
This doesn't match actual code development practices, in which blockwise copies, cuts and pastes are all too common.  Allowing these, we can take two arbitrary code bases and 'reconstruct' an 'ideal' minimal distance between them, measured in terms of change operations that developers are actually likely to use, which includes cut, copy, and paste.  This would allow us to reconstruct an 'ideal' change history in code bases in circumstances where the actual change history is missing (e.g. when no version control system has been used, or when code has been copied verbatim from one code base into another).

There seems to be a sound computational reason that this isn't routinely provided already: it seems too expensive. Even with just per-character insertions and deletions, computing the minimal difference between two arbitrary strings already takes quadratic time in the size of the difference found; diff doesn't evcen attempt to do this perfectly.  If we also allow blockwise copies and/or moves at a constant cost, the problem of determining the minimal edit distance between two arbitrary strings becomes NP-complete. However, it has been argued that realistic constraints can be imposed that make the problem quadratic again. (I am linking to this paper, but I haven't actually read it yet.)

My question to you: have you ever seen an application of block edit distance computations (that is, including substring moves and/or deletions and/or copies) in a piece of software built to compare the similarity of two pieces of software? Does there exist a common, widely available tool that supports this? (A diff on steroids.) Or has there been a project to use such a technique to detect copy-and-paste operations within a large base of source code?

(The reason I'm asking is that source code does not at all consist of arbitrary strings. These problems are NP-hard for arbitrary strings, but they may well turn out be in P for source code found in practice.)


texts: What does "refuting random 3CNF" formulas mean?

texts:
Intuitively, recall what 3CNF formulas mean:

Its a boolean formula with conjunctive normal form (i.e. formula of ANDs of clauses with ORs) with no more than three variables per conjunct.

I was reading a paper that said:

  under a widely believed assumption that refuting random 3CNF formulas is hard, it is impossible to efficiently learn this class using ony $O(\frac{n}{\epsilon^2})$ examples.

however, I wasn't sure what "refuting random 3CNF formulas" even meant so I was having a hard time understanding the sentence. Someone know what that means?


texts:
My question is as follows: Assuming that $P \neq NP$, show that there exist sets $A$ and $B$ in $NP$ such that neither $A \leq _T^p B$ nor $B \leq _T^p A$, where $A \leq _T^p B$ if there exists a polytime deterministic oracle machine that computes $A$ given access to $B$. That is, $A \leq _T ^p B$ if $A = M^B$ for some Turing machine $M$. I am getting stuck right at the start of the proof.

We have previously shown that there exists $B \in NP$ such that it is not $NP$-complete nor in $P$ by setting up a set of requirements and using delayed diagonalization. Given an $NP$-complete language $A$, and an enumeration of oracle polytime Turing machines $\{ M _e \}_{e\in \mathbb{N}}$, the requirements were
$$R_{2e}: \exists y (A(y) \neq M_e^B(y)) \\ R_{2e + 1} : \exists y(B(y) \neq M_e(y)).$$

I want to try a similar strategy to build $A$ and $B$ in $NP$, thus having requirements
$$ R_{2e} : \exists y (A(y) \neq M_e^B(y)) \\ R_{2e +1}: \exists y (B(y) \neq M_e^A(y)) $$

I don't really know how to start the process in this case, or if this is even the right method here. I would be thankful for some advice on how to continue or on a better strategy. Thanks in advance!


texts: Is the language of TMs that accept finite languages in $\mathbf{0}'$?

texts:
In this question it is asked, "Is the language of TMs that accept finite languages Turing-recognizable?".
It turns out this language $L=\{ \langle M \rangle \mid |L(M)| < \infty \}$ is not.
I ask this: We know that the halting problem is Turing-reducible to $L$ but is $L$ Turing-reducible to the halting problem?


texts: Find a string that covers many sets of binary strings with don't-cares

texts:
Consider $N$ sets $S_1,S_2,....,S_{N}$ of binary strings with don't-cares ($X$) with $|S_i| = n$ and the length of all strings is $m$.
In my application, $N=1000$, $n=100$ and $m=500$.

I have to find atleast one binary string with all set bits (either $1$ or $0$) that is compatible with at least one string of each set. Two strings are compatible if they are bit-wise similar. As we know $X$ bits are similar to both $0$ or $1$. For example, consider string $A=10XX0$ and string $B=X011X$. Here string $A$ and $B$ are compatible with each other.

As we can see, due to the size of each string ($m=500$), it's impossible to find a solution with brute force (i.e. create all possible strings of length $m$ and compare each with all strings of all sets). So, I am looking for a reasonable heuristic to find the solution.


texts: Please explain this formal definition of computation

texts:
I am trying to attack TAOCP once again, given the sheer literal heaviness of the volumes I have trouble committing to it seriously. In TAOCP 1 Knuth writes, page 8, basic concepts::

  Let $A$ be a finite set of letters. Let $A^*$ be the set of all strings in $A$ (the set of all ordered sequences $x_1$ $x_2$ ... $x_n$ where $n \ge 0$ and $x_j$ is in $A$ for $1 \le j \le n$). The idea is to encode the states of the computation so that they are represented by strings of $A^*$ . Now let $N$ be a non-negative integer and Q (the state) be the set of all $(\sigma, j)$, where $\sigma$ is in $A^*$ and j is an integer $0 \le j \le N$; let $I$ (the input) be the subset of Q with $j=0$ and let $\Omega$ (the output) be the subset with $j = N$. If $\theta$ and $\sigma$ are strings in $A^*$, we say that $\theta$ occurs in $\sigma$ if $\sigma$ has the form $\alpha \theta \omega$ for strings $\alpha$ and $\omega$. To complete our definition, let $f$ be a function of the following type, defined by the strings $\theta_j$, $\phi_j$ and the integers $a_j$, $b_j$ for $0 \le j \le N$:

  $f((\sigma, j)) = (\sigma, a_j)$ if $\theta_j$ does not occur in $\sigma$
  $f((\sigma, j)) = (\alpha \psi_j \omega, b_j)$ if $\alpha$ is the shortest possible string for which $\sigma = \alpha \theta_j \omega$
  $f((\sigma,N)) = (\sigma, N)$

Not being a computer scientist, I have trouble grasping the whole passage. I kind of get the idea that is behind a system of opcodes, but I haven't progressed effectively in understanding. I think that the main problem is tat I don't know how to read it effectively.

Would it be possible to explain the passage above so that I can understand it, and give me a strategy in order to get in the logic in interpreting these statements?


texts: Find out if a path exists avoiding circular obstacles

texts:
Given

a rectangle defined by its corners $(0, 0)$ and $(w,h)$,
$n$ circles $\{ (x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$ with the
same radius $r$,

I need to determine the smallest possible radius r so that there is no
way to get from $(0,0)$ to $(w, h)$ without touching those circles.
What I have tried is

Use binary search to determine r
But the issue is that since there is no limitations for the
coordinates of the points (e.g. for them to be integers) I can't get
any idea how to construct a graph and use some path finding algorithm
such as DFS.

Any help would be appreciated.

Examples
Example 1, $w = 15, h = 20$; circles with coordinates $(2,7)$ and $(7,3)$; the result is $d \sim 3.2016$

Example 2 (without the right radius, but just to show what the issue is)


texts: λ -terms that correspond to Haskell functions

texts:
Evening All
I already have a "grasp" of haskell (not terrible, about 6 month experience) and am trying to learn the fundamentals that sit behind it, thus am now turning my attention to trying to learn Lambda Calculus. I thought, perhaps mistakenly, that it might be a good idea to try to work out the λ -terms that corresponds to some functions in Haskell. I am trying the foldr and map functions.
soooo foldr should have the property
              foldr f u [N1, . . . , Nk] →f N1 (f N2 (. . . (f Nk u)))

and map would have (should imagine...)
              map f [N1, . . . , Nk] → [f N1, f N2, . . . , f Nk]

where → represents reduction by any number of β -steps....
But am struggling to flesh this out to be honest. Any help would be greatly appreciated...
Kind Regards.


texts:
I have another question with dimensionality reduction.
I have a matrix $S \in R^{k \times d}$  and S is  in {$- \frac{1}{\sqrt k}, \frac{1}{\sqrt k}$} and i have two vector $u,v \in R^d $.

I need to understand why $E[u'^T v' ]= u^Tv$ where $u'=Su$.

I just have a intution, that maybe i just prove the left(or right span vector), but the hint is compute $E[S^TS]$ that for me this expectation is expectation of E[ I ] that if i m wrong will be 0...

I m a bit lost with this stuff.

i m thinking to do this

$E[u^t v] = E[u^T \sum vi ]$

another question is about the interval ... using $1 /\sqrt k $ is the same if i use a -1,1 with scaled factor of $\sqrt k $?


texts: Regular language such that L(r) = L(r₁) L(r) ∪ L(r₂)

texts:
Prove or disprove the following statement: for arbitrary regular expressions $r_1$ and $r_2$ over an
alphabet $\Sigma$ such that $\epsilon$ belongs to $L(r_1)$, there exists a regular expression $r$ over $\Sigma$ such that $r = r_1r + r_2$.

My Solution: Let us consider $\Sigma =\{a\}$. $L_1$ is even number of symbols so $r_1 =(aa)^*$ and $L_2$ is odd number of symbols so $r_2 = a(aa)^*$. $r$ is either $r_2$ which is possible or $rr_1$. Now if we keep replacing $r$ with $rr_1$ in the expression we will end up getting an infinitely large string because $r$ cannot be $\epsilon$ (thats what I think). So in my opinion this language is not regular. But I am not sure if I am thinking correctly.


texts: Any elegant approach to search where users have permissions on subset of records?

texts:
I work in Search and have seen following problem appear in different forms. There are many users in an enterprise; they have ability to create records. Each user has variable level of access to some or all of the records of the enterprise; and the record creator can manage access to the record.

How do we design a search feature for these records?

Common approach(es):

Index the records with some information about the access level. This has many limitations. It only works if there are limited possibilities in the access permutations, which is generally not the case. Imagine files being shared on Google drive. If there are m users, then for each record there are 2^m possibilities of read permission (i.e., does a user has read access to the record or not). And if there are n documents, then total permission possibilities explode to n * 2^m (assuming my probability calculation is correct, in any case the permission info permutations are beyond manageable to keep with record).
Index all the records and execute the query on the documents, and later filter the results based on user's permissions.  This approach works for complex permission models however the downside is that we are searching ton of extra documents and later discarding them.
Index documents separately for each user (as we are sure that the user as access to them). Track each record shared to the user, so that only these limited set of documents are searched through for each query. This avoid the issue with #2; but if a lot of sharing is being done, then it will not scale well.

I am hoping that there is a better way to design this problem. Google Drive must be doing something more intelligent than what I am thinking above.


texts:
Hopefully this is the right board for my question, We are facing an issue creating a unique ID from the following inputs :

datetime (can be present more than once in the same set, cannot not be present in 2 different sets)
offset ( an integer representing each line position in the set, the offset will be reset when switching to next/previous set)

As output we would like to get a unique ID, which will be used for sorting purpose later.

The concrete example for this issue is the rotating logs files. They will be collected into same database/table and later-on they will be shown and sorted/filtered based on this unique id.

Example :

log1.txt (set 1)

2017-08-06 10:36:07,988 something (let say offset=54)
2017-08-06 10:36:07,988 something (let say offset=108)
2017-08-06 10:36:07,988 something (let say offset=162)
...
2017-08-06 10:40:06,488 something (let say offset=1200)  => A

log2.txt (set 2)

2017-08-06 10:40:06,788 xyz (let say offset=20)
...
2017-08-06 10:40:07,488 xyz (let say offset=200) => B
...

Obviously a naïve uid function by adding offset as milliseconds to the date will lead to collusion, the frequency of the collusion cannot be foreseen, it depends on the logged text and the rotation size. (A & B for collusion example).

Regards


texts: Count paths in matrix that visit each number exactly once

texts:
Let's say we are given matrix of size $N \leq 21 \text{ by } M \leq 21$ each element of the matrix is either $-1$ or number in the interval $[0, 20]$.

We want to count the number of paths that start in some node, visit each number exactly once by moving in only 4 allowed directions: up, down, left and right. We are not allowed do visit the elements where the value in the matrix is $-1$. So, we want to count paths that  have exactly length of 21 because  there are 21 numbers in the interval $[0, 20]$.

I know that we can solve this with dynamic programming in $O(N \cdot M \cdot (2^{21}))$. But this uses too much memory, is there way to optimize the memory use. I was thinking only about saving only the last row and the current, but if we do such we cannot move in the upper direction, so we wont count some of the solutions.

Is there any way how we can optimize the memory usage.


texts: models/formalism for optimization algorithms?

texts:
In Wolpert's "No free lunch theorems for optimization", he uses the following formalism for an optimization algorithm:
Let $X$ be a finite space of which an element has to be chosen, and let $Y$ be a finite space. Let $f:X\to Y$ be a cost function, where a higher value in $Y$ denotes a higher cost. An optimization algorithm is a mapping $a:(X\times Y)^*\to X$. i.e. an algorithm chooses an $x\in X$, then observes $f(x)$, and adds this to its list of observations, and based on the set of previous observations chooses another $x\in X$, etc.

We could have picked a different formallism for optimization algorithms, since this formalism is restrictive: it assumes that (1) the algorithm has query-access to $f$ but (2) no other type of information.

My question is not so much about this particular formalism of optimziation algorithms. My question is: I'm interested in a list of different models that formalize the intuitive notion of optimization algorithm. i.e. what are all the different ways of formalizing it, in a more general, or simply a different way than Wolpert does here? (I'd like as many different formalisms as possible). Is there a resource for this?


texts: Is reference counting GC vs. tracing GC a language property or an implementation property?

texts:
We sometimes hear "Swift doesn't do classic (tracing) GC, it uses ARC."

But I'm not sure if there is anything in the Swift semantics that requires reference counting. It seems that one could build one's own Swift compiler and runtime to use tracing GC.

So what exactly is "reference-counted" about Swift? Apple's implementation or the language itself? Are there parts of the language or the library that so strongly support ARC that we can use that label for the language itself?


texts: Use subset of training data as prediction data

texts:
At our company, we've started using Amazon Machine Learning to predict the likelihood of a certain segment of our customers cancelling their subscription.

We only have 500 customers in that segment so we uploaded training data of all our customers who

are on a subscription or
were on a subscription but cancelled

Amazon tells us there's an AUC score 0.70 which is just ok from what I read.

I'm new to Machine Learning so my question is the following:

Out of the 500 customers that are in the training set, can I load the ones that haven't cancelled into the prediction set to predict the likelihood of them cancelling their subscription in the future? Or can I only use the model for new customers that are not included in the training data?


texts: Correct term for “string consisting of words”

texts:
In a paper I am writing I want to make distinction between (1) string consisting of any characters and (2) string consisting of a chain of words from known language, with possible delimiters. My intuitive idea is to simply use string for meaning (1) and text for meaning (2). It sounds a bit naive, but this terminology could work, given that I define it properly in my paper.

Yet I have an uneasy feeling that meaning (2) has fancier name in fields of computer science or computational linguistics. So, what are the precise terms to make distinction between the two types of strings?

UPDATE

Suppose we have an alphabet Σ = {a, b, c, ~}, where ~ is a delimiter symbol, and language L = {aaa, bbb, abc}.

Now, the following strings satisfy definition (1), but not (2):

cba
a
aaaa
a~b~~

And the following strings would satisfy both definitions (because they are made of the words of language L).

aaabbbabc
abc
aaa~bbb~aaa~~~aaa
~
(an empty string)

In some applications my strings could be actual text in a human language like English, Lithuanian or Esperanto. But this is not required. It could also be a DNA chain, a binary file, or anything else. Also keep in mind, that in practical applications the strings would most likely be long (like a journal article, or entire corpus for that matter), so calling it a "sentence" would be a bit of understatement. Meaning of the text is entirely irrelevant here.

So, regarding definition (1) all is clear - I just call it a string on alphabet Σ. Now the core question is this: what do I call the strings from the second example to make them distinct from the first example. My initial idea is to call it a "text". One of the answers proposed "word string", which I like even better. Maybe you have seen other terms being used for such purpose in the literature?

It might seem that I'm in extreme hair splitting mode here. Yet that term will be all over my PhD thesis, very likely including the title. Therefore I really want to get my terminology straight.


texts: Decidability of the language that accepts a universal turing machine

texts:
Is the language $L_{universal} = \{ \left \langle M \right \rangle | M \textrm{is a universal turing machine} \}$ decidable?

I'm guessing it is decidable according to the definition of a UTM, that a UTM must be able to calculate every recursive function. Since the set of recursive languages and the set of all input words are both enumerable, we are theoretically able to determine if the given $\left \langle M \right \rangle$ is a UTM. Is my logic somewhat correct?


texts: Suppose I have an algorithm that works as follows when invoked: it calls itself recursively with probability $0 < p < 1$ and terminates with probability $1-p$. Does this algorithm terminate? On the one hand you can show that $\lim_{n \to \infty}p^n = 0$, so it must terminate at some point before infinity. On the other hand it also seems reasonable to say that it is possible for the algorithm to call itself repeatedly indefinitely. What is the correct interpretation?


texts: Mathematical proofs implemented purely by Lambda Calculus

texts:
I've seen often stated that Lambda Calculus can be used for mathematical proofing but I haven't yet seen any example how it is actually used for the task.

Is there a simple example, lambda abstraction or application that can be shown to be a valid mathematical proof? For example what does it take to make a Church numeral successor function regarded as a mathematical proof?


texts: Regular language where syntactic right congruence and syntactic congruence differ

texts:
Find an example of a regular language where the syntactic right congruence and the syntactic congruence are not identical.

I have gone through the relevant definitions and understand them, but could not figure out an example for this case.


texts:
I studying the related question.

https://stackoverflow.com/questions/13500560/number-of-ways-to-create-an-avl-tree-with-n-nodes-and-l-leaf-node

but it's not so general.

In-fact, We want to know with N keys, how many different AVL Tree, we can make?

we know with N=1 key is 1 AVL Tree. with N=2 key we have 2 different AVL Tree, but in general we can make any recurrence formula? for example for N=4, N=5 and so on.


texts: For a binary tree of n nodes, there is a subtree with n/3 to 2n/3 nodes

texts:
in my notes I have one fact:
in a binary tree with $n$ elements ($n$ divisible by three) there is a node $u$ such that the number of nodes in the subtree with root $u$ is at least $\frac{n}{3}$ and at most $\frac{2n}{3}$.

Does it work for every binary tree or only when $n$ is divisible by three?
How can I quickly prove the fact in my note? A simple idea?


texts: Maximum feasible subsystem problem (MaxFS) in 2 variables

texts:
Topic:
The maximum feasible subsystem problem, which is generally NP-hard [1].

Question:
Are there special algorithms in case of only 2 variables (2D linear constraints)? The problem seems to be a lot less complex in my humble opinion but is this true? Can you guys point me to any algorithms/papers for this limited case with reduced computational complexity?

References:
[1] E. Amaldi and V. Kann, The complexity and approximability of finding maximum feasible subsystems of linear relations Theoretical Computer Science, vol. 147, pp. 181–210, 1993.


texts: Partition problem with distinct integers

texts:
The partition problem is a well-known NP-complete problem. In the definitions I have seen, the input is assumed to be a multiset of integers, and we want to decide the existence of a partition into two sets that have the same sum. My question is:

  Is the partition problem still NP-complete if all input integers are distinct (i.e., no integer is repeated)?


texts: Is this a correct application of Rice-Shapiro theorem?

texts:
Let $\langle M\rangle$ be the encoding of a Turing machine as a string over $\Sigma=\{0,1\}$, and consider the language $L=\{\langle M\rangle| \text{ $M$ is a Turing machine that accepts a string of length 2014} \}$
I want to use The Rice-McNaughton-Myhill-Shapiro Theorem (page 14 in this) to prove that $L$ is acceptable:
Say $\mathcal{L}$ is the set of all acceptable languages that contain strings of length 2014.

This set is monotone: every superset of a $L \in \mathcal{L}$ also contains strings of length 2014 so belongs to $\mathcal{L}$

This set is compact: for every language in $\mathcal{L}$ I can choose the finite subset with strings of length 2014.

This set is finitely acceptable: this is the part I'm confused about. Given every finite language of $\mathcal{L}$ is there a TM that can accept this set of finite languages?


texts:
I came across the following question while practising for my final algorithms exam, but I am unsure how to get a linear time complexity for this problem. I assumed it would require checking which tiling patterns are compatible with each other, but get a bit stuck on how to proceed.
Thanks!


texts: What are some uses of the Thue-Morse sequence in computer science?

texts:
Note: I come from a mathematics background.

The Thue-Morse sequence $t_n$ is a binary sequence that takes the value $0$ at the positive integer $n$ if the number of $1$s in its binary expansion is even, $1$ otherwise.

A definition that is closer to computer science states that $t_n$ is the binary sequence obtained by starting with $0$ and successively appending the boolean complement of the sequence obtained so far.

Thus, $t_n$ begins $0,1,1,0,1,0,0,1,\ldots$

This sequence is of much interest in mathematics, but so far I have not come across any applications in computer science. This surprises me, for the two following reasons:

The Thue-Morse sequence is automatic, i.e., the sequence is fully characterized by a finite automaton,
It is a binary sequence.

  What theoretic or practical applications of the Thue-Morse sequence are there in computer science?


texts: Integral solutions to circulation problem

texts:
Suppose we have a circulation problem (with only one commodity), where all lower bounds, upper bounds, and costs are integers.  Are we guaranteed that if there is a solution, then there is an integral solution?  Is there an algorithm that can find one in polynomial time?
For standard network flow, we know that there is a max flow that is integral, and there are polynomial-time algorithms that can find such an integral flow.  I'm wondering if the same is true for circulation problems, which are a generalization of max-flow.


texts: Finding duplicates in a stream of numbers

texts:
This is an interview question.
Say you have a function foo() which returns some integer.
You need to write an algorithm that does the following:

(1). Call foo() in a loop, till the returned value of foo() is -1.
(2). Returns true if during the loop there were two calls of foo() which returned the same value.

This is what I thought to do, please tell me if this is efficient enough:

(1). Initialize a hash map , which maps an integer to the number of times we got it in the loop
(2). Call foo() in a loop till the returned value of foo() is -1, while updating the hash map accordingly.
(3). Check if there is a key in the hash map which is mapped to a value greater than 1.


texts: Is it theoretically possible to dynamically grow array size in stack memory?

texts:
I was wondering, given the usual stack memory functioning, whether it is possible for an array like primitive type allowed to grow in size to exist.
The functioning of such primitive type is as follows.

Any one function is allowed to have only one such primitive variable.
Appending to such primitive variable is allowed only within the function that it was initialized in.
If the function that such primitive variable was initialize in is not the last in the stack, such primitive variable is not allowed to grow in size.

I was wondering whether:

Such primitive type is theoretically possible.
Whether it is something that is already in use.


texts: Why finding the difference between the adjacent elements of the array to find the maximum difference?

texts:
I want to understand a tricky method to find the maximum difference between two elements such that larger element appears after the smaller number. I found easy solution keeping track of the minimum array but I don't get the following solution which first find the difference between the adjacent elements of the array and store all differences in an auxiliary array diff[] of size n-1. The  problems turns into finding the maximum sum subarray of this difference array.

Here is a working example plus my comments showing where I especially don't understand the algorithm.

// C++ program to find Maximum difference
// between two elements such that larger
// element appears after the smaller number
#include <bits/stdc++.h>
using namespace std;

/* The function assumes that there are
at least two elements in array. The
function returns a negative value if the
array is sorted in decreasing order and
returns 0 if elements are equal */
int maxDiff(int arr[], int n)
{
    // Create a diff array of size n-1.
    // The array will hold the difference
    // of adjacent elements
    int diff[n-1];
    for (int i=0; i < n-1; i++)
        diff[i] = arr[i+1] - arr[i];

    // Now find the maximum sum
    // subarray in diff array
    int max_diff = diff[0];
    for (int i=1; i<n-1; i++)
    {
        if (diff[i-1] > 0)
            diff[i] += diff[i-1]; // I especially don't get why we add differences
        if (max_diff < diff[i])
            max_diff = diff[i]; // and why we update the max_diff as the sum of differences
    }
    return max_diff;
}

/* Driver program to test above function */
int main()
{
int arr[] = {80, 2, 6, 3, 100};
int n = sizeof(arr) / sizeof(arr[0]);

// Function calling
cout << "Maximum difference is " << maxDiff(arr, n);

return 0;
}


texts: Improving copy cost of a bit array by using big-endian Patricia Trees (or similar)

texts:
I have an algorithm that on each iteration generates a copy of an object containing a bit array and modifies it (the modification is limited to just 1 element per copy)

While doing the time analysis I cannot neglect the copy cost as this bit array is encoding information about the input set, so for a very large number of elements I have to account for it..

I has been said that effective data structures exists, like big-endian Patricia trees, that can achieve a $O(log(n))$ when copying an instance, and I confirmed there are implementations using them like Data.IntSet from haskell that provides a very good TC for certain operations that I can use to refactor this part of the algorithm ($O(min(n,W))$ W=word size)

I have seen another post in Stack Exchange explaining that is possible to achieve a similar copy cost with AVL persitent trees.

I'm looking for confirmation about this or any other specialized structure that can achieve the reported time complexity for copy.


texts: How close are current computer technologies in terms of energy efficiency to the Landauer Limit?

texts:
I'm trying to figure out how close (in orders of magnitude) current computer technologies are in terms of energy efficiency to the Landauer Limit. However, I'm finding (seemingly) conflicting information about this, and the discrepancy seems to arise from different metrics and assumptions.
This Royal Society piece (without a source) refers to a 1 attojoule/operation ($10^{-18}$ J) "six orders of magnitude smaller than today’s devices," which implies that we are nine orders of magnitude from the Landauer Limit.
This Lesswrong article and this graph (full text downloadable here) analyze transistor switching energies and come up with a figure of three orders of magnitude.
Wikipedia, which cites this blog, claims that it is six orders of magnitude ("0.00001%"). I was able to verify the math the blog used, which based its calculations off of the 2012 RIKEN K Computer and used the assumption that 8.2 petaflops corresponded to $10^{20}$ bit operations (about $1.2 \cdot 10^4$ bit operations per floating point operation).
(1) Is there a widely accepted "standard" for the number of bit operations/transistor switches that correspond to each floating point operation, and does this number vary or change? I've heard numbers ranging anywhere from $10^4$ to $10^8$.
(2) What is the "correct" figure for the number of orders of magnitude that separates the energy efficiency current computer technologies from the Landauer Limit?


texts: K -> 2 tape reduction for nondeterministic Turing machines

texts:
How to I show that any language in NTIME(T(n)) can be accepted by a non-deterministic 2-tape O(T(n)) time-bounded Turing machine, with modifiable input tape?

I've seen the k to 2 tape reduction for deterministic Turing machines, which increase the running time by a logarithmic factor, but I'm not sure if I can modify that to help me prove the above statement.


texts: NFA with exponential number of states when determinized

texts: How can I build an example of a regular language where the minimal DFA has $2^n$ states and the minimal NFA has $n$ states? Obviously the DFA's state-set should contain all subsets of the the NFA's state-set, but I don't know how to start. Any suggestions to put me on the right track?


texts: Concatenate multiple integer arrays such that number of inversions in resulting array is minimal

texts:
Given N arrays of variable length.

Find a way to concatenate the arrays in such a way that the number of inversions is minimum

An inversion for an array Arr can be defined as,

a pair of indices (i,j) such that,

i != j

i < j

Arr[i]>Arr[j]

I tried to concatenate the arrays on the basis of sum, such that the one with minimal sum goes first and one with maximal sum goes last.

It didn't work out though.

Example:-

[14, 18, 18, 20, 16, 6, 11] SUM:- 103

[2, 4, 11, 40, 20, 14, 19] SUM:- 110

[14, 18, 18, 20, 16, 6, 11, 2, 4, 11, 40, 20, 14, 19] Inversions:- 42

[2, 4, 11, 40, 20, 14, 19, 14, 18, 18, 20, 16, 6, 11] Inversions:- 40


texts: Suppose we have a classification problem and we wish to solve the problem by Neural Network. What factors must one consider choosing an NN structure? e.g Feed Forward, Recurrent and other available structures.


texts: Applications of the splittance of a graph/ Turning graphs into splitgraphs

texts:
Let $G=(V,E)$ be a graph. For $C\subseteq V$ let $G[C]$ be the subgraph of $G$ induced by $C$.
A split Graph is defined as follow:

$G$ is a split graph if there exists a subset $C\subseteq V$ so that $G[C]$ is a clique and $G[V\setminus C]$ is an independant set (edges between $C$ and $V\setminus C$ do not matter).

There exists an efficient algorithm (linear time) to calculate the shortest sequence of edge insertions & deletions to turn a graph into a split graph (Important: If we also have to remove the edges between $C$ and $V-C$, then this problem turns $\textsf{NP}$-hard).
My question is: what are possible applications of this procedure?
My ideas so far:
Of course, if the distance of $G$ to a split graph is very small (compared to the number of nodes), we can probably adapt the algorithms for split graphs, and that way obtain efficient implementations for problems that would be $\textsf{NP}$-hard on general graphs.
A general situation where we (somewhat probably) have a near-split-graph would be a network to which we add a batch of random new objects, e.g. a company which just got a batch of newcomers.
Though I still wouldn't know what type of problem there is that could use the fact that the graph is a near-split-graph. Link to the complexity of some problems on split graphs


texts: Confused between the terms Process and Process Control Block

texts:
I was reading about the Long term scheduler, when I read that when memory is not enough and load on the CPU due to multiprogramming is too high, a process might be moved to secondary storage space (namely swap space). I am slightly confused as too what exactly happens when a process is moved out of memory. Is its "PCB(Process Control Block)" moved out and store in Hard disk or something else like "process state".
I believe that this confusion is due to lack of clarity between "process in memory" and "process control block". Are the two things different or the same?

The above two diagrams have been picked from the 3rd chapter of Operating Systems Concepts 9th edition.


texts: Distribution of number of references to other object in an object

texts:
I been thinking about an improvement to a garbage collector (details not important for this question) and wished to know how often does a object have no reference to other objects.  Clearly this will depend on the language.

Many people must have research this and published the data, yet I can't come up with the correct words to type into Google.


texts: Naive Bayes where Feature Space is LDA Output

texts:
I understand that the output for Latent Dirichlet Allocation is a distribution over K topics.

Suppose I have a Dx(K+1) matrix, where rows are documents and columns are the topic distribution + one column for class. For example, each row represents one movie review. The first K columns represent the topic distribution of the document, and the last column is the classification of this document. For example, if K=5, one row may read as:

2 | 0.25 | 0.4 | 0.1 | 0.15 | 0.1 | 1

where moview review 2 had 25% of the text about topic 1 (pleasure), 40% topic 2 (discontent), 10% topic 3 (personal feelings) ... and the classification of this document was to class #1.

How would I go about creating a Naive Bayes Classifier using this data?

Typically, I have used a Gaussian Naive Bayes where the feature space is iid over normally distributed variables, but this assumption I do not believe makes sense for LDA output. Would I need to assume the features are the individual columns distributed in a particular way (say a Dirichlet probability)?

This exercise is more for proof of concept to use Naive Bayes. I want to use, say 60%, of the data to construct a Naive Bayes Classifier and test the accuracy of the remaining 40%. My main concern is to how to define the PDF for the Naive Bayes Classifier.


texts: Designing a DFA that accepts strings such that nth character from last satisfies condition

texts:
This is a homework question, so I am only looking for hints.

I got a question in an assignment which states :

  Design a DFA that accepts strings having 1 as the 4th character from the end, on the alphabet {0,1}

I have been at this for a few hours now, and I think that designing such a DFA is not possible. However, I am not sure how to move forward in this direction to write up a somewhat formal proof.

So, what should I try to do to prove or disprove my hypothesis?


texts: What category does questions like "Given n points on 2D plane find ..." belong to

texts:
Not after a specific answer, do following questions belong to same set of problem types?

Given n points in on 2D plane, find 4 or 5 , or m subset of points with less total distant to each other than all other points.

Or

Given n points in on 2D plane, count the number of triangles, squares etc. that they form.

Or

Given n points in on 2D plane, find a point that is closeses to most number of points as possible.

are these optimisation questions? or is there another name for above type of questions, or there can be no category for all the questions of type

Given n points in on 2D plane, find $\cdots$

This question did not seem to be fit for SO or Software engineering, so I am asking it here, if there is better SE to ask this question I'll delete this question and ask it there ( in reverse order ).


texts:
Max-2-SAT is defined as follows. We are given a 2-CNF formula and a
  bound k, and asked to find an assignment to the variables that
  satisfies at least k of the clauses.

I can understand the trick used to prove 2-SAT is in P. You use get a contradiction by using unit propagation. But, I was wondering why does MAX 2-SAT escape this.

Also, I find it hard to believe this is NP-complete. Certainly, what is the problem that causes it to blow up.

Why wouldn't an algorithm like this work. Given a 2-SAT expression. Find it's length, which we can do in P. Need to check if there is at least k of the clauses.

So we just check $\binom n k$ posibilities and run like Horn algorithm on each sub expression of the n 2-SAT expression. Surely, where is the problem as we are just running a P algorithm a polynomial amount of time.

So I'm very confused. Sort of similar problem I have factorization and if that is in P or NP.


texts: Reference/book recommendations for search data structure

texts:
I am interested in data structures that support efficient searching of various kinds.

When I read the Wikipedia page of "search data structure", it says "Useful search data structures allow faster retrieval; however, they are limited to queries of some specific kind". So, obviously, there exists a correlation of one specific data structure and the searching operations it supports. For example, k-d tree supports efficient query of multiple-dimensional data.

Of course, the data structures I am thinking about are not limited to arrays or trees. They can also be graphs or more advanced structures.

I am new to this field. So I am wondering if anyone can recommend some books or review papers that summarize different search/query data structures.

Thanks in advance.


texts: DFA containing substring to not containing substring by flipping acceptability of all states?

texts:
For example, $D_1 = \{ w | w$ does not contain baba as substring$\}$

For $D_1$, I would make $F_1 = \{q_4\}$.
As I tried to design $D_2$ as the complement of $D_1$ which does not have baba as a sub-string, I've found that I can make $D_2$ by inverting all the acceptability of all states, making $F_2 = \{q_0, q_1, q_2, q_3\}$, since instead of accepting, the input string is rejected upon reaching the an acceptance state of its complement $D_1$.
From this, I believe that we can get the complement of any DFA simply by accepting when $D_1$ rejects, and reject when $D_1$ accepts, meaning $F_2$ is the complement of $F_1$.
Is my generalized proof correct?


texts: Relation between semi decidable, undecidable and countable sets

texts:
I know that

decidable problem: has both counting (bijection with $\mathbb N $) and membership algorithm (TM halts for both member and non member strings )
semidecidable problem: has counting algorithm and TM halts for member strings
countable problem: has only counting algorithm

Now I have come across undecidable language set which does not have membership algorithm (as semi decidable languages at least have TM which halts for member strings, which is not the case for undecidable problems), that is it does have TM that halt neither for member string nor for non member string.

I have doubt about the relationship between these language classes.

I know "decidable $\subset$ semi decidable $\subset$ countable".

Where does "undecidable" fit here?

Is it like this?:

(Match the color of text with that of the border. Region color is lighter shades of corresponding enclosed texts.)

Q. Is above diagram correct? Also I want to add "countable" to above. I feel, for finite alphabet languages, countable will be proper superset of "undecidable". Is it right?

PS: I feel, earlier I based my understanding of "undecidable" on incorrect definition given in this question. So I draw wrong diagram earlier. I believe its correct now.


texts: Compare asymptotic WC runtime with measured AC runtime

texts:
I have an algorithm and I determined the asymptotic worst-case runtime, represented by Landau notation. Let's say $T(n) = O(n^2)$; this is measured in number of operations.

But this is the worst case, how about in average? I tried to run my algorithm 1000 times for each $n$ from $1$ to $1000$.I get another graph which is the average running time against $n$ but measured in real seconds.

Is there any possible way to compare these figures?


texts:
I am reading the textbook algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani

The authors state in page $67$:

  The preceding formula implies an $O(n^3)$ algorithm for matrix multiplication: there are $n^2$ entries to be computed, and each takes $O(n)$ time. For quite a while, this was widely believed to be the best running time possible, and it was even proved that in certain models of computation no algorithm could do better. It was therefore a source of great excitement when in $1969$, the German mathematician Volker Strassen announced a significantly more efficient
  algorithm, based upon divide-and-conquer.

The statement that interests my more in this quotation, is:

  it was even proved that in certain models of computation no algorithm could do better.

Could anyone support me with some references where I can find a proof of that kind?


texts: reusable expressions in Context free grammars

texts:
say, we add the option of allowing let expressions to context free grammars:

let defines a variable that defines an expression from a specific Symbol of the grammar, and every instance of the variable has to be the exact same expression

eg:

T := (let ((z -> U) z + z)
U := x | y | Const | U +U | U ∗U | T

In the above example, T:= U + U, except that the two occurrences of U
have to be identical.

So, this grammar only allows expressions which are a sum of 2 identical expressions.

I think this grammar is strictly more powerful than context free grammar, but can anyone tell me if they are equivalent to any other known type of grammar.


texts: Given a network flow find if there's a min cut that only one of the given edges lay on it

texts:
Given a network flow $G=(V,E)$ with capacity function $C$ source $s$ and hole $t$,
and given 2 edges $e_1 , e_2 $.

Find if there exists a min-cut such that only one of the edges belongs to the min-cut.

Hope to get help.


texts: Are there any problems that get easier as they increase in size?

texts: This may be a ridiculous question, but is it possible to have a problem that actually gets easier as the inputs grow in size?  I doubt any practical problems are like this, but maybe we can invent a degenerate problem that has this property.  For instance, perhaps it begins to "solve itself" as it gets larger, or behaves in some other bizarre way.


texts: Can a recursive language be uncountable?

texts:
Does there exist a recursive language $L$ whose cardinality is uncountable?

I would like to have an explanation whether Turing Machine can encode uncountable languages and whether we can use this to reject the initial question.


texts: Is this a misleading or undesirable implementation of a hash map?

texts:
I read a C++ implementation of a hash map here.
https://www.geeksforgeeks.org/implementing-hash-table-open-addressing-linear-probing-cpp/

Let's say key k1 has a hash index of h. Suppose there's a collision with key k2 such that hash(k1) == hash(k2). Then won't the new hash index of k2 become h+1?

Key: k1     Index: h
Key: k2     Index: h+1

Suppose we introduce a third key k3 such that hash(k3) == h+1. Then when we insert k3 into the hash map, its hash index will become h+2.

Key: k1    Hash value: h      Hash table index: h
Key: k2    Hash value: h      Hash table index: h+1
Key: k3    Hash value: h+1    Hash table index: h+2

This can cause the hash indexes for keys to be shifted over 1 in the case of collisions (as seen above), and if collisions happen frequently then they could be shifted over more than once.

Is this a bad implementation of a hash map? From an aesthetic point of view I prefer the linked approach, where each hash node has a pointer to a next node, such that if multiple nodes have the same hash index, they are all part of the same linked list starting at that hash index.

In the linked approach, at least we have the assurance that a key will logically correspond to its hash index in the hash table, even if it's part of a linked list (in which case it doesn't physically correspond, but logically still does, since the head of the linked list is stored there).

Is the implementation of the hash map in GeeksForGeeks bad? Is the linked approach more logical and intuitive? What are your thoughts?

Note: The linked approach I refer to is simply to store a linked list at each hash index in the hash table, such that if multiple keys are hashed to that index, they are stored in this linked list.


texts:
How to show that  Max-cut$_{dec}$ is NP-complete using Mon-NAE-3SAT ?

Mon-NAE-3SAT definition :

An instance is a m clauses of three positive literals (no complemented variable) $x \vee y \vee z$
The question: is whether there is a Boolean assignment that ensures that each clause contains at least one variable

Max-cut$_{dec}$ definition :

Let $G = (V,E)$ be an undirected graph. A cut (or cut) is a partition of $V$  into two subsets $V_1, V_2$.
The size of a cut, note $c(V_1,V_2)$, is the number of edges $(u,v)$  of $E$ such that $u \in V_1$  and $v \in V_2$  or, conversely, $u \in V_2$ and $v \in V_1$.

The  Max-cut optimization problem is finding the largest cut. In its decision version, Max-cut$_{dec}$, each instance also includes a $k$ size objective and you have to decide if it exists a cut of $k$ size  or more.

actually I'm stuck on how to show :

that if $x, y, z$ are on the same side of the cut then the gadget contains at most 4 edges counted in the cut.
that if the three points $x,y,z$ are not all on the same side of the cut, then we can place points $a,b,c$ in $V_1$ or $V_2$ so that the gadget contains 5 edges counted in the cut.

I put the gadget below  which represents an $x \vee y \vee z$ clause.


texts: MIPS pipeline: choosing between slowing down a stage and adding a new stage

texts:
Suppose a new, more complicated, instruction is desired for this
  simple pipelined MIPS processor. Suppose, also, it could be
  implemented by either (a) adding new logic to the execute stage of the
  pipeline, or (b) adding a new stage (i.e a 6th stage) altogether.
  Assume that choice (a) would slow the execute stage down by 20%. Since
  choice (b) increases the number of stages by 20%, is the overall
  effect on execution the same? If not, describe how each choice affects
  execution time and indicate which choice is better.

This was a question in my exam, but I'm not sure if my answer to it is correct. Here is what I think:

If the execution stage time increased by 20%, then the new cycle time will likely be the time of the execution stage. So cycle time will increase by 20%.

Adding a new stage to the pipeline wouldn't affect the cycle time (assuming the new stage is shorter than or equal to the longest stage). It would increase the throughput, but also increase the latency of individual instructions by 20%.

So, no, they don't have the same affect on overall performance. The second choice is more efficient.

Now, am I correct?


texts:
I want to create a Red-Black Tree, with 2 values, (index, value) and I want to insert into the RB_tree based on the index.

So if I have the function: $\text{insert}(root, value, index)$ it will insert the value at $index$. However, because I insert based on the other indexes, if I insert at the index $1$ let's say, and I have already inserted at that index, then I would have to add to all the other node's indexes $+1$. The insert function is used only with valid indexes so, $index\in[0, size(RB\_tree)]$. What should I do to keep the insertion $O(\log n)$ and still have the indexes?


texts:
My theory

take a file examplesize:(3GB)

convert said file to a number

divide that number by a large prime number example:(2^82,589,932 · (2^82,589,933-1))[2018 Dec 07]

get the quotient and the remainder

if the remainder is still large do the math again to get another quotient and remainder until the remainder size is as small as preferred

build the compressed data
FFFF - First division
EEEE - Second division
....
LLLL - Final remainder length(hex)
RRRR - Final remainder
ZZZZ - File Name
Example: 0000ABC60000EF53....000468438FB1412e62696e
Example: FFFFFFFFEEEEEEEE....LLLLRRRRRRRRZZZZZZZZZZ

Because there are only 51 confirmed primes larger then 2 (as of 2018 Dec 07) and we would only need the longest 20 primes to shrink a file to the max useful size we would only need 80 bytes plus the remainder and file name.
For a (by my calculations)108PB file this could bring the file size to a few Kilobytes in size at most
Does this even sound feasible


texts:
I stumbled on this problem and I wanna know if there is a better solution.
There are $n$ 3d vectors with $x$, $y$, and $z$ components and I wanna find all pairs of perpendicular vectors in this set. Is there any better way than to verify all possible pairs of 3 vectors, some kind of optimization (not the obvious ones)?


texts:
I have been reading the following document about the undecidability of virus detection, available at:

https://enterprise.comodo.com/whitepaper/Impossibility_of_Virus_Detection_WP.pdf

the problem that I have is in the following part:

The part that I do not understand is the one that says:

Halts(P)=not(DetectVirus(MakeVirus(P)))

Because for what I read if P behaves like a virus, which is made by the function MakeVirus(P), then I suppose that DetecVirus() will detect it and because of that this program will halt. So I will end up with:

Halts(P)=(DetectVirus(MakeVirus(P)))=true

but why do they negate that term? is it because P is a virus, but DetectVirus failed to detect it, so their answer instead of being true is false because of:

Halts(P)=not(DetectVirus(MakeVirus(P)))= not(DetectVirus(MakeVirus(P)=returns virus)=false)=true

I am assuming that P is a virus, but DetectVirus() returns false because it failed to detect it; then the negation of this would be a true value, so in this case Halts(p) will also halt the program.

Could somebody explain me what am I doing wrong?

Thanks


texts: The difference between a bit and a Qubit

texts:
Ok, I have done a lot of research on Quantum computers. I understand that they are possibly the future of computers and may be commonplace in approximately 30-50 years time.

I know that a Binary is either 0 or 1, but a Qubit can be 0 or 1. But what I don't understand is how it can be anything other then 0 or 1. Surely a computer can only understand on and off, despite however fast it may be?


texts: Whats the diffrence between Disk scheduling and process scheduling? I mean i know the roles of disks and processes, but it seems to me they both have the same aim. to reduce monopolies, they even both share similar algorithms like first come first serve. Am i right?


texts: Is this an abuse big O notation as a power of a number?

texts:
Theorem 7.11 in Introduction to the theory of computation 3rth edition says

  Let $t(n)$ be a function where $t(n)>n$. Then every $t(n)$ time
  nondeterministic single-tape Turing machine has an equivalent
  $2^{O(t(n))}$ time deterministic single tape Turing machine.

I can understand that in this proof when we have a nondeterministic TM which every node in it can at most go to $b$  other nodes in its computation tree, then the time complexity of a deterministic Turing machine simulating it would be $O(t(n)b^{t(n)})$. But I'm not sure if I understand the $2^{O(t(n))}$ correctly.

Does it means that if $f(n) \in 2^{O(t(n))}$ then
$\exists b\in \mathbb{N} \; f(n)\in O(b^{t(n)})?$

On the other hand, the claim 1.5 in the Computational complexity book says

  For every $f : \{0, 1\}^∗ \rightarrow \{0, 1\}$ and time-constructible
  $T : N\rightarrow N$, if $f$ is computable in time $T(n)$ by a TM $M$
  using alphabet $\Gamma$, then it is computable in time $4 log |\Gamma|T(n)$
  by a TM $M$ using the alphabet $\{0,1,\square,\rhd\}$.

So every nondeterministic TM M running in $t(n)$ time can have an equivalent nondeterministic TM using $\{0,1\}$ alphabet running upper hand in $|\Gamma|^2t(n)$. Thus this equivalent TM's computation tree has at most 2 different branches in each step. Then we can have a deterministic simulator of that TM running in time $O(2^{|\Gamma|^2t(n)})$.

The intersection of 2 above statement suggests that carelessly we can say $O(2^{t(n)})=2^{O(t(n))}$, but we know $\forall b>2,\; b^{t(n)}\notin O(2^{t(n)})$.

Unfortunately, I didn't find any definition of $2^{O(t(n)}$. I wish to know is there any formal definition for $2^{O(t(n))}$?

-
Edit: There is a similar question here. But I'm doubting its answer is the same since the big O notation in the power is not just $O(1)$.

Suppose we have nondeterministic TM that each node of it goes to 3 other nodes. Then there is a deterministic Turing machine that simulates it in time $t(n)3^{t(n)}$. So we can't say that there is a constant $k$ that $t(n)3^{t(n)} < 2^{kt(n)}.$

Meanwhile, when I think more, this definition holds if we ignore the Sipser proof. I mean if we begin the proof by the statement that every nondeterministic TM has a version $\{0,1\}$ alphabet running in $c.t(n)$ then the answer's definition is correct.

I wonder if there is bad use of big O notation in the Sipser's book or $2^{O(t(n))}$ has a different definition.


texts: Decidability of intersection of two languages of same type

texts:
Given two context-sensitive languages, $L_1$ and $L_2$ is the problem of "whether $L_1 \cap L_2$ also belongs to CSL" decidable?

I have the same question for the case when $L_1$ and $L_2$ belongs to Recursive/Recursively enumerable language. I think, they are decidable because they are closed under intersection operation as can be seen here. But I haven't found any text mentioning this explicitly so I can't be sure.


texts: Gradient descent overshoot - why does it diverge?

texts:
I'm thinking about gradient descent, but I don't get it.
I understand that it can overshoot the minimum when the learning rate is too large. But I can't understand why it would diverge.
Let's say we have

$$J(\theta_0, \theta_1) = \frac{1}{2m}\sum_{i=1}^m (h_\theta(x^i)-y^i)^2$$

$$\theta_1 := \theta_1-\alpha\frac{\partial}{\partial\theta_1}J(\theta_1)$$

When the slope is negative the cost will converge to the minimum from the left of the graph, as $\theta_1$ will increase.
When the slope is positive it will converge from the right of the graph, as $\theta_1$ will decrease.
Now it might overshoot when the learning rate $\alpha$ is too large.
In that case it should overshoot again.
But not by much, should it not circle around the minimum? Why would it diverge?


texts: trying to understand the diagonal check of 8 queen problem

texts:
I was solving the 8 queen problem and tried to look through the internet for comparison solutions to see how my solutions compared to others. I found one very small bruteforce solution that confused me. And i was wondering if anyone care to explain how the diagonal comparison actually works?

void solve(int n, int col, int *hist)
{
    int i;
    int j;

    if (col == n)
    {
        print_solution(n, hist);
    }
    i = 0;
    while (i < n)
    {
        j = 0;
        while (j < col && !(hist[j] == i || abs(hist[j] - i) == col - j))
            j++;
        if (j < col)
        {
            i++;
            continue;
        }
        hist[col] = i;
        solve(n, col + 1, hist);
        i++;
    }
}

void main(void)
{
    int hist[8];

    solve(8, 0, hist);
}

the code in particular im having problem visualizing is

abs(hist[j] - i) == col - j)

from what i understand it checks the diagonals but i dont see it.


texts: Prove that there is no computable enumeration of all decidable languages

texts:
The question:

  Let $L_1,L_2,...$ be an enumeration of $\mathcal{R}$ and define $A_i = \{\langle M\rangle \ | \ L(M) = L_i\}$. Let $L$ be a language in $\mathcal{RE}$ such that $L \subset \{\langle M\rangle \ | \ \text{M is a TM that always halts}\}$. Prove that
  there exists an $i$ for which $L∩A_i = ∅$.

Hint $\downarrow$

  Hint: Build a TM that returns some (which?) element of $L$ and apply a diagonalization argument.

My approach

I thought of the Hint but I am not sure that the language I get is decidable and I don't know how to prove that all its "always halting" TMs are not in $L$.


texts: Algorithm for queue with multiple repeated different interval events

texts:
I have N events, each repeats after some time ti. I want a queue where I can pop out next event.

For example, I have events A,B,C with intervals 2,3,5 At the beginning they all are in the queue with values:

A-2, B-3, C-5

When I take out event, it should be A, after that I put it back, but add +2.

B-3, A-4, C-5

Next is B. I add +3

A-4, C-5, B-6

Next is A, I add +2

C-5, B-6, A-6

and so on.

What could be the best algorithm for that?


texts: Upper bound for the union of $n$ DFAs of size at most $m$?

texts:
Let $\Sigma$ be an alphabet of size $2$, and let's consider $n$ regular languages $L_i \subseteq \Sigma^*$ respectively recognized by $n$ minimal DFAs $D_i$ whose size are bounded by $m$. As the number $k$ of minimal DFAs of size at most $m$ is finite, there exists a function $f$ that returns this number $k=f(m)$.

Let $L \subseteq \Sigma^*$ be the language resulting from the union of the $n$ regular languages $L_i$.

Is the size of the smallest DFA $D_L$ recognizing $L$ always below $m^{f(m)}$ ?

And if so, how can we find a precise definition/close-form of $f(m)$ ?

My intuition is as follows : the size of a DFA resulting from the union of two DFAs $A$ and $B$ is not greater than $|A|.|B|$. Thus, if there are not more than $f(m)$ minimal DFAs of size at most $m$ then the size of the minimal DFA for the union of the $D_i$ can not exceed $m^{f(m)}$. Sounds correct ?

Considering that for $|\Sigma|=2$ the transition function of a DFA of size at most $m$ is a graph. Since the nodes degree is bounded by $2$, for each node there are $m^2$ possibilities of pairs of arcs. In this graph there are at most $m$ possible choices of initial state and at most $2^m$ possible choices of final states sets. Thus, the maximum number of DFAs of size at most $m$ is $f(m) \leq m^{2m}.m.2^m = 2^m.m^{2m+1}$.

Thus we can conclude that for $|\Sigma|=2$ the maximal number of states required for the union of $n$ DFAs of size at most $m$ is bounded by $m^{f(m)} = m^{2^m.m^{2m+1}}$.

We can then generalize to an arbitrary alphabet $\Sigma$ : the bound becomes $f(m) \le 2^m.m^{|\Sigma|m+1}$. But it looks like this bound could be tighter though...

Does someone have a better estimate ?

One motivation to find a tighter bound is that if we fix the amount $S$ (in number of states) of memory that is available on a computer then we could easily get the maximal size $m$ that the $n$ DFAs must not exceed in order to guarantee the complete computation of the minimal DFA $D_L$ for the union of the $n$ DFAs.

I would appreciate if possible, some papers related to this problem or a proof/counter-example.

Many thanks, Luz


texts: Asymptotic Question - Determining average case runtime of linear search with summation formula

texts:
My confusion arises when solving the average case. I thought that it would be: 1/n * (number of elements)

But in the solution, they do 1/n * (sum of all the elements). I know that this all goes down to N when in big-o notation but why are they summing all elements of the array and how did they get to just the sum formula? I ended up with the same answer but my thought process was different.

Question:
Consider linear search again. How many elements of the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to be any element in the array? How about in the worst case? What are the average-case and worst-case running times of linear search in Θ-notation? Justify your answers.

TextBook Answer

The average should look for (n + 1) / 2 elements

The worst case is n

Assuming equal probability of occurrence 1/n, average number of elements which need to be checked is 1/n * (1 + 2 + ... +n) = (n+1)/2. Running time is Θ(n)

Worst case, the element to search is dead last in the array. In that case n elements need to be searched. Running time is Θ(n)

So all are Θ (n).


texts: How to chose optimal initial pheromone value for a ant colony algorithm

texts:
I am trying to develop an ant colony optimization algorithm that will minimize the electricity load shedding on a given graph. The graph has some supply vertices  and some demand vertices. Supply vertices have the electricity to supply to the other demand vertices. It assume that the supply vertices fulfil its demand then supply to the other demand vertices.

In my method an artificial ant starts from a supply vertex with the electricity that the vertex generated. It will traverse the graph and give the electricity to the demand vertex until the electricity empty that the ant carried. This same ant placed in every supply vertices and distribute the electricity to the demand vertices. Note that if the ant reach in ant supply vertex then the ant do nothing and simply select the next vertex. If there are 10 ants then that 10 ants will distribute the electricity to the graph in 10 way. Note that the every ant will place to the source vertex every time randomly, so that it will ensure that there will no predetermined sequence. After get the result from that 10 ants separately we calculate the which ant has the graph that has minimum load shedding. Then
the pheromone trail will be updated according to path that the ant made.

This is the simple ant colony system that I implemented. To select the next vertex from $i$ to $j$, I used this method:

$$p_{ij}^k = \frac{[\tau_{ij}]^\alpha[\eta_{ij}]^\beta}{\sum_{\ell\in\mathcal{N}_i^k}[\tau_{i\ell}]^\alpha[\eta_{i\ell}]^\beta},\quad\text{if }j\in\mathcal{N}_i^k\,,$$

where the $\eta$ will represent the heuristic value of the next vertex. In my algorithm that is the load shedding value of the next vertex. And the $\tau$ is the pheromone value of the edge between $i$ to $j$. For the reference I am using this book.

The problem is I am not sure how to chose the initial pheromone value. Because the load shedding value is random and and range from 0 to infinity. Therefore this value dominate to chose the next vertex and it act like a greed algorithm. But if the pheromone value will taken carefully then the fluctuation of probability to chose next vertex vary.
Every ant makes the different result only that the ant place in source vertices random sequence.
So My question , what is the method or observation to chose the pheromone value for the initial state.

This is github repository of the code for this algorithm -
https://github.com/muztaba/SmartGridOptimization
Thank you.


texts: What is the relationship between tail recursion with other recursions?

texts:
I'm rather confused by the recursion theory.

From the link, the recursion theory was formed by Dedekind, Gödel and some other famous mathematicians. There are the following types of recursion. But where is tail recursion? can this concept parallel to these concepts? what else concept goes parallel to tail recursion?

 1.1 The Initial Functions
 1.2 Iteration
 1.3 Primitive recursion
 1.4 Primitive recursion with parameters
 1.5 Course-of-value recursion
 1.6 Double recursion
 1.7 Minimization (least search)


texts: How does the automatic complexity analysis of Codility work?

texts:
When completing exercises on Codility.com you submit your code to a server for analysis. You then receive a report containing the detected algorithm complexity of the code.

I was just wondering how it does this automatically - i.e. without any O(n) analysis?


texts: Suitable choice for moderate-size square matrix multiplication?

texts:
The problem is to find $C = AB$, where $A$ and $B$ are $n \times n$ matrices that may be sparse. Let $n$ be around 1000. The elements of $A$ and $B$ are real values, though, for practicality's sake, let's say we use floating-point numbers. Ideally, the approach would be fast enough for small $n$ and, of course, should not require size ($n$ value) of ~$10 ^ 6$ to break even relative to brute-force cubic time approach. The lower the running time, the better. Given ties, the lower the coefficient for running time, the better. Given ties again, lower space requirement is desired. Algebraic or combinatorial approaches are acceptable.

Then, what is a suitable algorithm choice for this moderate-size-input square matrix product problem?


texts: Detecting conservation, loss, or gain in a crafting game with items and recipes

texts:
Suppose we're designing a game like Minecraft where we have lots of items $i_1,i_2,...,i_n\in I$ and a bunch of recipes $r_1,r_2,...,r_m\in R$. Recipes are functions $r:(I\times\mathbb{N})^n\rightarrow I\times\mathbb{N}$, that is they take some items with non-negative integer weights and produce an integer quantity of another item.

For example, the recipe for cake in Minecraft is:

3 milk + 3 wheat + 2 sugar + 1 egg $\rightarrow$ 1 cake

... and the recipe for torches is:

1 stick + 1 coal $\rightarrow$ 4 torches

Some recipes could even be reversible, for example:
9 diamonds $\leftrightarrow$ 1 diamond block

If there's some combination of recipes we can repeatedly apply to get more of the items that we started with then the game is poorly balanced and this can be exploited by players.
It's more desirable that we design the game with recipes that conserve items or possibly lose some items (thermodynamic entropy in the real world - you can't easily un-burn the toast).

Is there an efficient algorithm that can decide if a set of recipes will:

conserve items?
lose items to inefficiency?
gain items?

Is there an efficient algorithm that can find the problematic recipes if a game is imbalanced?

My first thoughts are that there is a graph structure / maximum flow problem here but it's very complex, and that it resembles a knapsack problem. Or maybe it could be formulated as a SAT problem - this is what I'm considering to code it at the moment but something more efficient might exist.

We could encode recipes in a matrix $\mathbf{R}^{m \times n}$ where rows correspond to recipes and columns correspond to items. Column entries are negative if an item is consumed by a recipe, positive if it's produced by the recipe, and zero if it's unused. Similar to a well known matrix method for graph cycle detection, we could raise $\mathbf{R}$ to some high power and get sums of each row to see if item totals keep going up, stay balanced, or go negative. However, I'm not confident this always works.

Any discussion, code, or recommended reading is very appreciated.


texts: Deterministic context-free languages are not in general closed under substitution. I have been looking at the DK-test (it is described in the 3rd edition of Sipser's Intro. to Theory of Computation, 2012) which can be used to check if a given CFG is deterministic, and it seems to me this can be used to show that DCFLs are closed under substitution when the substituted languages are disjoint DCFLs. Is this a known result? Or is anything known about the substitution closure of DCFLs with other restrictions on the substituted languages?


texts: Online and parallizeable set intersection algorithm

texts:
I have problem that is reducible to the following:

From a collection of stacks, find all items whose "keys" are on all stacks.

My current solution to this problem is to just pop things off as quickly as possible store the items in the language's set type, compute the intersection every once in a while (the stacks are refilling constantly), and use that set, repeat.

The issue here is that the equivalent of the pop operation is expensive (I can do this at most 4k times a second), and it kills the chance of multithreading (as pops are destructive).

Is there a way of doing this such that I can multithread the intersection bit? I cannot practically use shared memory or requeuing items. The threads can communicate with each other via pipes/sockets if need be, but such communication should be kept to a minimum (not really interesting in starting up some whole separate client/server thing just for this part of my application)

As an idea of what I am dealing with, there can be up to 15 million items on the queues at any one time. By the time its "over" all items will have a match.

Ideas?

Clarification: These are message stacks (well queues really but the same thing) over the network. A pop is a consume operation over network, and push is a publish. Thats why its so slow. Since the issues is one of latency rather than bandwidth, multithreading can potentially help. I am not CPU bound. I have ~10 stacks, and up to 10 million items at a time. I have no control over the implementation of the stacks.


texts:
In classical computers we have List,Queue,Tree & etc data structures, since classical computers using 1's & 0's on those data structures. Then what happens when it comes to quantum computers,
Do they(computer scientists) need to create new data structures ?
Or use existing data structures with some sort of optimization ?
Thanks in advance.


texts: What are efficient data structures for inserting and accessing elements?

texts:
Is there a data structure to keep a list of elements (not necessarily sorted) that performs the Access (by index) and Insert operations in a reasonable asymptotic time?

When I say "reasonable time", I mean that it should be equal to or better than $O(\log N)$.

I'm looking for a structure similar to a dynamic array, but I need a better behavior in the Insertion operation. When the array size grows, the time grows exponentially (Except at the end of the array).


texts: How to prove that this language is not recursive enumerable?

texts:
I need to prove that the following language is not recursively enumerable, while its compliment is recursive enumerable:
$L := \{w \in \{0,1\}^* |$ TM $M$ with $w = \langle $ M $\rangle$ does not receive any input $\}$.
Should I use reduction from the halting problem in this case?


texts: Decidability of checking an antiderivative?

texts:
Let's suppose I have two functions $F$ and $G$ and I'm interested in determining whether

$$F(x) = \int G(x)dx.$$

Let's suppose that my functions are composed of elementary functions (polynomials, exponentials, logs, and trigonometric functions), but not, say, Taylor series.

Is this problem decidable? If not, it is it semidecidable?

(I'm asking because I'm teaching a class on computability and a student asked me if a TM could help you integrate a function whose integral was not currently known. I suspect that the functions we don't know how to integrate are more properly functions whose integral can't be expressed as a combination of the above elementary functions rather than functions for which we don't actually know the integral, but that got me thinking about whether the general problem of checking integrals was decidable.)


texts: Quicksort Partitioning: Hoare vs. Lomuto

texts:
There are two quicksort partition methods mentioned in Cormen:

(the argument A is the array, and [p, r] is the range, inclusive, to perform the partition on. The returned value is the index to the pivot after the partition.)

Hoare-Partition(A, p, r)
x = A[p]
i = p - 1
j = r + 1
while true
    repeat
        j = j - 1
    until A[j] <= x
    repeat
        i = i + 1
    until A[i] >= x
    if i < j
        swap( A[i], A[j] )
    else
        return j

and:

Lomuto-Partition(A, p, r)
x = A[r]
i = p - 1
for j = p to r - 1
    if A[j] <= x
        i = i + 1
        swap( A[i], A[j] )
swap( A[i + 1], A[r] )
return i + 1

Disregarding the method of choosing the pivot, in what situations is one preferable to the other?  I know for instance that Lomuto preforms relatively poorly when there is a high percentage of duplicate values ( i.e. where say more than 2/3rds the array is the same value ), whereas Hoare performs just fine in that situation.

What other special cases make one partition method significant better than the other?


texts: Recommendation algorithms based on a set of attributes

texts:
I'm building an application which should suggest products for the users. I want to base my recommendation on different attributes, like location, weather, date, etc. Each of these attributes can have multiple values so the feature space I need to consider is huge.
I was thinking about two approaches to solve this problem.
Firstly, using decision trees, so I create the tables with different decisions, e.g.

sunny; hot; France; summer; choose xyz
overcast, warm, Italy, spring, choose abc

Based on this data I could learn the decision tree and use it in my application.

Secondly, I could tag every recommendation item with the possible attributes to which it applies. For example:

xyz: {sunny} {hot} {France, Spain} {spring, summer}
abc: {overcast, raining} {cold, warm} {Italy} {spring, summer}

Then, based on the actual values of the attributes from the user I could infer an item to recommend.

The second option looks better for me as it requires from me only describing the recommendation items while the first approach requires describing a lot of situations which might happen so that the decision tree is of high quality. Unfortunately, I don't know any algorithm for the second solution.

Which approach would you use? If the second one, than what are the possible algorithms to have a look at?


texts: How to find close match of levenshtein distance

texts:
Let's say we have some function,

float distance(String a, String b) { /*...*/ }

to find the Levenshtein distance between two strings, and we have a large array of strings.

String[] strings = new String[1_000_000];

What would be an acceptable approach to map a String a to its closest match (i.e., the String b that produces the lowest result of distance(a, b)) in that array? This will need to be done often, and so going through the entire array every time would not make sense.

Of course, strings need not be an array.


texts: Complexity of dynamic card game algorithm

texts:
Consider the following dynamic card game with a regular deck of 26 red cards and 26 black cards. A dealer draws the unturned cards one by one, and we can ask him to stop at any time. For every red card drawn, we get 1 dollar and lose 1 dollar for every black card drawn. The problem consists in finding an algorithm which returns the expected value of the game. If we denote by $b$ and $r$, respectively, the number of black and red cards left in the deck at any time, the expected value of the game $E(b,r)$ satisfies:

$$E(b,r)=\max\left\{b-r,\frac{b}{b+r}\,E(b-1,r)+\frac{r}{b+r}\,E(b,r-1)\right\}\,,$$

with boundary conditions $E(0,r)=0$ and $E(b,0)=b$. The expected value of the game is therefore given by $E(26,26)$.

My question is, if we implement the recursive algorithm associated with the above formula, how can we determine its complexity? Using the trivial cases of $E(1,1)$ and $E(2,2)$, it would appear that we are dealing with exponential complexity, but is there a way to prove this properly, and if so, what is the number of necessary operations to compute $E(n,n)$ for an arbitrarily large integer $n$? Any ideas or references to literature would be greatly appreciated.


texts:
What is the time complexity of Halley's Method?

I am thinking ${\cal O}(\log(n)F(n))$, or something very similar to Newton-Raphson, but I feel as though there should be some change to the complexity in order to yield the greater convergence. However, I can't seem to find any solid ground to support any of my ideas (as nobody has ever seemed to have asked this question on the internet before)...

Halley's Method - Wikipedia


texts: Algorithm to find the first person in front of $A$ that is shorter than $A$

texts:
We have an array of $n$  positive integers $a_0,a_1\dots a_{n-1}$ and let $a_n=0$.

I need to build an array $b_0,b_1\dots b_{n-1}$ such that $b_i$ is the first integer larger than $i$ with $a_{b_i}\leq a_i$.  (Note that there is no requirement that the $b_i$ be distinct.)

Does anybody know if this can be done in reasonable time? (say $\mathcal O(n\log n)$ for example)


texts:
The task

If $x \in \mathbb{R}^d$ is a $d$-dimensional vector, recall that the $\ell_1$ norm of $x$ is given by

$$||x||_1 = |x_1| + |x_2| + \dots + |x_d|.$$

The $\ell_1$-ball of radius $\lambda$ is the set of points $x$ such that $||x||_1 \le \lambda$.

Consider the following algorithmic task:

Input: $x \in \mathbb{R}^d$, $\lambda > 0$
Desired output: $y \in \mathbb{R}^d$ such that $||y||_1 \le \lambda$ and $||x-y||_2$ is minimized

In other words, given $x,\lambda$, the goal is to project $x$ to the nearest point in the $\ell_1$-ball of radius $\lambda$.

This problem comes up when we want to learn a linear SVM with L1 regularization using stochastic gradient descent.

A proposed solution in the literature

The following paper proposes a solution:

D. Sculley, Matthew Eric Otey, Michael Pohl, Bridget Spitznagel, John Hainsworth, Yunkai Zhou.  Detecting Adversarial Advertisements in the Wild.  KDD 2011.

They propose an iterative algorithm $A$, with the property that iterating $A$ on $x$ eventually converges to the desired $y$: i.e., the sequence $x,A(x),A(A(x)),A(A(A(x))),\dots$ converges to the desired value $y$.  Their algorithm is in Figure 2 and is as follows:

Algorithm $A$, with input $x$:
 1. $c := \max(\lambda - ||x||_1,0)$
 2. $d := ||x||_0$
 3. $\tau := c/d$
 4. for each non-zero element $i$ of $x$, do:
 5.     $\qquad s := \text{sign}(x_i)$
 6.     $\qquad x_i := s \times \max(|x_i - \tau|,0)$
 7. return $x$

However, I don't see why this algorithm works.  For instance, at minimum we'd want the output of this algorithm to always satisfy $\lambda \le ||A(x)||_1 < ||x||_1$, but this doesn't seem to hold.  This algorithm often does nothing to the input if $||x||_1 > \lambda$, and it typically shrinks $x$ if $||x||_1 \le \lambda$; this seems backwards (we want the reverse).

Also, $\max(|x_i - \tau|,0)$ is an odd expression, as we always have $\max(|x_i - \tau|,0) = |x_i - \tau|$, so I don't understand why the max is there.

My question

Does the algorithm from Sculley et al. actually work?  Is there a typo or an error in this algorithm?  If so, can it be fixed?


texts: Prove that if $p_1 \times p_2$ is positive, then $p_1$ is clockwise from $p_2$?

texts:
In Introduction to Algorithms (CLRS), Exercise 33-1-1, we are asked to prove that if $p_1 \times p_2$ is positive then $p_1$ is clockwise from $p_2$ and if it's negative, then $p_1$ is counter-clockwise from $p_2$.
This is a picture from CLRS

I found the following proof:
https://sites.math.rutgers.edu/~ajl213/CLRS/Ch33.pdf
The proof above says to consider the angles both vectors make with the x-axis. We know the angle is $\arctan y/x$. We also know the cross product $p_1 \times p_2 = x_1y_2 - y_1x_2$. If this product is greater than zero, then this means that $y_2/x_2 > y_1/x_1$. Since $\arctan$ is monotone then the angle $p_2$ makes with the x-axis is larger. which means you need to move clockwise direction to get from $p_2$ to $p_1$
BUT the question is asking to prove that $p_1$ is clockwise relative $p_2$. What am I missing? is the above proof wrong?
I drew the following based on the proof above:


texts: Two-head one way finite memory machine accepts non-regular languages

texts:
I'm having trouble proving, or understanding why a two-head one-way finite memory machine could accept a non-regular language– for instance, $(w \mid w \in (a,b)^{*}, w= a^i b^i, i\geq 0)$.

For clarity, a two-head one-way finite memory machine works as follows –    it has  a   finite  control and a read-only input tape. The input tape  contains a  string, with a  special blank symbol at the right end. The  machine starts in the start state with both heads on the first symbol of    the input string. In one step the machine reads the current symbols under the two read heads, moves one or both of the heads one position to    the right, and  changes state. Each step of the machine is uniquely determined  by  its current state and the symbols read by the two heads. (That is, the machine  is deterministic.)  The machine accepts the input string    if  it  reaches an  accepting   state.


texts: Determine if two LR(1) action/goto tables always produce the same derivation

texts:
I am experimenting with implementing minimal LR(1) algorithms/techniques, but I find it very difficult to verify the correctness of what I've implemented.

Is there a fast algorithm to determine if two LR(1) action/goto tables accept the same language, given that they use the same grammar rules?

Or preferably a stronger (but easier to falsify) test, that two LR(1) action/goto tables will always produce the same derivation for any input.


texts:
Problem Statement: Given a string/pattern only consisting of '<' and '>' symbol, find the lexicographically smallest string that satisfies the pattern(made up of only lowercase english alphabets). Some examples are given below for better understanding.
Examples:

Input(String) - '>>'
Output(String) - 'cba' (because c > b > a)
Input(String) - '>'
Output(String) - 'ba' (because b > a)
Input(String) - '><>'
Output(String) - 'badc' (because b > a < d > c)

Constraints: String/Pattern length is always <= 25 and in the output string, no alphabet should be repeated.
I am unable to come up with any approach which has a lesser complexity than O(N!)(which would surely never pass the time limits), N being the given string/pattern's length. Any help is appreciated.
P.S. - This problem was asked in a HackerEarth hiring contest, and no, the contest is no longer live.


texts: Greedy Probabilistic Algorithm for $Exact$ $Three$ $Cover$

texts:
I have a probabilistic greedy algorithm for Exact Three Cover. I doubt it'll work on all inputs in polytime. Because the algorithm does not run $2^n$ time. I will assume that it works for some but not all inputs.
Our inputs are $S$ and $B$
$S$ is just a set of integers
$B$ is a list of 3-element {}s
Algorithm

Input validation functions are used to ensure that sets of 3 are $elements$ ∈ $S$.

A simple $if~~statement$ makes sure that $|S|$ % $3$ = $0$

I treat the sets like lists in my algorithm. So, I will sort all my sets from smallest to largest magnitudes (eg {3,2,1} now will be sorted to {1,2,3} )

I will also sort my list of sets called $B$ in an ordering where I can find all {1,2,x}s with all other {1,2,x}s. (eg, sorted list {1,2,3},{1,2,4},{4,5,6},{4,5,9},{7,6,5} )

I will also generate a new list of sets containing elements where a {1,2,x} only occurs one time in $B$.

Use brute force on small inputs and on both sides of the list $B$ up to $|S|$ / $3$ * $2$ sets. (eg. use brute force to check for exact covers on left and right side of the list B[0:length(s)//3*2] and reversed B[0:length(s)//3*2])

Seed the PRNG with a Quantum Random Number Generator
for a in range(0, length(B)):
    o = quantumrandom.randint(0, length(B))
    random.seed(int(o))

# I will create a function to shuffle B later

def shuff(B, n):
    for i in range(n-1,0,-1):
        random.seed()
        j = random.randint(0,i+1)
        B[i],B[j] = B[j],B[i]

Define the number of times while loop will run
n = length(s)

# This is a large constant. No instances
# are impractical to solve.

while_loop_steps = n*241*((n*241)-1)*((n*241)-2)//6

While loop
stop = 0
Potential_solution = []
opps = 0
failed_lists = 0
ss = s

while stop <= while_loop_steps:

    opps = opps + 1
    stop = stop + 1

    shuff(B,length(B))

    if length(Potential_solution) == length(ss)//3:
        # break if Exact
        # three cover is
        # found.
        OUTPUT YES
        failed_lists = failed_lists + 1
        HALT

    # opps helps
    # me see
    # if I miss a correct
    # list

    if opps > length(B):
        if failed_lists < 1:
            s = set()
            opps = 0

    # Keep B[0]
    # and append to
    # end of list
    # del B[0]
    # to push >>
    # in list.

    B.append(B[0])
    del [B[0]]
    Potential_solution = []
    s = set()

    for l in B:
        if not any(v in s for v in l):
            Potential_solution.append(l)
            s.update(l)

Run a second while loop for new_list if Step 5 meets the condition of there being only ONE {1,2,x}s )eg. {7,6,5} shown in step 4
Two Questions
How expensive would my algorithm be as an approximation for $Three$ $Cover$?
And, what is the probability that my algorithm fails to find an $Exact$ $Three$ $Cover$ when one exists?


texts: How to write an algorithm which doubles stack in order to accommodate for new members where push is in constant time in the worst case?

texts:
We're given the algorithm which uses stack in order to store data (stack is implemented via an array). When the stack is full the algorithm does the following:

Creates a new array double the size of the original one.
Copies all elements of the old array to the new array, preserving the order.

Adjust the algorithm so that the insertion of new element will be in constant time in the worst case.

The limitation here is we must use arrays as stack implementation.
The worst case is when for example the old stack of size $n$ is full and now we need to insert a new element. So we create a new stack $S_2$ of size $2n$ and we want to insert the new element to $S_2[n+1]$.
I'm stuck with the constant time requirement, I'd appreciate any hints to the right direction.
NB: I'm aware that the title is a bit general, I couldn't think of anything more specific, if you know under which category of algorithms it falls under please let me know and I'll edit the heading.


texts: Proof that median of an array is the number that minimizes the sum of manhattan distance to all points

texts:
Given a sorted array A, the problem is to find a number that minimizes the sum of Manhattan distance to the numbers in the array. I found that the median of A is the solution, but was not able to come up for a proof or explanation for the same ( i.e why its not mean).

Any help is highly appreciated.


texts:
Hi I'm attempting to self teach myself from Algorithms (Sedgewick) and ran across the following problem:

3.1.15: Assume that searches are 1,000 times more frequent
than insertions for a BinarySearchST client. Estimate the
percentage of the total time that is devoted to insertions,
when the number of searches is 10^3, 10^6, and 10^9.

As stated in the problem Searches (S) = 1000 * Inserts (I)

$S = 10^3 \to I = 1$
$S = 10^6 \to I = 10^3$
$S = 10^9 \to I = 10^6$

At this point in the book we are using simple arrays and linked lists to back symbol table (not efficient hash maps, trees, etc). This would mean searches take ~log2(N) time and insertions take ~N/2 time (assuming a uniform distribution on where inserts are placed).

Am I correct in calculating the % of insert to search time would approximately be:

$\frac{Inserts \times N/2}{Searches \times \log_2(N)}$

Using $Searches = 10^3 \times Inserts$ this reduces to

$\frac{N/2}{(10^3 \times log_2(N)}$

This would mean the percentage depends heavily on the initial size of the symbol table and is not a steady percentage that we can use to answer the question.

Any suggestions for what I am overlooking, should I be making an assumption about the initial size of the table?