texts: Proving P and NP on problems formulated as languages

texts:
To prove that a certain problem is in P we have to give an algorithm that decides or solves it in polynomial time. To prove that a problem is in NP an algorithm must exist so that it can check whether a certain input is a solution to the problem in polynomial time (validate the input).

I am very confused as to how we can apply that logic to problems that are defined as a certain language. I have attached such problem to this post from Spiser's book on formal automata. For example SPATH is essentially a language that contains a certain number of elements. If "deciding" SPATH is checking whether a certain input is in the language or not then how could one validate a possible solution to prove that its in NP.

For example is SPATH is the language that contains all graphs having a certain property. Would an algorithm that checks whether an arbitrary graph G is in SPATH or not in polynomial time be "deciding" SPATH and proving that it is in P or would be validating the input and proving that it is in NP?


texts: Examples of sophisticated recursive algorithms

texts:
I was explaining the famous deterministic linear-time selection algorithm (median of medians algorithm) to a friend.

The recursion in this algorithm (while being very simple) is quite sophisticated. There are two recursive calls, each with different parameters.

I was trying to find other examples of such interesting recursive algorithms, but could not find any. All of the recursive algorithms I could come up with are either simple tail-recursions or simple divide and conquer (where the two calls are "the same").

Can you give some examples of sophisticated recursion?


texts:
I'm trying to speed up the following function in c++:

void num_to_xy(int num, int *x, int *y):
    *x = (cl & 0x03) | ((cl & 0x10) >> 2) | ((cl & 0x40) >> 3) | ((cl & 0x100) >> 4) | ((cl & 0x400) >> 5) | ((cl & 0x1000) >> 6) | ((cl & 0x4000) >> 7);
    *y = ((cl & 0x0c) >> 2) | ((cl & 0x20) >> 3) | ((cl & 0x80) >> 4) | ((cl & 0x0200) >> 5) | ((cl & 0x0800) >> 6) | ((cl & 0x2000) >> 7) | ((cl & 0x8000) >> 8);

which basically converts num to an x,y coordinate.  This is equivalent to getting the x,y position of num in the following array

$\left| \begin{array}{ccc}
0 &1 &4 &5 &16 &17 &20 &21 &...\\
2 &3 &6 &7 &18 &19 &22 &23 &...\\
8 &9 &12 &13 &24 &25 &28 &29 &...\\
10 &11 &14 &15 &26 &27 &30 &31 &...\\
32 &33 &36 &37 &48 &49 &52 &53 &...\\
34 &35 &38 &39 &50 &51 &54 &55 &...\\
40 &41 &44 &45 &56 &57 &60 &61 &...\\
42 &43 &46 &47 &58 &59 &62 &63 &...\\
\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\ddots &
\end{array} \right|$

The array above follows a pattern where for all $k,n$, all numbers between $k4^n$ and $(k+1)4^n-1$ form a perfect square.

Can the code above be sped up without generating a ginormous list and storing all the values?  Or is there a completely different, faster method?


texts:
Is randomized quick sort runtime is independent of the sequence of input? but depends on the numbers in the input?

Let say A1 = [1,2,3,4,5] , A2 = [5,2,3,4,1] A3 = [5,4,3,2,1] , Will the randomized Quick sort will have same runtime in terms of big O for A1, A2, A2

but for B1 = [1,2,3,4,5] B2 = [11,12,13,14,15] will have different runtime i.e. depends on the digits in the input?


texts: Can truth tables be used in non-boolean algebra to derive functions?

texts:
There are obvious analogs (pardon the pun) between Boolean algebra and algebra. They have similar laws, operators and properties. I can't figure out why Karnaugh Maps and sum of products, which are used to derive a Boolean function from a truth table, doesn't have an equivalent in algebra.  Perhaps it does, but I haven't seen it.

My only explanation is that if it were possible, you could theoretically find a function for any arbitrary series of numbers (0, 2, 4, 6, 8 f(n)=2n). Thus, you could solve a ton of very difficult problems. I'm not necessarily looking for a formal proof but an explanation.

Right now, I am having fleeting ideas that it has something to do with infinite outputs and inputs, something to do with place values, or true or false equivalents in algebra. There's something here that's difficult to put my finger on.


texts:
Question: Is a compiler a kind of Gödel numbering program?
Wikipedia tells us that a compiler is: "In computing, a compiler is a computer program that translates computer code written in one programming language (the source language) into another language (the target language)". https://en.wikipedia.org/wiki/Compiler
Also wikipedia tells us: "a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number". https://en.wikipedia.org/wiki/G%C3%B6del_numbering
Work done: My intuition says yes. Here is my line of thought: a programming language is a formal language. Every program is a well-formed formula and a compiler assigns each symbol of this formula to a binary representation of a number that the computer can read. (detail: a computer is a universal Turing machine, so it can perform arithmetic)
But, I don't know the details of how compilers work, so I came here to ask if my reasoning is correct.


texts:
Given a set $P$ of $k$ points in a plane. The Distance Variant problem: partition set $P$ into two subsets $P_{1}, P_{2}$ so you can maximize,

$d(P_{1}, P_{2})$ = min $p \in P_{1}$ min $ q \in P_{2}$ $d(p,q)$, where
$d(p,q)$ is the Euclidean distance between $p$ and $q$. So basically, $d(P_{1}, P_{2})$ is the smallest distance between $P_{1}$ and $P_{2}$.

Let's say $G$ is a complete graph with vertex set $P$, and the edge $pq$ has weight $w(pq) = d(p,q)$.$T$ be the MST of $G$, $e$ be the edge in $T$ with the largest weight. Removing $e$ from $T$ would create two components $P_{1}, P_{2}$. Assume edge weights are distinct.

$1.$ What I want to prove is that $d(P_{1}, P_{2}) = w(e)$. I think there must exist some type of lemma which is used to aid this proof. My intuition/attempt: well in $T$ I know by removing $e$ would create two components which separate both $P_{1}, P_{2}$, and what is truly separating these sets, are $e$. Because of this the only path from $P_{1}$ to  $P_{2}$ and vice versa is through $e$. Because $e$ is the only path, then it must be smallest distance from $P_{1}$ to $P_{2}$.

$2.$ Curveball, let's say $P^*_{1},P^*_{2}$ are optimal solutions, I also think it would possible to show that  is $d(P^*_{1},P^*_{2}) \leq w(e)$, but I am unsure if it is actually possible.

$3.$ Algorithm application: I can somewhat see how this problem can be solved in ${O}(n^2)$, but still debating on which algorithm truly fits.


texts: what is the connection between evaluation context and call by value?

texts:
I been reading about $\lambda$-calculus and related stuff, but I got some confusions which i want to clarify.

The call by value reduction is expressed with two rules

$$
\frac{e_1 \rightarrow e_1'}{e_1e_2 \rightarrow e_1'e_2}
$$
and
$$
\frac{e_2 \rightarrow e_2'}{ve_2 \rightarrow ve_2'}.
$$

where $e$ is any lambda term and $v$ is a value (abstraction of the form $\lambda x.M$).

I encountered evaluation context while reading this paper source, on page 10, I did not understand the following expressions.

Evaluation  context(left-to right: hole, app fun, app arg, type fun)
$$
E ::=  [-]  \mid
       E \,t   \mid
       v \,E   \mid
       E \,[T]
$$

and E-CTX

$$
\frac{t_1 \rightarrow t_1'}{E[e_1] \rightarrow E[e_1']}
$$

and description below said

E-CTX permits reduction under any arbitrary evaluation context $E$.

So I did not understand above statement, and because I have no knowledge about evaluation context. I searched other posts and googled, but could not get useful clear descriptions.

(1) what is that evaluation context, why there is such thing?

(2) what does evaluation context do with call by value reduction? why not just say "call by value is used here, bla bla..."

(3) E-CTX permits ...., what does that mean?

(4) I think someone has to implement call by value together with polymorphic $\lambda$-calculus. But what about evaluation context, should it be be implemented somehow (which I have no idea now ) ?

Could you guys point out useful sources to read or just answer here if possible?
I am around this for a while, so it would be big help. Thanks in advance!


texts: Decidability of a Turing machine which always halts in at most ten steps

texts:
I have an exam coming up soon and I need help with this.  Consider the problem:

  Given a Turing machine $M$, determine if $M$ halts in at most ten steps on every input.

Is this decidable?  Prove your answer.


texts:
I read the question in Exercise 4.1-4 in Introduction To Algorithms:

Suppose we change the definition of the maximum-subarray problem to allow the result to be an empty subarray, where the sum of the values of an empty subarray is 0. How would you change any of the algorithms that do not allow empty subarrays to permit an empty subarray to be the result?

I cannot get what's an empty sub-array.
I came across the point that a single number can be returned if the array consists of negative elements only.
Please can anyone explain the concept of an empty sub-array? And how can we have an empty sub-array?
Even if a single element is returned it still means that sub-array is not empty. Please clear the doubt.
Edit:
To make it more clear as a question if I take an array of elements:
[-3,-4,-1,-8]

The answer would be -1 or 0?
Please explain if why it should be 0 and how can we conclude an empty sub-array.
Thank you.


texts: Can adjacency lists be used in directed graphs?

texts:
I've been reading: https://en.wikipedia.org/wiki/Adjacency_list

It says that that graph can be constructed with the list $\{b, c\}, \{a, c\}, \{a, b\}$.

However, what if I wanted to construct a directional list? Does $\{b, c\}$ point to $b$ or $c$?

How can you use a list to represent a directional graph?


texts: Scheduling optimization problem in theta(n)

texts:
I've been told it is possible to find a solution to this optimization problem in $\Theta(n)$ but I still don't know how I could do it. I did find easily a solution in $n\lg (n)$ though. I only need to have a VALID solution, not the optimal.

This is the problem :

Let say you have n tasks that have a start time and a max time. Each task takes 1 unit of time to complete.

So for example :

T1 = 2,3
T2 = 1,4
T3 = 4,5
T4 = 1,5
T5 = 3,4

This means that T1 CAN be started at time 2 and must be done by time 3. So a correct solution could be :

  T2, T1, T5, T3, T4

Any idea on how I could create an algorithm in $\Theta(n)$? For now I thought of using a sorting algorithm that does not use comparison but it only works with integer so I can't really get a reference to an object or something.


texts: How is Turing's Solution to the Halting Problem Not Simply "Failure By Design"?

texts:
I'm having a hard time viewing Turing's solution to the Halting Problem as a logician, rather than as an engineer.

Here is my understanding of the Halting Problem:

  Let $M$ be the set of all Turing Machines.

  Let $i$ be the set of all inputs for all the Turing Machines in $M$.

  Let every element in $M$ be an element in $i$.

  Let the boolean values $true$ and $false$ be elements in $i$.

  Let $h(M,i)$ be a function that returns:

  $true$ if and only if $M(i)$ halts
  $false$ if and only if $M(i)$ does not halt

  Let $p(M)$ be a Turing Machine in $M$ that:

  calls $h(M,M)$
  halts if and only if $h(M,M)$ returns $false$
  doesn't halt if and only if $h(M,M)$ returns $true$

  What happens when we call $p$ by passing $p$ to itself, $p(p)$?

The part I take issue with is implementing $p(M)$ so that it will not halt when $h(M,M)$ is $true$. My gut understands this approach as follows:

  Given a method $h()$ that works, and a method $p()$ designed to break $h()$, when we combine these methods to build a machine, that machine is broken.

I understand proof by contradiction is a valid approach to problem solving in formal logic, but this particular application of proof by contradiction seems flawed somehow.

What am I missing?


texts: Variant of bipartite matching, with real capacities from source and to sink, all others unlimited

texts:
I've got a variant of bipartite graph matching and I can't find any literature about it.

We have bipartite graph with real capacity edges from source to left vertices (the sum of which is 1), real capacity edges from right vertices to sink (also summing to 1), and unlimited capacity edges between left and right.  What is the fastest algorithm for max flow here?

To phrase it more colorfully, you have N types of dog food, totaling 1 kilogram; and N dogs, with each dog being able to eat a maximum quantity of food, but in total they can eat 1 kilogram. Not all dogs will eat all types of dog food, but they will eat up to their "capacity" of any combination of the types that they do like. How do you get the largest quantity of dog food fed to your dogs?

So far it looks like Edmonds-Karp is actually faster than push-relabel. I've been using the networkx python package implementation of both of these algorithms, but now I need to optimize for speed. I will be implementing a solution in C or Cython, but I'm concerned about the algorithm itself. It feels like there should be a specialized solution for this that works faster. Does anyone have any ideas?


texts: Order-statistic tree: Worst-case running time of a sequence of $n$ insertions/deletions and $m$ calls to SELECT operation

texts:
Assume I have an order-statistic tree, $T$, which is a red-black tree where every node $x$ also has the attribute $x.size$. How can I compute the worst-case running time of an arbitrary sequence of $n$ insertions/deletions and $m$ calls to SELECT($x, i$), which returns a pointer to the node containing the $i$th smallest key in the subtree rooted at $x$.
I know that insertion, deletion and SELECT is done in $O(\lg k)$ time where $k$ is the number of nodes in the tree $T$.
Any hints would be greatly appreciated.


texts: Find number of nodes that seperate graph to two or more subgrahps when removed individually - Find articulation points on a non-directed graph

texts:
Suppose that we have an undirected graph, and that for any two nodes there is a path from one to another. In such a graph, there might be some nodes that, if removed from the graph individually, leave behind the starting graph as two or more subgraphs - that is, removing one of the said nodes no longer makes possible to find a path between any two nodes.

What I want is a good algorithm to find how many these nodes are - nodes that if removed individually tear the graph connectivity apart.

What I have thought so far involves removing a node at the time and trying to reach all nodes from a starting node - failing to reach every node would mean the node removed is of the kind I am looking for. Some optimizations may apply, but that's the main idea.

Can you propose any better algorithm for this, e.g. taking advantage of say the degree of the nodes?

EDIT: After having found the answer, my question is equal to asking to find the number of articulation points in an undirected graph, so the title has changed accordingly.


texts: Resizing hashmaps and compression functions for hash codes

texts:
I am trying to implement a hash table for string keys as part of a university project. I was able to make a basic, working implementation without major issues. I am now trying to optimize the thing to go closer to a O(1) expected lookup / insert time.

I was reading up on hash functions and in particular, the MAD method for hashcode compression. From my understanding, the MAD methods needs parameters (namely a multiplier a, a prime p and and offset O): index = ((a * i + o ) % p ) % N
, where i is the hashcode and N is the size of the underlying array to store the data. It is noted everywhere that p must be bigger than N, which seems natural if we want to insert the data uniformly.

Now, my misunderstanding comes from hash tables for which we do not know the numbers of keys that will be inserted ahead of time, and have no fixed capacity. Is MAD still a viable technique? From my understanding, the parameters need to be tuned to ensure an even distribution of the keys across the whole array.

A lot of hash map literature I could get my hands on also seems to imply that the maps are of fixed sizes. I am trying to figure out the same things for the table size (a lot of people talk about a prime-sized table, which seems unrealistic for resizable hash tables).


texts: Is the length of the shortest quine in a programming language computable?

texts:
The length of the shortest program in a given (fixed) programming language that produces a given output is that output's Kolmogorov complexity, which is not a computable function on the set of possible outputs.

This is a classical result and is easily proven; a proof outline appears in the Wikipedia article on Kolmogorov complexity.

My question is about a related complexity metric operating on programming languages rather than program outputs. A quine is a program that outputs its own source code (and nothing else). Every Turing-complete programming language is capable of formulating quines (by Kleene's recursion theorem). We can therefore define the quine complexity of a programming language as the length of the shortest quine possible in that language.

Is the quine complexity a computable function on the set of programming languages?

My gut tells me that it is not, but the standard approach used to prove the uncomputability of the Kolmogorov complexity metric does not seem to work here.


texts: Proving at least $n-1$ comparisons are needed to test if an array is sorted

texts:
so I need to prove the following:

Prove that $n-1$ comparisons are sometimes necessary to test whether an array with $n$ distinct elements is sorted in increasing order, for any $n \geq 1$.

The problem comes with the following hint:

Assume an algorithm exists that always correctly tests if the array is sorted using at most $n-2$ comparisons and show there must exist an input where this algorithm fails.

Base on the hint, I tried proving this via contradiction and here is my attempt:

Assume an algorithm exists that correctly tests if the array is sorted using at most $n-2$ comparisons. Then, let A be an array of 2 random numbers $a$ and $b$. Given that we don't know the value of $a$ with relation to $b$ or vice versa, in order to find this relation, an thus find out if the array with n-distinct elements is sorted in increasing order, 1 comparison operation, namely between $a$ and $b$, is needed, but then $n-2 = 1-2 \neq 1$. Therefore we have arrived at a contradiction.

While this attempt is most likely wrong, I am somewhat familiar with proofs by contradiction, but I don't see how deriving a contradiction from my initial assumption (the one from the hint) helps prove that $n-1$ comparisons are necessary.


texts: What is the single type in a dynamic typing language?

texts:
Regarding static typing and dynamic typing, Practical Foundation of Programming Languages by Harper says:

  There have been many attempts by advocates of dynamic typing to
  distinguish dynamic from static languages. It is useful to consider
  the supposed distinctions from the present viewpoint.

  Dynamic languages associate types with  values, whereas static languages associate
  types to variables. Dynamic languages associate  classes, not types, to  values  by tagging them with identiﬁers such as num and
  fun. This form of classiﬁcation amounts to a use of recursive sum
  types within a statically typed language, and hence cannot be seen as
  a distinguishing feature of dynamic languages. Moreover, static
  languages assign types to expressions, not just variables. Because
  dynamic languages are just particular static languages (with a single
  type), the same can be said of dynamic languages.
  Dynamic languages check types at run-time, whereas static language check types at compile time. Dynamic languages are just as surely
  statically typed as static languages, albeit for a degenerate type
  system with only one type. As we have seen, dynamic languages do
  perform class checks at run-time, but so too do static languages that
  admit sum types. The difference is only the extent to which we must
  use classiﬁcation: always in a dynamic language, only as necessary in
  a static language.
  Dynamic languages support heterogeneous collections, whereas static languages sup-
  port homogeneous collections. The purpose of sum types is to support heterogeneity,
  so that any static language with sums admits heterogeneous data structures. A typical
  example is a list such as

 cons(num[1]; cons(fun(x.x); nil))

  (written in abstract syntax for emphasis). It is sometimes said that such a list is not
  representable in a static language, because of the disparate nature of its components.
  Whether in a static or a dynamic language, lists are type homogeneous, but can be class
  heterogeneous. All elements of the above list are of type dyn; the ﬁrst is of class num,
  and the second is of class fun.

  Thus, the seeming opposition between static and dynamic typing is an illusion. The
  question is not whether to have static typing, but rather how best to embrace it. Conﬁning
  one’s attention to a single recursive type seems pointlessly restrictive. Indeed, many so-
  called untyped languages have implicit concessions to there being more than one type.
  The classic example is the ubiquitous concept of “multi-argument functions,” which are
  a concession to the existence of products of the type of values (with pattern matching).
  It is then a short path to considering “multi-result functions,” and other ad hoc language
  features that amount to admitting a richer and richer static type discipline.

So "dynamic languages are just particular static languages (with a single type)". What is the single type in a dynamic  language?

For example, Python is said to use the reference model of variables, as opposed to the value model of variables. References are not explicit.

Is it because of references that a list in Python can have elements of different "types", i.e. achieving heterogeneous collections in the quote?
Is the "single type"  in Python the type for all the references?  Is it the same for other dynamic  typing languages, i.e. is  the "single type"  in a dynamic typing language the type for all the references? Or is reference just an implementation option of the single type in a dynamic language, and there might be other implementation options?
Do references which refer to values of different "types" have the same type?

Thanks.


texts: Good motivation for parallel data structures and algorithms

texts:
I have a more general question for you. I'm working in Parallel Data Structures and Parallel Algorithms. That is a nice topic with a lot of interesting challenges. However, I have some problem to argue for why is necessary use parallel solutions. The most common justification is "We need to take advantage of the current architectures", "Parallel alternatives speed up sequential alternatives", but it isn't enough. Some people can think: OK, I believe you, but I don't have any problem waiting 10 minutes for my efficient sequential algorithm instead of 2 minutes for your parallel algorithm. That reflects a weak spot of parallel solutions: they are, in general, difficult to program and need more time to debugging.

So, now I'm trying to find a better motivation for parallel solutions. I have this motivation now: There are problems that don't have efficient solutions in sequential, and parallel solutions appear like the best alternative for those kind of problems. My question now for you is: How characterize this kind of problems?. I thought in problems with a lot of computation, like some graph problems, but I would like to know other view points.


texts: What is the smallest $n$ such that $BB(n) > $Graham's number?

texts: BB represents the busy beaver function here. Do we even have any idea of what order of magnitude $n$ would have? Is it possibly around 10, or more like 1000?


texts: Complexity of Matrix Inversion when $n-2$ Eigenvalues are the same

texts:
Suppose we have a symmetric matrix $A \in \mathbb{R}^{n \times n}$ that has $n-2$ equal eigenvalues and the other two are distinct.

Question: What would be the complexity of its inversion?

On the one hand, if all eigenvalues are the same, then the matrix is equal to $aI$. Therefore, the inversion is $O(n)$.

On the other hand, if we can't assume anything than the inversion is $n^{2+\epsilon}$ where $\epsilon \approx 0.37$.

Note: Eigenvalues and eigenvectors are not given.


texts: prove language is Context-free and not regular

texts:
I have to prove that $\left \{ a, b \right \}^{\ast} - \left \{ a^ib^i | i\geq 0 \right \}$ is a context-free language and it's not regular.

So far I've got that this language is not regular because regular languages are closed under complementation and $\left \{ a^ib^i | i\geq 0 \right \}$ is a well know context free language (by the way do you have a link with a formal proof that $\left \{ a^ib^i | i\geq 0 \right \}$ is context free?)

For the context-free I'm a little confused
I've thought about building a PDA that recognize $\left \{ a^ib^i | i\geq 0 \right \}$ (pushing a's on the stack and popping a's when a b is read works?) I think is deterministic CF so i can use the same reasoning (complement of a DCF is a DCF language?)


texts: Why postfix is used more often than prefix expression?

texts:
i was reading stack and i came across the infix, preifx and postfix expression.So i understood that why postfix /prefix expressions are preferred over infix expression ( due to its unambiguous nature) .But i am not getting any enough information  about the popularity reason of postifx expression over prefix expression.

Why are we not using prefix expression than the postfix expression more often?

I am guessing that ,

it's related to the easiness of converting the infix to postfix
or the evaulation process of postifx is easy than prefix.

If so, Please someone elaborate on it.

thanks.


texts: Is there another common name for dominating set in graphs?

texts: I am looking for graphs which the value of a minimum dominating set is known (Where can I find a data set of graphs with known domination numbers?). So far I have not found anything, so perhaps I missed a search term. Does anybody know if dominating set goes by some other name?


texts: A variant of the vertex cover problem on trees

texts:
Consider the following variation on the vertex cover problem: given a tree on $n$ vertices, we are asked to calculate minimum size of a multiset $S$ such for each edge $(u,v)$ in the tree at least one of the following holds:

$u\in S$,
$v\in S$,
there are at least two vertices in $S$, each of which is adjacent to $u$ or $v$.

Since $S$ is a multiset, a vertex may be in $S$ multiple times.

My hunch is the following. First of all, we take into consideration the following fact: in optimal solution each vertex is in $S$ at most twice. So we can traverse tree in post-order and calculate results for the three cases where a vertex is not in the optimal $S$, it's in once and it's in twice.

Unfortunately I can't link relations between subproblems and I'm not sure if this idea would be correct.

Hints or references are both welcome. Many thanks.


texts: DFA accepting strings with at least three occurrences of three consecutive 1's

texts:
The problem states the following:

  Draw a deterministic finite automaton (DFA) accepting strings containing at least three occurrences of three consecutive 1's on alphabet $\Sigma=\{0,1\}$ with overlapping permitted.

I was able to come up "without overlapping" version as follows:

Regex of this DFA is (1+0)*111(1+0)*111(1+0)*111(1+0)*.
However this DFA does not accept 11111. This string should be accepted as the problem says overlapping of groups of three consecutive 1's is allowed. But I am not able to guess how do I do this. I feel I cannot do it with DFA as this will require to have some form of memory (for example, once I read 111, it should remember first occurrence of three consecutive 1's is read and also two consecutive 1's of next occurrence have already been read) which is not what DFA provides. Am I right with this?

If not with DFA, can I do this with non deterministic finite automaton (NFA) or deterministic pushdown automaton (DPDA) or non deterministic pushdown automaton (NPDA)? Or this can be done only with Turing machine?


texts: Parallelization of an iterative function application

texts:
What I have
An iterative process based on the application of a very simple function to represent a rate, with total dependence among any iteration and its predecessor (one input parameter for (n)th iteration is the output parameter from the (n-1)th iteration). Specifically,
$\qquad  f(x, y, z) = x + \frac{y - x}{z + 1}$
with $x$ the modeled rate (typical value between 0 and 1),  $y$ the contribution of every new record to the learning about the rate (typical value 0 or 1) and $z$ some kind of convergence/learning speed parameter (typical value any integer between 30 and 900). While $y$ and $z$ are constant, $x$ would be the result of the previous calculation.
What I want
Some kind of manipulation of the function that allows some level of independence among sequential iterations, thus allowing parallelization.
What I know (or believe to) so far:
There is extensive published literature on parallel iterative methods, but most of them are about classical methods like Map-Reduce for Machine Learning on Multicore by Chu et al.
But I'm failing to recognize which of them I could "use" to help me with my simple function.
Can someone help me pointing literature on the basics of function transformation aiming towards parallelization? Any thoughts on that matter will be very helpful.


texts:
I want to remove indirect left recursion from these rules:
    S-->TU,
    T-->US|b,
    U-->ST|a

I don't know if I can implement the algorithm correctly. My assumption is to make it like this:
S-->TU, T-->U'b, U'b-->U'a

Is this correct?


texts: Prove that the upper bound for T(n)=T(an)+T(bn)+O(n) is O(n)

texts:
While learning Median of Medians algorithm i came across the following lemma ;

"For any recurrence of the form $T(n)<=T(an)+T(bn)+O(n) $,
if $(a+b)<1$ the reccurence will solve to $O(n)$"

(Which means $T(n)$ is bounded by $O(n)$ for some constant $ $ for any
 $ n>n_0$ )

So i was trying to prove it (since i could not find any proof) using Substitution Method :
(there might be a proof using Master's theroem but i didnt know how to use it here , and i would also like to see a proof using Substitution Method )

So i tried to prove by induction .
We can assume that for for any $n<N$ , $T(n)<=k_2*n $ for some constant $k_2$.
Assuming the statement is correct from $min(a*N ,b*N)$ since $(a+b)<1$

(i dont feel like the previous sentence is entirley correct , maybe i should assume that for any number smaller than n ? Plus , I think I have to assume that they are positive here ?  )

$a*N$ and  $b*N$ are less than N and thus , we can use the induction hypothesis ;

$$T(N)<=k_2aN+k_2bN+xN $$
(since were given $O(n)$ i assumed there exists a constant x for which the given function is bounded by)
We want
 $$k_2aN+k_2bN+xN<=k_2N$$
=>   $$k_2a+k_2b+x<=k_2$$
since $a+b<1$ then i can continue but i can't see how to finish the proof .
I think i have to assume by contradiction that $T(n)$ is not bounded by $O(n)$
but im not entirely sure what my assumptions are .
Trying to do so i stated that for any constant $$T(n)<=T(an)+T(bn)+O(n)>O(n) $$
but that dont seem like the right way..

I would appreciate any help , thanks.


texts: Why high and lower bit of generator must be 1?

texts:
Here is an excerpt from Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 3 (The data link layer), Page 213:

  When the polynomial code method is employed, the sender and receiver must agree upon a generator polynomial, $G(x)$, in advance. Both the high- and low-order bits of the generator must be 1. To compute the CRC for some frame with $m$ bits corresponding to the polynomial $M(x)$, the frame must be longer than the generator polynomial. The idea is to append a CRC to the end of the frame in such a way that the polynomial represented by the checksummed frame is divisible by $G(x)$. When the receiver gets the checksummed frame, it tries dividing it by $G(x)$. If there is a remainder, there has been a transmission error.

My question is how do you determine high order bit? And why high order bit and lower order bit, both must be one? From my understanding, it is used to detect burst error but is my understanding true?


texts: How to check ambiguity of a specific grammar

texts:
Giving the following Grammar:

S → ^ | SaSMSM |  SMSaSM | SMSMSa
M → b | c

^ means eopsilon.

How can i check whether its ambgious or not?
My intuition is that its not: every time you derive,the a is placed in different places between the M's.

Can you give me a clue to get a better prove? Or give an example for its ambiguity?

In other words,Can i have to different derevation trees for a same string in this grammar?

Thank you.


texts: Finding a negative cycle in a bipartite graph

texts:
The Bellman-Ford algorithm can be used to find a negative cycle in a general graph, in time $O(|V||E|)$. Is there a faster algorithm for finding a negative cycle in a bipartite directed graph, where the edges in one direction (from X to Y) are all positive and the edges in the other direction (from Y to X) are all negative?

One idea that I considered is to solve two instances of the minimum-weight assignment problem: one with only the edges from X to Y, and one with only the edges from Y to X. Combining the two assignments gives a directed cycle in the original graph. However there are two problems with this idea:

The computational problem of finding a minimum-weight assignment is not necessarily smaller than Bellman-Ford, for example the Hungarian algorithm requires time $O(|V|^3)$.
The directed cycle found in this way is not necessarily minimum-weight in the original graph; it is possible that the original graph has a negative cycle while this algorithm will yield only a positive cycle. For example, consider a graph with four vertices in each side, with the following weights:
\begin{align*}
w(x_1\to y_1) = w(x_2\to y_2) &= 1
\\
w(y_2\to x_1) = w(y_1\to x_2) &= -2
\\
w(x_3\to y_3) = w(x_4\to y_4) &= 5
\\
w(y_4\to x_3) = w(y_3\to x_4) &= -3
\end{align*}
and all other weights are $+\infty$.

There is a negative cycle $x_1\to y_1\to x_2\to y_2$ (total weight -2). However, the minimum-weight assignment from X to Y has weight 12 and the  minimum-weight assignment from Y to X has weight -10 so the total is positive.


texts: How long should I spent on a coding challenge before looking at the answer

texts:
I’ve been spending an hour each day working through coding challenges trying to improve my algorithm and data structure skills.
I will say I’m happily employed, but I want to keep my skills sharp in this area since it’s necessary for most technical interviews for mid to large size companies.
My question is using the U.P.E.R. framework:
U - Understand the problem
P - Plan how you’re gonna solve the problem
E - Execute your plan
R - Review and optimize the solution
how long is too long to spend trying to understand a problem? I find myself spending sometimes 4-6 hours over the course of a week trying to understand a easy or medium problem and not getting past this point.
How long is a general rule of thumb to spend trying to understand the problem being asked before looking at the answer and trying to understand the solution?
I will say I don’t have anyone to ask for help, and I’m just trying to improve my skills.
I’m a fulltime software engineer but these problems always stump me.
I just want to get better but also don’t want to waste too much time on a single problem.


texts: What is the connection between combinatorial circuits and finite state automata?

texts:
The diagram on the Wikipedia page of FSA shows the hierarchy of the computational devices, in that diagram it is denoted that the finite state machines are superior to the combinatorial circuits.

Combinatorial circuits are the model of propositional logic i.e. both are equivalent, where we do a discussion about the truth values of variables and the logical connectives. Whereas the models beyond the FSA process the strings and decides the membership of a string with for some language.

If there is some connection between these two models then there must be some relation between propositional logic and regular/context-free/recursive languages.

How can we construct a corresponding FSA for a given combinatorial circuit?


texts: How can you determine what set of boxes will maximize nesting?

texts:
I'm trying to find a dynamic solution to the nesting boxes problem.

You're basically given a set of "boxes" which all have different dimensions. The goal is to find the maximum set of boxes that can be nested inside of each other.

So more formally,

Given set B = {b_1, b_2, . . . b_n} where each b_i contains a box with a width, height and depth.

Find the set of boxes that will allow you to nest as many as possible together.


texts: What is the fastest addition algorithm on a turing machine?

texts:
What's the asymptotic running time of the fastest algorithm for adding two $n$-digit decimal numbers on a Turing machine? To specify, the input is of the form $a_1+a_2$ where $a_1$ and $a_2$ are written out in the usual decimal expansion, and the output on the tape is just the result, $a_1+a_2$ (there is no need to keep the inputs). The best I can do so far is $O(n^2)$ time using this program I made: http://morphett.info/turing/turing.html?185f35a035e386d2a927c15b869b422a

The way this algorithm works is by finding the rightmost "non-added" digit of the number to the right of the addition sign (henceforth No. 2), marks this with an "o", and moving left until it finds a "non-added" digit of the number to the left of the addition sign (henceforth No. 1) and marking the result with a letter so that the machine will know how many decimal places to go to the left when adding next time. If there are any carries, these places are marked with numbers rather than letters because they haven't been 'reached' yet other than by the carry. The machine ends when all the digits on the right-hand number have been turned into "o"s and the machine encounters the plus sign instead of a number. Then, it cleans up all the "o"s and transforms all the letters into numbers and deletes any 0's at the beginning of the number.

I won't provide a rigorous proof, but this algorithm can be seen to be $O((n_2)^2)$ time complexity intuitively by the fact that for each digit in No. 2, the turing machine has to move about $n_2$ (which I use to denote the length of $a_2$) steps to the left, and since there are $n_2$ digits in No. 2, this algorithm takes about $n_2\times n_2=(n_2)^2$ steps. (Thus it runs in $O(n^2)$ time, assuming both numbers are of the same length, $n_1=n_2=n$). This improves on the naïve exponential time implementation of just subtracting one from No. 2 and adding one to No. 1 until No. 2 is exhausted, but is there any faster algorithm?

EDIT: Just to clarify I want the fastest algorithm for adding two decimal numbers of equal length, $n$. I use $n_1$ and $n_2$ as the lengths of $a_1$ and $a_2$ respectively only to emphasize that the algorithm is technically only quadratic in $n_2$, which is where it gets the $O(n^2)$ runtime from. I tried calculating the exact number of steps the algorithm takes, which is $n_1+2(n_2)^2+5n_2+max(n_1,n_2)+5+2c+d$, where c is the number of carries (bounded by $n_1$) and d is the number of digits in the result. Thus, a more precise runtime would be $O((n_2)^2+n_1)$, but left this out for conciseness and because in the end I only cared about the case $n_1=n_2=n$.


texts: How does increasing the page size affect the number of page faults?

texts:
If we let the physical memory size remain constant,

What effect does the size of the page have on the number of frames?
What effect does the number of frames have on the number of page faults?

Also, please provide reference strings as an example.


texts: How can you represent a Huffman-tree in Hex?

texts:
I was trying to store a Huffman tree in a binary file recently. I thought it wouldn't be a big problem since you actually have the binary codes already in front of you.
Well, the difference is that the file (in the hex editor) is logically coded in hex. So I tried to convert the "characters" from binary to hex. Without any success.
Let's take this tree as an example:

My first attempt was to simply convert Binary to Hex. So for example 01 became 0x01. But there is a problem now: There are duplicates. So 01 as well as just 1 both became 0x01.
So I couldn't use that. I also tried to just represent the  zeros and ones in hex, for example: 10 1... (The equivalent of 1 01) but that wouldn't be really efficient anymore.

So how could I now make a Huffman tree in Hex? Would I maybe even have to use a different encoding?
I hope I could describe my problem well enough.


texts: How can I study the nature of the structure of evaluation of function in lambda calculus?

texts:
I am specifically focusing on lambda calculus, following this paper: A Tutorial Introduction to the Lambda Calculus.

Suppose we have three functions that represent the natural numbers 0 and 1, and a successor function:

$\lambda sz.z = 0$

$\lambda sz.s(z) = 1$

$\lambda wyx.y(wyx) = succ$

Suppose I were to evaluate $succ\ succ\ 1$. As I evaluate this expression, it is becoming clear to me that it's not 3 as I might naively expect, but I do not truly grasp "why." Even as I go through the motions of evaluating the expression, I do not understand the nature of the turn of events and why certain expressions produce a certain result due to their structure and construction.

A question I might ask would be something like, why does $succ$ have that form, and is there an alternative form for $succ$ that produces the same result? If it is unique, what makes it special? I don't know how to answer these questions well yet, so I am seeking guidance.

Is there a method by which I can better visualize or understand the evaluation of expressions and how it affects the "class" of their output? I am very new to lambda calculus, so please excuse me.

Edit: I think I understand the rules for evaluation of lambda calculus (substitution, prevention of name collisions, etc.), but I have a hard time understanding the arbitrary rules by which one can construct lambda calculus' equivalent forms for the natural numbers, the successor functions, and the addition and multiplication functions. It's how these parallels to these concepts were mapped over to lambda calculus that I am interested in.

For example, why are the functions for "choose second," "false," and "discard next argument," and "0" have the same form and thus equivalent? There exists systems in which applying the zero function to a list of object does not result in returning a list with the front-most argument removed. Even if it is a convention, is there a reason why it is structured as such?

For example, why is does the successor function work? One can say that it was discovered through trial and error, but this makes for poor understanding of the nature of a concept besides "it is so" and "it works." I hope this makes sense.


texts: Equivalence in finite sets of turing machines

texts:
I have this exercise and I really don't know how to complete it:

Prove that for all finite sets S of Turing Machines it is decidable
whether or not given any two Turing Machines M1 and M2 in S they
recognize the same language, that is, L(M1)=L(M2)

I know that the problem of equivalence of languages is undecidable in general, but the additional hypothesis of the finiteness of the set S of machines does not suggest me any reason why this case should be different. Can somebody help me?


texts:
Today I was taught that since the height of a heap cannot exceed $\log n$, it is $O(\log n)$; height in my class was defined as the maximum number of steps in a simple path from a leaf to the root. That is fine, but I think we should further specify it as $\Theta(\log n)$ since it, at that same time, must be greater than $\log n - 1$, and hence also fits $\Omega(\log n)$. I suggested this after class, but I was repeatedly told that $O(\log n)$ was correct, and the correctness of $\Theta(\log n)$ was not explicitly confirmed.

Is $\Theta(\log n)$ correct? If so is there a common reason / justification to just use $O$ instead, and possibly even to avoid using $\Theta$?

Clarification: it's a binary heap.


texts:
At least in Java, if I write this code:

float a = 1000.0F;
float b = 0.00004F;
float c = a + b + b;
float d = b + b + a;
boolean e = c == d;

the value of $e$ would be $false$. I believe this is caused by the fact that floats are very limited in the way of accurately representing numbers. But I don't understand why just changing the position of $a$ could cause this inequality.

I reduced the $b$s to one in both line 3 and 4 as below, the value of $e$ however becomes $true$:

float a = 1000.0F;
float b = 0.00004F;
float c = a + b;
float d = b + a;
boolean e = c == d;

What exactly happened in line 3 and 4? Why addition operations with floats are not associative?

Thanks in advance.


texts:
I want to compute the partial order width i.e. the size of the maximum antichain in a given partial order.

By Dilworth's Theorem this is the same as minimal chains required to decompose the graph, but I cannot find any algorithms to compute any of these equivalent quantities.


texts: Implementing addition for a binary counter

texts:
A binary counter is represented by an infinite array of 0 and 1.

I need to implement the action $\text{add}(k)$ which adds $k$ to the value represented in the array.

The obvious way is to add 1, k times. Is there a more efficient way?


texts: Algorithm to generate inputs with certain properties, but not accepted by a given regular language

texts:
General

Given a regular language $L \subset \Sigma^\star$, I wish to generate at least one string not in $L$. (Obviously, this requires that there exists such a string; i.e., that $L \neq \Sigma^\star$. I would be interested in ways to decide this, if any exist.)

(Harder) I wish also to generate at least one string not in $L$, but such that the property $P$ holds. (Again, this requires $\exists w \not\in L : P(w)$ and $\exists w \in \Sigma^\star : P(w)$, but of course one must know $\Sigma,L,P$ to prove any of these.)

A somewhat naïve approach, when we can reliably generate $w : P(w)$, is to do so until $w \not\in L$. For the specific case below, this is not terribly difficult once we can generate strings from a context-free grammar. Is there better?

Specific

After thinking about Balanced braces, my stack-based implementation, and my slight rant about students knowing regular expressions are not sufficient for this problem, I would love to be able to do the following:

Given a regular expression1 that supposedly solves the balanced parentheses problem2, I would like to generate a string in the (context-free) language of balanced parentheses that is rejected by the regular expression.

This would be a nice way to highlight, based on intuition, that some languages are more bigger than others. It would also prove that the given RE is not equivalent to the desired language, though of course it does not constitute a proof that no RE is equivalent.

So, to recap:

$L$ is an attempt to recognize all strings in the language of balanced parentheses (doomed to fail);
$\Sigma = \{(, )\}$;
$P$ is the property that the given string is in the language of balanced parentheses

We can stick with the "proper" definition: concatenation, alternation, and Kleene-star repetition)
Again, stick with just ( and ) for simplicity


texts: How many optimal alignments can be there for a string of length m with a string of length n?

texts: So I was practicing optimal alignment algorithm and I was stuck with this question of finding optimal alignment for a string of length m with a string length n ? Also is it possible to run it in theta(n) times. Can anyone help me with this?


texts: SVM with a priori information about class probabilities

texts:
Given are two 2-d sets, each with its own bivariate normal distribution. I need to build an SVM classifier. The a priori probabilities of each class corresponds to the size of its set (20/50 for the first and 30/50 for the second one). I am quite confused about the way to implement the knowledge about set structure and a priori probability of classes. Any ideas appreciated.

(If your idea is supported by some R packages it would be very nice.)


texts: Algorithm to delete BST nodes with duplicated values

texts:
In a binary search tree the following must hold:

Greater keys are in the right-subtree
Smaller or EQUAL keys belong to the left-subtree

All the algorithms I found to delete a node start by finding the smallest node in the right subtree of the node we want to delete, the successor (or the greatest node in the left subtree, the predecessor), and replace the deleted node for the successor.

But what happens when BST nodes with the same key exist and we use the successor method?

If we use the predecessor, we don't run into this problem.

     4
   /   \
  2     5 <-- Delete 5
 / \   / \
1  3  5   7
         / \
       [7]  9 <-- 7 will take 5's place

Now we end up with:

     4
   /   \
  2     7
 / \   / \
1  3  5  [7]  <-- This 7 should be in the left subtree
           \
            9

The BST will still work (or not?), but the definition of BST won't fit this resultant tree anymore.

Is there another algorithm that takes this into account or is this result expected and generally accepted?


texts:
Consider an ordinary binary max-heap data structure with $n$ elements that supports insert and extract-max in $O(\log n)$ worst-case time.

  Question: If extract max is $O(1)$ amortized does that mean worst case is $O(n)$?

My answer: No, A sequence of $n$ EXTRACT_MAX will cost $O(n\log n)$. This is because in a Heap the leaves are almost on the same level and the number of leaves in a Heap is $O(n/2) = O(n)$. Calling EXTRACT_MAX each time removes the maximum element from the root and replace it with a new second maximum element and decrement a leaf. Thus, decrementing all the leaves (which are of $O(n)$) will take $O(\log n)$ time each as all leaves are almost in the same level totally giving a time complexity of $O(n\log n)^{1/4}$.

Does this make sense?


texts: How to find a subset of numbers such that its average is close to the average of the full set?

texts:
I have a set of n numbers whose average (arithmetic mean) is x. I have to choose a subset of k numbers from n such that its average is closest to x. Please note that k is the upper bound. If the average can be represented with less than k numbers, then that set is chosen.

For example:
set = {1, 2, 3, 4, 5, 6} (n = 6) (average = 3.5)
If k = 1 then the subset can be either {3} or {4}
If k = 2 then the subset is {3, 4}
If k = 3 then the subset is still {3, 4}

I have to write an algorithm for the same. If this problem is not solvable in polynomial time, what would be a good approach to solve it? Any heuristic approach?


texts: Why is Scale Space Needed to Detect Scale Invariant Features?

texts:
I have been doing research on the SIFT (scale invariant feature transform) algorithm, and while I have repeatedly read that in order to detect image features that do not vary with respect to scales of visual perspective, a scale space must be constructed from the source image using repeated Gaussian smoothing and taking differences of those Gaussians. Then local extrema are found in the four dimensional scale space which are designated as scale invariant key points. How this process is performed seems straightforward, but my question is why does this process work at all? What is special about the Gaussain blur that allows us to do this? In the publications that I am reading (listed below), the reason this works is not clear to me.

Lindeberg, Tony. “Detecting Salient Blob-like Image Structures and Their Scales.” Scale-Space Theory in Computer Vision (1994): 249-70. Web.
http://www.nada.kth.se/~tony/abstracts/Lin92-IJCV.html

Lindeberg, Tony. “Scale-space.” Encyclopedia of Computer Science and Engineering. Vol. 4. N.p.: n.p., n.d. 2495-504. Web. 16 Oct. 2016.
ftp://ftp.nada.kth.se/CVAP/reports/Scale-Space-EncCompSci.pdf

Lowe, David G. “Distinctive Image Features from Scale-Invariant Keypoints.” International Journal of Computer Vision 60.2 (2004): 91-110. Web.

EDIT

I have read many high level explanations of this concept, which generally say that as the sigma of the Gaussian increases, fine grained features should be suppressed and that coarse grained features should be generalizations of fine grained features. But I am looking for a more rigorous and possibly mathematical explanation of why this is the case.


texts: Number of distinct substrings in a string

texts:
From what I have come to understand, the best way to implement it is to use the suffix  array $S$ of the string $w$ and its LCP-array (Longest Common Prefix) $L$.

The answer can be obtained by

$$ \sum_{i=1}^{|w|} \left( |S[i]| -L[i-1] \right).$$

What I don't get is how and why is this working?

I would be very grateful if someone explained this.


texts: Minimum Height Trees. Why does deleting leaves layer-by-layer give us the answer?

texts:
Here is the problem I tried to solve. Finally, I gave up and found a solution which was correct. Here is it.

Here is the problem description:

  For a undirected graph with tree characteristics, we can choose any
  node as the root. The result graph is then a rooted tree. Among all
  possible rooted trees, those with minimum height are called minimum
  height trees (MHTs). Given such a graph, write a function to find all
  the MHTs and return a list of their root labels.

  The graph contains n nodes which are labeled from 0 to n - 1. You will
  be given the number n and a list of undirected edges (each edge is a
  pair of labels).

  You can assume that no duplicate edges will appear in edges. Since all
  edges are undirected, [0, 1] is the same as [1, 0] and thus will not
  appear together in edges.

Example 1 :

Input: n = 4, edges = [[1, 0], [1, 2], [1, 3]]

    0
    |
    1
   / \
  2   3

Output: 1

Example 2 :

Input: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

 0  1  2
  \ | /
    3
    |
    4
    |
    5

Output: 3, 4

Here is the solution I tried to understand:

  The basic idea is "keep deleting leaves layer-by-layer, until reach
  the root."

  Specifically, first find all the leaves, then remove them. After
  removing, some nodes will become new leaves. So we can continue remove
  them. Eventually, there is only 1 or 2 nodes left. If there is only
  one node left, it is the root. If there are 2 nodes, either of them
  could be a possible root.

I'm not sure I understand it so I could explain it to somebody. Why does deleting leaves layer-by-layer give us the answer?


texts: C(++) library for DFAs - free for academic use

texts:
(I'm aware that software questions are better suited for stackoverflow, but since DFAs are not something that software developers usually care about, I hope it's alright if I ask here.)

I'm currently working on a project to do with regular overapproximations for context free languages. For this purpose, I need to implement stuff that requires me to represent regular languages in a minimized form, intersect them, complement them, etc. - i.e. everything that's easy and quick to do with DFAs. However, I'm having a hard time finding still-maintained libraries for DFAs in C++. I could find libfa which does everything quite nicely, but that's as far as I've gotten. Grail hasn't been maintained in 15+ years and the download link is dead. FAdo seemed interesting initially, but it's in Python and I can't determine whether there's a way to use it as a C++ library, or whether it offers the functionality I mentioned above (the Docs are a bit slim).

Do you know of C(++) libraries for DFAs that offer minimization, intersection and complementation that are free for academic use? I'd like to have at least one alternative to libfa that I can use.


texts: in these days I'm doing research about the history of the mailing lists. Someone can suggest me interesting "Papers" or Article on the web in order to learn much about history and principal use of this service?


texts: Complexity of algorithm partitioning input into parts of size $n/100$ and $99n/100$

texts:
Merge sort always divides array of size $n$ into parts each of size $n/2$. It then merges these two parts. So its recurrence relation is $T(n)=2T(n/2) + O(n)$. What if there is an algorithm which is guaranteed to partition the array into two parts of sizes $n/100$ and $99n/100$? So its recurrence relation will be $T(n)=T(n/100)+T(99n/100)+O(n)$.
It feels like this relation is not as good as merge sort in terms of time. I think that such an algorithm's worst case time complexity should be between that of $O(n^2)$ and $O(n\log n)$.
I have two questions:

Is $n/2$ and $n/2$ partitioning the most optimal or $n/100$ and $99n/100$ partitioning also asymptotically optimal?
How to solve the recurrence relation $T(n)=T(n/100)+T(99n/100)+O(n)$?


texts: NP-complete proof from Dasgupta problem on Kite

texts:
I am trying to understand this problem from Algorithms. by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, chapter8, Pg281. Problem 8.19

A kite is a graph on an even number of vertices, say $2n$, in which $n$ of the vertices form a clique
and the remaining $n$ vertices are connected in a “tail” that consists of a path joined to one of the
vertices of the clique. Given a graph $G$ and a goal $g$, the KITE problem asks for a subgraph which
is a kite and which contains $2g$ nodes. Prove that KITE is NP-complete.

Any pointers to start with this problem? I am completely lost with it.


texts:
I use the A* search algorithm to to search for the shortest path from S to G.
The evaluation function is $f(n) = g(n) + h(n)$.

Since node A and B have the same estimated total cost, I choose to go node A.Then, the $f(n)$ of B is 8, C is 7, G is 10. After expanding C, $f(n)$ of G is 7. Therefore, the path is S-A-C-G with total cost 7.

However, there is a lower cost path S-B-G with $f(n) = 6$.
Is the path S-A-C-G still optimal or I did the search in the wrong way?


texts:
our uni is closed because of the COVID-19 and I'm trying to homelearn dynamic programming.

In our algorithms book, there is the following problem: (an example problem for dynamic programming)

  A driver has 3 cars. He wants to use all of the 3 cars, but want to
  use the least gas. Each car has a different engine, so it will consume
  different amounts of gas to get to each destination. What is the least amount of gas
  we can consume while still using each car? After he switches cars, he
  can't go back to the previous car.

  Input description:

  First is a number $n$, which is the number of destinations that he
  wants to reach.  Then there are 3 lines, each is the gas consumed
  while trying to reach each destination (line 1 is car 1, line 2 is car
  2, etc..)

  Example input:

  7

  2 4 1 5 1 1 2

  3 3 2 5 3 2 2

  1 1 5 4 3 3 3

  Example output:

  12 (third car (2 destinations), first car (4 destinations), second car (1 destination).)

However, I can't figure out how to start, as I'm still learning DP. Could you please help me or give me any hints?

I think it's a great good example problem, because other problems are very similar so if I master this one, I should be able to solve other problems.

Thanks!


texts: Reversible computation and no cloning theorem in quantum computing

texts: I am having a problem in understanding a conflict between reversibility in quantum computation and the No cloning theorem. Given a function f, we construct the reversible version of f by adding additional input and output wires to the circuit for f, possibly outputting junk bits. We then "copy" the output to another register to not to lose the output information using CNOT gates. But doesn't this contradict the No Cloning Theorem? We cannot copy the state of a quantum bit. Can we?


texts: How the language $\{a^nb^mc^nd^m | n \geq1, \ m\geq1\}$ is used to check whether formal and actual parameters are equal?

texts:
How does the language $L=\{a^nb^mc^nd^m \mid n \geq1, m\geq1\}$ abstract the problem of checking that the number of formal parameters in the declaration of a procedure agrees with the number of actual parameters in a use of the procedure?

I simply didn't get what each of the variables $a,b,c,d,n$ and $m$ will represent? Seems $1^{st}$ pair $(n,m)$ is for formal parameters and later for actual. But I didn't get why there are $a$ and $b$? Couldn't only single variable be ample?


texts: How do neural networks create results like its inputs?

texts:
I understand basic neural networks (input layer, hidden layers, output layer) and gradient descent learning. However I keep hearing about news talking about neural networks painting and making jazz music. That is puzzling me.

As I understand a neural network, you feed it the input data (i.e. a picture, music, ...) and it gives you some kind of classification on the result. But by reading those results it looks as if they were using the neural network to generate new results based on a training dataset. Because of that, I'm thinking the kind of neural networks they're referring to is essentially different from the ones I've studied, so I'd like to ask:

What are the differences between classic neural networks and the ones used to run these experiments? What makes them fundamentally different so that they are able to generate results similar to its input?
Do these results (generating results with a NN) have anything to do with deep learning? Or is deep learning just a better learning technique?


texts: Is sierpenski's triangle considered to be a computational model?

texts:
I was reading about sierpenski's triangle and i found that it is similar to pascal's Triangle, which can show coefficients in binomial expansion,  also rule 90 from ECA.

If Sierpenski's triangle can show coefficients in binomial expansion, and was simulated by other two systems {Pascal's Triangle} and {Rule 90} does that means it is a computationa model ?

What about rule 110, which is proved to be universal, is it a computational model also?


texts:
I have a subject called computer architecture in university but I don't get a clue of it.
We get assignments like: make a 2-bit two’s complement carry lookahead adder using 3 4-bit adder.

This is a circuit I have to make in Logisim, however, it's like you need an already deep insight in the subject to be able to make this; insights I don't have (because it's totally new for me).

Is there a kind of method to solve and make these circuits? Using truth tables or anything?

Note: I'm not asking for the solution for this specific problem, only for a method or steps-to-take in general, to be able to make any (basic) circuit.

This is the full exercise: http://msdl.cs.mcgill.ca/people/hv/teaching/ComputerSystemsArchitecture/materials/CA2/CA_Project_2.pdf (Ex5 if you want more explanation of the problem).

I was able to solve the other 4 by trying very hard and using Google but without actually knowing what I was doing.

So again, I'm not asking for this specific solution, only if there is a general way to solve these kind of assignments using a specific method or steps, eventually explained by using this one example-exercise.


texts: Shortest path visiting all nodes in an unrooted tree

texts:
I have a tree. This tree has no particular root (free-tree).
I want to find a path that visit all nodes. This path has to be the shortest possible.

All edges are considered to have a distance of 1.

My problem is not finding a Hamiltonian path, because I don't have any restriction on the number of times a node can be visited.

We don't know the source node of the path. The source has to be one allowing us to find the shortest path visiting all nodes.


texts: Compute pair of similar list from a collection of lists

texts:
Given a list of list of integers how to find pair of lists which have overlapping i.e. 1 or more elements are common.

Is it possible to solve without having cartesian product of initial list with itself


texts: Rounding of $2-10^{20}$ in IEEE double precision

texts: How do we get the rounding of $2-10^{20}$ in IEEE double precision? The textbook says it is $-10^{20}$, but I do not know why. I think my textbook only explains the rule for rounding mantissa.


texts: Where is the original literature for the specification of an Associative Array ADT?

texts: I'm looking for the formal specification for the Abstract Data Type Algebra for the Associative Array, Associative List (AKA multimap), and other similar ADT to cite for use in a data specification similar to Binary JSON. The Wikipedia Associative Array entry uses non-standard math terminology and their sources are all secondary sources with no original sources. There is an algebra for the Dictionary and it starts with Let x be a set and it defines operations on that set. Who invented the dictionary and when? It should be pretty old, possible from the Journal of the Association of Computer Machinery or similar publication.


texts: Number of circuits with at most $m$ logic gates

texts:
I'm working on the same exercise as described in this post:

How to show that hard-to-compute Boolean functions exist?

In the answer there I don't understand how the number of circuits with at most $m$ gates was found to be $O(m^{4m})$. My construction of the number of gates required:

Let any logic gate in the circuit take 2 inputs, which could be any of the $n$ inputs or any of the $m-1$ other logic gates. Then there are ${{m+n-1}\choose{2}}$ possibilities for the inputs into any logic gate. There are 16 different functions that act on 2 inputs, so let there be $16{{m+n-1}\choose{2}}$ possibilities for the inputs and type for any logic gate. Lastly, since there are $m$ gates, there will be $16^m {{m+n-1}\choose{2}}^m$ possibilities for the entire circuit.

Now we can say ${{m+n-1}\choose{2}}^m < \frac{1}{2^m}(m+n-1)^{2m} < \frac{1}{2^m}(2m)^{2m}$ when $m = 2^n/\log n$ (or $2^n/n$), so $16^m {{m+n-1}\choose{2}}^m < (32m^2)^m$. So we would want to show that $(32m^2)^m$ is less than $2^{2^n}$. This doesn't seem to be true anywhere, so I must have made a mistake somewhere.

I've looked online a bit and have found three different sources say that the number of circuits with at most $m$ inputs is $m^2$, $2^m$, and something similar to what I came up with. I understand that which gates to use is vague, but these are fundamentally different functions, and I'm very confused.


texts: How to translate boolean expressions to three address code?

texts:
There are two uses of a boolean expression in a language like C, one as a condition in flow of control statements and the other as boolean value in assignment and arithmetic expressions.

I was studying the translation of boolean expressions into three address code from the Dragon Book.

Now, I came across the following text and I seriously just don’t understand what the authors are trying to convey here. Could somebody please clarify for me?

  A clean way of handling both roles of boolean expressions is to first build a syntax tree for expressions, using either of the following approaches:

  Use two passes. Construct a complete syntax tree for the input, and then walk the tree in depth-first order, computing the translations specified by the semantic rules.
  Use one pass for statements, but two passes for expressions. With this approach, we would translate $E$ in while ($E$) $S_{1}$ before $S_{1}$ is examined. The translation of $E$, however, would be done by building its syntax tree and then walking the tree.


texts:
When implementing a dictionary ('I want to look up customer data by their customer IDs'), the typical data structures used are hash tables and binary search trees. I know for instance that the C++ STL library implements dictionaries (they call them maps) using (balanced) binary search trees, and the .NET framework uses hash tables under the hood.

  What are the advantages and disadvantages of these data structures? Is there some other option that is reasonable in certain situations?

Note that I'm not particularly interested in cases where the keys have a strong underlying structure, say, they are all integers between 1 and n or something.


texts: Kolmogorov complexity of a product of two numbers

texts:
In his book "Theoretical Computer Science", Juraj Hromkovic informally defines the Kolmogorov complexity $K(x)$ of a word $x$ consisting of zeros and ones as the binary length of the shortest Pascal program that generates $x$.  The Kolmogorov complexity $K(n)$ of a natural number $n$ is then defined as the Kolmogorov complexity of the binary representation of $n$.

To show that there's a constant $d$ such that $K(x)\leq|x|+d$ for all words $x$ (where $|x|$ is the length of $x$), he uses the following (pseudo) program $A_x$ to generate $x$:

begin
  write(x);
end

But he notes (in the 2007 German edition of the book, but not in the 2004 English edition) that we would have to prefix the code with two numbers $k$ and $l$ with $k$ being the length of the (constant) "prefix" of the program (up to and including the opening parenthesis) and $l$ being the length of the "suffix" (starting with the closing parenthesis).  The reason for this is that we can thus store $x$ verbatim (as a sequence of ones and zeros) while the constant part of the program is the same for each $x$ (and responsible for the constant $d$ above).

So far, so good.  I can understand how this is supposed to work, but because he tries to avoid encoding the length of $x$ into the program (as he writes himself) we obviously have to know where the program ends to make sense of $l$.  (One could for example image that one receives $A_x$ as a file.)

But two pages later there's an exercise where he claims that for a positive natural number $n=pq$ we have $K(n)\leq K(p)+K(q)+c$ with a constant $c$ independent of $n$, $p$, and $q$.  I think the basic idea here is that $c$ is the length of a program that executes the corresponding programs for the two factors and multiplies them.  But if the programs for $p$ and $q$ are programs like above we would need to know how long they are - which we don't.  I can easily see how to prove $K(n)\leq 2\max(K(p),K(q))+c$ or $K(n)\leq K(p)+\log_2(K(p))+K(q)+c$ or something similar, but I'm at loss regarding $K(n)\leq K(p)+K(q)+c$.  Any ideas?


texts: How to prove that the dual of the dual of a connected planar graph $G$ is isomorphic to $G$?

texts:
I find in many references the fact that if $G$ is a connected planar graph, then for any embedding, $G^{**} \cong G$. However, all those references either say that this fact is trivial, or give the proof as an exercice.
I am ok that this is clear on a small graph, with a nice embedding, but how can we prove this property rigorously?


texts: Can the test set of attributes be a subset of the training set's attributes?

texts:
I'm currently writing an application for a trick-based card game, where agents are assigned points based on the accuracy of their predictions of how many hands they're going to win. The number of tricks predicted will display a level of confidence to the other agents as well as also potentially allowing the agent to choose the Trump suit.

I've compiled a set of attributes (such as cards in hand, score sum total in hand) that will be useful in the prediction, but it would be ideal if I could include previous predictions in the training set.

My question is can my test data [attributes] be a subset of the training data [attributes ∩ predictions] both of which are predicting the number of hands that the agent will win?


texts: Formal definition of loss surface of multi-layered networks

texts:
Let $\mathcal{L}$ be a loss function associated with a multi-layered neural network.  So it seems almost everyone in AI/ML community is interested in  the Hessian $H=\partial^2 \mathcal{L}$ of $\mathcal{L}$. So if you read [1] on page 193 the left colum you find the following text

"An important question concerns the distribution of critical points (maxima, minima, and saddle points) of such functions. Results from random matrix the- ory applied to spherical spin glasses have shown that these functions have a combinatorially large number of saddle points. Loss surfaces for large neural nets have many local minima that are essentially equivalent from the point of view of the test error, and these minima tend to be highly degenerate, with many eigenvalues of the Hessian near zero.
"
Could anyone in the community shed some light on how formally the authors define (perhaps assuming some accepted definition in the community) the loss surface associated with either neural network or the loss function of the neural network?

My guess is that it is the level set of the loss function attaining one of its critical values (of the loss function). I would appreciate if someone would share any knowledge on the nature of the formal definition of the loss surface or any accepted common knowledge definition.
Many thanks.

[1] A. Choromanska, M. Henaff, M. Mathieu, G. B. Arous, and Y. LeCun. The loss surfaces of multilayer networks. In Artificial Intelligence and Statistics, pages 192–204, 2015.


texts: How to verify the solution to n queens problem

texts:
I have made an algorithm by which I recently finished counting solutions to 28 queens problem and I have the number. How do I verify that it is correct?

I have heard that it can be done in quadratic time. That is, given a solution to an nqueen problem it can be verified in polynomial time. I would like to know the algorithm too.

Thanks


texts: Every decidable language $L$ has an infinite decidable subset $S \subset L$ such that $L \setminus S$ is infinite

texts:
Given an infinite decidable language $L$, then if $S \subset L$ such that $L \setminus S$ is finite, then $S$ must be decidable. This is true since given a decider of $L$ we contruct a decider for $S$:
Simulate the decider of $L$ on the input, if it accepts, go over $L \setminus S$ and check if it is there, if it is, reject. If it isn't accept. If the decider of $L$ rejects - reject.
Another point is if $S \subset L$ is finite then $S$ also must be decidable, this is immediate that every finite language is decidable.
Now we have the last case where $S$ is infinite and $L \setminus S$ is infinite. We know that there must be some subsets $S$ corresponding to this case that are undecidable. This is since there are $\aleph$ such $S$ but only $\aleph_0$ deciders. Denote $D(L) = \{ S \subset L : |S|= |L \setminus S|=\infty \wedge S \text{ is decidable} \}$
Is it true that for all infinite decidable languages $L$ we have $D(L) \neq \phi$?
If this is true then as a conclusion we will have for all infinite decidable languages $L$ a sequence of decidable languages $L_n$ such that $L_0=L$ and $L_{n+1} \subset L_n$ and $|L_n \setminus L_{n+1}| = \infty$
We will also have a limit-set $L_\infty = \{ e \in L : \forall n \in \mathbb{N} \text{ } e \in L_n  \}$ and can dicuss if it is empty/finite/infinite and decicable or not.
This seems like a nice way to study decidable languages, and curious to know if this direction is indeed interesting and whether there are articles published regarding these questions
Thanks for any help


texts: counting binary, with moving position (turing machine)

texts:
I'm trying to make a turing machine that will take in a binary string as input x and output the binary representation of the length of x. So M(0110) returns 100, M(1010101010) returns 1010, ect. It also has to have a runtime of O(N).

So I can prove that the number of "flips" (changing a 0 to a 1 or a 1 to a 0) that occur when counting from 1 to n in base 2 approaches 2n as n goes to infinity. meaning it's O(n) in terms of runtime, but i'm not sure how to factor in the movement of the head of the tape that is writing the binary. Near as I can tell, the head may have to move at most log(n) place to go from the 1s place to the last power of 2s place. For example, going from 11111 to 000001 requires moving from the 1s to the 64s place, or 6 places. It then has to move back to the ones to create the binary representation for 65.

How is this operation as a not O(nlogn)?


texts:
So, I have a list of cities (A, B, C, etc) with weighted edges (two-way, undirected) between them with a list of cities that already have a store.

My task is to place a one new store at either A, B, C, etc so that I minimize the travel distance from any city to a store.

So my head is thinking

Perform Dijkstra's on every non-city vertex
Find the max distance among that node -> all other nodes.
Store that distance associated with the store it originated from.

The problem I encountered was

The easiest example of A, B, and C cities with a store already existing at A, has roads of
AB = 1, BC = 2.

Placing a store at B, would make C have to travel 2 units to the nearest store (at B).
While placing a store at C, would make B have to travel 1 unit (since it can backtrack to A where a store is at).

This "backtracking" to other nodes is causing my mix-ups. Since I'm only iterating from the point of view of either City B or C. B's point of view thinks the max distance to a store is 2, while C does as well. (Even though C should find the max value of 1 unit).


texts: Solving the Knapsack problem in $O(v^*n^2)$, where $v^*$ is the maximum value of all $n$ items

texts:
For my study I am supposed to develop an dynamic programming algorithm which solves the following simplification of the Knapsack problem in $O(v^*n^2)$ time ($v^*$ is the maximum value of all elements):

Let there be given $n$ elements $1,...,n$, a maximum weight $W$ as well as a weight & value function:
$w: \{1,...,n\}\to \mathbb{N}$
$v: \{1,...,n\}\to \mathbb{N}$
We then define $v^* = \max(v(1),...,v(n))$

The goal is to find a subset $M\subseteq \{1,...,n\}$ so that $\sum_{x\in M} w(x)\le W$ and so that $\sum_{x\in M} v(x)$ is maximal.
(I.e. we want to pack the subset of items that have the highest summed up value while not using up more weight than $W$)

I've been trying for quite some time, but I can't seem to come up with any idea or reduction rule that makes use of $v^*$.

Since this is a homework assignment, I'm looking for hints, not answers.

To be precise: The regular dynamic programming algorithm that solves the regular Knapsack problem can be used on this simplification as well (it might even be that the version given here is the standard version. The sources I've looked through so far don't say whether $w,v$ map to $\mathbb{R}$ or $\mathbb{N}$),
and find the optimal solution in $O(n\cdot W)$ time (see e.g. Wikipedia).

The algorithm variant I'm looking for however is independent of $W$, and instead uses the maximum value $v^*$ of any of the items.


texts: Minimum number of swaps to make two arrays strictly increasing

texts:
I'm trying to understand the solution of the following problem (LC 801):

Given two arrays, A and B, of the same nonzero length, find the minimum number of swaps (A[i] <--> B[i]) to make A and B strictly increasing.
The solution is guaranteed to exist for the given input data.
Example:
Input: A = [1, 2, 9, 4, 5, 6], B = [7, 8, 3, 10, 12, 13]
Output: 1 (swap 9 and 3)

The solutions posted by others consider a dp array, of size [2, A.size()], which is filled as follows:
int N = static_cast<int>(A.size());
std::vector<std::vector<int>> dp(2, std::vector<int>(N, N));

for (int ii = 1; ii < N; ++ii) {
  if (A[ii - 1] > A[ii] && B[ii - 1] > B[ii]) {
    dp[0][ii] = std::min(dp[0][ii], dp[0][ii - 1]);
    dp[1][ii] = std::min(dp[1][ii], dp[1][ii - 1] + 1);
  }
  if (A[ii] > B[ii - 1] && B[ii] > A[ii - 1]) {
    dp[0][ii] = std::min(dp[0][ii], dp[1][ii - 1]);
    dp[1][ii] = std::min(dp[1][ii], dp[0][ii - 1] + 1);
  }
}

return std::min(dp[0][N - 1], dp[1][N - 1]);

How to think / develop the idea for the solution?
It is clear that in the case the monotony is broken, i.e. A[ii] <= A[ii - 1] we need to swap, but, from trying a few test cases, this is not the optimal way to do the swaps.


texts: What are the reasons to learn different algorithms / data structures serving the same purpose?

texts:
I have been wondering about this question since I was an undergraduate student.
It is a general question but I will elaborate with examples below.

I have seen a lot of algorithms - for example, for maximum flow problems, I know around 3 algorithms which can solve the problem: Ford-Fulkerson, Edmonds-Karp & Dinic, with Dinic having the best complexity.

For data structures - for example, heaps - there are binary heaps, binomial heaps & Fibonacci heaps, with Fibonacci heap having the best overall complexity.

What keeps me confusing is: are there any reasons why we need to know them all? Why not just learn and get familiar with the best complexity one?

I know it is the best if we know them all, I just want to know are there any "more valid" reasons, like some problems / algorithms can only be solved by using A but not B, etc.


texts: Using MyHill Nerode theorem to prove a language is non-regular

texts:
The language is $S = (a^nb^m | n \geq m)$.

I'm having trouble understanding MyHill Nerode theorem. Basically if I want to use MyHill Nerode theorem to prove $S$ is non-regular, I have to show that there are infinitely many equivalence classes. So in this case if I choose $S = a^n$ is simply not working since $n \geq m$ and thus $a^mb^m \in S$. So I think I have to pick $S = b^m$ and $a^nb^m \in S$ but $a^nb^n \notin S$. Does my assumption accurate or any suggestion?


texts: What can we have in exchange if we drop subtyping from definition of Calculus of Inductive Constructions?

texts:
If we remove subtyping (https://coq.inria.fr/distrib/current/refman/language/cic.html#subtyping-rules) from CIC we will lose some expressive power. But is that power necessary for a programming language?

If we demand programmer to write e.g. Type(1) and Type(2) to mean respectively type and kind, that won't be anything novel in software engineering.

Can we get something in exchange? For example relaxed requirement on strict positivity of inductive types (without creating inconsistency in the language)?

We should get at least simpler term equivalence check where problem of η-reduction (https://coq.inria.fr/distrib/current/refman/language/cic.html#expansion) doesn't exist.

Is there some research on this topic? How does it compare to e.g. inductive types from NuPrl (https://ecommons.cornell.edu/handle/1813/6710)?


texts:
The only paper I can find about an implementation of a lossless video codec is an article by Michael Niedermayer which explains the FF1V compression pipeline.

I'm wondering if anyone else has found any articles similar to this. I've looked on IEEE and ACM and their articles mostly focus on one algorithm that's part of a compression pipeline.


texts:
There is a long row of cells. Each cell contains 0 or 1. A machine is positioned immediately to the right of a series of uninterrupted 1’s followed by an uninterrupted series of 0’s. In the following graphic the machine is denoted by a yellow line. It is immediately to the right of a series of three 1’s followed by many 0’s.

The machine is tasked to make a copy of the 1’s. When finished, the copy must be separated from the original by a single cell containing a 0. The final resting place for the machine is immediately to the right of the original 1’s. The following graphic shows the cells after the machine has fulfilled its copy task.

At each step the machine must decide whether to move left one cell or right one cell, and whether to write 0 or 1 to the cell that it is currently positioned at. The machine cannot see what is in the neighboring cells. It can only see the value in the current cell. The machine makes its decision based purely in the current cell’s value and on the decisions it made previously.

I was able to program the machine to perform the copy operation using nine states (S0 – S8).

QUESTION: Is there a way for the machine to perform the copy operation in less than nine states?

The above graphics show just one example, in which three 1’s are copied. Of course, the machine must be able to perform the copy operation on any number of 1’s.

The diagram below shows the nine states that I needed. But first, here is an explanation of a notation used in the diagram:

Here is the strategy I used: As described above, the 1’s must be copied. How to know which 1’s have been copied and which remain to be copied? Answer: Shift the leftmost 1 to the left one cell and then copy it. Repeat for the next leftmost 1. And so on. There will be a series of shifted 1’s that have been copied and a series of unshifted 1’s that remain to be shifted and copied. Once there are no more unshifted 1’s, the machine is done. State 0 is the final state. State 1 is the starting state.


texts: Finding recurrence when Master Theorem fails

texts:
Following method is explained by my senior. I want to know whether I can use it in all cases or not. When I solve it manually, I come to same answer.

$T(n)= 4T(n/2) + \frac{n^2}{\lg n}$

In above recurrence master theorem fails. But he gave me this solution, when

for $T(n) = aT(n/b) + \Theta(n^d \lg^kn)$

if $d = \log_b a$

if $k\geq0$ then $T(n)=\Theta(n^d \lg^{k+1})$

if $k=-1$ then $T(n)=\Theta(n^d\lg\lg n)$

if $k<-1$ then $T(n)=\Theta(n^{\log_ba})$

using above formulae, the recurrence is solved to $\Theta(n^2\lg\lg n)$. When I solved manually, I come up with same answer. If it is some standard method, what it is called ?


texts: Fast algorithm for finding the size of each connected component in a graph of 2D points

texts:
I've been thinking about this for a while now. Given a graph $G$ of 2-dimensional points (we draw the edges based on a "threshold" distance), find $s_1, s_2, \dots, s_k$, the sizes of all connected components in $G$.
The vertices of the graph are 2-dimensional points and there is an edge between $v_1$ and $v_2$ if the Euclidian distance between them is less than a given distance $t$ (the threshold above), otherwise there is no edge between $v_1$ and $v_2$.
Up until now, I've tried DFS methods and also attempted to use a QuadTree to group together "close enough" points.
For the attempt at QTs, I subdivide the plane into cells the diameter of which is sufficiently small to guarantee connectedness, then traverse the tree upwards to find all the neighboring cells and check if they make more connected points.
What I'm asking for is a more efficient algorithm (mainly on the time complexity front) (can be completely different or an improvement on the above, I'm open to anything). For context, the size of the samples I'm dealing with is ~100K.
PS: I do realize there are various other answers dealing with how to determine the connected components of a generic graph, but I believe that in this case (2D points and the need to "only" find their sizes) could benefit from more efficient methods. I could be wrong but there is no better way to find out.


texts: Can a computational complexity class be redefined by using any complete (decision) problem?

texts:
Let $\mathcal{C}$ be a basic complexity class (such as $\mathrm{NP}, \mathrm{PSPACE}$).
And $\mathcal{C}$ is closed under a reduction "$\leq$" (such as polynomial time many-one reduction "$\leq_{m}^{p}$", polynomial time Turing reduction "$\leq_{T}^{p}$").
Suppose that a decision problem $L \subseteq \Sigma^{*}$ is complete for $\mathcal{C}$ under reduction "$\leq$".
Let $[L]^{\leq}$ denote the closure of $L$ under reduction "$\leq$", which means that $[L]^{\leq}$ is a class consists all the languages that can be reduced to $L$.
$$[L]^{\leq} = \{ L' \in \Sigma^{*}| L' \leq L \}$$
Does $\mathcal{C} = [L]^{\leq}$ hold true?
Here is my proof.
Firstly, $L \in \mathcal{C}$, thus for every $L' \in [L]^{\leq}$, we have $L' \in \mathcal{C}$ which leads that $[L]^{\leq} \subseteq \mathcal{C}$.
In the other hand, since $L$ is complete, for every $L' \in \mathcal{C}$, $L' \leq L$. We conclude that $L' \in [L]^{\leq}$ which means that $\mathcal{C} \subseteq [L]^{\leq}$.
Now, I have proved that $\mathcal{C} = [L]^{\leq}$.
If this is correct, I can say that
$$[\text{SAT}]^{\leq_{m}^{p}} = [\text{3-SAT}]^{\leq_{m}^{p}} = \mathrm{NP}$$
Am I right?


texts: Understanding the definition of endless sets

texts:
In a course on theoretical computer science we have to prove if sets are endless. I have two problems with the exercise:

I don't understand exactly, what an endless set is (I find it very hard to understand, maybe because of the "endless")
I don't know, how I can prove that the given sets are endless

The definition given is this:

  A set $X$ is called endless set, if there is a endless family of sets $\{X_n\}_{n=0}^{\infty}$ with
  $... \in X_3 \in X_2 \in X_1 \in X_0 \in X$.

Can someone explain in simple words what an endless set is?


texts: Is the following Subset Sum variant NP-complete?

texts:
Is the following problem NP-hard:

Input: $A\subset\mathbb Z, k\in\mathbb N$
Question: is there a multiset of indices $I$, such that $|I|=k$ and $\sum_{i\in I} a_i=0$?

For example, on the input $A=\{-1,2\}, k=3$ we can take $I=\{1,1,2\}$ and thus we get $|I|=3$ and $a_1+a_1+a_2=(-1)+(-1)+2=0$, as desired.


texts: Eliminating ambiguity in $A \to AA \mid (A) \mid a$

texts:
I'm trying to solve this complier design problem related to ambiguity in CFG the given grammar is
\begin{align}
&A → AA \\
&A → (A) \\
&A → a
\end{align}
I was able to find that this given grammar is ambiguous but I don't know how to remove the ambiguity. How can I remove the ambiguity from the given production rules to get new productions without ambiguity?


texts: Algorithm Design: Efficient O(n) algorithm to get the ith to jth largest elements in an array

texts:
I am trying to design an efficient algorithm that retrieves the ith to jth largest elements in an array. For example, if the following array is the input:

[10, 14, 18, 3, 21, 25, 27]
i = 2
j = 4

The following array is returned:

[25, 21, 18]

18 is the 4th largest element in the array and 25 is the 2nd smallest element in an array. I've done a problem where you retrieve a list of the K largest elements in an array: in such a problem, the solution is pretty trivial (using a fixed-size minimum heap of size K to keep track of the K largest elements). In this case however, a heap seems out of reach to use because the minimum heap can only remove the smallest element from the heap (removing the kth smallest element within the heap seems really inefficient).

I could do QuickSelect (j - i) times to get all the elements, but that means doing a linear O(n) walkthrough (j - i) times, which yields a total time complexity of O((j-i) * n), but I was thinking about if it's possible to quicken the algorithm's time complexity to just O(n). Is there an O(n) algorithm to solve this problem?


texts: Does anyone know when the list data structure was mentioned in computer programming/algorithms? Who gave birth to this list concept?


texts:
I need your help with time complexity.

I have this recursive function:
$$
F(n) = \left\{
\begin{array}{l l}
F(n-2) + 10 F\big(\frac{n}{6}\big)^2 + 6 F\big(\frac{n}{7}\big) + \frac{n^4}{5} & \text{if } n > 1\\
2 & \text{otherwise}\\
\end{array} \right.
$$

and I had to do the same thing using recursion in C#, so I came up with this :

 public static int F1(int n)
{
    if (n > 1) return F1(n - 2) + 10 * F1((int)Math.Pow((n/6),2)) + 6 * F1(n / 7) + ((int)Math.Pow(n,4) / 5);
    else return 2;
}

I need help calculating the time complexity of this algorithm, and I don't even know where to start and how to do it, could you please give me a hand?

Thank you for any kind of help.


texts: Revisiting Fixed Point: What does it mean in the world of computer science?

texts:
A while ago I asked Fixed point, what does it mean in the world of computer science?

While the answers did help me to understand what Fixed point meant, the answers left me in a murky world when ever I thought about what a fixed point meant. In other words, no clear definition poped into my mind and I would wonder about in thought trying to match up a definition with what I was trying to learn or understand.

Today I was watching the video Categories for the Working Programmer by Jeremy Gibbons in which he stated: (Time index: 33:00)

  It's fix point because it's the solution of a recursive equation.

And I thought that makes sense; is it really that simple?

So the question is:

Can the definition of fix point be thought of simply as

  "It's the solution of a recursive equation."


texts:
I am a starting Ph.D. student in computer science, and I am trying to understand some classic game-theory papers, such as those by Nash, Kalai and Smorodinsky.   But I find it hard to understand the mathematical parts. It seems that these papers were written by mathematicians, for mathematicians.

Can you recommend a book that explains the mathematical preliminaries of game theory, to people without extensive mathematical background?


texts: Can file snapshots aid in detecting malware?

texts: I noticed certain programs have a feature that can have a 'snapshot' of a file from a certaim time and compare it to a more recent snapshot of the file. If one's system has a snapshot of a program when 'first' downloaded and  it can compare  this to the program 'as it is now' and if there are any changes this might indicate the file is corrupt and it could be marked for possible removal. So could this comparison feature be used to determine if a file is corrupt?


texts:
I'm reading an OS textbook and it was talking about TLB misses being handled by software. I'm very new to all this by the way. So there's a context switch to some kernel procedure. But surely in this case the TLB is not flushed, and the kernel code doesn't itself use the TLB, since that would defeat the purpose? But then how exactly does it work? I don't know why the text wouldn't address such a seemingly obvious question.

Plus you're still using virtual memory, right? So you would be doing two context switches, a bunch of page table lookups in memory, in addition to the actual kernel instructions, per missing TLB entry. It just seems counterintuitive to do all that work to make use of something that's supposed to save you work. Sorry if I'm getting something completely wrong here. Thank you in advance.


texts: Assigning a formula to an approximate value

texts:
Let's say I have a software that calculates integrals, formally if possible and if not, then it computes an approximation by taking a small $dt$. Of course if the integral is an unknown number, I wouldn't be interested in giving it a name. But if I calculate $\int_0^e\left(\frac{\pi}e+1\right)dt$, I'd like to get $\pi+e$ instead of $5.85987\dots$. Now of course any decent program would be able to calculate that integral that way. But if I made it a bit trickier, I'm quite sure most wouldn't. For example $\int_0^e\ln\left|\exp\left(\left(\frac{\pi}e+1\right)+\sqrt{2}i\right)\right|dt$. Maybe some programs would. But at some point, they would all fail. And when I reach that point where I can't compute it formally, I want to be able to say "Hey, it's not far from $\pi+e$".

How do I find an expression using (a small set of well-known) constants (for example $\{1,e,\pi\}$), $+$, ,$-$,$\times$ $/$ using as few characters* as possible which value is at a distance of at most $\varepsilon >0$ of my approximate value?

Obviously I could compute all the trees until I hit it or got more than $M$ elements (the maximum length of a formula that I could find interesting). M wouldn't be that big so it would be feasible. But isn't there a bright way of doing this?

Because my current vision of how this could be done, I think all algorithm better than the naive brute-force one are

Things I've though of:

Use inequalities. For example, if there is a sum at the root, order all the operands in the order: unknown sign, negative, positive so that once you're done with negatives and start the positive, if you get over the value you want, you know you're not getting anywhere. And things like that.
Keep a "do not try" subset of the variables. And pass it as an argument to the recursive function trying the trees. For example in $\pi + e - \cdot$, both $\pi$ and $e$ would be in the "do not try" subset since if they helped find a formula, then there would be a shorted one with the same value. But for that thing to be efficient, I'd probably need to remove $1$ from the constants and add an operation $n\times \cdot$ for all $n \in \Bbb Z$ but that brings a new problem: You have infinitely many operators and therefore infinitely many trees of a fixed size... And I'm pretty sure that unless I implement everything from structures to the actual algorithm with that specific goal in mind, it'll actually slow things down...

I'd be fine with any kind of deterministic algorithm even though I couldn't think of anything aside from the naive one plus removing some trees that could work.

* It's the only way I found to measure the relevance of a formula. But if you've got another one, I'd like to hear it :)


texts: Pick a random number in a pool with duplicates in O(1) time and less than O(n) space?

texts:
Imagine trying to pick a random number from a pool of numbers that contains:

i1 times the number 1
i2 times the number 2
i3 times the number 3
... etc

For example picking a random number in a pool of
30 times the number 1
90 times the number 2
would yield 1 with 25% probability and 2 with 75% probability.

let NU be the number of unique numbers
let NT be the total number of numbers
In our example NU=2, NT=120.

Is there a way to achieve this in O(1) time and less than O(NT) space?

Edit: corrected probabilities in example.


texts: Different iterations of regular expressions

texts:
A four-part question dealing with formal languages and regular expressions:

How many basic regular expressions (using only the rules 0/ϵ, 1/∅, *, +, and •) are there to match a given string?
How many using just *, +, and •?
How many using just + and •?
How many using just •?