texts:
What is the best book for a beginner in Introduction to number theory?

I am new to this field and getting deeper into cryptography, so I think reading some intro books about number theory can be of help.


texts: Allocating n processes to n servers, counting from the server perspective

texts:
In this question, I asked about a confusion I had counting the size of the sample space for allocation of n processes to n servers. Bangye gave a simple answer by approaching the counting problem from the perspective of the choice when allocating each process.

I'd like to know -- to expand my understanding of counting -- how we might count in a different way, from the server perspective: assigning each server to some number of processes.

The obvious problem I see is if I have already allocated one process to a server, I then can't allocate it to another, and so the analysis becomes complicated -- each server-based count is dependent on all other server-based counts.

Is this a common problem, and there's actually a heuristic to know which way to count things?


texts:
What does this expression mean?
Normal distribution with condition
I am reading a research paper and found the following expression (Eq.28 in the paper below).

It means a Gaussian distribution, but the mean component seems conditional probability-like expression $\it{\bf{s}}_t | \it{\bf{m}}_{b, t, m}^{(j)}$.
I have never seen this expression before and cannot find any info about it.
The variables $\it{\bf{s}}_t$ and $\it{\bf{m}}_{b, t, m}^{(j)}$ are both vectors and $\bf{\Sigma}_{b}$ is a covariance matrix.
Does anybody have an idea of what this expression means?
Original paper where the expression is.
The original paper can be found here: https://eprints.soton.ac.uk/437941/1/08340823.pdf
Thanks in advance.


texts: Most Efficient Method To Determine Triangle Fill Values Based On Corner Values

texts:
I have a triangle and the value of the pixel intensity at each of the three corners of the triangle.  I want to interpolate to find interpolated pixel intensities for a set of points inside the triangle.  How can I do this?

The method I've tried is to do an value determination based on the distance of that fill-in point from each of the corners.

As an example, here is a single triangle example, with three points described in the format of (Value, X, Y), though in practice all values might be floating point.

(1.78, 2337, 1955)
(2.95, 2342, 1948)
(1.12, 2347, 1941)


texts: How hard is it to factorize sum of two numbers

texts:
Say I have numbers with known factorizations $n = \prod \limits _i p_i ^{n_i}$ and  $m = \prod \limits _i p_i ^{m_i}$ (where $p_i$ is the $i$th prime).

How hard is it to factorize $m+n$? Is there a more intelligent algorithm than if factorizations of $m$ and $n$ were not known? Assume $n$ and $m$ coprime as it is trivial to make them so.

The fact that $m+n$ will share no factors with $n$ or $m$ seems very helpful for small numbers, but I doubt it offers much for large ones.


texts: Does Damas-Milner still have principal types if existential type schemata are added?

texts:
In the Damas-Milner type system, type schemata can be formed in two ways:

$T$
$\forall X. S$

Where $T$ ranges over monotypes and $S$ ranges over type schemata. The type-checking algorithm for this system is well known, and explanations of it can be found in several places.

What happens if I add a third type schema former?

$\exists X. S$

In other words, type schemata must still be in prenex normal form, but both universal and existential quantifiers may be used. As in Damas-Milner, only let-bound variables may be ascribed type schemata.

My questions are:

Does this system still have principal types?
How much does the type-checking algorithm change?


texts:
I'm interested in balanced base $B$ representation for fixed point arithmetic. The paper Fixed-point arithmetic in SHE schemes (Costache, Smart, Vivek and Waller, in Proceedings of 23rd International Conference on Selected Areas in Cryptography (SAC 2016), Springer Lecture Notes in Computer Science, vol. 10532, pp. 401–422, 2016; PDF) provides two examples using balanced based $B=3$. However, I don't understand the 2nd second representation, i.e.
$$\frac{8}{3}=10.\bar{1} $$
where $\bar{1}=-1$.
More generally speaking, I'm also interested in balanced form representation $B=5, 7$.
I believe this should be a well-known problem, though I was not able to google it. Do you know some relevant literature to this?


texts:
I am reading https://www.irif.fr/~mellies/mpri/mpri-ens/biblio/Selinger-Lambda-Calculus-Notes.pdf and would like to know, what the following statement means:

Lambda terms: M,N ::= x | (M N) | (λx.M).

It is from page 11.

What does for example mean? Is x a type of M and N?


texts: Should one limit the maximum level of a skip list node?

texts:
In Skip Lists: A Probabilistic Alternative to Balanced Trees by Pugh he suggests different strategies for choosing the level of an inserted node. One such strategy, called fix the dice, limits the level to our previous highest level plus one if a higher level was randomly chosen.
What are the practical implications of choosing this strategy, especially for large skip lists and those with p < 1/2?
I imagine it could lead to a higher than usual fanout, but without all too dramatic effects, especially if deletions are as common as insertions after some growth (since that would minimize the effect of lower than usual levels after that initial growth).
Any educated speculation or hints to already existing analyses are welcome.


texts:
Knuth, Donald E. (1971), "Optimum binary search trees", Acta Informatica 1 (1): 14–25,doi:10.1007/BF00264289

Please have a look at this paper, specifically page 18 in which he tries to prove his lemma that $R_{0,n-1} \leq R_{0,n} $ here $R$ refers to the minimal optimal node which will be the root of the binary tree containing elements $a_{0} ... a_{n} $ .

I understood the idea of the proof using induction that for some $k \,  j_{k}=i_{k} $ . Now the next part of the proof is cutting and replacing,I have understood perfectly till there. What i don't understand is how $F''$ weighted path length is equal to weighted path length of $F'$ for all $a_{n}$. Can anyone please give me a hint or a solution to that.


texts: Characterize an OS as multiprogrammed OS

texts:
Which of the following features will characterize an OS as multiprogrammed OS?

More than one program may be loaded into main memory at the same
time.
If a program waits for certain event another program is
    immediately scheduled.
If the execution of a program terminates,
        another program is immediately scheduled.

My attempt:

Only, statement (1) is correct, but statement (2) and (3) may not be true when there were no process at ready state. So, they should be false.

But, somewhere it explained as both statement (1) and (2) are true, and (3) is false.

And also, official key is given all statements are correct.

  Can you explain it, please?


texts: 3-SAT with negative-literals in each clause

texts:
Does a 3-SAT problem, where in each clause there is at least a negative-literal, always has a solution?

After looking at it, seems to me that the answer is yes, but maybe there is something I am not seeing.


texts: Are programming languages becoming more like natural languages?

texts:
Can we study programming languages in the context of linguistics? Do programming languages evolve naturally in similar ways to natural languages?

Although full rationality, and mathematical consistency is essential to programming languages, there still is the need (especially modern languages) to make them readable and comfortable to humans.

Are programming languages evolving to become more linguistic and thus more natural? For example machine code, punch cards and assembly languages have given way to more readable languages like Ruby and Python etc.

When I say computer languages are becoming more natural, I don't mean they contain more 'words we have in english', I mean they seem to becoming more like a natural language, in terms of their complexity of grammer and ability to express meaning (for example, being able to eloquently describe a query from a database in both rational and human understandable ways).

What do you all think? Are programming languages becoming more like natural languages, and thus becoming applicable to the laws of Linguistics?

Or perhaps languages live on a spectrum, where on one side you have the extreme rational languages and the other the more creative. Maybe, programming and natural languages are identical and both just lie on this language spectrum (their only difference, perhaps being the 'thing' they are trying to give their meaning to).

Is there a connection between the (Babel Tower effect) separation of human languages and of computer langages? Do they become more diverse for the same reasons (i.e. to solve different problems within ever-evolving computer-systems/culture-systems etc.)?


texts: NP-complete decision problems - how close can we come to a solution?

texts:
After we prove that a certain optimization problem is NP-hard, the natural next step is to look for a polynomial algorithm that comes close to the optimal solution - preferrably with a constant approximation factor.

After we prove that a certain decision problem is NP-complete, what is the natural next step? Obviously we cannot "approximate" a boolean value...

My guess is that, the next step is to look for a randomized algorithm that returns the correct solution with a high probability. Is this correct?

If so, what probability of being correct can we expect to get from such a randomized algorithm?

As far as I understand from Wikipedia, PP contains NP. This means that, if the problem is in NP, it should be easy to write an algorithm that is correct more than $0.5$ of the times.

However, it is not known whether BPP contains NP. This means that, it may be difficult (if not impossible) to write an algorithm that is correct more than $0.5+\epsilon$ of the times, for every positive $\epsilon$ independent of the size of input.

Did I understand correctly?


texts: What can Idris not do by giving up Turing completeness?

texts:
I know that Idris has dependent types but isn't turing complete. What can it not do by giving up Turing completeness, and is this related to having dependent types?

I guess this is quite a specific question, but I don't know a huge amount about dependent types and related type systems.


texts: Optimization version of decision problems

texts:
It is known that each optimization/search problem has an equivalent decision problem. For example the shortest path problem

  optimization/search version:
  Given an undirected unweighted graph $G = (V, E)$ and two vertices $v,u\in V$, find a shortest path between $v$ and $u$.
  decision version:
  Given an undirected unweighted graph $G = (V, E)$, two vertices $v,u\in V$, and a non-negative integer $k$, is there a path in $G$ between $u$ and $v$ whose length is at most $k$?

In general, "Find $x^*\in X$ s.t. $f(x^*) = \min\{f(x)\mid x\in X\}$!" becomes "Is there $x\in X$ s.t. $f(x) \leq k$?".

But is the reverse also true, i.e. is there an equivalent optimization problem for every decision problem? If not, what is an example of a decision problem that has no equivalent optimization problem?


texts: Which sort algorithm can I use as a metaphor for this learning philosophy?

texts:
TL;DR

Which sort algorithm:

Works in multiple passes.
Performs less and less of the total work at each subsequent pass.
When visualized, makes it clear that the decreasing amount of work at each stage is the result of "reaping the benefits" of the work done in previous stages.

The Long version

My nephew is having trouble with math at school and his teacher's methods don't seem to be doing him much good either, so I've begun to tutor him here and there and it's become clear that he has some gaps in his understanding which are hindering his progress. However, he resisting review of things he feels he is already familiar with because this feels like a waste of time to him, after all he "knows that already!". He's a bright kid but like so many children these days (and possibly since the dawn of mankind) he seems to want to rush ahead as quickly as possible, which hurts him in the long run.

There's ample pedagogical evidence that the mastery of a subject before progressing yields better results in the long run, but this can obviously feel like progress is much slower when you're just getting started. I've certainly felt that way and had to discipline myself to believe that deep understanding will beat mechanical routine in the long run (proficiency is important as well, of course).

So partly in an effort to make this case to him convincingly and perhaps mostly because I have a natural tendency to think about such things in algorithmic terms, I'm asking: which (if any) sorting algorithm(s) serve as a good illustration of this principle, that slow progress (more work?) in the initial stages makes subsequent steps easier (less work).

Quicksort's recursive nature isn't a good fit, and neither is merge sort. Insertion sort takes longer at each step (on average, about $k/2$ comparisons at stage $k+1$, I think) while bubble sort only does one comparison less at each pass.

I'm not concerned about $O(n^2)$ vs. $O(n\log n)$, sorting is an imperfect analogy for learning anyway. I'm just looking for a process I can visualize for him, that will set him thinking and that, hopefully, will give him a model to grab onto for use as a mental model for the process of learning (math), a model that places emphasis (and justifies the hard work involved in) on understanding of concepts instead of the memorization of procedures, even when it seems this gets you to the final answer more slowly.

The answer doesn't have to be a sorting algorithm actually, it just seems like the most natural place to look for such an example.

* Bonus points for providing an animation.


texts:
I am trying to complete question and would like to avoid copying answers, but I do not necessarily understand what I am doing.

I am working on the following problem:

  Suppose you are consulting for a company that manufactures PC. equipment and ships it to distributors all over the country. For each of the next n weeks, they have a projected supply $s_i$ of equipment (measured in pounds) that has to be shipped by an air freight carrier. Each weeks supply can be carried by one of two air freight companies, $A$ or $B$.

  Company $A$ charges a fixed rate $r$ per pound (so it costs $r$ x $s$ to ship a week's supply $s_i$).
  Company $B$ makes contracts for a fixed amount $c$ per week. independent of the weight. However, contracts with company $B$ must be made in blocks of four consecutive weeks at a time.

  A schedule for the PC company is a choice of air freight company ($A$ or $B$) for each of the $n$ weeks with the restriction that company $B$, whenever it is chosen, must be chosen for blocks of four contiguous weeks in time. The cost of the schedule is the total amount paid to company $A$ and $B$, according to the description above.

  Give a polynomial-time algorithm that takes a sequence of supply values $s_1, s_2, \cdots, s_n$ and returns a schedule of minimum cost. For example, suppose $r = 1$, $c = 10$, and the sequence of values is
  $11, 9, 9, 12, 12, 12, 12, 9, 9, 11.$

  Then the optimal schedule would be to choose company $A$ for the first three weeks, company $B$ for the next block of four contiguous weeks. and then company $A$ for the final three weeks.

I am trying to write algorithm, in pseudo code, that completed the following steps in order to solve the challenge, but I don't know even where begin this solution. My initial suspect on how to solve this:

Determine what the "optimal" formula looks like, which is: MIN((r*s + OPT(i-1), (3c + OPT(i-3))

This would determine the most optimal between $A$ or $B$ given their restrictions.
Therefore I would need to determine the most optimal schedules for the weeks preceding the $i^{\text{th}}$ week. Meaning I would end up running OPT(n-1) for every n, thus resulting in OPT(n) total runs so (n) time complexity.

Any advice on how to generate pseudocode for this would be appreciated...I am trying to learn but am not very effective.


texts:
I am having diffuculties understanding the principle of lookahead in LR(1) - items. How do I compute the lookahead sets ?

Say for an example that I have the following grammar:

S -> AB
A -> aAb | b
B -> d

Then the first state will look like this:

S -> .AB , {look ahead}
A -> .aAb, {look ahead}
A -> .b, {look ahead}

I now what look aheads are, but I don't know how to compute them. I have googled for answers but there isn't any webpage that explains this in a simple manner.

Thanks in advance


texts: Is this modified version of Nim solvable?

texts:
In the regular version of the game Nim, you have $n$ piles of stones, and you may remove one or more stones from a single pile in your turn. A modification I thought of involves the concept of piles that may contain not just stones, but also other piles. Let's call these "super-piles". Similarly, we may have "super-super-piles" – piles that may contain stones, piles, or super-piles. In general, a "$k$-pile" may contain stones, and/or $i$-piles for any $1\leq i<k$.

Now, in your turn, you may choose any $k$-pile, and remove all of its contents. Note that this $k$-pile may either be the outermost one, being contained in no bigger pile, or else it may be one of the contents of a $(k+1)$-pile. As in regular Nim, the person with no possible move loses.

Is this version of Nim known? Does it have a name? I've tried looking it up on the internet and in popular Game Theory textbooks, but I've had no luck. If this has not been worked upon previously, Can this game be solved using the Sprague–Grundy theorem? In simpler words, given the starting state of the game, can you predict whether the first player would win or the second one, assuming both players play optimally?


texts: Is address bus size same as physical address size and is that the same as word size?

texts: I am having some confusion between address bus size, physical address size and word size however (I do understand that unit of memory access is word and when word size is one byte then it's known as byte-addressable).


texts:
we have  a six-sided dice numbered from  1 to 6, and each has the probability $p =\frac{1}{6}$. My task is to create a unbiased method to generate a random number  from 1 to 10 using the given dice.
I am aware that the method should maps the following set $$ \{1,\dots 6\}^k\mapsto \{1,\dots, 10\}$$, with $k$ is the number of time we throw the dice. For sure not the 36 elements will be mapped into the set  containing  1 to 10. What i mean, the method will use a while loop and only stops if  a certain tuple is found. My task then is the find those tuples and prove each thoese 10 tuples has the probaitly of $\frac{1}{10}.$
I think $k$ should be 2 in this case , but then i am not quite sure how to extract the  10 elements from 36 elements ($6^k$,with $k=2$) and have a probability of $p'=\frac{1}{10}$.
can we maybe also  generalize that for$ n$ elements ?

$$ \{1,\dots 6\}^k\mapsto \{1,\dots, n\}  $$
I will appreciate any good ideas.


texts: Pushdown automaton from given code for parsing a while statement

texts:
I was preparing for my exam and have some questions that can possibly come on the test.
There is a task to make pushdown automata from a given code:

void compile_while() {
  // while ( expression )
  if (symbol == SYM_WHILE) {
    get_symbol();

    if (symbol == SYM_LPARENTHESIS) {
      get_symbol();

      compile_expression();

      if (symbol == SYM_RPARENTHESIS) {
        get_symbol();

        // zero or more statements: { statement }
        if (symbol == SYM_LBRACE) {
          get_symbol();

          while (is_not_rbrace_or_eof())
            compile_statement();

          if (symbol == SYM_RBRACE)
            get_symbol();
          else {
            syntax_error_symbol();

            exit(EXITCODE_PARSERERROR);
          }
        } else
          // only one statement without {}
          compile_statement();
      } else
        syntax_error_symbol();
    } else
      syntax_error_symbol();
  } else
    syntax_error_symbol();
}

First of all, I don't understand why we need to construct PDA for it because we can do it without stack too and second, I don't understand how the pushdown automata for it would look like.

Can someone help me to understand this task and show me how the PDA for it looks like?


texts:
In some languages (such as C), arrays seem very simple to me. When allocating memory for these, all you need to do is pick a starting point in memory and then allocate the next dataTypeSize * arrayLength bytes as reserved. Retrieving items just means looking at the memory address startPoint + (index * dataTypeSize).

But in other languages (such as JavaScript and ActionScript), there is no requirement to make them fixed when creating the array. In fact, most often in actual use, an empty array is created, then new items are one by one appended to the array in a for loop.

How is the memory managed when you could at any time append add an item to the end, or prepend an item to the beginning? Do you need to redefine space in memory every time the size changes?


texts: Prove that variable projection is recursive

texts:
Let $\varphi:\mathbb{N}\to\mathbb{N}^*$ be an arbitrary recursive enumeration of finite strings and
$\mathcal{I}^n_i(x_1,...,x_n) = x_i $
be the $i$-th projection over $n$ variables.

I would like to show from the point of view of recursion theory that the "variable" projection
$$ (n,y) \mapsto \mathcal{I}_y^{\text{len}(\varphi(n))}(\varphi(n)) $$
is recursive.

Using TMs this is quite straightforward: just simulate the TM that computes $\varphi$ and print only the $y$-th term of that TM executed with input $n$.  I am interested in a purely "recursion-theoretical" proof, i.e., I would like to know how that function can be written in terms of primitive recursion and/or $\mu$-recursion, which I'm finding tricky.


texts: Turing reducibility of 2 versions of the satisfiability problem

texts:
I need help with this problem.

  There are 2 versions of the satisfiability problem:

  [1] decision version: determine whether an arbitrary formula f is
  satisfiable or not

  [2] search version: if an arbitrary formula f is satisfiable, return
  an assignment of truth values to variables in the formula that makes f
  satisfiable. if f is unsatisfiable, return NIL.

  Show that [2] is Turing reducible to [1].

I have to prove that the oracle algorithm of [1] entails that of [2] to say "[2] is Turing reducible to [1]".

I see that [2] is just the oracle algorithm of [1] since it discriminates the satisfiability of an arbitrary formula f.

Can this mean the oracle algorithm of [1] entails that of [2]? If can, what would be the reason?


texts:
The teacher gave us this code that inserts a node in a binary search tree, but I am not sure what the $z.p = y$ instruction does. wouldn't the algorithm work without it?

abr_insert(T, z) //z is the node that must be inserted
    {
            y = NULL;
            x = T.root;
            while(x != NULL)
            {
                    y  = x;
                    if(z.key < x.key)
                            x = x.left;
                    else
                            x = x.right;
            }
            z.p = y; //here is the instruction that I don't understand
            if(y = NULL)
                T.root = z;
            else if(z.key < y,key)
                    y.left = z;
            else
                    y.right = z;
    }


texts: How to generate all possible test cases of length $n$ for comparison sorts

texts:
Comparison sorts only care about the relative order of elements, not their exact values. So if the relative order of two arrays are the same, a comparison sort algorithm will act the same way on those two arrays.

For example, [0, 3, 1, 9, 1] is the same as [-3, 12, 7, 13, 7], since their relative orders are the same.

I want to generate all possible test cases of length $n$ for comparison sorts that all possible relative orders are considered, and no two different test cases have the same relative order.

The number of possible test cases of length $n$ is given by A000670.

Here are all possible test cases of length 0:

[]

Here are all possible test cases of length 1:

[0]

Here are all possible test cases of length 2:

[0, 0]
[0, 1]
[1, 0]

Here are all possible test cases of length 3:

[0, 0, 0]
[0, 0, 1]
[0, 1, 0]
[0, 1, 1]
[0, 1, 2]
[0, 2, 1]
[1, 0, 0]
[1, 0, 1]
[1, 0, 2]
[1, 1, 0]
[1, 2, 0]
[2, 0, 1]
[2, 1, 0]

Is there a generic way rather than brutal force to generate these test cases?


texts: Can hash tables handle variable sized entries?

texts:
Let's say I have a hash table of 10 buckets where each bucket is of a number of bits. However each bucket doesn't have to have the same number of bits. Is it possible to achieve this? Or does it require padding every entry?

For example:

Index 0 has 12 bits.
Index 6 has 5 bits.
Index 1-5, 7-9 are empty.

Does this imply I must have an array of size 12 * 10 = 120 bits, just so that I can modulus into a specific bucket? Or is it possible to store the above in something that is much smaller, ie 17 bits?


texts: Solving constants in the recursive term with master theorem

texts:
We are learning how to solve recurrence relations in different ways (Forward Substitution, Backward Substitution, Master Theorem, etc...). I really thought I understood the topic since most of the problems were in the form of $aT(\frac{n}{b}) + f(n)$ where applying the Master Theorem is no sweat, but we're given this recurrence relation wherein there is a constant inside the recursive term, I am not sure anymore if Master Theorem would still work, or is there another way?
\begin{align*}
T(n) = 3T\left(\frac{n}{3}-2\right) + \frac{n}{2}
\end{align*}
This one has a constant 2 inside the term, and I don't know how to show that this recurrence relation is upper bounded by $ O (n \log n) $.


texts: Query on consequences of $\mathsf{P=BPP}$

texts: We know $\mathsf{P=BPP} \implies \mathsf{NEXP\not\subseteq P/Poly}$ or permanent does not have polynomial sized circuits. However permanent needs superpoly circuits imply $\mathsf{NEXP\not\subseteq P/Poly}$ since $\mathsf{P^{\#P}\subseteq  PSPACE\subseteq NEXP}$. So why dont we just say $\mathsf{P=BPP} \implies \mathsf{NEXP\not\subseteq P/Poly}$?


texts:
GeoQuery is a dataset used for benchmarking semantic parsers. It contains 880 queries about USA geography. The queries are in Prolog format, for example:

  answer(A,longest(A,(river(A),traverse(A,B),const(B,countryid(usa)))))

(this represents a question for the longest river that passes through the us).

I have read several papers about the GeoQuery, but they don't seem to give a formal definition of the grammar underlying the dataset. The email address in the dataset page seem to be dysfunctional. So, my question (addressed primarily to researchers who have worked with the GeoQuery dataset before) is twofold:

Is there a formal definition of the GeoQuery language?
Is this language context-free?

EDIT:

It seems that, if the number of variables (A, B, C...) is unlimited, then GeoQuery is not context-free, because a CFG cannot make sure that two variables in different places are identical (this is similar to the {ww} language, which is not context-free).

But what if we limit ourselves to A, B and C?


texts: Random permutations by probability matrix

texts:
I have the following problem:

I need to generate $\ell$ random permutations each of length $n$ from a list of $m$ elements ($m \ge n$) by a predefined probability matrix $P$ of size $n$ x $m$.

Distribution probability matrix $P$ = {$p_{i,j}$} describes the probability that i-th position is occupied by $j$-th element ($i\in \{1,\dots,n\}$ and $j \in \{1,\dots,m\}$).

Of course
 $1 \ge p_{i,j} \ge 0$ and $\sum\limits_{j=1}^m(p_{i,j}) = 1$ (rows of matrix P are normalized, to be equal 1)

$\sum\limits_{i=1}^n(p_{i,j}) > 0$ (each element has nonzero probability to be at least on one position)

If $p_{i,j} = 0$, then $i$th position of permutation can not be occupied by $j$th element.
 If $p_{i,j} = 1$, then $i$th position is occupied only by $j$th element

Example:
 For $$P = \begin{bmatrix} 0.5 & 0.5 & 0 \\
 0 & 0.5 & 0.5 \\
 0.5 & 0 & 0.5\\
 \end{bmatrix},$$
 I get only two permutations [1 2 3] and [2 3 1] with the same frequency.
 But for $$P = \begin{bmatrix} 0.01 & 0.99 & 0 \\ 0 & 0.01 & 0.99 \\ 0.99 & 0 & 0.01\\ \end{bmatrix},$$ I significantly prefer permutation [2 3 1]

Realistic values $\ell = 1\,000$–$10\,000$, $n = 30$, $m = 50$

Is there any suitable and effective (fast) algorithm?

Edit: The problem is motivated by permutation sampling for stochastic combinatorial optimization. Permutations are parametrized via probability matrix P. The probability matrix P is generated by black-box objective function responses.

Edit2: This is typical algorithm for permutation sampling at stochastic optimization problem:

Generation of partial permutations $x$ by probability matrix $P$

Generate a random permutation $(\pi_1, ... ;\pi_{n})$ of the set of positions $(1,...,m)$.
Define $P(1) = P$ and set $a = 1$.
Generate $x_{\pi_{a}}$ according to the distribution formed by the $a$-th row of $P(a)$ , that is $(p_{(\pi_{a},1)},... ,p_{(\pi_{a},m)})$. Thus, element $x_a$ is placed into position $a$.
Obtain $P(a+1)$ from $P(a)$ by first setting the $x_{a}$-th column of $P(a)$ to 0, and then renormalizing the rows to sum up to 1.
If $a = n$ then stop and return $x$; otherwise set $a = a + 1$ and return to step 3.

Matrix $P$ is during optimization cycle obtained by update algorithm, which produce stochastic (not bistochastic) matrix. I want to be sure, that this algorithm is mathematically correct.


texts: How does C++'s type checking work when passing overloaded or templated functions as parameter

texts:
As I understand, C++ in general features 'one-way' type checking. That is checking the sub-expressions and get their types, and see if the types so far satisfy the constraints imposed by the current expression node. It's an algorithm progressing from bottom to top.

However, C++ also features overloading and template. When you pass such a function directly as the argument to another function, during type checking we cannot immediately get the type of the sub-expression since it is overloaded or using template. So how does it work?

It's possible that C++ does more than 'one-way' type checking. If that's the case, please explain to me how the feature is implemented.


texts:
Could somebody explain the difference between dependent types and refinement types? As I understand it, a refinement type contains all values of a type fulfilling a predicate. Is there a feature of dependent types which distinguishes them?

If it helps, I came across Refined types via the Liquid Haskell project, and dependent types via Coq and Agda. That said, I'm looking for an explanation of how the theories differ.


texts: ML functions from polymorphic lists to polymorphic lists

texts:
I'm learning programming in ML (OCaml), and earlier I asked about ML functions of type 'a -> 'b. Now I've been experimenting a bit with functions of type 'a list -> 'b list. There are some obvious simple examples:

let rec loop l = loop l
let return_empty l = []
let rec loop_if_not_empty = function [] -> []
                                   | l -> loop_if_not_empty l

What I can't figure out is how to make a function that does something other than return the empty list or loop (without using any library function). Can this be done? Is there a way to return non-empty lists?

Edit: Yes, if I have a function of type 'a -> 'b, then I can make another one, or a function of type 'a list -> 'b list, but what I'm wondering here is how to make the first one.


texts: In memory paging, how does the S.O. know where the page is in secondary Memory?

texts:
So every process has its own Page Table, the page table references the frame where the page is in physical memory and also has a valid-invalid bit that tells whether it is in physical memory or in secondary memory.

But how does the S.O. knows exactly where the page is saved when the valid-invalid bit it's off?
Is there another table I'm missing? Or it just does a linear search through the whole SWAP space?


texts: How to determine valid handle for given bottom up parser?

texts:
I came across following question:

  Consider the grammar:

  $E → E + n\text{ | }E × n\text{ | }n$

  For a sentence n + n × n, the handles in the right-sentential form of the reduction are
  (A) $n, E + n$ and $E + n × n$
  (B) $n, E + n$ and $E + E × n$
  (C) $n, n + n$ and $n + n × n$
  (D) $n, E + n$ and $E × n$

Solution given was:

n+n×n
E+n×n  //reduce n to E
E×n    //reduce E+n to E
E      //reduce E×n to E

  Hence option D

Then I came across following problem:

  Consider the following grammar:
  $A\rightarrow A(B)|B$
  $B\rightarrow B*C | id $
  $C\rightarrow (id)$
  Which of the following can be the correct handle in bottom up parsing for the given grammar?
  (A) (id)
  (B) id*C
  (C) id
  (D) none

The given solution was (A)(id)

Doubts

After thinking about the definition of the handle and two problems, I concluded following:

If problem asks which are valid handles for given string and grammar, then we have to actually try parsing that string with given grammar and determine which handles are reduced during parsing.
But, if no string is given, and just the grammar is given, then following are valid handles:
(a) right hand side of each production
(b) those sentential forms which can be derived from start symbol by doing rightmost derivation are valid handles. For example, $B*(id)$ is a valid handle as we can derive it by doing rightmost derivation as follows: $S\rightarrow B\rightarrow B*C\rightarrow B*(id)$

As explained in 2nd bullet point of point 1 above, answer of 2nd problem is wrong and both of $A$ and $C$ options are correct: both $(id)$ and $id$ are valid handles.

Am I correct with both conclusions above?


texts: A query regarding the hierarchy of monotone Complexity Classes

texts:
I have recently started studying the monotone complexity classes. There doesn't seem to be a single/clear containment hierarchy or single source regarding the same. Can we create one?

The classes are namely: $mTC^0, mNC^0, mNC, mAL, mcoNL, mL, mNL, mP, mNP, mP/Poly$. (I think that covers most)

The relationships I am aware of:

$mTC^0 \subset mNC^0 \subset mL$
$mL \subset mNL$
$(mP = mAL) \subset mNP$
$mNC \neq mP$

My queries about containment relationship b/w:

$mNC$ vs. $mP$
$mP/Poly$ vs. $mP$

Please feel free to add Open Questions and other known relationships b/w these classes as you see fit.


texts: A Turing machine recognizing languages of Turing machines

texts:
How can a Turing machine be constructed to recognize languages consisting of Turing machines that accept a certain set of strings?

An example: the language $L = \{\langle M\rangle\mid M \text{ accepts a string }0^n1^n2^n \text{ for some }n\geq 0\}$.

Does a TM recognizing such language exist or are these kinds of languages never recognizable?

If a recognizer exists for such languages, do they base on testing every possible string in input? For example would a valid recognizer for $L$ be:

M = "On input $\langle M\rangle$,

Repeat for $i = 0, 1, 2, 3,\dots$:
Construct string $s=0^i1^i2^i$ and simulate $M$ on $s$. Reject if $M$ rejects $s$, otherwise continue."?

Is there a better way to construct a recognizer for such languages?


texts: Are SAT problems with at most one false clause NP-complete?

texts: Is the problem of deciding whether a SAT instance, where at most one clause is false (that is, any given variable assignment will either lead to all clauses being true, or all but one), is satisfiable solvable in polynomial time?


texts: Designing a context free grammar for a language; When to use the empty string

texts:
$L= \{a^{2i}b^{j}vc^{j}(ac)^{i} |  i,j \ge 0, v \in \{a,b\}^*\}$ over the alphabet $\Sigma = \{a,b,c\}$

How can a grammar be created from the language without the use of the empty string. Below is my example that does use the empty string.

$S \rightarrow aaSac|B$

$B \rightarrow bBc|C$

$C \rightarrow aC|bC|\epsilon $


texts: Automata that recognizes Kleene closure of permutations of three symbols

texts:
This is an automata theory homework question.

I need to create DFA that meets the following criteria:

Alphabet $\Sigma = \{ a, b, c \}$
Machine accepts empty string and strings of length that is a multiple of three, with every block of three containing one $a$, one $b$ and one $c$.

So far, I came up with this machine, it is obvious:

However, I can't get it to accept empty string. Does it mean there is a transition q0 → q3?

Update1:  Following corrections by Dave Clarke I made some corrections.

A regular expression for this machine is $(www)^*$ where $w = \{abc,acb,…\}$. Therefore to represent multiple of three, I need to copy this (on the picture) machine 3 times. Final state should have arrows pointing to the first copy, for transitions marked 'a', 'b','c'.
As it was pointed out, since this is DFA, I need to add missing states. This can be accomplished by adding "dead" states.
Empty string should correspond to $\varepsilon$-transition from qStarting → qFinal.

Update2:
As it was pointed out, my regular expression is wrong ! It should be $(w)^*$. Here is the final machine, that I think should be correct.(I didn't include "dead" state)


texts: Successive shortest path without reduced costs

texts:
The successive shortest path algorithm, used to solve the minimum-cost flow problem, can be described as follows :

  Successive shortest path (for minimum-cost flow) :

  while all flow is not sent :

  compute shortest path between source and sink nodes w.r.t. arc costs (through Dijkstra's algorithm for example).
  augment the most flow possible through this path (and add reverse arcs on this path).
  compute reduced costs on arcs in the network (through updating node potentials).

Is computing reduced costs necessary, i.e., does the algorithm function correctly without modifying any arc costs?

Edit : The algorithm gives the same solution, with or without reduced costs computation, on some example networks done by hand.


texts: Derivation of the energy function of a hopfield network

texts: Can someone please point me towards a rigorous derivation of the energy function of a discrete Hopfield network. What I want, is the derivation must start out with the structure of the network and prove that the critical points of the dynamical system can be obtained by minimization of some function (possibly by constructing the Lyapunov function of the dynamical system). I cannot seem to find such a rigorous proof. Thankyou!


texts:
I am reading Algorithms 4th edition by Robert Sedgewick and am stumped at a particular problem. On page 460 of the book the author is describing a technique to hash strings and use prime numbers for modular hashing. Starting from the fourth line:

 If R is greater than any character value, this computation would
 be equivalent to treating the String as an N-digit base-R integer,
 computing the remainder that results when dividing that number by M.

Where the algorithm being used to hash a N-character long String is:

int hash = 0;
for (int i = 0; i < s.length(); i++)
   hash = (R * hash + s.charAt(i)) % M;

How does the above algorithm result in a base-R integer?

Here M and R are integers (random) and s is the string of length N.

I am assuming that by the 'above computation' the author means the computation within the parentheses => R*hash + s.charAt(i)


texts: Single-source shortest paths as a linear program

texts:
I saw that I can formulate single-source shortest path as the following linear program:

Given $G=(V,E)$ and $w\colon E\to R$ and with negative cycles, find
$\max\,d(s,t)$ such that

\begin{align*}
    d(s,v) &\le d(s,u)+w(u,v) \quad \forall (u,v)\in E \\
    d(s,s) &=0
\end{align*}

We want to find the shortest path from $s$ to $t$ so we are we maximizing $d(s,t)$?


texts:
I have an array, [23,12,11,0,5,2,7,8,15,14]. I choose the rightmost element (14) as the pivot and set lo = 23 and hi = 15. Then since lo = 23 > pivot = 14, I don't change the position of lo. However for hi = 15 it is > pivot = 14, so I move one step to the left, which results in hi = 8. Since hi = 8 is < pivot = 14, I fix the position of hi = 8. Then I swap lo = 23 and hi = 8 which gives the new array [8,12,11,0,5,2,7,23,15,14].
The next lo position is 12 and hi position is 7. Since hi = 7 is < pivot = 14, I fix the hi position at 7. However, for the lo position at 12, it is smaller than the pivot = 14. So, I increase the lo position to 11 then 0 then 5 then 2, all of which is still < pivot = 14. I increase the lo position to 7 which is the hi position too.
After this step, I'm unsure on how to continue. I know that if the element at the position of lo=hi is > pivot, then we can swap it, and obtain 2 partitions (left of pivot and right of pivot). However, in the case the element at lo=hi is < pivot = 14, I'm not sure how to continue.


texts: Can I write a regular expression or regular grammar for this language?

texts:
Let's say I have a formal language,

  a^n b^n which mean ab,aabb,aaabbb

Can I write any regular expression or grammar to create a language like this? I am positive not entirely sure that there is not regex possible, however have no idea about the grammar part?


texts: Help writing a dynamic programming algorithm in English

texts:
It’s Friday night and you have $n$ parties to go to. Party $i$ has a start time $s_i$ end time $t_i$ and a value $v_i \ge 0$. Think of the value as an indicator of how excited you are about that party. You want to pick a subset of the parties to attend so that you get maximum total value. The only constraint is that in order to get a value $v_i$ from party $i$ you need to attend the party from start to finish. Hence you cannot drop in midway and leave before the party ends. This means that if two parties overlap, you can only attend one of them. For example, if party 1 has a start time of 7pm and ends at 9pm and party 2 starts at 7:30pm and ends at 10pm, you can only attend one of them. On the other hand, if party 2 starts at 9pm or later then you can attend both. Given as input start times, end times and values of each of the n parties, design an $O(n \log n)$ time algorithm to plan your night optimally. Describe in English the idea of your algorithm. If you use dynamic programming define the memo table, base case and recursive steps. You don’t need to write the pseudo code or provide a proof of correctness.

I am having difficulty beginning this problem. My initial thought was to have the base case be to choose the value with the initial start time and the greatest $v_i$, however if party $i$ runs for your entire start to end time, you might not maximize $v_i$. I would greatly appreciate some insight into how to do this problem.


texts: Kosaraju's Algorithm-Strongly connected components

texts:
In Kosaraju's Algorithm, using first dfs (traversing on reverse graph) we calculate finishing time of nodes, and then traverse (actual graph) in reverse order of finishing times.
why not without reversing graph, using first dfs (traversing on actual graph) we calculate finishing time of nodes, and then traverse (actual graph) in actual order of finishing times.
In case my proposed method is wrong please provide me with a counter example.


texts: Find list of tickets with best price sum

texts:
I have an optimization problem, where i need to find set of tickets for certain period, such that sum of prices for these tickets is minimal.
Algo should accepts list of trips and list of tickets as input. And output list of tickets with min possible sum price with conditions that this list of tickets covers all trips.
Trip has following fields:
OriginZone
DestinationZone
EndOfTripTimestamp

Ticket object consists of these fields:
OriginZone
DestinationZone
MaxNumberOfTransfers  // 0 if limited by duration
MaxDuration           // 0 if limited by transfers
Price

It's considered that ticket covers trip if Ticket.OriginZone =< Trip.OriginZone and Ticket.DestinationZone >= Trip.DestinationZone. Example:
Ticket {OriginZone: 1, DestinationZone: 4, MaxNumberOfTransfers: 1, MaxDuration: 0} covers trip {OriginZone: 2, DestinationZone: 3}
MaxNumberOfTransfers specifies how much times this ticket can be used. If value it's value is 2, this ticket can cover 2 trips that happen between OriginZone and DestinationZone. MaxDuration specifies period in seconds, in which this ticket can be used from time of purchase(for example if ticket is valid for 24 hours, this field will be set to 24 * 3600). It should be considered that ticket was bought right before first trip that it's used for.
This fields are exclusive. So if MaxDuration field is set, than MaxNumberOfTransfers is not used.
Here is example, of how this algo should work:
> trips = [
{OriginZone: 1, DestinationZone: 2, EndOfTripTimestamp: 2020-09-16T15:00:00},
{OriginZone: 3, DestinationZone: 4, EndOfTripTimestamp: 2020-09-16T16:00:00},
{OriginZone: 1, DestinationZone: 2, EndOfTripTimestamp: 2020-09-16T17:00:00},
{OriginZone: 3, DestinationZone: 4, EndOfTripTimestamp: 2020-09-17T18:00:00}
]
> tickets = [
{OriginZone: 3, DestinationZone: 4, MaxNumberOfTransfers 1, MaxDuration: 0, Price: 10},
{OriginZone: 1, DestinationZone: 2, MaxNumberOfTransfers 1, MaxDuration: 0, Price: 10},
{OriginZone: 3, DestinationZone: 4, MaxNumberOfTransfers 2, MaxDuration: 0, Price: 15},
{OriginZone: 1, DestinationZone: 2, MaxNumberOfTransfers 2, MaxDuration: 0, Price: 15},
{OriginZone: 3, DestinationZone: 4, MaxNumberOfTransfers 0, MaxDuration: 24 * 3600, Price: 13},
{OriginZone: 1, DestinationZone: 2, MaxNumberOfTransfers 0, MaxDuration: 24 * 3600, Price: 13}
]
> algo(trips, tickets)
OUTPUT:
  {OriginZone: 1, DestinationZone: 2, MaxNumberOfTransfers 0, MaxDuration: 24 * 3600, Price: 13}
  {OriginZone: 3, DestinationZone: 4, MaxNumberOfTransfers 2, MaxDuration: 0, Price: 15},

To clarify this example, here you see 4 trips that happened in period of 2 days. In first day there's 3 trips overall, 2 from zone 1 to 2, and one from zone 3 to 4. And on second day there's one trip from zone 3 to 4. So algorithm picks 2 tickets to cover these trips -- 24 hour ticket for zones 1 to 2 and ticket with 2 transfers for zones 3 to 4.
Overall this looks like combinatorial optimization problem, but i wasn't able to find any non trivial algorithm for solving it. So, currently i'm using brute force algo that looks like:
recursive_function(trips, tickets):
    trip = trips[0]
    find best price iterating over tickets:
        price, tickets_list = recursive_function(trips[1:], tickets)

   return tickets_list with best price sum

So, my question is, is there any common problem that's similar to my and have non-trivial solution? Or maybe someone can recommend me some topics to look closely into.


texts: How many node does the final B-tree have?

texts:
I'm currently studying the B-Trees chapter of Introduction to Algorithms. One of the question from the chapter is:

  Suppose that we insert the keys $\{1,2,...,n\}$ into an empty B-tree with minimum degree 2. How many nodes does the final B-tree have?

I think given that a node will have between $t-1$ and $2t-1$ keys, where $t$ is the minimum degree, so the answer for this question will be somewhere between $n$ and $n/3$? This is where I'm stuck, any help would be appreciated.


texts: Can we quantify how close a partially correct programs is to being correct?

texts:
I know that there is something called partial correctness, but I was wondering if there was a way to tell how close a semi-correct program is to a fully correct program.

For example, if you had a sorting program that almost completely sorts an array, could you use Hoare logic to determine how close it is to getting the correct answer? One way to do this would be to make the precondition a series of and statements and see how many of these statements the weakest precondition, resulting from the postcondition being propagated through the program, would be able to imply.

However, this method seems to be very crude. Is there any other way to do something like this?


texts: Time complexity of matrix multiplication in Big-Align

texts:
I am reading the following paper:

Big-Align: Fast Bipartite Graph Alignment.  Danai Koutra, Hanghang Tong, David Lubensky.  International Conference on Data Mining (ICDM 2013).

I'd like to understand one of the paper's claims about the running time of their algorithm.  Their algorithm uses matrix multiplication as follows:

where $n \gg d$, $\bf A,B$ are a $n \times d$ matrices, $\bf U$ is a $n\times n$ matrix, and $\bf S$ is a $n\times n$ diagonal matrix with only the first $d$ diagonal elements being non-zero, with $\bf U,S$ derived from $\bf A$ via a SVD decomposition as indicated above.  $\bf A$ has rank at most $d$, so there are at most $d$ non-zero singular values in $\bf S$. All matrices contain only non-negative values.

The multiplication of a $l\times m$ matrix and a $m\times n$ matrix take $O(lmn)$ time.

How can we compute $\bf P$ in $O(nd^2)$ time?  I think it suffices to compute $\bf B \cdot \bf X$ in $O(nd^2)$ time.  I tried different multiplication orders but cannot arrive at a $O(nd^2)$ time complexity. For example,

  1) first compute $US^{-1}$, then result is a $n\times n$ matrix with only the first $d$ columns being "non-zero". Since $S$ is diagonal with $d$ non-zero diagonal elements, the time complexity is $O(nd)$.

  2) then compute $A^T(US^{-1})$, the result is a $d\times n$ matrix with only the first $d$ columns being "non-zero". The time complexity is $O(nd^2)$.

  3) then compute $B(A^TUS^{-1})$, the result is a $n\times n$ matrix with the first $d$ columns being "non-zero". The time complexity is $O(nd^2)$.

  4) then compute $S^{-1}U^T$ similar to 1), the result is a $n\times n$ matrix with the first $d$ rows being "non-zero". The time complexity is $O(nd)$.

  5) finally the do multiplication $(BA^TUS^{-1})(S^{-1}U^T)$, but this takes $O(n^2d)$ time.

I tried some other order without success to derive $O(nd^2)$ complexity. Am I missing something, or the paper is wrong about this?


texts: Determining the cost of multi phase multiway merge sort

texts:
Let's say I have a disk with an average seek time of 10ms, an average rotational latency of 5ms and a transfer time of 1ms for a 4kb block and the cost of reading the block is the sum of these values. If I have to sort a large relation consisting of 10,000,000 blocks of 4kb each and I have 320 blocks of main memory available for buffering then how would I determine the cost of this multi phase multiway merge sort. I know that in the first phase you need to create sorted runs of 320 blocks each then do 319-way merges. Also because of the small memory, this would usually be in 2 phases but here it will turn into 3 phases.

I also know that the number of sorted sublists is 10,000,000/320 = 31,250 but I'm not sure where to go from here to determine the cost.


texts: How to calculate complexity of an algorithm which calls a subroutine?

texts:
Consider the following example:

Algorithm $A$ has Algorithm $B$ as its subroutine. The running time of algorithm $A$ without counting the time spent running the algorithm $B$ subroutine is $O(n^4)$. One call of algorithm $B$ takes $O(n^3)$ time. In a single run of algorithm $A$, algorithm $B$ is called at most $10n^2$ times.

What is the running time of algorithm $A$ including subroutines?

a. $O(n^4)$

b. $O(n^9)$

c. $O(n^7)$

d. $O(n^6)$


texts:
Is there a difference between an execution model and a computation model? Or the two terms refers to the same things?

Thanks in advance.


texts: A problem about the midpoint ellipse algorithm

texts:
I have read the book "Computer Graphics with Open GL" (Hearn, Fourth Edition) recently. However, when I read the midpoint ellipse algorithm, the following example in the book is confusing me:

  For region 2, the initial point is $(x_0,y_0) = (7,3)$ and the initial decision parameter is $$p2_0 = f_{\text{ellipse}}\Big(7 + \frac{1}{2}, 2 \Big) = -151$$

in which $f_{\text{ellipse}}(x,y) = r^2_y x^2 + r^2_x y^2 - r^2_x r^2_y$.

When I fed the value into the formula mentioned above, eventually, I get -23. Therefore, is the result given in this example wrong?


texts:
An array A holds n integers, and all integers in A belong to the set {0,1,2}. Describe an O(n) sorting algorithm for putting A in sorted order.
Your algorithm may not make use of auxiliary storage such as arrays or hash tables. More precisely, the only additional space used, beyond the given array is O(1). Give an argument to explain why your algorithm runs in O(n) time.

This is a self-answered question, but other answers are certainly desired.


texts: What is the time complexity of a linear search performed using 2 pointers?

texts:
For an array, I'm using a left pointer (pointing to 0) and a right pointer (pointing to end).
For every iteration, if my search element is not found, I increment left and decrement right.
This iteration continues until left <= right. Find the code snippet below
left = 0
right = length - 1

while left <= right:
    // search logic
    left += 1
    right -= 1

What will be worst the time complexity of this algorithm?
Also, is this a type of linear search?


texts: How to get the upper, lower and average bound of a given algorithm?

texts: How to get upper, lower, average bound of  given algorithm? What should be the first step I should do? I search on the internet and only give me the definition of those 3. For example if take the algorithm of nlog(n)+2 then how do we find the lower and upper bound of this? What would be the first step?


texts:
I was reading in Wikipedia about it and one of the main things that were pointed out was that it is only an optional mechanism. This bugs me more than it should as I cannot find any information that I can understand about it.

Can anyone explain to me like I am a five-year-old why are they optional?


texts:
There is a large body of literature on RAMs with "reasonable" and "unreasonable" operations, where "unreasonable" operations would yield a machine with too much power to be practically feasible.

For example, it is known that for integer RAMs, allowing unit-cost multiplication yields a machine that is exponentially faster than a Turing machine. In conjunction with Boolean operations, this would yield a machine that can solve PSPACE-complete problems in polynomial time. The situation gets worse if division or left shift are added. As a result, computational models allowing these sorts operations to be performed in constant time on arbitrarily large integers are typically considered to be "unreasonable" in that the resulting models are far too powerful to be practically feasible.

How does this situation generalize to real RAMs, where the registers are allowed to be real numbers?

One canonical model of real computation is the Blum-Shub-Smale machine, which can compute rational functions at unit cost.

Is this model "reasonable?" What other operations are allowable on a real RAM that would lead to reasonable/unreasonable behavior?


texts: Pumping lemma regarding {a^2k w | w ∈ {a, b}*, |w| = k}

texts:
I had a question regarding the Pumping lemma for regular languages, I have been studying for an exam and came across the question {a^2k w | w ∈ {a, b}*, |w| = k}. In the website it lists the answer and I'm having a little bit of trouble trying to figure out what a specific part of this answer means. It states:

  Assume L is regular. From the pumping lemma there exists a p such that every
  w ∈ L such that |w| ≥ p can be represented as x y z with |y|≠0 and |xy|≤ p. Let
  us choose a^2p b^p. Its length is 3p≥p. Since the length of xy cannot exceed p, y
  must be of the form a^k for some k > 0. From the pumping lemma a^2p-k b^p must
  also be in L but it is not of the right form since the number of a’s cannot be twice
  the number of b’s (Note that you must subtract not add , otherwise some a’s
  could be shifted into w). Hence the language is not regular.

So my issue lies in the very last line of the proof where it states that " you must subtract not add, otherwise some a's could be shifted into w"

Is there anyone that could help me visualize what this could possibly mean, I feel as though it may be trivial but I seem to be having trouble with it.

Thank you in advance!


texts:
https://en.wikipedia.org/wiki/Type_inhabitation
The wiki article above says,

To be sound, such a system must have uninhabited types.

What is the definition an uninhabitated type? Do all programming languages have uninhabited types? What would be an example in Haskell? Or C? Or Java? Or Python?


texts: Data points as outcomes of a random experiment

texts:
It is well known that

Random variable is a function from sample space of a random experiment to $\mathbb{R}$.

Consider the following sentences from deep learning book

  Let $\{x^{(1)}, \cdots , x^{(m)}\}$ be a set of $m$ independent and
  identically distributed data points. A point estimator or statistic is
  any function of the data: $$\hat{θ}_m = g(x(1), \cdots , x(m))$$.
  ...........................................................................................................................................................
  For now, we take the frequentist perspective on statistics. That is,
  we assume that the true parameter value $θ$ is ﬁxed but unknown, while
  the point estimate $\hat{θ}$ is a function of the data. Since the data
  is drawn from a random process, any function of the data is random.
  Therefore $\hat{θ}$ is a random variable.

Now my doubts are

1) Input to a random variable is an outcome of a random experiment. Then is it true that each data point is an outcome of a random experiment? If yes, then what may be that random experiment and who are running it?

2) If dataset is a subset of or itself a sample space, then what is the reason for many statements stating every dataset has an underlying probability distribution? instead of saying that each dataset is a subset of a sample space of a random experiment?

3) Output of a random variable is a real number. But in general parameter can be a vector of real number. How to understand it?


texts: Maximizing the sum of adjacent pairs of elements

texts:
I encountered the following interesting problem on stackoverflow:

  Given numbers $a(1)<\cdots<a(n)$, find a permutation $\pi$ that maximizes $$\sum_{i=1}^{n-1} a(\pi(i)) a(\pi(i+1)).$$

The answers there claim that the answer doesn't depend on the numbers themselves, and is always given by the order $$\ldots,a(n-5),a(n-3),a(n-1),a(n),a(n-2),a(n-4),\ldots$$ However, the proof (given in the comments) isn't convincing.

  Is the answer on stackoverflow correct? Can we prove it?


texts:
I can't wrap my head around how the SR Latch works.
Seemingly, you plug an input line from R, and another from S, and you are supposed to get results in $Q$ and $Q'$.

However, both R and S require input from the other's output, and the other's output requires input from the other other's output. What comes first the chicken or the egg??

When you first plug this circuit in, how does it get started?


texts: Use of FFT in order to multiply two positive integers of $n$ digits

texts:
We're given two positive integers $t$ and $s$ of length $n$ in binary representation.

  Suppose we divide the numbers into ${n \over k}$ blocks of size $k=\lg n$
  using FFT algorithm.

  Suppose that the multiplications that occur during recursive calls do not increase the length of the resulting numbers (not necessarily true in reality but can be supposed for the sake of the algorithm) therefore the multiplications can be performed in $Θ(k^2)$ bit operations.

  How can we complete the computation is $O(n\lg^2n)$?

We can represent $x$ and $y$ as a sum. For example:
$$
t = t_0\cdot 2^0+t_1\cdot 2^1 +...+ t_{{n \over k} -1}\cdot 2^{{n \over k} -1}
$$

Essentially powers of two are analogous to $x$'s in a polynomial $a_n\cdot x^n+...+a_1\cdot x^1+a_0\cdot x^0$.

Therefore we can use FFT on the coefficients vector of $t$.

Let $\bar t, \bar s$ be the coefficients vectors of their corresponding sum representation.

Then:
$$
q = \operatorname{FFT}(\bar t) \cdot \operatorname{FFT}(\bar s)\\
p= \operatorname{iFFT}(\bar q)
$$
where $\operatorname{iFFT}$ is the inverse FFT algorithm and $q$ is the point-wise result of $\bar t\cdot \bar s$. FFT operations run time is $O({n  \over k}\lg{{n \over k}})$ but we know that the length of the result of bit multiplication of $x_i\cdot y_i$ is still $k$ so the run time is really $O(k^2\cdot {n  \over k}\lg{{n \over k}}) = O({nk}\lg{{n \over k}})$.

I'm not sure how I can complete the algorithm in $O(n\lg^2 n)$ time from this step though.


texts:
This is a homework question, I'm wondering if anyone could help.  Recall $RP$ is the set of languages recognized by randomized algorithms in polynomial time.  The question is given an algorithm in $RP$ allowed to consult an oracle in $RP$, prove the "lowest complexity bound" for a set recognized by this algorithm.

I don't think this is a very good question, it's not clear exactly what is meant by lowest complexity bound.  I suppose this means any set in this class ($RP^{RP}$) must fall in which complexity class..that is, find the lowest such one and prove it.

Any ideas?


texts: Why is building a heap $\mathcal O(n)$ and not $\theta(n)$?

texts:
From what I see online, all seem to suggest that heapifying takes $\mathcal O (n)$ time, but it seems like it should always takes $\theta(n)$ time, even in the best case. Is something wrong with my pseudocode? Is there a more optimized way to do heapification?

Heapification(H[1...n])
for i <- floor(n/2) downto 1 do
  k <-i; v <- H[k]
  heap <- False
  while !heap && 2k <= n do
    j <- 2k
    if j <= n
      if H[j] < H[j+1]
        j <- j+1
      if H[j] > v
        H[k] <- H[j]
        k <- j
      else heap <- true
  H[k] <- v


texts:
I have an array of objects, each of them has a numeric id and another array attached to them.

The array in the object contains the dependencies of that object. Each dependency is an id from the other objects. There are no circular dependencies.

Let's take this diagram:

The ids of the objects are in the upper rectangle, the dependecies are in the lower one.

I need to sort the array in a way, so if an object depends on another object, then it needs to be after that object in the array.

So for the example above it would be

3 1 2 4


texts: Minimizing Turing machine-like automaton with no final states

texts:
I have a deterministic finite automaton which behaves mostly like a Turing machine, with following difference (relevant to this question):

The tape is initially finite.
The automaton can insert and delete cells from the tape.
Actions are associated with states rather than with transitions (this includes head shift and tape manipulation).
The automaton has no accepting/final state. The computation is only terminated when the machine exits the tape. The final state of the tape is the machine's output.

I know most of the states in the machine are redudant (equivalent to other states). However the good old DFA minimization algorithm won't work here, because it starts its work on the final states (which I don't have).

The algorithm should be efficiently computable (the machines in question have hundreds of thousands to millions of states).

Is this possible in the general case? Every algorithm I make up fails in some cases.


texts:
At present, I am doing a project on Optical Character Recognition (OCR). I am looking forward to improve the results by checking the output words of my OCR code with existing words from a text file. The file contains all English words.
Word is good to go if it exists in the file, but if it doesn't then I want to replace it with a word from the text file. Suppose the word in the image was "horse", and the OCR gives "hurze". Which algorithms should I use for detecting errors and their corrections.
I know that sometimes the correction depends on the context of the sentence. But, the thing is that I am not looking for 100% results. I just want to improve my results for OCR.
Can you suggest me anything else? I am looking forward to ideas.


texts: Does linear programming admit a strongly polynomial-time algorithm?

texts:
The linear programming problem: find a strongly-polynomial time algorithm which for given matrix A ∈ Rm×n and b ∈ Rm decides whether there exists x ∈ Rn with Ax ≥ b.

I know that Steve Smale's lists some of the unsolved problems in mathematics. But such a linear programming problem is it until now not-solvable ?


texts: clarification on multiple access in data link layer

texts:
In physical layer, we already have methods to share a common link by dividing into channels using FDM etc.

Then why do we need to think about multiple access at data link layer? I.e why csma, csma/cd are needed? We shouldn't be seeing any collision at all when I'm using a different channel for communication right?
Do these protocols come into play only when i'm using a less bandwidth link due to which I can't share them by dividing into frequency bands  at all?


texts: Getting the sorted sequence from a level-wise sorted min-heap

texts:
A heap sorted by levels is a heap which:

Every parent is smaller than its children.
The nodes in each level are sorted from the smallest to the greatest.

I need to describe an algorithm with $O(n)$ runtime that prints the values in the heap in sorted order.

I only manage to do it in $O(n \log(\log n))$ using another heap but  have no idea of how to do it in $O(n)$.


texts:
Exactly $1$-in-$3$ SAT ($X_3SAT$) is a variant of the Boolean satisfiability problem. Given a set of clauses, each clause having three literals, is there a set of literals such that each clause contains exactly one literal from this set?

$X_3SAT$ is known to be $NP$-complete. It remains $NP$-Complete even when it is monotone (all literals are positive) and linear (no two clauses share more than one variable in common).

I think an unsatisfiable monotone linear instance must have at least four loops. A loop is a sequence of clauses such that each clause has one variable in common with the previous clause in the sequence, a different variable in common with the next clause, and no variables in common with any other clauses in the sequence. The last clause in the sequence "loops" around to the first. Loops have relatively few satisfying assignments. A monotone linear length three loop has four satisfying assignments. Loops can often be reduced and removed. These are some reduction rules for loops.

X() = $X_3SAT$ instance

($a,b,c$) = $X_3SAT$ clause (choose exactly one literal to be True)

X($T \leftarrow a$) = replace literal $a$ with True and $\overline{a}$ with False

X($a \leftarrow \overline{b}$) = replace literal $\overline{b}$ with $a$ and $b$ with $\overline{a}$

Some Loop Reduction Rules:

$(x_1,y_1,y_2)(x_2,y_2,y_3)(x_3, \overline{y_3}, \overline{y_1}) + X() = (x_1,x_2,x_3) + X(F \leftarrow y_2,x_1 \leftarrow \overline{y_1},x_2 \leftarrow \overline{y_3})$

$(x_1,y_1,y_2)(x_2,y_2,y_3)(x_3,y_3,y_1)(x_1,x_2,z_1) + X() = (x_1,x_2,x_3) + X(x_1 \leftarrow y_3,x_2 \leftarrow y_1,x_3 \leftarrow y_2,x_3 \leftarrow z_1)$

$(x_1,y_1,y_2)(x_2,y_2,y_3)(x_3,y_3,y_1)(x_1,y_3,z_1) + X() = (x_1, \overline{x_2}, \overline{x_3}) + X(F \leftarrow y_3,x_2 \leftarrow \overline{y_2},x_3 \leftarrow \overline{y_1},x_1 \leftarrow \overline{z_1})$

$(x_1,y_1,y_2)(x_2,y_2,y_3)(x_3,y_3,y_4)(x_4,y_4,y_1)(x_1,x_2,x_3) + X() = X(F \leftarrow x_2,T \leftarrow x_4,F \leftarrow y_1,F \leftarrow y_4,x1 \leftarrow \overline{x_3},x1 \leftarrow \overline{y_2},x1 \leftarrow y_3)$

$(x_1,y_1,y_2)(x_2, \overline{y_2}, \overline{y_3}) + ... + (x_{k-1},y_{k-1},y_k)(x_k, \overline{y_k}, \overline{y_1}) + X() = X(F \leftarrow x_1,F \leftarrow x_2,...,F \leftarrow \overline{x_{k-1}},F \leftarrow x_k,y_1
 \leftarrow \overline{y_2},...,y_1 \leftarrow y_{k-1},y_1 \leftarrow \overline{y_k})$ for k even

$(x1, \overline{y_1},y_2)(x_2, \overline{y_2},y_3) + ... + (x_k, \overline{y_k},y_1) + X() = X(F \leftarrow x_1,F \leftarrow x_2,...,F \leftarrow x_k,y_1 \leftarrow y_2,y_1 \leftarrow y_3,...,y_1 \leftarrow y_k)$

I am looking for other loop reductions.


texts: Add a road to a network (Graph problem with Dijkstra)

texts:
Recently i have found a problem stating:
There is a network of roads G=(V,E)(it is not directed) connecting a set of cities V. The length of each road e ∈ E is le. There is a proposal to add one new road to this network, and there is a list E′ of pairs of cities between which the new road can be built. Each such potential road e′∈ E has an associated length. As a designer for the public works department you are asked to determine the road e′ ∈ E whose addition to the existing network G would result in the maximum decrease in the driving distance between two fixed cities s and t in the network. Give an efficient algorithm for solving this problem.

The basic solution was to apply to 2 times Dijkstra (from s to city x and from t to a city y) and then try all the edges from E' which would result into

2*(Dijkstra) + (|E'|) = ((|V|+|E|)⋅ log |V|+|E’|)

But then on the web I found an altrenative solution:

  If you run Dijkstra for every edge in E’, the running time is (|E|⋅|E’|⋅ log |E|)

I do not understand this alternative. Could anybody explain this strategy to me?
Thanks in advance!


texts: Real time application with DFA or NFA application

texts:
Can anyone here give an example of DFA or NFA real time application?

And, can I know what are complexity and decidability problems in real time application? Does every real time application have complexity and decidability problems?


texts: Is the simulation of how a warehouse functions (eg Amazon) a discrete event simulation problem

texts:
If i wanted to write a piece of software that simulated a warehouse where typical warehouse procedures occur eg

loading of trucks onto conveyors
goods being transported around a warehouse by machines
goods being packed by operatives
goods being picked by operatives
... etc

should this be modelled / is this known as a discrete event simulation problem or a continuous event simulation problem.. or both?


texts: How to prove LTL-formulas true for all paths?

texts:
I'm quoting a question from my homework which I don't understand its wording.

Also, I'm not looking for an answer for my problem, I just want to be pointed at some articles/tutorials/reading/tips to solve them.

Gp ⇒ (p U q) U p
(p U q) ∧ (q U p) ⇔ p ∧ q
Fp ⇔ F(Xp)
X(Fp) ⇔ F(Xp)
(p U (q ⇒ ¬Xq)) ∧ (FGq) ⇔ p U (Gq)

They ask me to prove if these formulas are true for all paths but it seems like they want me to prove them to be equivalent instead.


texts: Event-based architecture (in the context of Distributed Systems)

texts:
Our course lecture slides divide architectures of distributed systems into:

object based architectures (e.g. typical distributed web application)
resource-centered architectures (e.g. torrents and magnet links)
event-based architectures (e.g. ???)

I do not understand the explanation on the slides and they don't provide any examples. A google search will not return any results for event-based architecture in the context of distributed systems, only in other contexts where the meaning is different. Can someone explain what are "event-based architectures" with a simple example like "torrents" are for resource-centered architectures?


texts: Is Dekker's algorithm not k-bounded for any finite k?

texts:
Consider this version of the algorithm, for only 2 processes, 0 and 1:

Initially flag[i]=false

1.    flag[i] := true
2.    while flag[1-i] do{
2.1.    if turn = 1-i then{
2.1.1.    flag[i] := false
2.1.2.    await turn=i
2.1.3.    flag[i] := true } }
3.    Critical Section
4.    turn := 1-i
5.    flag[i] := false

I believe this algorithm is starvation-free. But is it $k$-bounded-waiting for a specific $k$? or is it not $k$-bounded for any finite $k$?


texts: How does this star1 variation work? (star1 is a stochastic (dice) algorithm for artificial intelligence in adversarial games)

texts:
I don't understand how the star1 variation mentioned in the paper is Sparse Sampling for Adversarial different than the usual star1 algorithm?

  (Taken from the bottom of page 7). This variant can be easily
  described in terms of the descriptions of Star1. To enable sampling,
  one need only change the implementation of getOutcomeSet on line 5 of
  Algorithm 1. Instead of generating the full list of moves, the new
  function samples c outcomes with replacement and assigns a uniform
  distribution over the new outcome set of size c.

Does the variation only generate some of the possible game states and not all of them?

I think I understand star1 but I don't really understand star2 because it is more complicated. I only have a bachelor's degree in computers and this theoretical stuff is way above my head. Thanks for any help that I get. :)


texts: How to make an algorith which calculates expected and actual time to give a number in the -1 to 1 range?

texts:
I'm trying to create an algorithm for time spent on a blog post which gives a number in the -1 to 1 range. Negative numbers will mean that users spent less than expected time on a post, while positive numbers means the opposite.

Now, what I've tried to do so far is to:

Set an expected time (in seconds):

Expected time = Number of words in the post / Average words per
second, based on age

The actual time a user spends on an article will be recorded from when a user enters and leaves the page.

However, I'm struggling to find a way to user the Expected Time and Actual Time to get a number in the -1 to 1 range, where a more negative number means that the user spent less time than expected and vice versa.

I know that it's possible to normalize a number in the -1 / 1 range with a formula like this:

2 * ( (x − minX) / (maxX − minX) ) - 1

But I don't really understand how to use it in practice to get the result I want. So, how can I use Expected Time and Actual Time to get a value between -1 and 1?


texts: Are all reductions from NP-complete problems either NP-complete or are contained in P?

texts:
Let's say we have a problem $A \in \mathsf{NP}$. Now let's say we have a reduction $f(\mathsf{SAT}): A \leq \mathsf {SAT}$.
So, assuming that $A$ is not $\mathsf{NP}$-complete we have that $f(\mathsf{SAT})$ is $\mathsf{FNP}$-hard:

$\mathsf{\exists  C: \{A \in  C \subseteq FNP},\ f(\mathsf{SAT}) \in \mathsf C\}$.
$\mathsf{NP \subseteq C}$.

Since you can use $f(\mathsf{SAT})$ to solve $\mathsf{NP}$-complete problems, $\mathsf C$ can only be $\mathsf{NP}$-hard.
Although assuming that $A$ is $\mathsf{NP}$-complete the reduction is polynomial-time deterministic reduction. I.e. $f(\mathsf{SAT}) \in \mathsf {FP}$.
But what about cases when $f$ is $\mathsf{FNP}$-intermediate? Are they inexistent? For example, if, say, there was a $\mathsf {UP}$ reduction from $\mathsf{SAT}$ to $\mathsf{GI}$, would that mean that $\mathsf{UP=NP}$ is true?


texts: Bellman-Ford parent pointer (?) negative cycle

texts:
First of all, let me preface by saying that this question is not completly new but the original question hasn't been answered. More important, this is only basic question on understanding the proof itself.

So after some search in the site I found the following question : Bellman-Ford algorthm and negative cycle proof.

The guy is trying to understand how to prove that a cycle in parent pointer is necessarily a negative cycle.

My question is very basic and isn't duplicate, I just couldn't find anything in the document on the related question which answers my question.

What does it mean a cycle in the parent pointer? I mean I could a graph whereas the cycle in the parent pointer isn't a negative cycle... I don't understand why It must be a negative cycle.

See an example of a graph I have in mind :

Now suppose the first node we start with is (a) and suppose the we travling the edges in the following order: ab,bc,cd.

and here we goes, we have a cycle in the parent pointer, and as far as I understand that is (c) becuase it is the parent of (d) and yet the cycle isn't negative cycle.


texts: How to draw the heap for an array in Java?

texts:
I have an assignment to draw the heap after an ArrayList and a LinkedList is created.
public static void main(String[] args) {
     List list = new ArrayList();
     list.add(0);
     list.add(1);
     list.add(1);
     list.add(2);
}

and
public static void main(String[] args) {
     List list = new LinkedList();
    list.add(0);
     list.add(1);
     list.add(1);
     list.add(2);
}

So far I have a tree set up for [0, 1, 1, 2] so that it just goes down like a tree from 0, 1 and 1, then 2. But I don't know if that's correct and if it'd be different for the ArrayList and LinkedList.


texts: Do cryptographic hash function solve clustering problems with linear probing?

texts:
I understand in open addressing hash tables some clustering will always happen just by random chance, even if the input data is perfectly random, leading to some "best possible" lookup performance hit (for an open addressing scheme).

If the hash function is of low quality, and we use linear or quadratic probing, we may observe "primary" and "secondary" clustering effects that make clustering, and therefore lookup performance, worse.

My question is: would using a cryptographic hash function result in linear / quadratic probing having the "best possible" lookup performance, effectively eliminating primary and secondary clustering problems?


texts:
I have a function to count upper bits of a 32 bit value. So if a number is 11100011111..., the result is 3 as there are 3 ones in the most significant place before a 0 is hit.

I need to convert the function to use only bitwise operations (no if statements or while loops) and the total number of operations should be lesser than 50.

Question: How can this be converted to bitwise operations only while keeping less than 50 ops?

Here is the Code:

  int count = 0;
  int i = 28;

  while(i >= 0) {
    int temp = (x>>i) & 0xF;
    i-=4;
    if(temp == 0xF) count+=4;
    else {
      int mask = 0x1;
      int a = (temp>>3) & mask;
      int b = (temp>>2) & mask;
      int c = (temp>>1) & mask;
      int d = temp & mask;

      if (a != 1) break;
        count+=1;
      if (b != 1) break;
        count+=1;
      if (c != 1) break;
        count+=1;
      if (d != 1) break;
        count+=1;
    }


texts: What is the Big-Oh asymptotic complexity of learning in Random Forests?

texts:
Random Forests is a bagged ensemble of CART learners. The following is what I've found, but am not sure if I'm completely right.

CART (Classification and Regression Trees) uses the Gini index for splitting (whereas Shannon's Entropy function is used in ID3). From what I know, it's asymptotic complexity can be represented as $O(n \log n)$, where $n$ is the number of samples and $m$ is the number of attributes.

Assuming $M$ to be the number of trees in a Random Forest, it's asymptotic complexity ought to be $M$ times that of CART, hence $O(Mnm \log n)$. This is neglecting the constant factors that scale linearly such as random selection of features for each tree of the forest.

Is this notion correct? Or is there more to this?


texts: Why do non regular languages have infinitely many equivalence classes?

texts: For example, for the language $L = \{a^nb^m|n \neq m\}$, why does it have infinitely many equivalence classes? How do I show/see that?


texts: If g is a PRG and f is a OWF, is G'(x) = f(g(x)) a PRG?

texts:
Just like the title states.
If I have a pseudo-random generator $g\colon \Sigma^n \rightarrow \Sigma^{2n}$ and a one-way function $f$, is $g'(x)=f(g(x))$ a pseudo-random generator? And why?
My instinct tells me it is, but I can't really explain why.


texts: Is the halting problem claim true with the advent of AI

texts:
Alan Turing states that, there can't be a program that can decide if a program will ever stop. But with such advances in AI, won't computers will be able to analyze code and decide like humans on whether a program will halt or not.

Am I missing something in his claim?

Or is it too fictitious?


texts: Algorithm to output all instances of stable matching

texts: So the Gale-Shapley algorithm is just one way to output one stable matching instance. Is there any algorithm that can allow us to output all stable matching solutions ? Thanks


texts: Is there a non-recursive and uncountable language L?

texts:
Does there exist a non-recursive language, L, such that the cardinality of L is uncountable?

I would really like an explanation as to why this question is true or false because at the moment, I have no idea.
My understanding is that all recursive languages have to be countable since the set of all finite strings is countable.
But I'm not sure if there is a non-recursive language which is uncountable.
Any help would be greatly appreciated,


texts: Quick sort, Hoare's partition algorithm. Is there a mistake in CLRS?

texts:
The following problem appears in "Introduction to Algorithms" by Thomas Cormen et. al., aka CLRS.
Problem 7-1.b
Hoare's partition algorithm from the book.

Part b: Assuming the subarray $A[p,\cdots,r]$ contains at least two elements, show that the indices $i$ and $j$ are such that we never access an element of outside the subarray $A[p,\cdots,r]$

I think this it is not possible to prove this because this statement is not correct, i.e., during the course of execution we happen to access elements outside the array.
Here I prove the converse of part b by using a counter-example.
Consider the array A = [1,2]. Let p = 1 and there r =2.

Initially, $i = 0$, $j = 3$ and $x = 1$.
After the loop $5-7$ executes once, $j$ becomes 2 and the condition in line 7 fails resulting the termination of the loop $5-7$.
Now we reach the loop $8-10$. Now let's look at the state after this loop executes twice. $i = 2$ and the condition in line 10 still holds. Therefore the loop executes a third time and $i$ becomes 3.
Now to test the condition in line 10 we access $A[3]$ which is outside the subarray $A[1,\cdots, 2]$

Is there a mistake in my reasoning or is the problem statement wrong?


texts: In the beginning, computable functions were always total, but when where the partial functions included

texts:
The modern definition of computable functions $f\colon \mathbb N \to \mathbb N$ as given on Wikipedia quite naturally describes partial functions, and not just total functions. Now I am reading some historical references, and before and around the 1930's people just seemed to be concerned with total computable function, so that when they talk about computable functions they always mean total functions.
As an example let me cite An unsolvable problem of elementary number theory by A. Church, here he just considers total functions right from the start, and when he introduces $\lambda$-definable, or recursive functions, he also just considers total function.
So at what point, and why, people dropped the assumption that computable functions always have to be total?


texts: efficiently find connected components in undirected graph considering transitive equivalence

texts:
I have a set of nodes and a function foo(u,v) that can determine whether two nodes are equal. By "equal" I mean transitive equivalence:
 If 1==2 and 2==3 then 1==3 and also: If 1==2 and 1!=4 then 2!=4

When given a set of nodes I can find all connected components in the graph by passing every possible combination of nodes to foo(u,v) function and building the needed edges. Like this:

import networkx as nx
import itertools
from matplotlib import pyplot as plt

EQUAL_EDGES = {(1, 2), (1, 3), (4, 5)}

def foo(u, v):
    # this function is simplified, in reality it will do a complex calculation to determine whether nodes are equal.
    return (u, v) in EQUAL_EDGES

def main():
    g = nx.Graph()
    g.add_nodes_from(range(1, 5 + 1))
    for u, v in itertools.combinations(g.nodes, 2):
        are_equal = foo(u, v)
        print '{u}{sign}{v}'.format(u=u, v=v, sign='==' if are_equal else '!=')
        if are_equal:
            g.add_edge(u, v)

    conn_comps = nx.connected_components(g)
    nx.draw(g, with_labels=True)
    plt.show()
    return conn_comps

if __name__ == '__main__':
    main()

the problem with this approach  is that I get many redundant checks that I would like to avoid:

1==2  # ok
1==3  # ok
1!=4  # ok
1!=5  # ok
2!=3  # redundant check, if 1==2 and 1==3 then 2==3
2!=4  # redundant check, if 1!=4 and 1==2 then 2!=4
2!=5  # redundant check, if 1!=5 and 1==2 then 2!=5
3!=4  # redundant check, if 1!=4 and 1==3 then 3!=4
3!=5  # redundant check, if 1!=5 and 1==3 then 3!=5
4==5  # ok

I want to avoid running in O(n^2) time complexity.
What is the correct way (or maybe an existing function in any python library) to efficiently find all connected components by a custom function?


texts: Maximising Success of candy distribution: Maximising the absolute difference

texts:
N people attend a gathering and will be given candies at the end.

Each person gets at least one candy
Maximum number of candies any ith person can be given, is given in an array A[ ] of length N

Success of the event is calculated by a number as follows:

initial success=0

for i=2 upto N,

success = success + absolute value of (A[i]-A[i-1])

Where A[i] is the maximum candies that can be given to i th person

Task is to find how many candies to be given to each person, to maximise the success of the gathering.

  Example: If there are 6 people and the array is 3 9 9 2 2 2, the best distribution of candies is 3 1 9 1 2 1, which maximises the success
  value to 20

What is the algorithm to be used for this problem?

  I tried the following algorithm:

  Compare two items in the given array. Over write the smaller integer to 1. If one of the integers is already 1, no need to act and continue to next comparison.
  If the integers are same, check making which integer as 1, gives higher contribution to the Success and decide.

Though my algorithm is working for most of the cases, it is not leading to optimal solution in the example case. It results in 1 9 1 2 1 2. Success of the result is 19, which is lesser than 20.


texts: When and how to generate parse tree while top down parsing

texts:
I am trying to build a parser that will eventually output a 3 address code.

My question is, how do I build the parser to go from parsing in a table driven top down parsing to then give me a parse tree?

I am looking for more psudo code than anything. Not anything concrete. For example, I have a table with the first and follow sets of all non-terminal. I take this non terminal and do the standard parsing technique for table driven parsing.

When and how do I take those choices for the parsing to create the parse tree?

Below is the grammar I am trying to parse out, I take the corresponding first and follow sets to the grammar and the parse out the input using the table driven parsing technique.

Grammar

  expr        ::= term {addop term}
  term    ::= factor {mulop factor}
  factor     ::= variable| unsigned-number| ( expr)
   variable ::= identifier
  addop ::= + | -
  mulop ::= * | /


texts: MAX3SAT proof help? Showing that NP = coNP iff MAX3SAT is in NP

texts:
For a 3CNF $\phi$, denote by $c(\phi)$ the largest number of clauses satisfied under an assignment. Define:

$\mathrm{MAX3SAT} = \{\langle\phi, k\rangle\mid c(\phi) = k \text{ and }\phi\text{ is a 3CNF}\}$.

Prove that NP = coNP if and only if MAX3SAT is in NP.

I've been working on this forever and can't seem to figure out anything. Any help?


texts:
This is a kind of follow-up to a question I asked on superuser, where I asked for the definitions of a 'distinghuisable state' and a 'memory cell'. My questions where properly answered, but I was still confused about a certain matter.

I'm reading this little paper, and in particular these sentences:

  To perform useful computation, we need to irreversibly change distinguishable states of memory cell(s) .... So the energy required to write information into one binary memory bit is $E_{bit}= k_BT \ln2$

So my interpretation of this is that the author says that to compute, you need to change the state of bits ($ 0 \rightarrow 1$, $1 \rightarrow 0$) in order to compute.

But is that actually a reasonable statement? I'm not really interested in the rest of the paper, only this part. Do computers (I'm not talking about supercomputers, or future computers which use qubits and whatnot, but just your average computer) compute using bits with 2 dinstinghuisable states?

I actually was able to find this so-called 'SNL-expression' somewhere else, namely this pdf, on page 223; it's actually a part of MIT's ocw.


texts:
Based on this video,  the tutor explains the knapsack problem with dynamic programming approach. One thing is not cleared in this video, which is my main question.

All the values on the first row (except 0) are set to 1 because value and weight (on that row) are 1 hence, we cannot exceed that number

Below is the complete example of the tutor as linked in the above video.

My question:

  -What would be the values of the first row if weight and value were not both the same?

So let's say  value is 25 and weight 3 (first row values):
I suppose the first row results would be 0,25,25,25,25,25,25,25

Let me know if i am wrong.
Thank you.

Note that the first row is important to be correct as every row depends on the previous one. The tutor's example in the video, is not the best as the first row value and weight are both 1.


texts: symmetrical subtraction between $L_1 \in \mathsf{P}$ and $L_2 \in \mathsf{NPC}$

texts:
If $L_1 \in \mathsf{P}$ and $L_2 \in \mathsf{NP-Complete}$ and $L_3$ is the symmetric difference between $L_1$ and $L_2$, is $L_3$ also in $\mathsf{NP-Complete}$ necessarily?

I'm pretty sure the answer is no but I can't find even one example that shows I'm right.


texts:
To me (but I might be wrong) Rice's theorem asserts that it's not possible to formalise the demonstration of a non-trivial property of a recursively enumerable language within the same given language. The modus ponens being the basis for demonstrating, Rice therefore says in substance that you will necessarily need a metalanguage to define it.

What I call Carroll's paradox is referred in Wikipedia under What the Tortoise Said to Achilles.

Wikipedia explains the following:

  The Wittgensteinian philosopher Peter Winch discussed the paradox in The Idea
  of a Social Science and its Relation to Philosophy (1958), where he argued that the paradox showed that "the actual process of drawing an inference, which is after all at the heart of logic, is something which cannot be represented as a logical formula ... Learning to infer is not just a matter of being taught about explicit logical relations between propositions; it is learning to do something" (p. 57). Winch goes on to suggest that the moral of the dialogue is a particular case of a general lesson, to the effect that the proper application of rules governing a form of human activity cannot itself be summed up with a set of further rules, and so that "a form of human activity can never be summed up in a set of explicit precepts" (p. 53).

In other words, Carroll's paradox shows that it's not formally possible to prove a property of a language purely with propositions of this language. You will need to admit a rule (or a principle) that "the modus ponens means X" with X using everyday words. I.e. you will need a meta language.

I will concede that it is a philosophical way to ask the question. But Carroll's paradox can be described in a formal (mathematical) way (done here).

Hence am I mistaken in principle to say that Caroll's paradox implies Rice's theorem?


texts:
In an exam I took we were asked to provide a tailrecursive definition of a recursive function. I failed miserably and the provided solution makes absolutely no sense to me. If anyone could explain that would be very helpful for my resit. The provided solution is the following:

Given are the functions $f, g, h \in \mathbb{N} \rightarrow \mathbb{Z}$ with $f.0 = 20, g.0 = 37, h.0 = 13$ and for $n>0$:

$$
f.n = 3*g.n-7*h.n \\
g.n = n^2-h.(n-1) \\
h.n = f.(n-1)+g.(n-1)
$$

For the tailrecursive version of $f$ specify

$$
\psi \in \mathbb{Z} \rightarrow \mathbb{Z} \rightarrow \mathbb{Z} \rightarrow \mathbb{Z} \rightarrow \mathbb{N} \rightarrow \mathbb{Z} \\
\psi .a.b.c.d.n = a * g.n + b * h.n + c * (n + 1)^2 + d
$$

Such that $f.n = \psi .3.(-7).0.0.n$

Then

$$
\psi .a.b.c.d.0 = 37 * a + 13*b+c+d
$$

and

$$
\psi .a.b.c.d.(n+1)\\
= \text{\{ spec \}}\\
a*((n+1)^2+h.n)+b*(4*g.n-7*h.n)+c*((n+1)^2+2*n+3+d)\\
= \text{\{ arithmetic \}}\\
4*b*g.n+(a-7*b)*h.n+(a+c)*(n+1)^2+d+c*(2*n+3)\\
= \text{\{ Construction Hypothesis \}}\\
\psi .(4*b).(a-7*b).(a+c).(d+c*(2*n+3)).n
$$

The main problem I am having is how they arrived at the specification, since the actual calculation I can follow. If anyone has any insights as to how the specification was obtained I think I would be able to grasp the answer better.

Thank you in advance.


texts: How to calculate Kolmogorov Complexity if we have access to an Oracle for the HALT Problem

texts:
I try to solve the following exercise:

We know that K (x), the complexity of Kolmogorov, is incomputable. Show how
calculate it, if we have an oracle for the membership problem (or for the HALT problem, if it accommodates more).

I have solved it in the following way:

Let (w) be the string to which I compute K (w).

(1). I have a TM 'G', which generates TM descriptions in order of length 'Mi'.

(2). The generated descriptions 'Mi' and (w) are inputs of a TM that has a Oracle for the Membership Problem TMO 'Memb'.

     * If TMO 'Memb' rejects then TM 'G' generates a new description Mi + 1, returns to step (1).
     * If you accept this description Mi and (w), they pass as input to the TM 'R', go to step (3).

(3). TM 'R' runs the description Mi with input (w) and prints the number of steps (t).

(4). Then K(w) would be |< Mi >| + t

It would be necessary to run TM 'R' or I can replace the problem of the Membership with the one of the HALT Problem and this gives me that number of steps that I calculate with TM 'R'?

regards


texts: Coloring graph with constraints on assortativity

texts:
I have come across the following problem and I would love for your thoughts on an optimal solution or approximate calculations worth trying.
The formulation of the problem in the form of graph theory:
Given a weighted graph $G=(V, E)$. In addition, we have $C$ colors and $f([C_1, ...C_n])$ the distribution function of vertices in the graph by color (That is, how many nodes of each color are in the graph). Also given an assortativity parameter, $M$. In general, assortativity is the tendency of nodes in the graph to attach to others that are similar in some way. For simplicity, set it to be the number of edges between vertices of the same color (Originally it is a little more sophisticated calculation. But unnecessary for our needs.).
Now, I want to color the graph such that the constraint on the number of vertices of each color is met and in addition, we minimize the expression: $|M-M(G)|$ (recall,  $M$ is the desired parameter and $M(G)$ is the parameter as it is calculated on the given coloring). Of course, we are not only interested in the minimum value, but also the coloring that created it.
This problem also has a parallel formulation for matrices:
Given symmetric matrix $A$ ($n\times n$) - this is the adjacency matrix of the above graph. The value of the entry $A_{ij}$ is set to equal the weight of the edge $(i,j)$. Here, too, we are given a distribution function of the rows and the columns in the matrix by color. As before, we have an assortativity parameter, $M$.
Now, let's try to find symmetric coloring of rows and columns in the matrix (if any line is colored in a certain color, so is the corresponding column) such that the constraint on the number of rows and columns of each color is met.
In addition, we will try to minimize the expression: $|M-\Sigma(A_{i,j}|\text{where column } i \text{ and row } j \text{ are in same color})|$ (which means, the difference between the desired $M$ and the sum of all entries that their colum and their row are in same color).
Epilogue:
I know that both formulas are completely equal. I hope the two different perspectives help me and others to think about different directions to solve the problem.
For the sake of curiosity, I will say that this problem is part of a challenge I face and it is to generate pseudo-synthetic social networks with real-life constraints. This is a problem that I formulated and not part of an article or a home exercise.
Thanks in advance.


texts:
I was asked the following question in an interview and I don't understand what is the best solution for it -
Assume you have an application that needs memory. It asks for a program for this memory, 20 bytes each time.
Each allocation (calling to malloc) costs another 8 bytes, so actually, you use 28 bytes (if you allocate 100 bytes, so it costs you 108 bytes).
The memory can be freed later and then its address is available again.
You need to find a program to minimize the byte cost.
I thought to allocate 100 bytes at the beginning, then to use a variable to save the address and a counter to save the available bytes. Then at each allocation, insert the address to a HashSet (represents all the taken addresses), and increase the address variable by 20 and decrease the counter. But then if the taken address is freed I need to take it out of the Set (thought about another set). Eventually, I didn't save much memory in this solution(each variable and address takes 4 bytes).
I can't think of a better solution, I will be happy to hear any other suggestions,
Thank you


texts:
I am following this algorithm example: https://en.wikipedia.org/wiki/Christofides_algorithm#example

The graph:

[![enter image description here][1]][1]

Calculate minimum spanning tree T:

[![enter image description here][2]][2]

Calculate the set of vertices O with odd degree in T

Same as "the minimum spanning tree T" as the degree of all vertices are odd.

Form the subgraph of G using only the vertices of O

(as all were odd, this should give us the original graph)
[![enter image description here][1]][1]

Construct a minimum-weight perfect matching M in this subgraph

(I am not sure if I did this right)
[![enter image description here][3]][3]

Unite matching and spanning tree T ∪ M to form an Eulerian multigraph

[![enter image description here][4]][4]

This is definitely not right.

What went wrong?