Find k maximum numbers from a heap of size n in O(klog(k)) time I have a binary heap with $n$ elements.  I want to get the $k$ largest elements in this heap, in $O(k \log k)$ time.  How do I do it?

(Calling deletemax $k$ times yields a $O(k \log n)$ complexity.  I'm looking for $O(k \log k)$.)

The only solution I've come up with so far is the following:

You have 2 arrays. A(largest numbers), B(to analyze).

It's easy to find the largest number, since we already have the heap. We move the maximum number to $A$.
We move the maximum number's children to $B$
We sort $B$
We add the children of the largest number in $B$
Remove the largest number from B (first element of $B$), add it to $A$
Repeat the procedure until there are $k$ elements in $A$

The question here is: do we get a $O(k \log k)$ complexity? we obviously repeat the procedure $k$ times, but does the sorting take $O(\log k)$ time? I guess if the array is already sorted it's easy to insert a new number in $O(\log k)$ time. However, will the length of array B always be less than or equal to $k$?

Can you please confirm or deny my solution? If it's wrong, can you please help me find a solution to this problem?

Hint: Each time you perform one iteration of your loop, how much does the size of $B$ increase?  Each time you perform one iteration of your loop, how many numbers are added to $A$?

You terminate once $k$ integers have been added to $A$... so how many times will the loop iterate?  What does this tell you about how large $B$ can get?  What does that say about the running time of your algorithm?

(I am giving only a hint, so you can have the pleasure of working out the answer on your own.)


Select optimal subintervals from array I have an input array and I have to select an indefinite number of intervals from it so that the "profit" is maximal and I have exactly T elements selected in total, where T is given. Profit means the sum of all the elements of an interval, except for the first element. An interval can consist of a single element, meaning that the profit for such an interval is 0. The array may contain negative numbers. Apparently dynamic programming is the answer to this problem, but I cannot think of an efficient algorithm to solve it. This is homework, so I would appreciate any help.

Search for maximum subsequence sum problem, here you will find a linear time solution. Bentley's "Programming Pearls" gives several alternative algorithms and some history. The linear time solution is obvious in hindsight, but it took several tries by experts to come up with it...


Why add a +1 to the constant proving an O(n) bound? I have calculated a running-time function $T(n) = 4 + 4n$, which is $O(n)$.

To determine the constant $C$ given by the relation $|T(n)| < C \cdot g(n)$,
we take

$\qquad\displaystyle \lim_{n \to \infty} T(n)/g(n)$

which gives us

$\qquad\displaystyle \lim_{n \to \infty} (4+4n)/n = 4$.

However, in the answer sheet it say to take

$\qquad\displaystyle \lim_{n \to \infty}(4+4n)/n + 1 = 5$.

What is the purpose/reasoning for this $+ 1$ term, I haven't seen anything about before?

We want to find a $c$ such that $4+4n\le cn$ for all $n$ greater than or equal to some bound $N$. So we need a $c$ such that $(4+4n)/n \le c$, or $(4/n)+4\le c$. Now while it's true that
$$
\lim_{n\rightarrow\infty}\frac{4}{n}+4=4
$$
we can't use $c=4$ since for all positive $n$ we have $(4/n)+4>4$. In other words, we need to pick $c$ to be some number larger than 4 and 5 is as good a choice as any in this case. There's nothing magical about picking a $c$ one greater than the limit; it's just one choice out of infinitely many.


Complexity of testing membership in a disjoint set I have a disjoint set data structure (sometimes known as a union-find data structure) where I store a value in each "node".  I want to look up a node by value.  How can I do this?

The representations normally discussed in literature, both linked list and forests, deal with operations being given nodes (of the linked list or forest), not values contained therein, which avoids any difficulty caused by having to find the node that contains a given value. From what I can see, the question of whether a given disjoint set contains in any subset a given value, or finding the node that contains a given value if one exists, is scarcely touched by the literature.

However, given values, this question needs to be addressed for an implementation of what the CLRS Introduction to Algorithms calls Make-Set(x) if one wishes to not trust the user of the API to always know what is and is not in the set, as it has a prerequisite that x does not already exist in the set.

With both representations, I see no way better than $O(n)$ to check membership, as one must always check all nodes for equality. Obviously one could maintain a separate mapping of values to nodes for the set, with $O(log n)$ lookup given an ordered value type, but this means duplicating the whole set in memory. Is there any way to represent a disjoint set while being able to test set membership in less than $O(n)$ time without duplicating the data?

There's an easy way to find the node that contains a given value.  You have two data structures: a union-find data structure (that keeps track of which nodes are in the same equivalence class), and a hashtable (that maps from a value to the node(s) that contain that value).

The MakeSet operation adds a new set to the union-find data structure and adds a new entry to the hashtable.  The Union operation and Find operations use only the union-find data structure.  The "look up a node by value" operation uses the hashtable.

The running time of the MakeSet, Union, and Find operations is as in the underlying union-find data structure.  (MakeSet incurs an extra $O(1)$ (expected, amortized) time to insert into the hashtable, but this doesn't change the overall running time of MakeSet.)   The running time of looking up a node by value is $O(1)$ (expected, amortized) time, if you have a good hash function and if each value is only found in a single node.

This doesn't require duplicating the data, if you use pointers in lieu of duplicating: each entry in the hashtable can have a pointer to the node, and each node has a pointer to the value, so values and nodes aren't duplicated.  Of course, this does increase the memory usage (by at most a constant factor); nothing is free in life.


Amortize time for a counter with the operations INCREMENT and DECREMENT Let a binary counter with the operations INCREMENT and DECREMENT.

I need to show that you can't implement this kind of counter with constant amortized time per operation.

Hence, I need to show that there's a series of $N$ operations with amortized time of $\omega(N)$.

My Try:
Let's assume we made $2^k-1$ INCREMENT operations. Hence, our counter is a sequence with $k$ 1's. Now, Let's consider a sequence of $N$ operations alternating between DECREMENT and INCREMENT (DEC,INC,DEC,INC,DEC...)

Each operation must be $\Theta(k)$. Somehow, I need to figure out that it has to be that the amortize time is $\omega(N)$. How?

Your solution is on track. As you comment, if you increment a counter $2^k-1$ times and then do $m$ increment/decrement operations, in total you must have modified at least $km$ array positions (this will serve as our lower bound on the running time). In your case $N = 2^k-1 + m$. If you choose, for example, $m = 2^k+1$, then $N = 2^{k+1}$ while the lower bound is $km \geq \log_2 N \cdot (N/2) = \Omega(N\log N)$. This shows that the amortized running time is $\Omega(\log N)$, which is certainly superconstant.

We can easily get a matching (non-amortized) upper bound. If we only perform $N$ operations, then the value of the counter is in the range $[-N,N]$, and so takes $O(\log N)$ bits to represent. It is not difficult to implement increment and decrement so that they take time linear in the length of the representation, so $O(\log N)$ in this case.


Converting a digital circuit to two layers of OR and AND gates The other day someone mentioned to me that you could take an arbitrary digital circuit which mapped N input bits to M output bits, and replace it with a layer of OR gates and a layer of AND gates.  I believe he said there would be 2^N ANDs and ORs each.  I haven't been able to find any more information about this though.

Is this true?

And are there similar techniques for say using only XOR and AND gates?

Yes, it's true.  You can use  conjunctive normal form to express the circuit in two layers, where the first layer has OR gates and the second layer consists of $m$ (multi-input) AND gates.  However, there's a catch: you have to have a way to complement (negate) some of the inputs to the OR gates for free.  If you want to count the OR gates as a separate layer, then it takes three layers; if you imagine that your OR gates actually allow you to complement any subset of their inputs (e.g., the gate can compute $x \lor y$, $x \lor \neg y$, $\neg x \lor y$, or $\neg x \lor \neg y$), then it's just two layers.

Or, you can use disjunctive normal form to build a two-layer circuit where the first layer uses AND gates and the second layer contains $m$ (multi-input) OR gates.  Again, the same catch applies: you need to be able to complement the inputs to the AND gates "for free".

You can use disjunctive normal form to build a circuit where at most one input to any OR gate will ever be true at a time.  This means that you can replace the OR gate with an XOR gate without changing its functionality.  Therefore, yes, you can built a two-layer digital circuit where the first layer has only AND gates and the second layer has only XOR gates -- assuming you can complement some of the inputs to the AND gates for free.

For "XOR-of-ANDs", you can actually write any N-to-1-bit circuit as an XOR of ANDs, without any complementation at the input, if you allow the final XOR to optionally include an additional input that's held at the constant 1 (or, equivalently, if you allow the final gate to be either a XOR or a NXOR).  In particular, given any boolean function $f:\{0,1\}^N \to \{0,1\}$, you can write it as a multivariate polynomial $f(x_1,\dots,x_N)$ modulo 2.  Now $x^2=x \pmod 2$, so since everything is modulo 2, that means that you can eliminate all powers of two or higher: every multivariate polynomial can be expressed in the form

$$f(x_1,\dots,x_N) = \sum_S c_S \prod_{i \in S} x_i \pmod 2,$$

for some constants $c_S$, where $S$ ranges over all subsets $S \subseteq \{1,\dots,N\}$.  (For example, we might have $f(x_1,x_2,x_3) = x_1 x_2 + x_2 x_3 + x_3 + 1 \pmod 2$ as an example of such a polynomial.)  Now note that product modulo 2 is AND, and sum modulo 2 is XOR, so we get a XOR-of-AND representation of any boolean circuit.

As your colleague mentioned, in the worst case these circuits might need approximately $2^N$ gates, so this can be highly inefficient in some cases.

I don't know if it is possible to write every circuit as an AND-of-XORs (with some complements or constants somewhere).


Does this argument prove CFLs are not closed under union? Context free languages are not closed under complementation. This follows from their property of non-closure under intersection:

If CFLs were closed under complementation, then they must have also been closed under intersection, which is not the case. Now as we know, CFLs are not closed under intersection and complementation, can’t we use the following arguments to say CFLs are not closed under union, too!

In RHS, we are performing two operations viz. intersection and complementation, none of which guarantees the closure of the given CFLs. So, how does result of these two operations claims to remain a CFL? Doesn’t this prove that the result is not necessarily a CFL?

Yet, it’s known that CFLs are closed under union. Where is the flaw in the argument? Where am I wrong?

Your first proof is valid. You are assuming by contradiction that CFLs are closed under complement and arriving at the absurd conclusion that they must be closed under intersection. Notice that this works for any intersection operation between two CFL languages.

Your second proof is wrong. You would need to assume that CFLs are closed under union and arrive at a contradiction. In your case your are not showing that, under the assumption, CFLs are closed under complement and intersection (hence the absurd). You are just showing that CFLs must be closed w.r.t. a particular operation in which you perform complements and intersections in some particular order.

Using the same logic I could prove the following erroneous claim.

Claim: CFLs are not closed under the identity operation $\textrm{Id}(L) = L$.

"Proof": CFLs are not closed under complement and, given a CFL $L$, $\textrm{Id}(L)$ can be written as $\textrm{Id}(L) = L = \overline{\overline{L}}$.


Hardness of a constrained quadratic maximization Consider the following quadratic maximization:
\begin{align}
\max_{\mathbf{x} \in \mathcal{X}} &\quad\mathbf{x}^{T}\mathbf{A}\mathbf{x}
\end{align}
with
\begin{align}
\mathcal{X} = \lbrace
\mathbf{x} \in \mathbb{R}^{n} :~ \|\mathbf{x}\|_{2}=1, \|\mathbf{x}\|_{0}\le k
\rbrace,
\end{align}
where $\mathbf{A}$ is a positive semidefinite matrix and $k \le n$ is a sparsity parameter.
This problem is NP-hard, by a reduction from the max-clique problem.

I am interested in a similar problem obtained by imposing additional structure on $\mathcal{X}$.
In particular, assume that the $n$ variables in $\mathbf{x}$ are partitioned into $k$ disjoint groups.
We restrict the feasible set to unit-length vectors $\mathbf{x}$ with one active variable per group.
That is, $\mathcal{X}$ contains again $k$-sparse vectors, but the support cannot be arbitrary; it contains (at most) one nonzero entry for each of the $k$ groups.

Note that the feasible set in the modified problem is a subset of the previous maximization, but the number of feasible supports can still be exponential in the number of variables $n$ (for appropriately chosen $k$).

I suspect that the modified problem is also NP-hard. Any ideas on how to show that (or disprove)? Feel free to share your intuition.

(I have found the answer to my question, so I am sharing a sketch here).

The quadratic maximization can be shown to be NP-hard by a reduction from the following problem:

Given $k$-partite graph $G=(V_{1}, \dots, V_{k}, E)$, does $G$ contain a $k$-clique.

Note that the latter problem is a (seemingly) special case of the max-clique problem restricted to a particular family of graphs. It can however be shown that it is also NP-complete by a reduction from the general max-clique problem itself (See here).

Let $\mathbf{A}$ denote the adjacency matrix of $G$.
Let $S$ be an arbitrary set of $k$ vertices and $\mathbf{A}_{S}$ denote the principal submatrix corresponding to $S$, i.e. $\mathbf{A}_{S}$ is the $k\times k$ adjacency of the graph induced by $S$.
If the vertices in $S$ form a $k$-clique in $G$, then all off-diagonal entries of $\mathbf{A}_{S}$ are equal to $1$, and its principal eigenvalue $\lambda_{1}(\mathbf{A}_{S}) = k-1$.
In any other case, that is, if $S$ is not a $k$-clique, then $\lambda_{1}(\mathbf{A}_{S}) < k-1$.
Finally, note that since $G$ is $k$-partite, a $k$-clique (if one exists) will contain a single vertex from each of the sets $V_{i}$, $i=1,\dots,k$.

Let $\mathbf{A}^{\prime} = \mathbf{A} + |\lambda_{n}(\mathbf{A})|\cdot\mathbf{I}$, where $\lambda_{n}(\mathbf{A})$ is the smallest eigenvalue of $\mathbf{A}$;
$\mathbf{A}^{\prime}$ is a PSD matrix.
Further, consider $k$ disjoint groups of variables corresponding to the sets $V_{1}, \dots, V_{k}$ of $G$.
We solve the quadratic maximization with input $\mathbf{A}^{\prime}$ and the specified groups of variables.
The maximum objective value will be equal to $k-1 + |\lambda_{n}(\mathbf{A})|$ if and only if $G$ contains a $k$-clique.


Show that NP∩coNP =∅ I know that P is a subset of NP, but I'm not sure what this tells me about P as it relates to coNP?
I feel like this is how I should go about proving it, but I'm not sure how. Otherwise, I could find a language that is in both NP and coNP, but I'm not sure how to prove any examples of that.

I know that I can prove L and L complement both exists in P and therefore NP, but I don't know how to relate this to coNP.

Read the definition of NP and co-NP. By that definition, every problem in P is automatically both in NP and co-NP. There’s nothing to prove, that’s how they are defined.


Decomposing a bipartite graph of maximal degree d to d matchings I have tried for the last few days to prove that any bipartite graph of maximal degree d may be broken into (at most) d matchings.

My main approach is to prove this inductively over the maximal degree d. This would require me to show that there must exist a matching which contains an edge for every one of the maximal degree nodes. (Such that the removal of this matching will leave me with a bipartite graph of maximal degree d, for which my inductive claim holds)

What I do know is to find a maximum matching (Via either some max-flow algorithm, or using the augmenting paths method, and arriving to the Gallai-Edmonds decomposition of the graph), but can't augment it to a maximum matching in which all maximal degree nodes are necessarily matched.

I was not able to prove it nor find a counter example for this subclaim, and would appreciate help. Thanks

Possible approach: If a bipartite graph is $d$-regular then it can be decomposed into $d$ perfect matchings by Hall's theorem. Any bipartite graph of maximal degree $d$ can be completed to a $d$-regular bipartite graph (possibly by adding vertices).


Is this language is Context-free language or not? Is anybody can help me please to determine is this language is Context-free language or not?

L={wvw | w,v∈{a,b,c}+}

for example:

part of the language: acbac, abcab, bbcbb

not part of the language: abab, aa, abcc

I tried to prove using pumping lemma for context-free languages like that:

I take this word from language w=aacbbaa.
I split the word to 5 parts uvxyz and if I can pump u and y and the word stays inside  language the language is context-free:

u-aa, v-cc, x-b, y=bb, z=aa
after I pump v and y the word is still in language->
u-aa, v-cccc, x-b, y=bbbb, z=aa ->
aaccccbbbbbaa

But the answer inside answers section is that the language is not context-free.

What wrong with my prof?

You can't use the pumping lemma to prove that a language is context-free (see, e.g., here).  The pumping lemma is only useful to prove that the language is not context-free.  See our reference questions for details on how to prove that a language is or isn't context-free: How to prove that a language is context-free?, How to prove that a language is not context-free?.

So, one thing wrong with your proof is where you say "if... the word stays inside language the language is context-free" -- that's not correct.


Why do we study closure properties of formal languages? In automata theory we study formal languages like Regular, CF, CS and etc. and each of them have their own closure properties under union, intersection, star and etc. . I like to know, why it is important to study such properties?

I think that the more fundamental question here is why study specific kinds of formal languages at all. One answer is that formal languages of specific kinds have been found useful in the construction of compilers. Another answer is that in the past they played an important part in artificial intelligence (nowadays statistical methods are more important).

Once we agree that regular languages and context-free languages are an interesting object of study, closure properties are basic mathematical properties of these objects. In fact, part of the beauty and appeal of the subject of regular languages is the large number of properties that they satisfy, including closure properties. Regular languages serve as a model for other families of languages, and one tries to mimic one's knowledge of regular languages on other families of languages.

Closure properties are also interesting beyond formal languages — Tychonoff's theorem in topology is one example.

Specific closure properties of regular languages have given rise to a new type of algebraic structure, Kleene algebras, which abstract some of the closure properties of regular languages and of context-free languages.


What is the fastest way to merge two B trees? Given two B-trees of some order $m$ -  $T_1,T_2$, such that $y > x$ for every pair $x \in T_1$ and $y \in T_2$.
What is the fastest way to create a new tree that is the union of both $T_1,T_2$?

My current solution is naive in a sense that I create an array and insert all $T_1$ elements, than all $T_2$ elements.
As a result I have a sorted array which I can create a new tree off of with a cost of $n \log n$

I'm thinking that there must be a better solution, something like the AVL merging question but I can't figure it out.

It is great that you have obtained a sorted array, which runs in $O(n)$ time.

Once we have $n$ elements in a sorted array, every kind of "nice" tree, that I know, can be built in $O(n)$.   In particular, we can build a $B$-tree in $O(n)$ time.

Here is an example. Suppose the sorted array is $$[1, 2, 3, 4, 5, 6, 7,8,9,10,11,12,13,14,15,16,17]$$ and we want to build a $2$-$4$ $B$-tree.  Split the array into groups of $2$ numbers, except that last group that could be $2$ or $3$ numbers.
$$\{1, 2\}, \{3, 4\}, \{5, 6\}, \{7,8\},\{9,10\}, \{11,12\}, \{13,14\}, \{15,16, 17\}.$$

Had the number of groups been an odd number, great. Otherwise, distribute the elements in the last group so that the number of groups becomes odd.

$$\{1, 2\}, \{3, 4\}, \{5, 6\}, \{7,8\},\{9,10\}, \{11,12, 13\}, \{14,15,16, 17\}.$$

Label the groups successively as $g_1, g_2, \cdots, g_7$. Let $g_1$ be the root of the tree. Let the left child of $g_i$ be $g_{2i}$ if $2i\le n$ and the right child of $g_i$ be $g_{2i+1}$ if $2i+1\le n$. Now we have a complete binary tree where

each node contains at least 2 number, and
each internal node has 2 children.

That means, it is a $2$-$4$ $B$-tree.

The example above should provide enough idea so that a full algorithm for general situations should not be too difficult to figure out.


Boolean Algebra: Operation Linkage Laws Im studying some properties of Boolean Algebra and found the Operation Linkage Laws.

Im not able to understand how this laws are possible, and the remark on the proof is not really clear for me. Can any one show me the proofs of this laws or share any resources where I can find a more detailed proof of the laws?

The proposition states that if any of the four statements holds, then the other three also holds. This gives in total 12 different theorems. For the proof, you can use truth tables or the axioms of Boolean algebra.

What the comment is trying to explain is that, say, $xy=x$ isn't universally true (consider $x=0,y=1$). However, if $xy=x$ then also $x+y=y$, and vice versa. This is in contrast to identities such as $x+x=x$, which always hold (for all values of $x$).


Is the capacity achieving input of a discrete memoryless channel unique? Consider a classical discrete memoryless channel (DMC). Let $p$ be an input probability distribution and $Q$ be the channel's transition matrix. $q = Qp$ is a valid output probability distribution. The components of $p$ and $q$ are given as $p_i$ and $q_i$ respectively.

The capacity of this channel is given by maximizing the mutual information.

$$I = \max_{p}\left[\sum_ip_i\left(\sum_{j}Q_{ij}\log(Q_{ij})\right) - \sum_{j}q_j\log q_j\right]$$

But, we know (Theorem 2.7.4 in Cover and Thomas, 2006) that $I(p)$ is concave in $p$.

If $I(p)$ is not simply a linear function (i.e. $q = Qp$ is not a trivial relationship) and is differentiable everywhere (seems like a reasonable assumption), does this not imply that the capacity achieving $p$ is unique?

I believe the answer is "yes", when $Q$ is square and nonsingular, and "not necessarily", otherwise. See "On the Capacity of a Discrete Channel. I", by Saburo Muroga, Journal of the Physical Society of Japan, Vol. 8, No. 4, July - August 1953, pp 484-494.

You might also be interested in my note on Muroga's paper, in which I attempt to provide an alternate proof of the feasibility of the optimal input probability distribution, in the special case of a binary channel, and to correct what I think is a trivial error in Muroga's paper (although this might simply have been Muroga being too polite to point out a trivial mistake by Shannon), and I also try to simplify a part of Muroga's argument:

"On the Computation of the Shannon Capacity of a Discrete Channel with Noise", S. Cowell, arXiv:1701.08731v2 [cs.IT] [here]1


What are the differences between symbolic execution and SAT solvers? My understanding is that symbolic execution only deals with specific paths and bad patterns, while SAT solvers, or satisfiability modulo theories in general, provide a much more robust analysis of the program.

Could someone validate the statement above and (briefly) explain the differences between these two formal verification methodologies?

TL;DR: They differ in their basic input and output. SAT and SMT solvers don't know what programs are; they are tools that answer yes or no questions about mathematical formulas. Symbolic execution, on the other hand, is a method of analyzing programs. Symbolic execution usually relies on SAT and SMT solvers, but not the other way around.

SAT and SMT solvers don't directly have anything to do with programs. Instead, a SAT or SMT solver takes as input a mathematically described "formula", and answers, roughly, whether it is true or false. (Often a third option is allowed, unknown, for cases where the solver is unable to figure out an answer.)
For example, a possible input to a SAT solver is (a and not b) or (not a and c). That is, it is a mathematical formula, where a, b, and c here are Boolean (0 or 1) constants. The SAT solver is supposed to decide if it is possible for the formula to be true, by choosing values of a, b, and c. SMT solvers are similar, but a, b, and c would be replaced by more complex formulas using integers, strings, functions, etc., for example x + 3 = y^2.

Symbolic execution is a fancy way of running a program, but not how the program was intended to be run. Instead, the program is run using so-called "symbolic" values, which are kind of like placeholders. For an example of what that means, suppose I have a function like f(x) = if x > 0 then 1 else 0. Now, normally, I would run the program by inputting, say, 3, and get f(3) = 1, since 3 is greater than 0. With symbolic execution, I run the program by inputting a placeholder variable, input, and I evaluate the program to get two cases: either input > 0 and answer = 1 or input <= 0 and answer = 0. This may seem useless, but it ends up being a powerful way of analyzing programs.

The connection between the two is that symbolic execution often relies on SMT solvers during execution, to figure out if a certain path is actually possible, or if it should be discarded. For example, an SMT solver could be used to determine if input <= 0 and answer = 0 is possible (the answer is yes, for example if input = 0).  In this way, SMT is kind of the "driving force" behind what makes symbolic execution feasible.


Existence of d-regular subgraphs in a k-regular graph The claim is as follows:
Let's say we have a $k$-regular simple undirected graph $G$ on $n$ vertices. Then, does $G$ then always have a $d$-factor for all $d$ satisfying $1 \le d \lt k$ and $dn$ being even.

I think its true, since we can construct a

$k+1$-regular graph from $G$ by adding $\frac{n}{2}$ edges for even $n$ or
$k+2$-regular graph from $G$ by adding $n$ edges for odd $n$

And the converse for the above.
We can construct a $k$-regular graph on $n$ vertices by

removing $\frac{n}{2}$ edges from a $k+1$-regular graph for even $n$.
removing $n$ edges from a $k+2$-regular graph for odd $n$.

Hence, using the converse argument, we can say that the original claim is true, since from a $k$-regular graph $G$ we can construct

$1$-factor, $2$-factor, ... $k-1$-factor for even $n$ or
$2$-factor, $4$-factor, ... $k-2$-factor for odd $n$

Is my argument correct or is there any flaw in this argument?

Your conjecture is false. There are regular graphs with an even number of vertices yet without a 1-regular subgraph. See this question on Mathematics.

The complement of such a graph gives a counterexample to your claim that you can always add a perfect matching to increase the regularity (when the number of vertices is even).

In the bipartite case, however, your conjecture is true. Any $k$-regular bipartite graph can be decomposed into $k$ perfect matchings. This follows from Hall's theorem.


Round-Robin Scheduler - What exactly is the quantum time used for? Suppose you have three stages for a job:

Creation stage = the job gets created

Executing stage = the job is executed/served

Finishing stage = the job is "marked" as finished.

Now, say the quantum time for a round-robin scheduler is 100ms. From what I understand, the 100ms is spent on the executing stage. Am I right to assume that the creation and finishing stage is OS stuff, and what really the quantum time is used on, is the executing time?

I'm a bit confused because I'm trying to write a model, and for the scheduler I'm trying to figure out whether "job 1 was created" counts as a "turn" or consumption of quantum time for that given job. So, if "job 1 was created" happens, then it switches to "executing job2".

I might be mixing up OS tasks and CPU execution here.

For the Round-Robin Scheduler the quantum time is to ensure that each process has a share to the CPU and we don't have starvation problems. It's known for being fair, such that each process shares the CPU equality. Quantum time is it's the amount of time spent on each process in the CPU until we context switch to the next process in the ready queue. For example say you have P1, P2, and P3 in the ready queue. And some P4 enters the ready queue at 550ms. The RR would perform something like this:

P1 - 0   to 100ms
P2 - 100 to 200ms
P3 - 200 to 300ms
P1 - 300 to 400ms
P2 - 400 to 500ms
P3 - 500 to 600ms [P4 enters]
P4 - 600 to 700ms
... [P1 to P4 cycles]

If a process has a CPU-bound execution that is less than the time slice. Then we move to the next process keeping the same time slice. For example let's say P1 only needs to run for 50ms until it's done. Then you have:

P1 - 0   to 50ms [finnished, start P2]
P2 - 50  to 150ms
P3 - 150 to 250ms
P2 - 250 to 350ms
P3 - 350 to 450ms
...


Computing losing positions in modified Wythoff's game efficiently Wythoff's game is as follows: there are two players $A$ and $B$ ( $A$ being the first player ) and there are $2$ piles of stones. When his turn a player can remove one or more stones from anyone pile or same number of stones from both the piles. A player unable to make a move loses. Also it is assumed that both the players play optimally.

As mentioned in the link the losing configurations $(n_k,m_k)$ ( $n_k$ stones in one pile and $m_k$ stones in another ) are given by
$$ n_k = \lfloor( k*\phi) \rfloor$$
$$ m_k = \lfloor( k*\phi^2) \rfloor$$
where $k$ is any natural number ( and $n_k \le m_k$ ) and $\phi=\frac{1+\sqrt{5}}{2}$. For example $\{1,2\}$ ( two stones in one pile and one stone in another ) is a losing position.

Modification to Wythoff's game"

In this modified game instead of ${\it2}$ piles there are ${\it 3}$ piles. And when his turn a player can move one or more stones from anyone pile or same number of stones from any $2$ piles or same number of stones from all the $3$ piles.
How do I compute the losing positions for this modified game efficiently ? The inefficient way of course is to find the grundy number of each  configuration $\{a,b,c\}$. This method is inefficient because I want to calculate  number of losing positions given that number of stones in each pile can be between $1$ and $1000$.

This is a project Euler question ( stone game ). I would appreciate hints
only.

There is no closed form for $n=3$ piles. But one can solve the question efficiently using dynamic programming.


Can a DPDA be created for a Language which includes the null string? Can a DPDA be created for a Language which includes the null string?

The way I understand it, in a DPDA, you can have at most 1 move from any instantaneous description Delta(q,a,Z) where q is a state, a is some input, and Z is a stack-character.

Also, if you have a transition Delta(q,lambda,Z), you can't accept any other input from that state.

So, back to the original question. Can a DPDA accept a language which lambda and anything else?

Yes, we can simply make the starting state an accept state. With no input (i.e. empty string) the machine halts immediately, and accepts.


How can I assign cooks to customers? I haven't done much algorithm writing till now. I have a specific scenario and I am wondering which approach shall I take.

Scenario:

Let us suppose that

we have 4 guys (A,B,C,D)
We want to assign them a certain task whose duration varies from 40 mins - 1 hr 15 mins.
The task duration varies depending on the number of people (1-6) which he needs to serve. (i.e 40 mins for 1 person and 75mins for 6).
Now we want to utilise these 4 guys(A,B,C,D) in particular time slots. let's say:

  06:30 to 11:00 & 16:00 to 22:00

I don't only want the code rather I would love to get some info about good algorithms which are best suited for this scenario following with some code.

All resources have equal efficiency. Efficiency is not much of our concern.
We can have any number of customers who are to be served. I'll try to explain this by one scenario:

  A,B,C,D are cooks(assume) who need to work during the mentioned time slots(6:30 to 11:00 & 16:00 to 22:00). Customers(as an individual or some group who are living together in a flat) can book the cooks to cook food for them. The cooking time (40 mins to 75 mins) is directly proportional to the number of people for whom it is being cooked. The customer should be able to register himself on some website and the website would allocate the resources(A,B,C,D) to the registered users accordingly.

Input:

How many people are enrolling for the service
Desired time slots

output

Available cooks as per the selected time slot

Update 2:

There can any number of cooks.
There can any number of customers with no relation to cooks.
Once a customer books any cook , its not compulsory that the cook has to serve in both(lunch & dinner) time slots. The customer can select opt for the same cook if he's(the cook) available or else the customer will be asked to select another cook who is available during that time

This looks like an instance of the assignment problem.  (No, it doesn't require a square matrix.)


What is oblivious RAM and how does it work? Could anybody explain me what exactly oblivious RAM is?

I found the following explanation which makes it kind of clear to me, but I would like to get a sense of the technical aspects:

  Encryption is not always enough to ensure privacy. If an adversary can observe your access patterns to encrypted storage, they can still learn sensitive information about what your applications are doing. Oblivious RAM solves this problem by continuously shuffling memory as it is being accessed; thereby completely hiding what data is being accessed or even when it was previously accessed.

Oblivious RAM is an interface between a program and the physical RAM that when you perform a read or write, does both at the same time on the physical RAM to hide if you are reading or writing. Plus, it shuffles the memory from time to time so that an adversary seeing only accesses to the physical RAM cannot know whetever you accessed the same data twice or accessed two different data. Thus hiding the access patterns to the physical RAM.

Instantiations I know of rely on oblivious sort, which is a way of sorting elements in a list by comparing and eventually swapping elements in an order predefined, that does not depend on the comparison results.


Why choose D* over Dijkstra? I understand the basis of A* as being a derivative of Dijkstra, however, I recently found out about D*. From Wikipedia, I can understand the algorithm. What I do not understand is why I would use D* over Dijkstra. To my understanding, Dijkstra gives a best path and D* works backwards from the end goal, but unlike A* it seems to do many calculations, so it doesn't seem as efficient.

The main reason for choosing D* is that it is incremental. Basically, when your initial route gets blocked, an incremental search algorithm is able to take advantage of the previous calculations. Dijkstra doesn't do this; it needs to recompute everything from scratch. Such an incremental approach is often used in robotics, navigation, and planning.

This is the short answer. For much more, I think you would be interested in How do the state-of-the-art pathfinding algorithms for changing graphs (D*, D*-Lite, LPA*, etc) differ?


Behaviour of Dijkstra in Case of Negative Edge Weight I came across a serious doubt regarding the implementation of the Dijkstra algorithm and hence wanted to discuss.

For the given below graph

What should be the Cost to reach Node G from Source Vertex A?

I was getting 2, as vertex E is the last processed vertex and when it was being processed

$E.d=9,(E,G)=-7$ so $G.d=2$ changed.

Some implementation of Dijkstra says that once a vertex v has been relaxed, then it's estimated $v.d$ is never changed.

Like here

https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/

Here $v.d$ is changed only when sptSet[v] for that vertex is false, means that vertex was not processed before.

But CLRS says that for each vertex U that belongs to queue and results from
U=EXTRACT_MIN(Q), we relax all edges leaving U.

So, If I follow the implementation of Dijsktra of what is given in CLRS, I get cost of 2 to reach node G from source Vertex A.

Please guide what should be correct.I am really confused about it.

The article on Dijkstra's algorithm at GeekForGeeks say "Dijkstra’s algorithm doesn’t work for graphs with negative weight edges in general."

Introduction to Algorithms by Corman et al. says "Dijkstra’s algorithm solves the single-source shortest-paths problem on a weighted, directed graph for the case in which all edge weights are nonnegative."

As explained in the linked question and answer and as OP has found, the general proof of the correctness of Dijkstra's algorithm will fail if there are negative edges, hence discussing Dijkstra on graphs with negative weight edges doesn't make sense.

I would advise you to stay away from Dijkstra’s algorithm when a graph that has negative weights appears. It might work in some cases, but it may lead you into troubles that will be avoided if you apply Bellman–Ford algorithm or Floyd–Warshall algorithm.

By the way, the shortest distance from $A$ to $G$ is 2.


Number of $1$'s in a Kolmogorov-random number The problem I'm trying to tackle is to show that for a Kolmogorov-random number of length $n$, the amount of $1$'s in its binary representation is greater than $n/4$.

My only idea so far, is to use a Turing machine that takes indices of $1$'s as an argument and produces a binary sequence accordingly. Then, for instance, we could say the amount of ones is at least $\sqrt n$ as (roughly) $C_U(n)\leq \sqrt n\log n < n$ for $n$ large enough (each index is at most of length $\log n$).
But this doesn't allow us to infer there are more than $n/4$ ones.

Is there any other way to generate some given number that would prove the statement in question?

I've found an answer which uses certain facts I was not aware of, but it's nevertheless really good.

Our machine $M$ takes the length of a number, $n$, and an index $j$ as an input (we encode the first argument in such a way so that there was no doubt where it ends, i.e. putting $0$ in between every digit and ending with $1$). $j$ denotes the $j$-th number with less than $n/4$ ones in a lexicographic order. The only problem we have now, is to evaluate how big $j$ can be.

We have $$j_{\max}=\sum\limits_{i\leq n/4}\binom{n}{i}$$

Often, when proving Second Shannon's Theorem, the above sum (even more general, with $\lambda n,\ \lambda\in (0,1/2]$) is evaluated to be less than $2^{nH(\lambda)}$ with $H(\lambda)$ being the entropy of a non-fair coin throw.

Thus, we get $j_{\max}\leq 2^{nH(1/4)}$. Since $H(\lambda)\leq 1$, a number with less than $n/4$ ones cannot be random besides finitely many cases.

More exactly, $$C_U(x)\leq 2\log(n) + nH(1/4) + c$$ and this, for $n$ large enough, is less than $n$.


How to prove that a predicate is prefix closed Suppose we have the predicate

$\qquad A.p.q ≡ (∀i \mid p≤i≤j<q : X.i≤X.j)$

which says that $X[p..q)$ is ascending.

Apparently, the predicate holds for empty segments, is prefix closed and is postfix closed.

I would like to prove that the predicate above is indeed prefix closed, but I am not able to; that is, I am unable to prove that

$\qquad A.p.q \implies (∀s \mid p≤s≤q : A.p.s)$

and I wondered if somebody could help?

Your predicate states that $X_p \leq X_{p+1} \leq \cdots \leq X_{q-1}$. If you take any subinterval of $[p,q)$, say $[p',q')$, you will still have $X_{p'} \leq X_{p'+1} \leq \cdots \leq X_{q'}$. In other words, a subinterval of a non-decreasing sequence is also non-decreasing.

Now that you know why what you want to prove is true, it remains to prove it formally. Always remember: the first step is to understand why something is true, and only then should you try to prove it. In fact, most of the time in mathematics and computer science we skip the second step, that of proving things formally, since it obscures the situation.


Find height of a ternary tree Ternary heap is like a binary tree, just every node can have up to $3$ sons and not $2$.

I try to bound the number of nodes in the heap, $n$, using the height of the heap $h$.

The solutions get to:

$$
3^h < n < 3^{h+1}
$$

Yet, I get to:

$$
\frac{3^h}{2} < n < \frac{3^{h+1}}{2}
$$

In short, what I do is:

$$
\sum_{i = 0}^{h - 1}3^i = \frac{3^h-1}{2}
$$

For all the nodes in all levels except for the last level, because all the levels are full.

If the last level is full:

$$
\frac{3^h - 1}{2} + 3^h
$$

If the last level has only $1$ node, we get:

$$
\frac{3^h - 1}{2} + 1
$$

From here I conclude what I showed at the beginning.

Why the solutions get to something else?

The expected solution is wrong.

Pick $h=0$. The only ternary heap with height $0$ has only one node. Nevertheless the expected solution says that it needs to have at least $3^0 + 1 = 2$ nodes.

In case you meant to write $3^h \le n \le 3^{h+1}$ instead of $3^h < n < 3^{h+1}$, the expected solution is still wrong.
Consider a ternary heap with $n=2$ nodes. This heap has height $1$ but according the expected solution it should have at least $3^h = 3$ nodes.


Predicting target location given cursor speed and direction Do you guys know of any method or algorithm you are able to predict where a user is moving their cursor given its speed and bearing?

I'm trying to predict if and when users are moving their mouse to a certain part of the screen (address bar location).

Could I exploit Fitts's Law in this regard?

Fitts's law gives you a guess for the length of the movement (in terms of screen distance), and so gives you a rough spot where the user is aiming. Make a list of "points of interest" where the user is likely to click (a priori), and then put together a score which takes into account both the probability that the movement ends at the point, and its prominence. Pick the point with maximal score.

Machine learning has been used to derive the parameters for Fitts's law, and I'm not sure anything more is needed here apart from some UI experiments.


Difficulty in proving the existence of one-way functions By definition:

A polynomial-time computable function $f:$ $\{$0,1$\}$$^*$→ $\{$0,1$\}$$^*$ is a one-way function if for every probabilistic polynomial time Turing Machine $PTM$ there is a neglegibible function $E$ $:$$\mathbb{N}  → \mathbb{N} $
  $ \ s.t. \ $ $Pr$ $x$ $∈$ $\{$0,1$\}$$^n$ $[PTM \ \ inverts \ \ f(x)] ≤ E(n)$.

Now, reading the definition above, the existence of one-way functions seems like an easy bet, however it is considered a stronger assumption than $P \neq NP$.
Apparently proving the existence of these functions would be more difficult than proving $P = NP ?$   And I'd like to know the technical reasons for this, does it have something to do with the "for every" in the definition?

What steps would a mathematician or computer scientist take to prove that one-way functions exist? I believe that since proving its existence would also prove $P \neq NP$, this means that we cannot use the techniques that we know for sure does not work: Relativization, diagonalization, Natural Proof.

So,  what form could such a proof take? Maybe something in  second(+)-order logic?

Apparently proving the existence of these functions would be more difficult than proving $P\not =NP$? And I'd like to know the technical reasons for this, does it have something to do with the "for every" in the definition?

The answer is in your question itself:

  I believe that since proving its existence would also prove $P\not =NP$

This is indeed the case. Somebody that proves the existence of one-way functions automatically also proves $P\not = NP$. On the other hand, it is conceivable that you could prove $P\not = NP$ without proving that one way functions exist. Thus, proving the existence of one-way functions is at least as hard as proving $P\not = NP$.

  What steps would a mathematician or computer scientist take to prove that one-way functions exist?

Coming up with an extremely clever and creative idea that nobody came up with before.


Why does packet data don't need trailer/footer while frame needs it? Why does packet don't need trailer/footer while frame needs it?

I am trying to understand networking concept regarding OSI & TCP/IP layering. I have googled a bit and it says that the footer in data link layer pdu (frame) is needed as a mark of the end of the pdu.

But why does packet data etc in the layers above it doesn't need footer to mark the end of the pdu as well?

OSI Layer 2 is usually tasked with getting the information from the upper layers, provided in octets (bytes), into bits suitable for sending over the physical link (OSI Layer 1). On the receiving side, the bits need to be converted back into bytes.

Links do not usually have the nice property of sending an exact sequence of 0 and 1. There is timing to consider (e.g. on a TTL line, scan the voltage n times per second). shifting (especially in parallel lines), bit damage, etc. Also, on asynchronous lines (most ones, except ATM (asynchronous transfer mode), textbook example for a synchronous protocol, always makes me smile), there are periods of no data transfer. This means that the sender and recipient somehow have to signal beginning and end of “transfer blocks”.

This is all rather difficult, so the frame header and trailer do not necessarily have to be full numbers of 8-bit blocks. They often include some easily-recognised bit patterns, such as a large-ish number of either all-zeroes or all-ones, followed by a toggle sequence such as 010101, and only then followed by data; this allows the recipient to synchronise on the sender better. Even DCF77 works like that, so receivers can synchronise to the exact beginning of a minute.

Going further, Layer 2 switches often operate in “fast pass-through mode”, in which they only need to have received the header (containing the target (and often source) address) to decide where to send the frame, not needing to fully buffer the entire frame for this decision, leading to faster throughput (less latency). On the other hand, the sending side may, indeed, wish to calculate the checksum on the fly and append it, in the trailer, which is only needed on the recipient side, not on the switches in between. This all allows for cost reduction in hardware.


How to compare two objects for percentage of equivalence I'm trying to create a nodeJS application. It allows users to rate a bunch of songs and it stores them in their user profiles. I use this information to compare them to other users, and try to find users with similar interests in songs, and I suggest them new songs based on that.

Each user profile basically looks like this

userID: [the userid of the user]
songs: [the list of songs that the user has rated]
ratings: [the corresponding ratings each user gave to the song]

Each song is represented by a 9 digit whole number and each rating is a whole number from 1 to 6. Basically put, I have to compare one user to the rest of the users to determine which of them match this user the best. By match, I mean gave the same songs similar ratings. To do this, I created a simple algorithm.

Step 1) Create a list, in which each entry maps our target user to each of the other
        users.
Step 2) Now consider each entry, determine which songs both of the users have rated, and
        store those songs (along with the corresponding ratings each user gave them) in
        this entry itself
Step 3) Now iterate through each entry and perform the following operations

        a) let percentage = 0
        b) let num = [the number of songs that both users rated]
        c) iterate through each song (that both the users rated) and perform the
           following operations

                i)    determine the score our target user gave this song and store it in
                      variable a
                ii)   determing the score the other user gave this song and store it in
                      variable b
                iii)  map a and b to new values based on this
                        1 --> -3
                        2 --> -2
                        3 --> -1
                        4 -->  1
                        5 -->  2
                        6 -->  3
                iv)   now calculate sum as
                    sum = |a| + |b|
                    where || is the absolute values
                v)    now calculate degree as
                    degree = sum/2
                vi)   now if a * b is less than 0 then
                            calculate (percentage - degree) and store that value
                            again in percentage
                          if not then
                            calculate (percentage - degree) and store that value
                            again in percentage

        d) now  calculate (50 + (percentage / (6*num))*100) and store that value
           in this entry as match

Step 4) Now that I have my list of entries (along with the match between each pair
        of target user and other user) I sort the list in descending order of match
        and from that, I can determine which users have the closest match in taste by
        selecting from the first entries

Now for each user pair, I am completely neglecting the songs that one user rated and the other didn't, and that is okay for me.

There are several problems with this method though, the biggest one being that this algorithm is very time consuming for a large set of users (say around 1,000,000). And also that I have to load in all the users, every time I need to find a set of matching users for just 1 user. And I need to do this repeatedly for that user, to update his/her list.

Is there a way to make this more efficient? Can I assign a value to each user that takes into account all the songs that they rated, and use that number to compare the users? Is that even possible? I guess what I'm asking is, how can I compare and contrast this data, mathematically, to find similar users, efficiently. Also, can someone suggest a proper tag for this type of question?

EDIT

D.W. has suggested a solution, but how do I implement it? Can you provide more detail?

One approach is to use low-rank matrix factorization to approximate the ratings matrix, then use a nearest neighbors data structure.

In particular, let $M$ be the $m \times n$ ratings matrix, where $M_{ij}$ is the rating that user $i$ has provided to user $j$.  Look for a $m\times r$ matrix $U$ and a $r \times n$ matrix $V$ such that $M$ is well-approximated by $UV$ (e.g., $||M-UV||$ is minimized, except that missing entries of $M$ are ignored).

Once you've done this, each user can be mapped to a $r$-dimensional vector that summarizes their scores.  Store the set of all of these vectors in a data structure that supports nearest neighbor search, e.g., a k-d tree.  If you have chosen $r$ small enough (e.g., 10 or so), then nearest neighbor search should be very efficient.  This will let you find the users who are most similar to a given user, and thus make a recommendation (e.g., using the  k-nearest neighbors classifier).

There are many other approaches you could use: read the extensive literature on recommender systems and collaborative filtering.

As far as your other issue:

  I have to load in all the users, every time I need to find a set of matching users for just 1 user

Keep the data structure in memory, rather than re-loading it into memory each time.


Why use a CFG instead of a DFG I just realized a Control-Flow Graph (CFG) is composed of basic blocks, which is a set of instructions. It is mentioned that you can still do stuff like dead code elimination and whatnot, with the CFG, but that seems like you'd be reaching into the basic block to figure that out. At that point you are dealing with individual instructions. But that's the domain of Data-Flow Graphs (DFG). Data-Flow Graphs are made of connections between individual instructions.

My question is, why not just always deal with individual instructions instead of the basic blocks. It seems like in the end you are using individual instructions anyways. Wondering the advantages a CFG has over a DFG, and vice versa.

A control-flow graph serves a different purpose than a data-flow graph.  They aren't alternatives.  A control-flow graph represents the flow of control: which instruction can follow another.  A data-flow graph represents the flow of data: which instruction can read data that was created by another.

Perhaps you mean to ask why each vertex in a control-flow graph represents a basic block (a group of instructions) rather than a single instruction.  That's an optimization. You could have each vertex represent a single instruction, but often you'll have a long sequence of consecutive instructions with no control-flow transfer, and they all have the same properties, so it is natural to collapse them into a single vertex.  Also subsequent program analyses may be faster with this optimization; see Why is it better to do the data flow analysis in the basic blocks.


Is there any way to distinguish between LL(k) and LR(k) grammar? I am recently studying about Compilers designing. I came to know about two types of grammar one is LL grammar and other is LR grammar.

We also know the facts that every LL grammar is LR that is LL grammar is a proper subset of LR grammar. First one is used in top-down parsing and the second one is used in bottom-up parsing.

But is there any way to so that we can say that a given grammar is LL or LR?

$LL(k)$ and $LR(k)$ grammars are nice not just because they can be parsed efficiently, but also because we can check if a grammar is $LL(k)$ or $LR(k)$, and because we can generate tables for them (parse tables are used to parse input strings). Note that for these two classes, having the parse table immediately allows you to check whether the grammars are in the classes, because this is so if and only if the tables contain no errors. Also, yes, there are classes of grammars which we can parse efficiently if we have a parse table, but for which we cannot generate the table if it exists.

Any textbook on parsing methods will teach you how to generate the tables for $LL(1)$ methods and possibly also for $LR(1)$ (though $SLR(1)$ is more common). Textbooks such as Parsing Theory by Sippu and Soisalon-Soininen also treat the parse table generation for $LL(k)$ and $LR(k)$ grammars.

Unfortunately, for really weird grammars, the parse tables for $LL(k)$ and $LR(k)$ (though not for $LL(1)$) can blow up and become huge; they will do this even for normal grammars if $k$ is high enough. There are tests available that can check whether a grammar is $LL(k)$ or $LR(k)$ or not that run in polynomial time (table generation is exponential). For details, read the textbook above. Note that in a lot of cases, the table is reasonably sized, so the test is not needed.

If you don't want to try values of $k$ to see if your program works, but instead want to have your computer figure out whether there exists a value of $k$ such that your grammar is $LL(k)$ or $LR(k)$, you are unfortunately out of luck, as this is undecidable. If your grammar is $LR(k)$ for some $k$ though, you can decide whether your grammar is $LL(c)$ for some $c$, possibly different from $k$ (see here for details).


Can I simplify successive XOR operations? I'm doing an online programming challenge where successive XOR operations are used (from codewars.com, if you don't want to create an account, here are the instructions).

We have a rectangle of known dimensions where every value of column and row (zero-indexed) are XOR-ed in order to create a value. Then, we must compute the sum of every value of that rectangle.
(i.e. for a rectange of 8 columns & 5 rows, the first value would be 0 ^ 0 = 0, then 0 ^ 1 = 1, etc. until 7 ^ 4 = 3, then the sum of every value would give 105, which is the result)

I've tried different approach to this problem, but every one of them end up being too slow and not enough efficient. The naive solution is of time complexity $O(N^2)$, which becomes too slow when we're working with a lot of values.

Here would be the function to compute the value of 1 row.
(x is the number of columns & y is the number of the current row)
$$
f(x,y) = (0 \oplus y) + (1 \oplus y) + (2 \oplus y) + (3 \oplus y) + .. + ((x - 1) \oplus y)
$$
So the whole rectangle would be that function from 0 to y - 1 for the y value.

So my question is: Is there a way where I can simplify a function like that to gain efficiency ?

Yes, there are ways to improve the efficiency greatly.

Let ${}_k{i}$ be the $k$-th digit of $i$ in binary representation, i.e., it is 0 if $\lfloor i/2^k\rfloor$ is even and 1 otherwise. For example, since $19=(10011)_2$, $_019=1$, $_119=1$, $_219=0$, $_319=0$, $_419=1$. In most programming languages,  ${}_k{i}$ can be computed as $(i\text{>>}k)\%2$.

Let us apply the power of summand splitting and rearrangement to inspect the contribution to the sum by the $k$-th digits in isolation.

$$\begin{aligned}
\text{total sum}
&=\sum_{\text{ row } i\,}\sum_{\text{ column }j\,} i \oplus j\\
&=\sum_{\text{ row } i\,}\sum_{\text{ column }j\,} \sum_{0\le k\lt u} ({}_k{i}\oplus {}_k{j})\cdot 2^k\\
&=\sum_{0\le k\lt u} 2^k\sum_{\text{ row } i\,}\sum_{\text{ column }j\,} {}_k{i}\oplus {}_k{j}\\
&=\sum_{0\le k\lt u} 2^k\left(\#\{\text{row }i\mid {}_k{i}=1\}\cdot \#\{\text{column }j\mid {}_k{j}=0\}\right.\ + \\
&\quad\quad\left.\#\{\text{row }i\mid {}_k{i}=0\}\cdot \#\{\text{column }j\mid {}_k{j}=1\}\right)
\end{aligned}$$

We can set $u=\lceil\log_2\max(m+1, n+1)\rceil$ or any integer such that $n,m\lt 2^u$, where $n$ is the number of rows and $m$ is the number of columns. If $m$ and $n$ are ints or longs in Java or C#, $u=63$ could be a good choice.

Now the problem is shifted to compute $\#\{\text{row }i\mid {}_k{i}=0\}$ and the like ones. We have
$$\begin{aligned}
\#\{\text{row }i\mid {}_k{i}=0\}
&=2^k\left\lfloor\frac {n-1}{2^{k+1}}\right\rfloor +
\min\left(n-2^{k+1}\left\lfloor\frac{n-1}{2^{k+1}}\right\rfloor,\ 2^k\right)\\
\#\{\text{row }i\mid {}_k{i}=1\}
&=2^k\left\lfloor\frac{n-1}{2^{k+1}}\right\rfloor +
\max\left(0,\ n-2^{k+1}\left\lfloor\frac{n-1}{2^{k+1}}\right\rfloor -2^k\right)
\end{aligned}$$
In terms of Java, they are, respectively,

((n-1)>>(k+1)<<k) + Math.min(1<<k, n - ((n-1)>>(k+1)<<(k+1))),
((n-1)>>(k+1)<<k) + Math.max(0, n - ((n - 1)>>(k+1)<<(k+1)) - (1<<k))

The time-complexity of the algorithm is about $O((\log n)^2)$


Logarithmic vs double logarithmic time complexity In real world applications is there a concrete benefit when using $\mathcal{O}(\log(\log(n))$ instead of $\mathcal{O}(\log(n))$ algorithms ?

This is the case when one use for instance van Emde Boas trees instead of more conventional binary search tree implementations.
But for example, if we take $n < 10^6$ then in the best case the double logarithmic algorithm outperforms the logarithmic one by (approximately) a factor of $5$. And also in general the implementation is more tricky and complex.

Given that I personally prefer BST over VEB-trees, what do you think ?

One could easily demonstrate that :

$\qquad \displaystyle \forall n < 10^6.\ \frac{\log n}{\log(\log(n))} < 5.26146$

Do not forget that $\log n$ still grows exponentially (in $\log(n)$) faster than $\log(\log n)$!

Indeed, if you look at the quotient of $\log(n)$ and $\log(\log(n))$, there is not much impressive to see:

[source]

But still, you get a factor five to six for sizes up to $100000$. Note that larger sizes are not uncommon in practice, and a speedup by that factor is awesome! It may make the difference between having results after lunch or only tomorrow. Be aware that part of the speedup may be eaten away by higher constants of the tree implementation; you would have to plot (or analyse) $c\cdot \log(n)$ and $d\cdot \log(\log(n))$ with $c,d$ the actual runtime constants to get a real picture.

Additionally, what Dave mentions is important: if the operation sped up thusly is executed, say, linearly often, constant speedups become linear speedups, i.e. you may decrease the leading constant of your entire algorithm! As I said above, that is awesome. Just look at what happens if you run the operation $n$ times:

[source]

Now if that's not worth the trouble I don't know what.


What is name of type " Function->Value->Bool = if (Bool) Function (Value) " in Category theory? I am very new to functional programming so sorry if the question is stupid.
Having this function
const noname = func => val => bool => bool? func(val) : val

And following situation
// if event.target has css class 'draggable-box' , add drag listener to it, using event
compose(
    noname( add_drag_listener )(event),
    elem_has_css_class('draggable-box'),
    prop('target'),
)(event)

In Category theory, what is the correct name for the noname function? Is there such a type?

Maybe currying is the syntax you refer, and passing arguments as functions:

const sum = (a, b, c) => a + b + c;
const partial = a => b => c => sum(a, b, c);

console.log(partial(1)(2)(3));          // 6


Polygons generated by a set of segments Given a set of segments, I would like to compute the set of closed polygons inside the convex hull of the set of the end of those segments. The vertices of the polygons are the intersections of the segments. For example, if you draw the 6 lines restricted which equations are: $x=-1$, $x=0$, $x=1$, $y=-1$, $y=0$, $y=1$, I would like the algorithm to output the four unit squares around the origin.

You're trying to compute something called the arrangement of the line segments.  The arrangement is a planar straight-line graph whose vertices are either endpoints or intersection points of line segments.  The vertices partition the lines segments into smaller segments, which are the edges of the arrangement.  Finally, the vertices and edges partition the plane into several components; these are the faces of the arrangement.

Suppose you are given $n$ line segments, and $k$ pairs of those line segments intersect.  (You don't know $k$ in advance.)  The intersection points can be computed in $O((n+k)\log n)$ time using the Bentley-Ottmann sweep-line algorithm.  (The running time can be reduced to $O(n\log n + I)$ using a more complicated algorithm, where $I\le k$ is the number of intersection points, but the additional effort is probably not worth it.)  The algorithm can be modified to report, for each intersection point, which segments intersect at that point.  Then it is simply a matter of careful bookkeeping to construct a standard data structure that represents the arrangement.

A few caveats to keep in mind:

The faces of the arrangement are not necessarily simple polygons.  If the union of the line segments is connected, each bounded face is a weakly simple polygon, but a single edge can be incident to the face no both sides.  If the union of the segments is disconnected, then faces can have holes, which are either trees or weakly simple polygons.
Most textbook (and Wikipedia) descriptions of the Bentley-Ottmann algorithm assume that the input segments are in general position.  In this context, "general position" means that at most two segments intersect at any point; no segment endpoint lies on another segment (in particular, the intersection of two segments is either empty or a single point); and no two endpoints have the same $x$-coordinate.  In practice, however, this assumption does not hold.  As usual in computational geometry, handling degenerate cases correctly and robustly is the most difficult part of implementing the algorithm.  (What does your implementation do when the input contains 42 copies of the segment [(0,0),(1,1)], 17 copies of the segment [(0,0),(2,2)], and 9 copies of the zero-length segment [(1,1),(1,1)]?)
For small numbers of segments (at most a few dozen), it's probably faster to use a brute-force $O(n^2)$-time algorithm to compute the intersection points.


Minimal Path Covering Consider a connected undirected graph $G = \langle V, E\rangle$, we say that a subset $C$ of vertices is a Path-Cover if the following holds. For every finite path $p$, it holds that $p$ traverses all the vertices in $C$ iff $p$ traverses all the vertices in $V$. I am interested in finding a Path-Cover of minimal size in polynomial-time, yet all my attempts failed.
I tried a greedy approach where I start with $C = V$, and then I remove a vertex and check whether the graph remains connected. Yet, I'm not sure whether this greedy approach gives a global minimal Path-Cover.

This is only my Intuition on the problem, without any proof or explicit algorithm. This might yield an algorithm that can calculate directly the minimal path covering, or at least you might be able to use it to approximately solve the problem.

To start out, consider the simplest case: a path graph with $n$ nodes. Clearly, you will need only 2 vertices - both endpoints.
Now, lets take a look at a more complicated (and useful) graph: a cycle with $n$ nodes.
The smallest path covering must contain all nodes, since otherwise we can easily construct a path that goes through all nodes except one.
The important bit here, is that we can think of a general graph as a "combination" of such cycles and path graphs (any combination of such graphs with one or more nodes in common).
Basically, an idea behind trying to find the smallest path covering is to identify the cycles and paths. Then, start by "marking" each node at those cycles. Then using the "path graphs" try to identify which nodes you don't have to include (for example, think of two cycles connected by a path. Marking any node in one cycle is the same as marking the "endpoint" of the path graph. So the minimal path covering will mark every node that isnt in the path). Always make sure that both graphs at the endpoints of a path graph are "marked" (a graph is marked if any node in it is marked), as well as any graph connected to a node in a cycle is marked.
This is the basic idea of an algorithm to find which nodes we have to include in the minimal path covering. Try to refine this idea a bit more, and it will give a way to calculate or at least approximate the minimal path covering.


How would a CPU know if a piece of data is in cache or RAM or on disk? How would a CPU know if a piece of data is in cache or RAM or on disk?

This would imply there's some sort of meta addressing scheme on where everything is.

How does the CPU know if a piece of data is in L1 cache?  The L1 cache is part of the CPU (it's on the same chip) so the CPU just asks the L1 cache "do you have the data for address X?"; if it gets the answer "yes", it is good; if it gets the answer "no", then the CPU tries to read from RAM.

How does the CPU know if a piece of data is in physical memory or on disk?  The operating system keeps track of what data has been paged out to disk.  See https://en.wikipedia.org/wiki/Virtual_memory for details on that.


Applications of Depth-First Spanning Tree I know that depth-first search can be used to produce a depth-first spanning tree, which classifies all edges as tree edges, forward edges, backward edges or cross edges. Are there any algorithms that make use of the depth-first spanning tree?

You can find bridges, i.e. edges whose removal causes the graph to separate into disconnected components.

Assuming connected, undirected graphs, the key insight is that a tree edge $e = (v,w)$ ($v$ being the father of $w$ in the tree) is a bridge if and only if there is no backwards edge¹ connecting $w$ or a successor of $w$ with an ancestor of $w$ (in the search tree). If there were such an edge, $e$ could not be a bridge as it's part of a cycle.

By augmenting the depth-first search algorithm in a suitable way, we can do these checks along the road and thus get an $O(n + m)$ algorithm.

There can be no forward and cross edges!


Second Chance Page Replacement In the second chance page replacement algorithm, if a page's reference bit is already set to 1, and the next page in line of the reference string is the same page, does the reference bit stay at 1 or is it reset to 0?

The reference bit stays at 1, it is set to 0 only in two circumstances, when the page is read from disk, or when the algorithm gives a page a second chance.


Why do depth-limited search algorithm and BFS have different memory complexity? Let be $b$ the branching factor of the tree.

Let be $d$ the depth of the shallowest solution.

Let be $l$ the limit given to depth-limited search algorithm

Why is depth-limited search algorithm memory complexity $\mathcal O(b)$ times something (which is actually $\mathcal O(bl)$) whereas BFS is $\mathcal O(b)$ power something (which is actually $\mathcal O(b^d)$)?

Let be b the branching factor of the tree.
Let be d the depth of the shallowest solution.
Let be l the limit given to depth-limited search algorithm

Breadth-first search (BFS)
In the worst case, suppose that our solution is at depth d, and we expand all nodes but the last node at level d, then the total number of generated nodes is $ O(b^{d}) $.
As all these nodes must retain in memory while we expand our search, then the space complexity is $O(b^{d})$.
Depth-limited search algorithm
Unlike BFS, Depth-limited search algorithm has a very modest memory requirements, it needs to store only the path from the root to the leaf node, beside the siblings of each node on the path. Depth-limited search algorithm removes a node from memory once all of its descendants have been expanded.
DFS requires storage of only $O(bl)$ nodes thus space complexity is $O(bl)$.


How do you compute the Pareto Front of a set? I need to decide which solution is the best design, in order to do that I need to compare them. Lower energy used and lower weight is better. My initial idea was to order both the fields best to worst and chose based on which one finished higher but whats better 3rd and 2nd, or 1st and 4th?

Pareto front is a set of nondominated solutions, being chosen as optimal, if no objective can be improved without sacrificing at least one other objective.

(Energy Used, Weight)

(30,20)

(50,30)

(10,40)

(20,50)

(40,10)

Diagram Showing the Table

A multi-objective optimization problem can be formulated as

\begin{align}
    \min\limits_{\phi \in \Phi} & \quad [f_1(\phi), f_2(\phi), \ldots, f_m(\phi)]^T \label{eq:mo-objectives} \\
    s.t. & \quad g_j(\phi) \leqslant 0,~j = 1, \ldots, J \label{eq:mo-constraints}
\end{align}

Without loss of generality, assume that all objective functions are minimization functions. In this problem, the first equation represents the set of $m$ objective functions and the second denotes the problem constraints, which generate a polytope $\mathcal{P}$. Furthermore, $\Phi$ denotes the set of feasible solutions contained in $\mathcal{P}$ and $\phi \in \Phi$ represents a feasible solution.

A solution $\phi_1 \in \Phi$ dominates another solution $\phi_2 \in \Phi$ if and only if $f_i(\phi_1) \leqslant f_i(\phi_2)$ for all objective functions $\{f_1, f_2, \ldots, f_m\}$ and $f_i(\phi_1) < f_i(\phi_2)$ for at least one objective function $f_i$.

A solution $\phi' \in \Phi$ is said to be non-dominated if and only if there is no solution $\phi \in \Phi$ such that $\phi$ dominates $\phi'$.

A non-dominated solution $\phi^* \in \Phi$ is said to be Pareto-optimal if and only if, for all solutions $\phi \in \Phi$, $f_i(\phi^*) \leqslant f_i(\phi)$ for all objective functions $\{f_1, f_2, \ldots, f_m\}$ and $f_i(\phi^*) < f_i(\phi)$ for at least one objective function $f_i$.

The Pareto-front is the set of the Pareto-optimal solutions.

We can derive a simple algorithm to compute the Pareto-front of a given subset of solutions $\Phi' = \{\Phi'_1, \ldots, \Phi'_n\} \subseteq \Phi$. This algorithm will be specifically designed for your case (two objectives), but can easily be generalized to any number $m$ of objective functions.

First of all, assume that the solutions in $\Phi'$ are ordered in increasing order of the first objective (energy used). In addition, ensure that, for a given value of energy used, the solutions are also ordered in increasing order of their second objective (weight).

Let $i \gets 1$.
Add $\Phi'_i$ to the Pareto-front.
Find smallest $j>i$ such that $\operatorname{weight}(\Phi'_j) < \operatorname{weight}(\Phi'_i)$.
If no such $j$ exists, stop.  Otherwise let $i \gets j$ and go to step 2.


What are the other language models of computation similar to lambda calculus? I hope this question makes sense, but I was wondering if there are other models of computation similar to lambda calculus that you can use to build up axiomatic mathematical and logical fundamentals like numbers, operators, arithmetic functions and such?

Yes, there are many models of computation, and of those many are extensions or modifications of the $\lambda$-calculus. You may wish to learn about partial combinatory algebras, which are very general models of computation, of which the $\lambda$-calculus is an example. Every partial combinatory algebra has a $\lambda$-like notation for defining functions. They encompass examples such as: $\lambda$-calculus, Turing machines, Turing machines with oracles, topological models of computation, PCF, etc.

Many models of computation can be seen as extensions or modifications of the $\lambda$-calculus. Let us consider the simply typed $\lambda$-calculus augmented with various features:

System T is $\lambda$-calculus with natural numbers and primitive recursion. It is not Turing complete.
The aforementioned PCF is $\lambda$-calculus extended with natural numbers and general recursion. It is Turing complete.
There are many extensions of PCF, for instance PCF++ can perform parallel computations, PCF+catch can throw and catch exceptiosn, PCF+quote can disasemble code into source code, etc. These are all different computation models based on the $\lambda$-calculus.
In another direction, we can extend the $\lambda$-calculus with more powerful types, for instance System F is a $\lambda$-calculus with polymorphic types. It is quite powerful but not Turing complete.

All of this is just scratching a rich theory of models of computation and functional programming languages (which is what extensions of $\lambda$-calculus are, more or less). If you are interested in the topic, you can start by reading some books on the principles of programming langauges (for practical aspects), or some books on realizability theory (for theoretical aspects).


Perfect Probabilistic Encryption still requires key length about as long as message Let $(E,D)$ be a probabilistic encryption scheme with $n$-length keys (given a key $k$, we denote the corresponding encryption function by $E_k$) and $n+10$-length messages. Then, show that there exist two messages $x_0, x_1 \in \{0,1\}^{n+10}$ and a function $A$ such that

$$\mathrm{Pr}_{b \in \{0,1\}, k \in \{0,1\}^n}[A(E_k(x_b)) = b ] \geq \frac{9}{10}.$$

(This is problem 9.4 from Arora/Barak Computational Complexity.)

My gut intuition says that the same idea from the proof in the deterministic case should carry over. WLOG let $x_0 = 0^{n+10}$, and denote by $S$ the support of $E_{U_n}(0^{n+10})$. We will take $A$ to output $0$ if the input is in $S$. Then, assuming the condition stated in the problem fails to hold for all $x \in \{0,1\}^{n+10}$, we conclude that  $\mathrm{Pr}[E_{U_n}(x) \in S] \geq 2/10$ for all $x$. This implies that there exists some key so that $E_k$ maps at least $2/10$ of the $x$ into $S$ (the analogue of this statement in the deterministic case suffices to derive a contradiction), but now I don't really see how to continue. Is my choice of $A$ here correct, or should I be using a different approach?

It seems you have to use some different approach. There is a hint in Arora/Barak's book. From that hint, I got the following solution.

Again we set $x_0=0^{n+10}$. The algorithm $A$ works as follows. Let $y=E_k(x_b)$ be its input. Let $Y_{x_1}$ denote the set of ciphtertexts $y$ such that there exists some $k$ satisfying $D_k(y)=x_1$ ($D$ is the decryption algorithm). The algorithm $A$ outputs $1$ if and only if $y\in Y_{x_1}$ (so $A$ runs in polynomial time if P = NP). Then we have

$$\mathrm{Pr}_{b \in \{0,1\}, k \in \{0,1\}^n}[A(E_k(x_b)) = b ]=\frac{1}{2}\left(1-\mathrm{Pr}_{k\in\{0,1\}^n}[E_k(x_0)\in Y_{x_1}]\right)+\frac{1}{2}.$$

If this probability is less than $9/10$ for all $x_1\in \{0,1\}^{n+10}$, then we have $\mathrm{Pr}_{k\in\{0,1\}^n}[E_k(x_0)\in Y_{x_1}]>1/5$. This means $\mathrm{Pr}_{k\in\{0,1\}^n,k'\in\{0,1\}^n}[D_{k'}(E_k(x_0))=x_1]>2^{-n}/5$. Note this inequality holds for all $x_1\in \{0,1\}^{n+10}$, which means

\begin{align}
1&=\mathrm{Pr}_{k\in\{0,1\}^n,k'\in\{0,1\}^n}[D_{k'}(E_k(x_0))\in\{0,1\}^{n+10}]\\
&=\sum_{x_1\in\{0,1\}^{n+10}}\mathrm{Pr}_{k\in\{0,1\}^n,k'\in\{0,1\}^n}[D_{k'}(E_k(x_0))=x_1]\\
&>\frac{2^{n+10}\cdot2^{-n}}{5},
\end{align}

a contradiction!


Proving a problem as NP-complete According to this article,
A problem X can be proved to be NP-complete if an already existing NP-complete problem (say Y) can be polynomial-time reduced to current problem X. The problem also needs to be NP. Now my question is:

  Do we also need to prove that problem X can be reduced to at least one
  NP problem?

According to the definition of NP-completeness, each and every NP
problem must be reducible to NP-complete problem. As problem X is NP, are we not supposed to prove that this NP problem can be reduced to other NP-complete problems? Why does this reduction have to be only one way to prove a problem is NP-complete?

As you have stated, there are two very clear requirements for a problem $X$ to be $\mathbf{NP}$-complete:

$X \in \mathbf{NP}$.
$X$ is $\mathbf{NP}$-hard. That is, for every $Y \in \mathbf{NP}$, $Y$ is (poly-time many-one) reducible to $X$.

  Do we also need to prove that problem $X$ can be reduced to at least one $\mathbf{NP}$ problem?

No, as this is not one of the above requirements. However, if you are able to do so, you've proved that $X \in \mathbf{NP}$ (i.e., requirement no. 1): Suppose $X$ is reducible to $Y \in \mathbf{NP}$. Then verifying $x \in X$ can be done in poly-time by reducing $x$ to an instance $y$ of $Y$ and then verifying $y \in Y$.

  As problem $X$ is $\mathbf{NP}$, are we not supposed to prove that this $\mathbf{NP}$ problem can be reduced to other $\mathbf{NP}$-complete problems?

There is no need to. If you know $Y$ is $\mathbf{NP}$-complete and you show $X \in \mathbf{NP}$, then necessarily $X$ is reducible to $Y$. There is no need for you to do "extra" work.

  Why does this reduction have to be only one way to prove a problem is $\mathbf{NP}$-complete?

I am afraid I am not quite sure which reduction you are referring to, but if you are talking about reducing $X$ to $Y$, then the answer is simply: That is what the definition of $\mathbf{NP}$-completeness requires you to do.


Is random access allowed in the Bit Complexity model, or is it just expensive? In the RAM model, you're allowed to do unbounded indirect access (pointers can be arbitrarily large and still fit in a single machine word).

In the Bit Complexity model (no wiki article, sorry), machine words are constant sized. So storing the address of an entry in a table of size $N$ would require $O(lg(N))$ words.

This raises the question: Are you even allowed to do a multi-word random access into a table of size $N$ when using the bit complexity model? It's a bit of a strange operation, because the machine can't "hold the jump in its head" while making it. On the other hand, it could be allowed but cost $O(lg(n))$ time instead of the RAM model's $O(1)$ time.

I realize that this is basically just a definition, with interesting things on either side, but I'm wondering what the common definition is. Is bit complexity just another way of saying "multi-tape turing machine"?

According to Fürer's paper, the underlying complexity model is a Turing machine without random access, or equivalently, Boolean circuits. So no random access is allowed. Check also Diem's writeup on the subject.


Alternatives to directly connected networks for representing frequently-updated graphs What are the relative merits of the various graph representations, such as adjacency matrix, edge list, adjacency list, directly connected network etc. Given that this graph will be frequently updated, split, joined to other graphs?

Business Context: I am writing a molecule editor in C# and have currently used a directly connected network.  By this, I mean each edge maintains direct object references to each node, and each node supports a collection of edges, although this has proven to present problems when updating. I am looking for a better way of doing this.

The model should support

Adding and removal of nodes
Adding and removal of edges
Splitting connected graphs into two separate graphs
Joining graphs together

EDIT:  by a 'directly connected network' I imply the following.  Vertices are Atom objects.  Edges are Bond objects.  Each Atom has a collection of Bonds, and each Bond has a StartAtom and EndAtom.  The collections hold object references, so it is possible to directly retrieve the Atoms by calling Bond.StartAtom and Bond.EndAtom.  Setting the StarAtom or EndAtom requires that both Bond collections on each atom be update in synchrony.

Also, Atoms and Bonds reside within a Molecule, each being stored in one of two dedicated collections, and each Atom and Bond holds a direct reference to its parent Molecule.  Also, Molecules may contain an arbitrary number of child Molecules, and each of these has a reference to its parent.

The major difficulty with this approach is book-keeping.  Molecular graphs, when being edited are constantly being updated.  A typical operation is to remove a linking bond between to portions of a Molecule, which would split it into two separate Molecules.  Or to perform the revers operation, joining the Molecules into one combined Molecules, simply by drawing a bond between two disconnected Atoms.

The current approach is challenging to maintain easily and reliably.  When you add the requirement that you must support Undo and Redo then it becomes near impossible.  So I am looking for any approaches or design patterns that would simply this task though abstracting the representation.  I am currently experimenting with an edge-list approach.  I want to know if there are any better ways of doing it.

You might be interested to know after all that I settled on an edge-list representation.  This allows easy cloning and has loosely coupled nodes and edges, which makes it idea for frequent editing operations.

Thanks for all the help and constructive comments.


Determing Big Oh Of Given Data I'm trying to determine the big O time complexity of the following
data set where the first column is the input size, and the second column is the execution time in seconds. Where possible, I should determine the exponent of the dominant term and provide an estimate for the coefficient on the dominant term.

I made the following
graph of the data and a log/log graph to try and figure it out. At first I thought it might have been 1/n or something along those lines but as n gets quite large, the execution time increases again instead of asymptotically approaching a value.
The log graph having such a distinct pattern leads me to believe that the answer will lie there but I'm stuck as to where to go from here. Any help would be great.

You can't.  You can't infer big-O complexity from a finite set of data points, as big-O complexity is about asymptotics.  See, e.g., How to fool the plot inspection heuristic?.


Determining if a TM decidable or not, with limited information Were being asked to determine the whether this Turing Machine is decidable or not

"Given a two way, one-tape DTM $M$ whose tape set is $\Gamma=${$a,b,B$} and a string $x\in${$a,b$}*, determine whether $M$ will ever overwrite a symbol $a$ by a symbol $b$ in its computation on input $x$"

I'm not looking for answers, just hints on how to even approach this problem. Like, would we declare a language which is a subset of that language, and then apply reducibility?

A TM cannot be "decidable". What you are asking is whether the language that you describe is decidable.

Hint: the language $A_{TM}=\{<M,w>: M \text{ accepts }w\}$ is undecidable even if we restrict to TMs with a binary work alphabet. Try to reduce from this problem, by utilizing only the letters $\{a,B\}$ from $\Gamma$. Then, you can use $b$ only when you need it.

Please comment if you need further hints.


How to prove every well-balanced orientation of an Eulerian graph is Eulerian? I'm trying to prove that every well-balanced orientation of an Eulerian graph is Eulerian.

I want to prove it by showing that for any two vertices $u$ and $v$, their local arc connectivities coincide, that is

$\qquad \displaystyle P_D'(u,v)=P_D'(v,u)$

for every well-balanced orientation of an Eulerian graph. How can I do this?

Your statement follows from Corollary 1 in

L Lovász, Connectivity in digraphs, Journal of Combinatorial Theory, Series B, Volume 15, Issue 2, October 1973, Pages 174-177

The Corollary says, that if you have a vertex $u$, and for every other vertex $v$ the number of edge-disjoint paths from $u$ to $v$ equals the number of edge-disjoint paths from $v$ to $u$, then we have $\text{indegree}(u)=\text{outdegree}(u)$. Since the statement is true for every vertex of the graph, the orientation is Eulerian.

The proof of the corollary and its corresponding theorem is rather technical, but self-contained, and needs less than two pages.


What happened if we implement quicksort without tail recursion? On Wikipedia, it said that

  The in-place version of quicksort has a space complexity of $\mathcal{O}(\log n)$, even in the worst case, when it is carefully implemented using the following strategies:

    in-place partitioning is used
    After partitioning, the partition with the fewest elements is (recursively) sorted first, requiring at most $\mathcal{O}(\log n)$ space. Then the other partition is sorted using tail recursion or iteration, which doesn't add to the call stack.

Below is naive quick sort:

Quicksort(A, p, r)
{
 if (p < r)
 {
  q: <- Partition(A, p, r)
  Quicksort(A, p, q)
  Quicksort(A, q+1, r)
 }
}

Below is tail recursion quick sort:

Quicksort(A, p, r)
{
 while (p < r)
 {
  q: <- Partition(A, p, r)
  Quicksort(A, p, q)
  p: <- q+1
 }
}

Algorithms above are based on this link

What if we just use in place partitioning? Is it not enough to make quicksort having space complexity of $\mathcal{O}(\log n)$?

Below is what I understand of stack call of quicksort. Do I misunderstand it?

Suppose I have sequence of number: $\{3, 5, 2, 7, 4, 1, 8, 6\}$. I use in place method in this case.

input    : 5   3   2   7   4   1   8   6
partition: 3   2   4   1  (5)  7   8   6
stack 1  : 2   1  (3)  4
stack 2  : 1  (2)
stack 3  : 1                               - stack 3 removed
stack 2  : 1  (2)                          - stack 2 removed
stack 1  : 1   2  (3)   4
stack 2  :              4                  - stack 2 removed
stack 1  : 1   2  (3)   4                  - stack 1 removed
input    : 1   2   3   4  (5)  7   8   6
stack 1  :                    (6)  7   8
stack 2  :                        (7)  8
stack 3  :                             8   - stack 3 removed
stack 2  :                        (7)  8   - stack 2 removed
stack 1  :                    (6)  7   8   - stack 1 removed
input   : 1   2   3   4   5   6   7   8 -> sorted

We need $3$ stacks at most, which is $$\log(n) = \log(8) = 3$$

If what I told above is correct, the worst case with that method is $n$, which is happened when the pivot is the minimum or maximum

input    : 5   3   2   7   4   1   8   6
stack 1  :(1)  5   3   2   7   4   8   6
stack 2  :    (2)  5   3   7   4   8   6
stack 3  :        (3)  5   7   4   8   6
stack 4  :            (4)  5   7   8   6
stack 5  :                (5)  7   8   6
stack 6  :                    (6)  7   8
stack 7  :                        (7)  8
stack 8  :                             8
stack 7  :                        (7)  8
stack 6  :                    (6)  7   8
stack 5  :                (5)  6   7   8
stack 4  :            (4)  5   6   7   8
stack 3  :        (3)  4   5   6   7   8
stack 2  :    (2)  3   4   5   6   7   8
stack 1  :(1)  2   3   4   5   6   7   8
input    : 1   2   3   4   5   6   7   8 -> sorted

we need $8$ stacks, which is $n$

That's why in place partitioning is not enough. But if I am correct, what makes it different using tail recursion?

And also, anyone can give pseudo code for iteration instead of tail recursion?

You're correct that your version with a loop doesn't guarantee O(log n) additional memory. The problem is that you have recursively sorted the partition "on the left". You ignored:

  the partition with the fewest elements is (recursively) sorted first

This is essential. It ensures that each time you make a recursive call (and lay down a new stack frame, requiring constant additional memory), the sub-array that you are sorting is at most half the size of sub-array being sorted at the previous stack level. Therefore the maximum depth of the recursion is the base-2 log n, which gives the desired bound on memory use.

In your code you permit a worst case in which you recursively sort the larger partition, having size only one smaller than the previous at each step. Then indeed the recursion depth can be n.

The way to make the code entirely iterative, with no call-recursion at all, is (as always) to use a stack data structure instead of the call stack. So instead of recursively calling to sort the small partition, you push the large partition on to the stack (by which I mean, push a pair of integers describing its location in the array) and loop around to continue sorting the small partition. When the size of the piece you're working on hits 1 you pop the stack and loop around to continue sorting that.


Constructing inequivalent binary matrices I am trying to construct all inequivalent $8\times 8$ matrices (or $n\times n$ if you wish) with elements 0 or 1. The operation that gives equivalent matrices is the simultaneous exchange of the i and j row AND the i and j column. eg. for $1\leftrightarrow2$
\begin{equation}
\left( \begin{array}{ccc}
0 & 0 & 0 \\
0 & 1 & 1 \\
1 & 0 & 0 \end{array} \right) \sim
\left( \begin{array}{ccc}
1 & 0 & 1 \\
0 & 0 & 0 \\
0 & 1 & 0 \end{array} \right)
\end{equation}

Eventually, I will also need to count how many equivalent matrices there are within each class but I think Polya's counting theorem can do that. For now I just need an algoritmic way of constructing one matrix in each inequivalence class. Any ideas?

I have made some progress towards answering this question. I am posting here in case anyone else is interested and also because this construction might have some usefulness for (directed) graphs.

Count the number of 1s in each row. Let $a_0$ be the number of rows with zero 1s, $a_1$ the number of rows with one 1 and so on up to $a_8$ which is the number of rows that have eight 1s. Obviously $\sum a_i=8$. The proposed parametrization that I have come to after trial and error is:
$$(a_1,\cdots, a_8; T, S)$$
where T is the trace of the matrix and S is $1$ if the matrix is symmetric and $0$ otherwise.
T runs from $0$ to $\sum_{i=1}^8 a_i=8-a_0$.

From my trials and errors it looks like that if two matrices are different in this parametrization then they belong to different equivalence classes, so to construct a representative in each class we just scan through the space of parameters as described above.

(Update) It turns out that this parametrization works fine for n=2 but not for n=3 as it can be seen by a brute force calculation. I still think it provides some insight on the structure of the answer and I invite people to try and modify/extend it to cover the most general case.


What are some good hints for proving non-regularity with the pumping lemma? My CS Theory Professor said that when proving that a language is not regular by the Pumping Lemma, that there are some 'tricks' for solving languages more complicated that something like $L = \{a^{n} b^{n}\mid n \in\mathbb{N}\}$. Although I know that these come with practice, I wondered if this community would have some input on the matter?

If you don't quite know what I am asking, think to calculus, when your professor used something that HE knew would get you from point a to point b that if YOU don't know, you cannot solve the problem.

Always notice that you apply the reverse direction of the implication stated in the lemma when proving non-regularity. That is for any $k\in \mathbf{N}$ you pick a word $w\in L$ (depended on $k$) that has length at least $k$ and there is no way to split the word into three parts, such that pumping the middle parts in or out keeps the word in the language. Notice that you only consider partitions where the first two words together have length $k$ or less, and of course the middle part is not the empty word.

So here are a few general ideas.

Keep in mind that you pick the word dependent on $k$, so $k$ usually appears in the word $w$ as a parameter. For example in $\{a^nb^n \mid n\ge 0\}$ you pick $w=a^kb^k$.
It is crucial to pick the right word $w$. Pick a word that has an easy structure. Make it as easy as possible.
Notice that you are only allowed to pump at the beginning of the word. Use this restriction, by choosing a word in which the first $k$ letters have a simple structure.
For unary languages like $\{a^{n^2}\mid n\ge 0\}$ pick a very large word and hope that the distance to the next word in $L$ is larger than $k$.  In the example pick $w=a^{k^2}$, the the next larger word in $L$ is $a^{(k+1)^2}$, but $(k+1)^2-k^2=2k+1$. Pumping the middle words once, gives a word that is too short. Another idea for unary languages is to pick $i$ in terms of $k$.
Don't forget to cover the case of pumping the middle word out.

You can see the (reverse direction) of pumping lemma as a two player game. Someone picks a $k$ then you pick the $w\in L$, then he splits the $w$ according to the rules, then you pick a repetition of the middle word. If the pumped word is not in the language then you win. If this game has a winning strategy for you, then $L$ is not regular.


Terminology - the reason for symbol reuse in programming languages What is the term in programming language creation that is the rationale for symbol reuse? Though potentially confused with overloading, it is not so much the application of symbol reuse, but the logical result of a limited vocabulary in the world of common symbols.

I seem to recall running in to the term when reading about the development of C - that one eventually runs out of simple symbols, so the language designers took a reasonable approach to use familiar symbols to mean different things, rather than invent new symbols for every new need. Additionally, they desired to stay within the 7-bit ASCII alphabet. The particular meaning is determined by the number/type of operators used or the broader context.

An example is from C/C++ where < is used as

a delimiter in template definitions (template <int N>)
#include delimiter, searching system headers first (#include <filename>)
a less-than comparison operator (x < y)
left bit shifts (x << n)
the ostream operator (std::cout << val << std::endl)

Point - there are cases of symbol reuse beyond strict overloading, and I believe that there is a one-word term whose definition is something like "the condition of using the same symbols for different purposes by necessity or for the sake of maintaining familiarity."

The main reason is very mundane. At the time C was designed, and
notations for many things, we did not have any form of graphics, or
very seldom (like one graphic screen for the whole university, even in major places). Actually, the main output devices were the teletype or the line-printer, with a standardized and
limited character set. Even the alphanumeric screen came later for most. No windows or mouse excepts in rare labs (Xerox).q

So that was a general constraint for everyone. For writing papers, we
could add hand-written symbols in blank spaces left by the typist. But
for more mechanized works such as programs listing (i.e. the printed
text of programs) and for execution result, we had to do with what
characters were available on the printing device.

Another problem was that increasing the number of symbols was limited
by the standard encoding in seven or eight bits. Memory was very
costly. The syntax of Fortran (the version of that time) was influenced by the format of punched cards.

Then there is a tradition. Mathematicians have been reusing symbols too. And so does natural language. We get diversity by composing them, or using context. And this was fortunate for Gutenberg, and made writing generally much easier. Compare Chinese and Latin writing.

Regarding how this could be called, I must say there is no word that
comes to my mind. Not even the feeling that there was a specific word
for that. I did quite a bit of theoretical and practical work on
programming language syntax and I do not remember this as an issue,
except as explained below.

Short of knowing what word you may look for, I can try to guess, and some
obvious candidates would be homonymy or homography. Or maybe polysemy.

A specific case, but which concerns more identifiers, is scoping
rules. In some languages they apply also to operators.

So far, that is the best I can contribute to this onomasiological issue.