What is the best way to merge cycles to minimise total weight? Suppose I have a vertex-disjoint set $S$ of simple cycles in a weighted undirected graph. So no vertex $v$ is contained in more than one cycle. A cycle $c$ is a closed path with no repeated vertices: $c=(v_1, v_2, \ldots, v_n)$, where $v_n=v_1$. Each edge $e=(v_i,v_j)$ has a positive weight $w(e)$. The weight of a cycle $w(c)$ is the sum of its edge weights: $w(c) = w(v_1,v_2)+\ldots+w(v_{n-1},v_n)$. The total weight of $S$ is the sum of all its cycle weights.

Naively I want to merge all the cycles in $S$ into a single cycle with the smallest total weight. I also want to somehow preserve most of the edges of the original cycles. I am not looking for an optimal solution, just an efficient heuristic.

I can merge two cycles by removing an edge from each one and connecting them up with new edges. For example, suppose I have two cycles $c=(v_1, v_2, \ldots, v_n)$ and $c'=(v'_1, v'_2, \ldots, v'_k)$. I can remove edges $(v_a,v_{a+1}), (v'_b,v'_{b+1})$ and add edges $(v_a,v'_b), (v_{a+1},v'_{b+1})$ to form a single cycle $(v_1, \ldots, v_a, v'_b, \ldots, v'_{b+1}, v_{a+1}, \ldots, v_1)$. This move is somewhat similar to 2opt and there are O(nk) such moves possible. I can continue merging cycles in this fashion until I reach a single cycle. Essentially I am building a minimal spanning tree that spans cycles.

Although the above procedure works in giving me a single cycle, it rarely gives me a cycle with a small weight. I can enhance this procedure by merging 3 cycles at once in a move similar to 3opt, but then I have to perform significantly more computations.

So here are my questions:

Is this a well known problem?
Can I improve the efficiency of this approach?
Is there an efficient heuristic that produces a cycle of small weight?

Attached are some examples. In the left figure a 3opt move is optimal, while in the right figure a sequence of 2opt moves is best.

Here is a numeric example that I constructed. Using the optimal merging method we get a weight of 43, while the greedy algorithm gives us a worse solution of weight 50. Even if we join the bottom cycle by removing the new edge we added (weight 10) we would still get a worse solution (I didn't draw it for clarity).

This is NOT an answer. This post is just to construct a concrete numeric example out of the left diagram in the picture in the question.

(This answer, too long to fit as a comment, was requested by a user who wanted to see a concrete numeric example which his greedy algorithm may fail. It was written about the same time when OP added a numeric example that is exactly the same except a slightly different weight assignment.)

Let $G$ be the complete undirected graph on 12 vertices $A_1, A_2, A_3, A_4, B_1, B_2, B_3, B_4, C_1, C_2, C_3, C_4$.

Let $S$ be the set of the following three simple circles.

the circle $c_A$: $A_1, A_2, A_3, A_4, A_1$.
the circle $c_B$: $B_1, B_2, B_3, B_4, B_1$.
the circle $c_C$: $C_1, C_2, C_3, C_4, C_1$.

All edges in the three circles weigh 1. The edges $A_3B_2, A_4B_1, B_3C_2, B_1C_4, C_3A_2$ and $C_4A_3$ weigh 2.
  - All other edges weigh 16.

We are allowed to merge two cycles by removing an edge from each cycle and connecting them up with two new edges, repeatedly until we reach a single cycle. The goal is to reach a cycle with the smallest total weight.

A description of an optimal solution for $S$.

Remove edge $A_2A_3$ and $B_2B_3$. Add edge $A_3B_2$ and $A_2B_3$.
Remove edge $A_2B_3$ and $C_2C_3$. Add edge $B_3C_2$ and $C_3A_2$.

We end up with the simple cycle $A_1, A_4, A_3, B_2, B_1, B_4, B_3, C_2, C_1, C_4, C_3, A_2, A_1$, which has weight $3* 2+ 9*1 = 15$.

A description of greedy algorithm on $S$ that considers all pairs of two existing cycles at a time.

Since the three cycles are symmetric, WLOG, let us merge cycle $C_a$ and cycle $C_b$. To avoid adding an edge whose weight is 16, we have only one choice. Remove edge $A_3A_4$ and $B_1B_2$. Add edge $A_3B_2$ and $A_2B_3$. The resulting circle, named $c_{AB}$, is $A_1, A_2, A_3, B_2, B_3, B_4, B_1, A_4, A_1$.
Now it is time to merge $c_C$ and $c_{AB}$. To avoid adding an edge whose weight is 16, we have only two choices. We can either remove $B_3B_4$ and $C_1C_2$ and add $B_3C_2$ and $B_4C_1$, resulting with cycle $A_1, A_2, A_3, B_2, B_3, C_2, C_3, C_4, C_1, B_4, B_1, A_4, A_1$, whose weight is $4 * 2 + 8 * 1 = 16$. Or we can remove $C_3C_4$ and $A_1A_2$ and add $C_3A_2$ and $C_4A_1$ cycle, resulting with cycle $C_1, C_2, C_3, A_2, A_3, B_2, B_3, B_4, B_1, A_4, A_1, C_4, C_1$, with the same weight 16.

Conclusion: A simple greedy algorithm does not guarantee the desired smallest weight.

I have also constructed a planar graph out of that left diagram. However, it is much more messier to describe the construction and to show the algorithms and their results.

Furthemore, it is not hard to construct an example where the greedy algorithm that considers all triples of existing cycles at a time will not reach the smallest weight. I believe, with a bit of more work, we can show a greedy algorithm that considers all combinations of a fix number of existing cycles does not guarantee the desired smallest weight.

It is quite possible this problem does not have a polynomial solution that always yields the smallest weight. In fact, it looks like this concern is implied by the OP since the question asks for "an efficient heuristic that produces a cycle of small weight".


Register Transfer Activity In a simple architecture(not considering parallel architecture) how exactly this can be performed in a single clock cycle:
P:R1 <- R2, R2 <-R1
where R1 and R2 are registers and P is a control variable.

I do not exactly understand when does this microoperation gets completed on the rising edge of the beginning of the cycle or just before clock transition.

One way this can be performed in a single cycle is through register renaming.  If the processor supports register renaming, no data needs to be moved: one simply renames which register is called R1 and which one is called R2.

If the processor doesn't support register renaming, the other option is that the data can simply be swapped between the two registers.


Can you take classical code and compile it to quantum code? Is there anyway for example, to take a trivial program from C such as:

int main() {
  int i = 1 + 1;
  return 0;
}

And compile this down to some form of Quantum Abstract High-level language, i.e. Quantum C?

From what I understand, quantum arithmetic is quite tricky business that uses QFTs. My first thought was to do the following for the example above:

Initialise two qubits and set the amplitudes like following:
$$ 0|1|0|0$$

Where 0100 = 2 in decimal.

Somehow return this quantum register.

Using the amplitudes, you could perform 32-bit arithmetic with 32 qubits?

I haven't answered the notion of creating a function or returning either.

Essentially what I'm asking is the following, can we take known quantum methods (using Unitary functions to perform calculation) and apply this to classical code and if so, how?

EDIT: I've looked further and seen a few papers on Quantum Full Adders, I assume this is the way to go for addition? Is this too much? In quantum computation books that describe quantum assembly, there is not much mention of addition.

Doubly-controlled NOT gates are universal  with respect to classical functions. Quantum computers can perform doubly-controlled NOTs. So even a quantum computer not allowed to perform fancy operations involving superposition, and not allowed to perform irreversible operations such as measuring or clearing a bit, can perform any classical computation.

For example, a quantum computer can basically directly run the gates making up a VanRentergem addition circuit:

Quantum computers are actually slightly better at reversible computation than classical computers. Classically you sometimes need an extra scratch bit to compute a function, because of permutation parity issues, but quantum shenanigans get that down to zero. Though of course emulating irreversible functions still requires introducing new scratch bits each time.


Given that A reduces to B in $O(n^2)$ and B is solvable in $O(n^3)$, solve A Suppose a problem A reduce to problem B and reduction is done in $O(n^2)$ time.
If problem B is solved in $O(n^3)$ time then what about the time complexity of problem A?

Approach:
A is reduced to B . Here reduction is done at polynomial time.
Here B is solved in polynomial time.  So A should also be in polynomial time.
Now A can not be harder than B, So I think A can be $O(n^3)$ or $O(n^2)$.  But logically if I reduced A to B and if B is $O(n^3)$ then it makes no sense for A to be $O(n^2)$, else why would I reduce it to higher complexity? So A is $O(n^3)$.
But my doubt is,  we say while reduction that A can not be harder than B then how can we decide whether it is $O(n^2)$ or $O(n^3)$.
Or is this argument only valid for P, NP classes of problem when I say A can not be harder than B or B must be at least as hard as A?
Answer given is "A is $O(n^3)$",  but why can't it be $O(n^2)$ as "A can not be harder than B" but can be of equal complexity? Or is reducibility just an argument for complexity classes?
Explain if possible how reduction actually works, and why I couldn't apply it to my problem.

You have a reduction, but you don't know what size the new problem will be.

Say you have an instance of problem A of size n. And you can reduce it to an instance of problem B in time O (n^2). If you can reduce it to an instance of size $O(N^{1/2})$ then you are fine: You took O (N^2) for the reduction, and $O(N^{3/2})$ to solve the instance of B.

If you reduce the instance of problem A to an instance of size O (n log n) of problem B, then you will take O (n^3 log^3 n) to solve the instance of B.

So the time for the reduction and the time for solving B are not enough. You need to know the size of the new problem as well. (Of course you can't create an instance greater than O (n^2) in O (n^2) time, so the worst case is O (n^6), but it could be much better).

The answer that was given (O (n^3)) is definitely wrong. It doesn't follow from the information you were given.


2-SAT reduction to Easy Puzzle Solving Introduction

I've been developing interest in complexity classes and thought I was unable to prove my problem is NP hard, so I wanted to see if it was P-hard. I wanted to see if my puzzle solving is special.  I have linked a previous question of mine to help clarify what is mentioned below.  Explained here

Random Instance of 2-SAT used for attempt reduction

  I took an instance of my problem X

  Let's say my problem X is determining if a puzzle is valid for my language

  (a∨¬b)∧(¬a∨b)∧(¬a∨¬b)∧(a∨¬c)

  Instance of X

  a = shift(L) puzzle

  ¬ a = invalid puzzle

  ¬b =  invalid puzzle

  b = shift(L) puzzle

Reduction into Shorter Instance

  (a∨¬b)∧(¬a∨b)

This boolean expression is only checking for 2-sat. Being True  (valid puzzle) or False (invalid puzzle).

My idea is that a deterministic machine will consider n^2 x n^2 puzzles as invalid if the lower right-hand box is not filled. My puzzles are solved in quadratic time when provided a puzzle with this n x n box. Any other puzzle will simply fail to be solved if it does not follow my language. I have used an algorithm that can determine in poly-time that those failed puzzles are invalid puzzles. Because, the solver will not know it as an invalid puzzle. So it will try to map it out in my language thus giving an invalid puzzle.

Question

I have the algorithm and proven that it works in poly-time, the problem is that I only know how to prove it by showing the algorithm. I just don't know how to write it out mathematically. How would I properly do this?

I'm going to need to question your premise here.

I have no doubt that you can poly-time reduce 2SAT to your custom problem. But you can poly-time reduce 2SAT to pretty much anything. The idea of "P-hardness" under poly-time reduction isn't really a useful one.

For example, let's take the following problem:

  IS-IT-ONE: given a single bit, is that bit a 1?

This problem is "P-hard" under poly-time reduction. For example, I can reduce 2SAT to it:

  Reduction from 2SAT to IS-IT-ONE

  Solve 2SAT the usual way
  If the problem is satisfiable, let $B$ be 1
  If the problem is unsatisfiable, let $B$ be 0
  Run IS-IT-ONE on $B$ and return the result

This reduction runs in poly-time, because solving 2SAT can be done in poly-time.

In other words:

Every problem in P can be poly-time reduced to any other non-trivial problem.

(Only two languages are considered "trivial" for this purpose: "return true" and "return false", aka $\Sigma^*$ and $\varnothing$.)

If you're interested in classes smaller than P, great! There are several of them, such as L: the set of problems that can be solved using a logarithmic amount of memory. It may or may not be the same as P—that's an open problem.

But if you want to talk about P versus L or NL or anything else within P, you can't use poly-time reductions any more. When talking about L, for example, you'll usually want a log-space reduction, using a Turing machine with writable tape bounded by the log of the input size. These aren't as famous as poly-time reductions, but they're still quite important in complexity theory.


Huffman coding for non-dyadic distribution I have a question regarding the methodology of Huffman coding. So, is there a Huffman coding methodology that approximates the minimum average number of bits per decimal character when the odds of information symbols are not powers of 2? I can't understand or find anything relevant

Huffman's algorithm solves the following problem. Given a distribution $P=(p_1,\ldots,p_n)$, find a prefix code $w_1,\ldots,w_n$ which minimizes the expected codeword length $$ \sum_{i=1}^n p_i |w_i|. $$
If $p_i = 2^{-\ell_i}$ then the optimal solution has $|w_i| = \ell_i$, and the resulting expected codeword length is exactly the entropy of $P$, but Huffman's algorithm works for any distribution.
If we call a distribution in which $p_i = 2^{-\ell_i}$ dyadic (there is no common term in the literature), then Huffman's algorithm "rounds" an arbitrary distribution $P$ into a dyadic distribution $Q$ which minimizes the Kullback–Leibler divergence $D(P\|Q)$.
We can get closer to the entropy of $P$ by encoding together groups of symbols. If you encode $m$-tuples of symbols together, then the expected codeword length per symbol (i.e., dividing the expression above by $m$) is at most $H(P) + 1/m$, and in particular, it tends to the entropy as $m \to \infty$. Shannon's source coding theorem shows that you cannot go below the entropy using any encoding scheme, so using Huffman coding in blocks is asymptotically optimal as the block size goes to infinity.


generalizing ball-bin problem to k-universal family I am trying to solve a question in the book on Probability and Computing by Michael Mitzenmacher, Eli Upfal. The question asks to generalize ball-bin problem for 2-universal hashing to $k$-universal hashing.

In the standard bin-ball problem setup there are $n$ bins and $n$ balls. These $n$ balls are randomly thrown (independently) in $n$ boxes and we try to find maximum occupancy in any bin. This can be done by considering a hash function $h: [n] \to [n]$. We say that ball $i$ goes in bin $h(i)$. In this case hash function comes from a 2-universal family. It is shown that for 2-universal hash family, max occupancy is $l_{\max}=1+2\sqrt n$ with probability greater than $\frac{1}{2}$. It follows with usual application of Markov's inequality. Now we try to generalize this to hash $h$ coming from a $k$-universal family and find $l_{\max}$ so that max occupancy is less than that with probability $\frac{1}{2}$.

I tried to do following: First set up indicator variable as in previous case for 2-universal problem

$X_{ij}=1$ if ball i goes in bin $j$. Now load for bin $i$ is $X=\sum_{j=1}^{n}X_{ij}$.

Since hash is now $k$-universal we try to go for Markov on $k^{\text{th}}$ moment instead of Markov (which comes from 1-st moment) to get probability bound of $\frac{1}{2n}$. In the end we apply union bound. But I am unable to simplify expression for $k$-th moment in this context to get an answer.

Definition of $k$-universal hash function

$\mathrm{Pr}(h({i_{1}})=h({i_{2}})=\cdots=h({i_{k}}))= \frac{1}{n^{k-1}}$ for any $k$ distinct elements $i_1,\ldots,i_k$.

Let $B_j$ be the number of balls in the $j$'th bin. Then
$$
\mathbb{E}\left[\sum_{j=1}^n \binom{B_j}{k}\right] =
\sum_{i_1 < \cdots < i_k} \Pr[h(i_1) = \cdots = h(i_k)] =
\frac{\binom{n}{k}}{n^{k-1}} \leq \frac{n}{k!}.
$$
Let $C_j = B_j - (k-1)$. Then
$$
\mathbb{E}\left[\sum_{j=1}^n C_j^k\right] \leq k! \mathbb{E}\left[\sum_{j=1}^n \binom{B_j}{k}\right] \leq n,
$$
and so with probability at least $1/2$,
$$
\max_j C_j^k \leq \sum_{j=1}^n C_j^k \leq 2n,
$$
hence $C_j \leq (2n)^{1/k}$, implying that $l_{\max} \leq (2n)^{1/k} + k-1$.


Why do some inference engines need human assistance while others don't? I am learning Automated Theorem Proving / SMT solvers / Proof Assistants by myself and post a series of questions about the process, starting here.

Why is it that automated theorem provers, i.e. ACL2, and SMT solvers do not need human assistance while proof assistants, i.e. Isabelle and Coq, do?

Find the series' next question here.

Validity of higher order formulae is in general not decidable and search spaces are huge, so all you can hope to do is to try to find a proof -- assuming it exists -- by cleverly enumerating the proof space (think sledgehammer, aptly named) but that is rough. Humans can play the oracle, providing the key lemmata to guide proof.

Automated provers, on the other hand, typically deal only with decidable (subsets of) logics, for instance propositional logic or subclasses of first-order logic, so they may run a long time but you know they are going to be successful eventually.

Note that there are approaches to enable proof assisstants to find those important lemmata, e.g. IsaPlanner. The tool guesses (inductive) lemmata by enumeration and random testing and then tries to prove them. By iterating the process, many lemmata of e.g. typical data type definitions can be found automatically.

Small ABC

validity -- a formula is valid it holds whatever you assign to the free variables.
free variables -- those variables that are not bound by quantifiers such as $\forall$ and $\exists$
decidability -- a (boolean) property is (Turing) decidable if there is an algorithm that answers "yes" or "no" (correctly) after a finite amount of time.
propositional logic -- also zero order logic; no quantification allowed.
first order logic -- quantification is only allowed over individuals, i.e. you can do $\forall x. P(x)$ but not $\forall f. f(4) > 0$.
higher order logic -- you may quantify over (and "build") arbitrarily complex objects, e.g. higher order functions (functions that take functions).


Prove $\{xy: x \in A \land y \in B \land |x| = |y|\}$ is context-free This is problem 2.44 from Introduction to the theory of computation by Michael Sipser.

If $A$ and $B$ are languages, define $A \diamond B = \{xy: x \in A \land  y \in B \land  |x| = |y|\}$
Show that if $A$ and $B$ are regular languages, then $A \diamond B$ is a $CFL$.

My try:
Let us define the following languages:
$$L_1 = \{ x\#y : |x| = |y| \}$$
$$L_2 = \{ x\#y : x \in A \land x\in B \}$$
$L_1$ is context-free, can be proven in a similar way to as done here
$L_2$ is concatenation of regular languages, and hence regular.
Context-free languages are closed under intersection with regular languages, and hence $L_1 \cap L_2 = \{x\#y: x \in A \land  y \in B \land  |x| = |y|\}$ is context free.
Let us define the homomorphism $h$ such that $h(\#)=\epsilon$ and as the identity homomorphism for all other symbols.
$h(L_1 \cap L_2)=A \diamond B$, and since Context-free languages are closed under homomorphism, we conclude the requested result.

Does my proof make sense?

There are many ways to prove this. Here is another one, which proves a stronger result: $A \diamond B$ is linear.

Suppose that both $A,B$ are languages over a common alphabet $\Sigma$. Let $\langle Q_A,q_{0A},\delta_A,F_A \rangle$ and $\langle Q_B,q_{0B},\delta_B,F_B \rangle$ be DFAs for $A^R$ (the reverse of $A$) and for $B$. We construct a linear grammar with a nonterminals $\{S\} \cup Q_A \times Q_B$, with the following rules:

For every $f_A \in Q_A$ and $f_B \in Q_B$, the rule $S \to \langle f_A, f_B \rangle$.
For every $q_A \in Q_A$, $q_B \in Q_B$, and $\sigma_A,\sigma_B \in \Sigma$, the rule $\langle \delta_A(q_A,\sigma_A), \delta_B(q_B,\sigma_B) \rangle \to \sigma_A \langle q_A, q_B \rangle \sigma_B$.
The rule $\langle q_{0A},q_{0B} \rangle \to \epsilon$.

In fact, your proof also shows that $A \diamond B$ is linear, since $\{a^n \# b^n : n \geq 0 \}$ is easily seen to be linear, and all the closure properties you use also hold for linear languages.


Every graph with $\delta(G) \ge 2$ has a cycle of length at least $\delta(G)+1$? I'm reading up on graph theory using Diestel's book. Right on the outset I got confused though over proposition 1.3.1 on page 8 which reads:

  Proposition 1.3.1. Every graph G contains a path of length $\delta(G)$ and a cycle of length at least $\delta(G)+1$ (provided that $\delta(G) \ge 2$).

Following the proof I can see why this would be true if G actually contains a cycle, but I keep thinking there are many graphs, like the path graph itself and connected trees, with $\delta(G) \ge 2$ but which don't have any cycles.
I found this question on the same proposition, asking to prove it. The accepted answers there seem to quote Diestel's proof verbatim, assuming G just has a cycle.

I'm pretty sure I'm missing something, so I wonder why one would choose this formulation or whether I'm simply misunderstanding the proposition. Is it assumed that graphs are cyclic unless stated otherwise? Might this be specific to the context in a way I managed to overlook?

As a reminder, $\delta(G)$ is the minimum degree, taken over all vertices of $G$.

If $\delta(G) \geq 2$ every vertex is connected to at least 2 others. This invariably leads to a cycle in any finite graph.

To see why, try to construct a path without a cycle from a graph with $\delta(G) \geq 2$. Every vertex you add is connected to either a previously added vertex (forming a cycle), or an other vertex. However, in turn, that vertex is connected... Since the graph is finite you will at some point run out of vertices to add which you haven't seen already, forcing you to form a cycle.


Is there a formal name for this graph operation? I'm writing a small function to alter a graph in a certain way and was wondering if there is a formal name for the operation.  The operation takes two distinct edges, injects a new node between the existing nodes of each edge and then adds an edge between the two new nodes.  For example:

add new nodes a and b to the graph
let edge1 = (x,y), let edge2 = (u,v)

delete edge (x,y)
create edges (x,a), (a,y)

delete edge(u,v)
create edges(u,b), (b,v)

create edge (a,b)

Your attempt is like subdivision. Actually you used two subdivision and finally you add extra edge between center of subdivision nodes.


Rigorous Proof of Insertion Sort Currently I self study CLRS book (Outside of any course, so I got no access to an instructor)

And I am stuck proving Insertion Sort, The proof in CLRS book is not so formal.

Here's the algorithm:

INSERTION-SORT(A)
   for j=2 to A.length (= n)
      key = A[j]
      i = j-1
      while (0<i and key<A[i])
         A[i+1]=A[i]
         i = i-1
      end while
      A[i+1]=key
   end for
end procedure

I tried to formalize the proof with the following pre-post conditions:

Pre-Condition: $A=A_{org}$ and $j=2$ (I.e. $A_{org}$ holds the original values of $A$)
Post-Condition: The array $A$ consists of the same elements as in $A_{org}$ but in a sorted order that is $\forall i_1,i_2\in\{1..n\}, i_1<i_2\to A[i_1]\leq A[i_2]$.

My loop invariant is:
($p$ denotes the $p$'s iteration)

$I(p)="\text{The array $A[1..j-1]$ consists of the same elements as in $A_{org}[1..j-1]$} \land \forall i_1,i_2\in\{1..j-1\}, i_1<i_2\to A[i_1]\leq A[i_2] \land j=2+p"$

Now when I try to prove the inductive step I got stuck and cannot proceed because of the nested $while$ loop and because of the informal sentence "The array $A[1..j-1]$ consists of the same elements as in $A_{org}[1..j-1]$".

Any help on how to prove Insertion Sort rigorously and how to formalize the sentence "The array $A[1..j-1]$ consists of the same elements as in $A_{org}[1..j-1]$" will be appreciated (I want my loop invariant to contain only mathematical symbols and not informal english phrases).

(BTW: I am trying to write the proof in the same style as in Susanna. Epp's Discrete Mathematics book)

Any help will be appreciated. Thanks.

Hint: first prove a loop invariant for the nested while, i.e. you need to prove that the nested while shifts to the right the elements as required to insert the j-element indexed by the outer for loop in its correct place. Then, prove the loop invariant for the outer for loop taking into account the suggestion by @Yuval and you are done.


What does 'relocation' mean? I am reading about Base & Bounds memory protection mechanism, and I noticed the use of the term 'relocation' in the context of address space, but failed to understand the meaning associated with it.

Below are some examples:

U.C Berkeley L02/CS162:

  relocating loader

Wisconsin S15/CS537

  Each process appears to have a completely private memory of size equal
  to the bounds register plus 1. Processes are protected from each
  other. No address relocation is necessary when a process is loaded.

Furthermore, I searched for the term and found only the definition on Wikipedia that wasn't very clear to me.

Does anyone have any idea?

Relocation means moving stuff from one place to another. In your case, there is a program which contains some absolute addresses, which make sense if the program is located at a certain address A. If the program is loaded to a different address B, we need to update all of these addresses, translating them by B−A. This is address relocation. A loader (a program loading another program to memory) which does this is called a relocating loader.


Incomputable sets of low degree vs Rices theorem? I have heard that there are sets that are not computable, but are lower in degree than the halting problem.
How does this not contradict Rice's theorem? Are there any concrete examples of such sets?

This is not an answer, but way too long to be a comment.  I just wanted to cite Robert I. Soare's Recursively Enumerable Sets and Degrees, Chapter V: Simple Sets and Post's Problem.

1: Immune Sets, Simple Sets, and Post's Construction
The only r.e. degrees constructed so far are $\textbf{0}$ and
$\textbf{0}'$.  Post's Problem was to construct other r.e. degrees,
i.e., to construct an r.e. set $A$ such that
$\emptyset \lt_\text{T} A \lt_\text{T} \emptyset'$.  Post's Program
for constructing such a set $A$ was to ﬁnd some easily deﬁnable property
on $\overline{A}$ (compatible with $A$ being nonrecursive) which
guarantees incompleteness ($K \not\leq_\text{T} A$).
Recall (from Theorem II.4.5) that $K$ (and hence any creative set) has
an inﬁnite r.e. set (and therefore inﬁnitely many inﬁnite r.e. sets)
contained in its complement. Post's idea for constructing $A$ incomplete
was to make $\overline{A}$ sufﬁciently "thin" with respect to
containment of inﬁnite r.e. sets so that $\overline{K}$ could not be
Turing reduced to $\overline{A}$.
1.1 Deﬁnition. (i) A set is immune if it is infinite but contains no
infinite r.e. set.
(ii) A set $A$ is simple if $A$ is r.e. and $\overline{A}$ is immune.
1.2 Proposition. If $A$ is simple then:
(i) $A$ is not recursive;
(ii) $A$ is not creative;
(iii) $A$ is not $m$-complete (i.e., $K \not\leq_m A$).
Proof. (i) $\overline{A}$ cannot be r.e., since otherwise it contains an
inﬁnite r.e. set (namely $\overline{A}$).
(ii) The complement of a creative set does contain an inﬁnite r.e. set (by
Theorem II.4.5).
(iii) If $K \leq_m A$, then $A$ is creative (by Corollary II.4.8). $\Box$
1.3 Theorem (Post [1944]). There exists a simple set $S$.
Proof. Let $A = \{(e,x) \;:\; x \in W_e \;\&\; x > 2e \}$.  Now $A$ is
$\Sigma_1$ and hence r.e. Let $\psi$ be any p.r. selector function for
$A$ (in the sense of Theorem II.1.6) and let $S = \text{rng}\; \psi$.
(Intuitively, enumerate $W_e$ until the ﬁrst element $\psi(e) > 2e$
appears in $W_e$, and then put $\psi(e)$ into $S$.) The following facts
give the simplicity of $S$.
(1) $S$ is r.e. ($S$ is the range or a p.r. function.)
(2) $\overline{S}$ is inﬁnite.  To see this, note that $S$ contains at
most $e$ elements out of $\{0,1,2,\dots,2e\}$, namely $\psi(0),\psi(1), \dots, \psi(e-1)$. Hence $e + 1 \leq \text{card}(\overline{S} \upharpoonright (2e+1))$, so $\overline{S}$ is inﬁnite.
(3) If $W_e$, is inﬁnite, then $W_e \cap S \neq \emptyset$, because
$(e,x) \in A$ for some $x > 2e$ and so $\psi(e)$ is deﬁned and $\psi(e) \in S \cap W_e$. $\Box$


Is Prediction the same as Compression? Just came across this transcript that states:

The principle is that prediction is the same thing as compression. And
what that means is that whenever you have a prediction algorithm, you
can also get a correspondingly good compression algorithm for data you
already have, and vice versa.

Even though the article gives some examples, I would like to know some answers from this community on the question: Is Prediction the same as Compression?

Fundamentally, yes. Prediction can be used to compress, and compression is a form of prediction. More generally, any learned pattern can be used to compress and vice versa.
This rabbit hole goes a lot deeper, for example I'd suggest A Tutorial Introduction to the Minimum Description Length Principle as a thorough introduction into trying to learn and choose models using compression.


$\mathsf{2EXP} = \mathsf{EXP}^{\mathsf{EXP}}$? It is clear that any language in $\mathsf{EXP}^{\mathsf{EXP}}$ can be computed in $\mathsf{2EXP} = \mathsf{DTime}(2^{2^{\mathsf{poly}(n)}})$.

My question is whether the converse is true: is $\mathsf{2EXP} \subseteq \mathsf{EXP}^{\mathsf{EXP}}$?

Consider the problem
$$A^f =
A_{TM}^f =
\{\langle M,x,t \rangle \mid
M\in DTM \text{ and }
M(x) \text{ halts and accepts in } f(|t|) \text{ steps}\}.$$

Now
$L^{\exp}$ is complete for $\mathsf{EXP} = \mathsf{DTime}(\exp (n^{O(1)}))$ and
$L^{\exp\exp}$ is complete for $\mathsf{2EXP} =\mathsf{DTime}(\exp\exp(n^{O(1)}))$.

We show that $L^{\exp \exp}$ is in $\mathsf{EXP}^\mathsf{EXP}$.

Given $\langle M,x,t \rangle$,
we simply write $\langle M,x,1^{\exp(|t|)} \rangle$ on the query tape and
ask it from $L^{\exp}$ and return its answer as output.

This algorithm is in $\mathsf{EXP}^\mathsf{EXP}$, therefore $\mathsf{2EXP} \subseteq \mathsf{EXP}^\mathsf{EXP}$.


How to prove that the erosion of a convex set by a convex set will result in a convex set? How to prove that given convex sets A and B, the erosion of A by B will result in C - a convex set, too?

I was given this question as a test-preparation, and I think it shuold be a proof, but I don't know how to prove it.

A convex set is a set where every line connecting 2 dots in the set, must be part of the set, too. Now, if I would take a convex set A, I don't see how can I use erosion on it to get a non-convex set. Every example I try to create ends up the empty set, because the "holes" in B that are suppose to the "holes" in C, make C be all-zero.

Can someone help with a direction to a proof?
Thanks

(Convexity is closed under intersection) Given a family of convex set $C_i$, where $i\in I$ for some index set $I$, then $\cap_{i\in I}C_i$ is convex.

In other words, the intersection of convex sets are convex.

Proof. Suppose two points $p$ and $q$ are in $\cap_{i\in I}C_i$. That is, for each $i\in I$, $p\in C_i$ and $q\in C_i$. Consider $L$, the line segment between $p$ and $q$. By the definition of convexity, $L\subseteq C_i$. That is $L\subseteq \cap_{i\in I}C_i$. By the definition of convexity again, $\cap_{i\in I}C_i$$ is convex.

(Convexity is closed under translation) If $C$ is a convex set, then $C_t=\{x+t\mid x\in C\}$ is also convex.

In other words, if you translate a convex set, you will get a convex set.

Proof is skipped.

(Convexity is closed under erosion) Suppose $A$ is a convex set. Let $B$ be another set. Then the erosion of $A$ by $B$ is convex.

Proof. I will let you figure out given the above two lemmas. Another hint is given in the statement itself, which is, you do not need $B$ to be convex at all.

Is the erosion of $A$ by $B$ always empty?

Imagine both $A$ and $B$ are disks centered at the origin. $A$ is a huge while $B$ is a very small. Then the "erosion" by $B$ can only remove a small stripe along the circumference of $A$. The inner part of $A$ will not be "eroded". So the erosion of $A$ by $B$ will keep a significant part of $A$.

You can also check an example on Wikipedia.


basic doubt on policy iteration consider the policy iteration algorithm for a finite state MDP. Suppose the initial policy is a stochastic policy. Now, can the optimal policy be deterministic after improvements ? Or, can we say that always the optimal policy will be a stochastic one ? Confused about this. Any ideas will be helpful. The reason I am asking this question is that in the absence of model i.e. when we need to need to use Monte Carlo methods then each of the improved policies must be a stochastic one to make sure action-value function estimates are near equal to the mean.

A stochastic policy can perfectly represent a deterministic policy by assigning probability 1 to a unique action.

Depending on how you are adjusting the policy it might take time to converge into a deterministic one, however it can get there in the limit.


Binary integer programming problem without exponential memory Consider binary integer programming problem with n variables.
I think the branch and cut algorithm takes exponential memory. What are
existing algorithms without much memory? Please suggest.

There is in general not likely to be any algorithm for this problem that will take polynomial time (and polynomial space); the problem is NP-hard, and thus not believed to allow an efficient algorithm.  If you just want polynomial space, then exhaustive search works.  You're not likely to find any algorithm that uses polynomial space and is guaranteed to be faster than exhaustive search; that would contradict the strong exponential-time hypothesis.  All existing methods are heuristics that might work well on some instances but not others.


Find all non-isomorphic graphs with a particular degree sequence I have a degree sequence and I want to generate all non-isomorphic graphs with that degree sequence, as fast as possible.

The only way I found is generating the first graph using the Havel-Hakimi algorithm and then get other graphs by permuting all pairs of edges and trying to use an edge switching operation (E={{v1,v2},{v3,v4}}, E'= {{v1,v3},{v2,v4}}; this does not change vertice degree).

Are there any faster algorithms?

To the best of my knowledge, nothing considerably better is known. For instance, your problem was part of the Combinatorics REGS 2012 program at Illinois.

With that being said, I can think of three possible engineering approaches that might work:

Use what you have (perhaps as a baseline for benchmarking other approaches).
Use the suggestion of Yuval: use the configuration model to generate all such graphs, and check for isomorphism between them. For instance, you can use nauty that is fast and highly optimized.
If your degree sequences are of length $n$ for some small $n$ (or you can afford to do a lot preprocessing), generate all $n$-vertex graphs. For this, you can either download them all from McKay's homepage, or use e.g., geng. If you have additional information, you might use an even more specific generator such as plantri (geng has options too). Once you have the graphs, iterate over them and check whether they have the right degree sequence.

By the way, Sage also has much of this functionality built-in, see e.g., here (for instance, search for "Generate all graphs with a specified degree sequence").


Transforming NFA into DFA In the examples I was given I have the following NFA diagram:

Then it gives the conversion process

Could someone explain to me the process of obtaining the second column:

{1,2,4} = a{1, 2, 3, 4}, b{1, 4, 5}

This is the standard procedure for converting NFAs to DFAs. The first row should be read as "If you know you're in one of the states $0$, $1$ and $4$ and you read an $a$, you'll have to be in one of the states $1$, $2$ and $4$; if you read a $b$, you'll have to be in one of $1$, $4$ and $5$." The other rows are similar.


If $L$ is CFL and $\overline{L}$ is CFL, then is L regular? I've seen in previous exams that professors marked the theory as correct:

  If $L$ is CFL and $\overline{L}$ is CFL, then L is regular.

I just don't see how this would work. How would we prove such a thing? I also can't come up with contradicting languages.

As Shaull noted in the comments, $\{a^n b^n\}$ works. The language is trivially context-free but not regular, so I'll show the complement is context-free. A word which is not of the form $a^n b^n$ is either $a^n b^m$ where $n\neq m$, or not of the form $a^n b^m$ at all. So

$(a+b)^{\ast}-{a^n b^n}=\{a^i b^j: i \neq j\} \cup ((a+b)^{\ast}-a^{\ast} b^{\ast})$

which is a sum of context-free language $\{a^i b^j: i \neq j\}$ and the complement of $a^{\ast} b^{\ast}$ which is a regular language.

Another way to see it is that $\{a^n b^n\}$ is a deterministic context-free language, which is a class closed under complement. In other words any nonregular DCFL is a counterexample to the question.

I'll leave the following question to the reader:

  Suppose $L$ and $\overline L$ are CFLs, is $L$ a DCFL?


Help need to learn Quantum Computation and Information I want to learn quantum computation and information. I am studying from Nielsen & Chuang book for this.
Is there any online vedio (lecture series) starts from
basics of quantum computation and information up to factorization, discrete log, search etc?

I haven't watched them myself, but you could probably do worse than Michael Nielsen's videos, Quantum Computing for the Determined.

I'd recommend also that you look online for written lecture notes; there is a very strong culture in the field of having students scribe notes which then have a habit of finding their way online. These can sometimes vary substantially in quality, but often the lecturer will take them and edit them, resulting in quite a good set of notes. Just as an example that I grabbed off the top of Google, Ronald de Wolf's lecture notes seem fairly comprehensive; but others surely exist, and if you find the going hard with those notes, you will probably find one set of notes which better suits your learning style.


Extracting Boolean Function using Machine Learning How can machine learning help extract a Boolean relationship in a given binary input-output data set?

Let us assume that the given data set is exhaustive - ie. it cover all possible input combinations, can we derive the boolean relationship between inputs and outputs? (Say we assume x inputs and 1 output)

Further, if the dataset is not exhaustive, can we predict the output for "(n+1)"th input vector if we know outputs for the previous "n" input vectors? (in other words, can we "learn" how the function behaves?)

I'd greatly appreciate if you can share what approach should I devise to work on this problem, and if possible, about any on-going research on this topic?

UPDATE: As rightly pointed out by @D.W.
Several heuristics exist to tackle such NP-hard problems in logic synthesis and minimization.

The essence of my question is to find out if any Machine Learning algorithm can be adopted and developed, which potentially performs better than the currently known heuristics when deployed at scale.

And importantly, if any "recent" advances in ML can be of help in developing tools for Electronic Design Automation?

If you have an exhaustive list of all possible inputs, and the output for each, you already know the relationship between the input and output.  You don't need fancy machine learning.

If you want to explicitly write a formula for this relationship, it is easy to write a DNF formula (each clause corresponds to a single input-output pair, i.e., a single row in the truth table).  It's also easy to write a CNF formula, using a similar construction (each clause corresponds to a single input where the corresponding output is false).

If you want to find the minimal-length formula for this relationship, that is probably NP-hard (in fact it is "even harder" in some sense).  However there are heuristics.  Read about Karnaugh maps, Quine-McCluskey, the Espresso heuristic, and the fields of logic synthesis and circuit minimization.

I don't expect machine learning to perform better than existing methods.  Existing methods have a lot of intelligence built in, based on this specific problem.  ML methods wouldn't be able to benefit from any of that.

Ultimately, if you want to know whether some machine learning method performs better than standard methods, the only way to know for sure is to try it.  But I don't expect it to yield useful results, without new insights.


Sorted array with odd indexed elements swapped randomly A sorted array $\mathcal{A}$ with even number of elements is given. Consider $\mathcal{A}$ be partitioned from the middle such that both parts ($\mathcal{A}_1, \mathcal{A}_2$) contain equal number of elements. We choose some arbitary odd indexed (index with $1,5,9$ etc.) elements from $\mathcal{A}_1$ and swap them with some other random odd indexed elements of $\mathcal{A}_2$. Even indexed elements of $\mathcal{A}$ remain untouched.

We need to device an algorithm to check whether an element $\mathcal{x}$ exists in $\mathcal{A}$ in $O(\log n)$ time.

Hint:

Use binary search to find the possible locations of $x$ in the original array.
If you find two even elements $y,z$ with $y<x<z$ and the element between them $w$ is does not belong there, then $w$ might have been switched with $x$. Find the proper position of $w$ using binary search and look if $x$ is there.


Validity of Algorithm for Testing Two Floating Point Numbers This question is related to the epsilon- (or delta- if you prefer) test for floating point equality. But my question is not how to do it. Instead I have a related algorithm for testing equality, and I would like feedback as to what might be wrong with it.
The idea is to take the quotient of two floating point numbers and compare it to one. This eliminates the difficulty of choosing a value for epsilon. I have tested it extensively and am happy with the results. Here is a sample implementation in Java.
public class DoubleEquals
{
    public static final double  EPSILON = 1e-14;

    public static boolean equals( double param1, double param2 )
    {
        // Accounts for 0, +/-INFINITY;
        // if both values are NaN the result will be false
        boolean result  = param1 == param2;
        if ( !result )
        {
            double quot = param1 / param2;
            result = quot > 0 && (1 - quot) < EPSILON;
        }

        return result;
    }
}
```

There is one method to compare floating point numbers for equality, which is both very simple and correct: You use the equality (==) operator.
There is another method to compare whether floating point numbers are identical, which unlike the equality operator would find that -0 and +0 are not the same, and that NaNs with the same bit pattern are the same: Use memcmp. (Don't do this if your compiler stores 80 bit long double into 128 bits).
What you are talking about is the question: "Are these two numbers so close together that their difference could be due to rounding errors alone", and another question would be "Are these two numbers so close together that we don't care that they are different".
Swift has decided to put an operator for the latter into its standard library. This considers floating numbers with an n bit mantissa "as good as equal" if the difference is at most the last n/2 bits.
So first don't call your function "equals", because that is a lie. Call it "almostEqual" or something like that. Then make sure that it returns true without failure whenever x == y, that almostEqual (x, y) == almostEqual (y, x) for all pairs x, y, and that it returns the same result if you scale x, y both by the same power of two (unless this produces overflow or underflow).
Be aware that you cannot guarantee that almostEqual(x,y) and almostEqual(y,z) implies almostEqual(x,z). This also implies that you cannot make it compatible with any hash function.


Regular Expressions. Reversal of concatenated strings verification What is the significance of reversing string $v$ in the following? Can't the string $v$ contain exactly what is in the string $v^R$, since you are just choosing from the alphabet $\Sigma^*$? I don't fully comprehend this question.

  Consider the language
  $$L = \{uabcv\mid u,v\in\Sigma^*\}$$
  over the alphabet $\Sigma = \{a,b,c\}$.  Is it true that reversal of $L$ is the set
  $$L_2 = \{ucba(v^R)\mid u,v\in\Sigma^*\}\,?$$
  (Please note that the parentheses are used only to clarify that it is only the string $v$ that is reversed.)

Any help is appreciated.

For the first part,
$$L=\{aw|w\in\{a,b\}^*\}$$
and
$$L_R=\{wa|w\in\{a,b\}^*\}$$

It is true that $L_R$ is the reverse of $L$. $L$ represents the set of strings starting with the symbol $a$, and $L_R$ represents the set of strings ending with the symbol $a$. Note that for some $w$ such that $aw\in L$, you only need to find some $w'$ such that the reverse of $aw$ is $w'a$. You do not need $w=w'$, so your example does not counter the statement.

For every string $w\in\Sigma^*$, where $\Sigma=\{a,b\}$, reversing the characters of $w$ must also belong to$\Sigma^*$. Thus, every string $aw$ in $L$, there is a string which is its reverse in $L_R$ and vice-versa.

For the second part, there is no significance in reversing $v$. It might be intentionally a part of the problem statement.


Solving or estimating the recurrence $T(n) = x + T(n-\log_2 n)$ I am trying to either solve or find a tight bound $\Theta$ for the following recurrence relation:

$$T(n) = x + T(n-\log_2 n)\,.$$

For some nonzero constant $x$ (we can suppose it to be 1, for simplicity). Thus far, I have been able to prove the following:

\begin{align*}
T(n) &\in O(n)\\
T(n) &\notin \Omega(n)\\
T(n) &\in \Omega (n^p)\quad \forall p \in (0,1)\,.
\end{align*}

But I am now stuck, I cannot figure how to either solve the recurrence or find a $g(n)$ to prove a tight bound: $T(n) \in \Theta(g(n))$. May somebody know how to solve this?

If you want to know, this recurrence arises in the following context: in maxiphobic heaps[1] where the "weight" of the heap is its number of nodes, the merge operation is recursive, but its complexity is $\Theta(\log n)$, even in the worst case. If the meaning of the weight is changed to mean the height of the heap, the complexity for average random inputs remains $\Theta(\log n)$, but you can construct a worst-case pathological input where in each step merge calls recursively itself with almost all of its input, minus a degenerate subtree of at most $\log_2 n$ elements, approximately. I want to find a tight bound for the complexity of that worst case.

[1] C. Okasaki, 2005. Alternatives to Two Classic Data Structures. In Proceedings of 36th SIGCSE Technical Symposium on Computer Science Education, pp. 162–165. ACM. (ACM Digital Library)

Assuming an appropriate base case, it is easy to see that $T(n) \geq (n/\log_2 n) \cdot x$, since at each step we subtract at most $\log_2 n$, and thus it takes t least $n/\log_2 n$ steps to reach zero.

In the other direction, denote by $m$ the current input ($n$, $n-\log_2n$, and so on). As long as $m \geq n/2$, the input decreases by at least $(\log_2 n)/2$ at each step, and so it takes at most $2n/\log_2 n$ steps to reach $n/2$. Then it takes at most $4\sqrt{n}/\log_2 n$ steps to reach $n^{1/4}$, and so on. After $\log\log n$ such phases, $m$ will be $O(1)$. This gives an upper bound proportional to $x$ times
$$
\frac{2n}{\log_2 n} + \frac{4\sqrt{n}}{\log_2 n} + \cdots \leq \frac{2n}{\log_2 n} + 4\sqrt{n} + 8n^{1/4} + \cdots + 2\log n \cdot n^{1/\log n} = \\
O(n/\log n + \sqrt{n} \log\log n) = O(n/\log n).
$$
Thus $T(n) = \Theta(xn/\log n)$.


Quantum computers and computable functions A quantum computer can possibly calcluate computable functions faster, but it can't calculate functions which a normal computer can't calculate?

If a function is not computable? Does this mean it will never be computable? Even if we change the axioms which our mathematical system is based on or we find a contradiction in it? Are we never be able to find something in the universe which can calculate these functions?

Is that right?

You are correct, a quantum computer defined properly: with a finite gate set and rational (you can relax this to algorithmic, but that can be bit circular) transition probabilities will get you only the computable (by a classical Turing machine) functions. Although it might compute them faster than a classical computer.

To get a hyper-computer (something that computes functions that are not computable by a classical Turing machine), you need to sneak something that usually feels 'non-finitary' into the model -- the most common suspect is a non-computable real number -- which your model then extracts its power from. You can make these sort of models of computation from modifying classical or quantum systems. If I recall correctly, the first definitions of quantum TMs were actually accidentally hyper-computing because they allowed non-algorithmic phases in their operators.

To turn to your last question of "Does this mean it will never be computable?", what you are asking about is the Church-Turing thesis. It states, in its vaguest form, that anything that is computable is computable by a Turing Machine. Most people believe this thesis.

  Even if we change the axioms which our mathematical system is based on or we find a contradiction in it?

Here you are asking about Kleene's variant of the Church-Turing thesis. Since the CT-thesis cannot be 'proven' (we can always continue to disagree about the first 'computable' in the vague definition), we have to rely on mathematician's beliefs and philosophical discussion. Most mathematicians believe that in any reasonable axiomatic system, any 'finite-feeling' model of computation will be at most Turing-complete.

  Are we never be able to find something in the universe which can calculate these functions?

It is important to note that here you are asking a completely different (but related) question than the previos. You are asking about the physicalist variant of the Church-Turing thesis. Although historically this was not the preferred interpretation of the CT-thesis, from my experience it is now the most common way of reading the thesis. Again, here most computer scientists and physicists familiar with CS believe that all functions computable by machines in the physical world are Turing-computable.


How to represent a recurrence that increments by one at each tree level? I am using a merge sort like algorithm. Each level of the tree has a different Big O runtime. The runtime as a whole can be represent as follows:

$$O(\sum_{i=0}^{log(n)}2^{\frac{n}{2^i}} * 2^i)$$

I am trying to find the recurrence. Since this is like merge sort we can start with the classic 2T(n/2). However, I am unsure how to write what comes after 2T(n/2) in the recurrence below: $$T(n) = 2T(n/2) + O(2^{\frac{n}{2^i}} * 2^i)$$
       i++ each recurrence

I am aware that this is exponential time. My assumption is that this all simplifies to O(2^n). Is that assumption correct?

Bogo Sort + Merge Sort Example

As each time $n$ is divided by $2$ and $2$ multiplied by 2, it should be:
$$
T(n) = 2T(\frac{n}{2}) + 2^n
$$
Now, if you expand it:

$$
T(n) = 2(T(\frac{n}{2^2}) + 2^{\frac{n}{2}}) + 2^n = 2T(\frac{n}{2^2}) + 2 \times 2^{\frac{n}{2}} + 2^n
$$

How can we guess $T(\frac{n}{2})$? Because $i$ is changing from $0$ to $\log{n}$. If we suppose $T(0)$, when $i = 0$, it will be the not recurrent part of the equation. Hence, we found that it is $2^n$. How did we find we should multiply by $2$? Because each time the relation is multiplied by $2$ and we have a power of it in each iteration. Hence, it should be multiplied by the recurrent part of the relation, which is $T(\frac{n}{2})$ here.

Eventually, form the mater theorem, we can conclude that $T(n) = \Theta(2^n)$.


Sequence of N operations Amortized Analysis A sequence of $N$ operations is performed on a certain data structure.

The $i$-th operation costs $i$ if $i$ is a power of 2, else it costs 1.

How can I calculate the amortized cost for every operation using the potential function method?

How about this. Assume we maintain a binary counter $C$ that counts the operations executed so far. Let $D_i$ be the data structure after the $i$-th operation. We then define as potential $\Phi(D_i)$ number of $\tt 1$-digits in $C$. As usual $c_i$ denotes the actual costs, and $\hat c_i$ the amortized costs.

If $i$ is not a power of two, then we have
$$ \hat c_i = c_i + \Phi(D_i) - \Phi(D_{i-1}) \le 2 .$$
This is true since the addition of a $\tt 1$ on $C$ will turn one digit from $\tt 0$ to $\tt 1$ while possibly turning some digits from $\tt 1$ to $0$.

If $i$ is a power of two then clearly
$$ \hat c_i = c_i + \Phi(D_i) - \Phi(D_{i-1})= i + 1 - (i-1) =2 .$$

As a final comment, the amortized costs do always depend on the potential function. So another potential function yields different amortized costs.


Interrupts and polling Are Interrupts really just an abstracted form of polling?

I saw a system-file-watcher library that stated it used polling, as opposed to listening for events. Is the .NET framework SystemFileWatcher class just an abstraction of polling?

In a computer, interrupts are stacked, and the CPU checks the interrupt stack after every cycle, so this is pretty much polling, right? - Albeit more efficient than checking every individual device.

Not really.

Polling requires CPU cycles to poll a device and respond if needed. Detecting interrupts takes up no extra CPU cycles and is almost always done in parallel with instructions being executed. CPU cycles are only used up in servicing the interrupt.

Also, with polling, you have a control over how and when you poll devices whereas interrupts are generally out of sync with the program (or at least, you cannot exert too much control over when they arrive).

The mindset behind polling driven and interrupt driven code/architecture is entirely different.


Infinite union of regular language Deciding if the infinite union of a set of regular languages is regular is undecidable.

By closure property of regular languages, regular language is not closed under infinite union so is the above problem undecidable?

Since every language is a countable union of regular languages, you're basically asking whether one can decide whether a given language is regular. Thus, for any reasonable representation, this task will be undecidable.

Consider the following representation of your problem, say a machine $M$ represents an infinite series of regular expressions if given input $i$, $M$ produces a regular expression $r^M_i$. You now ask whether the following language is decidable:

$L=\left\{\langle M\rangle \Big| \text{$\bigcup\limits_{i}L\left(r_i^M\right)$ is regular}\right\}$

If $M$ does not represent a series of regular expressions, i.e. on some input $i$, $M(i)$ is not a valid regular expression, then $\langle M\rangle\notin L$. $L$ is undecidable, since you can reduce the language $L_R=\{\langle M\rangle | \text{$L(M)$ is regular}\}$ to it ($L_R$ is trivially undecidable by Rice theorem). Your reduction will, given $M$, generate a machine $M'$ which on input $i$ will simulate $M$ on all inputs of length $\le i$ for $i$ steps, and according to the result, will generate a regular expression which corresponds to the union of all words that were accepted during this simulation. Clearly $\bigcup\limits_{i}L\left(r_i^{M'}\right)=L(M)$, and the validity of the reduction immediately follows.


Confusion regarding dependencies Let say we have a relation with 5 attributes {A, B, C, D, E}. Let say we have two candidate keys as A and B,C. Let us say we have a partial dependency as B -> E with regards to the candidate key B,C. The database designer decides that A will be the primary key of the relation. Now since we had B -> E, will it be called a partial dependency or a transitive dependency? Is the relation 2NF or not even 2NF?

As the definition of the 2NF is:

  A functional dependency on part of any candidate key is a violation of 2NF. In addition to the primary key, the relation may contain other candidate keys; it is necessary to establish that no non-prime attributes have part-key dependencies on any of these candidate keys.

This schema is not in 2NF.


What's the true meaning of $(a + b)^\omega$ in regular expression I'm starting to dabble in language theory, regular expression & infinite words.

I'm not quite sure I completely get the meaning of this expression:

$(a + b)^\omega$

$^w$ meaning infinite repetition, I'm not positive it's standard syntaxe or just our class.

My main question is - do I have to "settle" on either a or b after some position in the infinite word? $abbbbaab^\omega$ would be fine but not $abbbbaa[ a | b]^\omega$ (e.g. I keep having either a or b infinitely)? My understanding is that an English translation would be "you must either have a, or b, at any given position indefinitely". So the + would be like a or condition, essentially.

Expending on that, then $((a+b)(c+d))^\omega$ would accept any alternating patter of (a or b)(c or d), e.g. things like acbcbcadad... but again wouldn't have to "settle" on either $(ac)^\omega$ or $(ad)^\omega$ or $(cc)^\omega$ etc...

The notation is standard but it's an omega ($\omega$, the first infinite ordinal; basically, the infinity in "There are infinitely many natural numbers"), not a $w$ (the 23rd letter of the Latin alphabet).

Both as a closure operator applied to languages and as an operator in $\omega$-regular expressions, $^\omega$ is directly analogous to ${}^*$, except it denotes the concatenation of infinitely many things, rather than any finite number of them.


Which object-oriented programming language is the closest to the untyped sigma-calculus? I'm wondering which of the dynamic object-oriented (or prototype-oriented) languages (like JavaScript, Ruby, Python, etc.) can be considered as the closest to Abadi and Cardelli's untyped sigma calculus?

JavaScript looks perfectly like untyped sigma calculus.

It supports first-class citizens, described in paper concepts in terms of prototypes, closures, clone (called split), (dynamic) method override, objects dynamic creation, extension, delegation, subsumption, object fragments and polymorphism (which is understatement in terms of this language). Essentially it supports every operation described in the paper.

Since it uses prototype based inheritance the update of methods is one of the basic operations in this model. It recently started to support hierarchical class inheritance (but it was not needed, since emulating any kind of hierarchical behavior is possible with very short code).

Origins of Cardelli work predates the creation of JavaScript, but also worth mentioning is that JavaScript description as general purpose any language emulator with very short code to support such was described by Don Knuth (which predates Cardelli work, no connection between Knuth paper and creation of JS was ever made in any direction, but both papers exactly describe the JS properties).

Other languages fail with method backups or dynamic method override. But this is not the case for other prototype based languages (at least the most populqr ones), which fully support $\varsigma\text{-calculus}$ (take for example "Self").


Is it possible to add every word in a file to a set in $\mathrm{O}(n)$ time? The Problem:

I am currently analyzing a simple program that takes a file of length $n$, splits it into its individual words (seperated by white space) and adds those words to a set:

def file_word_set(name):
    with open(name) as f:
        res = set()
        words = f.read().split()
        res.update(words)
        return res

My Analysis:

Splitting a file of length $n$ into individual words takes $\mathrm{O}(n)$ time. The splitting will produce a list of $k$ strings where $0 \leq k \leq n$. These strings will be of varying length. Inserting a string into a set can be done in $\mathrm{O}(m)$ time where $m$ is the length of that string. This is because we must iterate through each of the characters of the array in order to determine its location in the underlying hash-table. Since the total length of all $k$ strings is no more than $\mathrm{O}(n)$, we will need to consider $\mathrm{O}(n)$ characters in total when building the set. Therefore the function takes $\mathrm{O}(n)$ time.

Is this correct?

Splitting

While splitting you have to touch every element once to see that is a delimiter or not. So it $\in \mathcal{O}(n)$

Assuming a Hash-based Map is used;

  cost of Inserting a string

It is $\in \mathcal{O}(1)$ but if you consider the hash function as not a constant then you have to analyze the hash function itself. When we are talking a hashmap, the string size, usually, is not considered.

  Total insert cost

It is $\in \mathcal{O}(n)$,

  Total cost

It is the sum of all = $ \mathcal{O}(n) + \mathcal{O}(n)= \mathcal{O}(n)$


MIPS with one read port in the register file? I'm studying the MIPS multi-cycle datapath, and I'm wondering what would happen if there was only one read port in the register file for certain instructions.

First, for R-type instructions, I know that it takes in 2 registers(for example, with 'add', rs and rt are both passed into read-port 1 and read-port 2 in the register file) and then added in the ALU. With only one read-port, the fetch step will be the same amount of time (fetching the instruction won't be affected), but the execution step will take 2 clock cycles instead of 1, because there will be a clock cycle for each time a register is passed in. Then, the other steps will also take the same amount of time after that.

But what about the load and store instructions? The register file takes rs and rt into the read-ports normally, but for example, sw STORES it's value in rt. Will this mean that the execution step won't be affected because rt will be passed into the "write register" port? Could anyone clear this up for me?

For your MIPS CPU with 1read + 1write register file :

ALU instructions will last two cycles as you describe.
Load instructions can be executed in 1 cycle (with data in cache, etc...)
Store instructions must be split in two cycles to get the two source registers.

Another example, in SPARCs, STORE R1,[R2+R3] require two cycles with a 2R1W register bank, whereas LOAD [R1+R2],R3 can be executed in 1 cycle.


Given the phrase "Where NONE of the following are TRUE" and two statements how should a boolean logic be composed? Let's have two statements

(value > 10)
(value < 25)

And a list of items with the following values

10
20
30

This is what a truth table would give

Item  Value  (value > 10)  (value < 25)
----  -----  ------------  ------------
1     10     FALSE         TRUE
2     20     TRUE          TRUE
3     30     TRUE          FALSE

Example 1

Where ALL of the following are TRUE
   value > 10
   value < 25

This one is easy and we get the following

Where (value > 10) AND (value < 25)

The result is then a single value of 20

Example 2

Where NONE of the following are TRUE
   value > 10
   value < 25

This is where I am not sure of what to generate.

This would be "simple" as it is only a NOT of the whole expression

Where NOT ((value > 10) AND (value < 25))

However, the result is then two values (10 and 30)

From what someone would think of NONE of the two statements would be something like:

Where NOT ((value > 10) OR (value < 25))

And the result would be that no items are produced.

What is the correct meaning of NONE here?

The correct meaning is:

"Where (NOT (value > 10)) AND (NOT (value < 25))".

Applying one of the De Morgan's laws:

1) P AND Q <=> NOT( (NOT P) OR (NOT Q) )
2) P OR Q <=> NOT( (NOT P) AND (NOT Q) )

we get:

"Where NOT ( (NOT(NOT(value > 10))) OR (NOT(NOT(value < 25))) )"

and the equivalent final result is

"Where NOT ((value > 10) OR (value < 25))" :-)


Minimal DFA for language of all strings over $\{a,b\}$ whose penultimate symbol is $b$ Design a minimum state deterministic finite automata for accepting those strings over the alphabet $\{a, b\}$ whose last but one symbol is $b$.

Note that we have at least three states:

The second last character is $b$ so the tail 2-substring is either $ba$ or $bb$.
The last two characters are $ab$ (read at least one more character).
The last two characters are $aa$ (read at least two more characters).

which leads to the following DFA:

The above DFA contains minimal number of states if and only if it equals its minimization. Following this page in DFA Minimization using Equivalence Theorem we have

$P_0 = \{(1, 2), (3)\}\\
P_1 = \{(1), (2), (3)\}$

In $P_1$ we used the fact that one single character may lead state 2 to an accepting state, whereas 1 does not "reach that far". Since $P_1$ gives no opportunity for further refinement, we may stop and we know that the DFA is minimized.


Which algorithms can not be parallelized? Is there any algorithm which is very difficult to parallelize or the research is still active?

I wanted to know about any algorithm or any research field in parallel computing.

Anything, I searched for, has a 'parallel' implementation done. Just want to do some study on any unexplored parallel computing field.

This article gives a number of problems that are easy to solve sequentially but difficult to parallelise: http://en.wikipedia.org/wiki/P-complete

The circuit value problem ("given a Boolean circuit + its input, tell what it outputs") is a good starting point — easy to understand, easy to solve with sequential algorithms, and nobody knows if it can be parallelised efficiently.


Hill Climbing Search With the hill-climbing search algorithm, I do not quite understand how the algorithm can get stuck at "plateaus/ridges." Moving one step back, what exactly denotes a "maximum" or "minimum" in a problem? For instance, in the 8-queens problem, it is said that it hits a local minima 86% of the time. Can someone please elaborate more on how and what denotes maximas and minimas and given this, how the algorithm can get stuck at a plateau.

What I know so far is the following:

Expand the current state, find the best neighbor, and that becomes the new current state.
No looking beyond one step from where you are, no memory

Consider the general problem of maximizing such function $f$ on a domain $V$. Now suppose there is a graph $G=(V,E)$ on $G$. A local maximum is a vertex $v$ such that $f(v) \geq f(u)$ for all neighbors $u$ of $v$. A global maximum is a vertex $v$ such that $f(v) \geq f(u)$ for all $u \in V$. Hill climbing can get stuck at a local maximum which isn't a global maximum. Perhaps you can construct such an example yourself.

In the 8-queens problem, the domain $V$ is the set of chess boards with k non-conflicting queens on them for $k=0$ to $k=8$. There is an edge between two such boards if you can reach one from the other by placing one queen. The fitness function is simply the number of queens on the board. Simple hill climbing gets stuck if it ends up in a board with fewer than eight queens where no more queens can be placed, because there is no edge that goes to a board with more queens on it.


how to understand the occurrences of free variables? I am thinking that many example only takes free variable with one occurrence, such as  $(\lambda x.x )y$ where $y$ is free.

can we say $y y $ is a $\lambda$-term and two $y$ are same free variable?
I did not see such examples so far, just wondering.

A possible definition (From Lambda-Calculus and Combinators):

  Definition 1.11 (Free and bound variables) An occurrence of a variable
  $x$ in a term $P$ is called:

  bound if it is in the scope of a $\lambda x$ in $P$
  bound and binding, iff it is the $x$ in $\lambda x$
  free otherwise

Let's define the set of free variables $FV$:

The free variables of $x$ are just $x$, that is $FV(x) = \{x\}$
$FV(\lambda x. P) = FV(P) \setminus \{x\}$ (since $x$ is bound)
$FV(st) = FV(s) \cup FV(t) $

And maybe you just need some examples:

$y$ is free in $y$
$x$ is free in $(\lambda x.x)x$ (Try to work out why)
$y$ is free in $(yy)$.


Maximum depth of a B+ tree Given $K$...# key values, $n$...# pointers in a node.

I read somewhere, that the maximum depth is defined as $\lceil\log_{\lceil\frac{n}{2}\rceil}(K)\rceil$. However, it is not correct, as I can come up with a counterexample. When the tree is minimum filled, it won't work.
E.g.:

This is a valid $B^+$-tree, the root has at least two childs, each inner node has at least $\lceil n/2 \rceil$ childs and each leaf has at least $\lceil \frac{n-1}{2}\rceil$ record. So, $n=3$ and $K=4$, then $\log_2(4) = 2$. Now, when you fill up the leafs: [1,1,2,2,3,3,4,4], then it is again a valid tree and $K=8$, hence $\log_2(8) = 3$, but same depth.

Notice: I am looking for a formula or explanation but for a $B^+$-tree not a $B$-tree. A source would be nice.

Since you're not sure where you read it, is it possible you are misremembering slightly what the result was?

In a B+ tree, we require that every node has between $n/2$ and $n$ children.  In other words, every node is required to have at least $\lceil n/2 \rceil$ children.  This means that any tree of depth $d$ where all leaves are at depth $d$ must have at least $\lceil n/2 \rceil^d$ leaf nodes.  Thus, any such tree must have depth at most $\lceil \log_{\lceil n/2 \rceil} L \rceil$, where $L$ is the number of leaf nodes.  Perhaps this is what you read.

Note that the number of key value is related  to the number of leaf nodes: $\lceil b/2 \rceil -1 \le L/K \le b-1$.  This would let you get a similar result in terms of $K$, for a full tree with all leaves at the same level.

Detail: Here I have ignored that the root is usually allowed to have as few as 2 children.  This has only a small effect on the answer.


Which Tree traversal String is unique? Assume we have a tree and we want to serialize it.

Example:

Tree:
      1
     / \
    3   2
   / \ / \
  5  N N  N
 / \
N   N

can result as:

"1,3,5,N,N,2,N,N, N", // Pre Order serialization;
"N,5,N,3,N,1,N,2,N", // In Order serialization;
"N,N,5,N,3,N,N,2,1", // Post Order serialization

I would like to know, which one of these three serializations is unique for all trees and why ?

Preorder traversal:

This traversals always yield unique binary trees. (proof for this remains. To me it seems that it is correct due to procedure to construct tree that follows. However it might not be the case.)

For instance consider traversal sequence $6,5,N,N,5,3,N,N,2,N,N$.

We can proceed as follow to construct binary tree.

  First symbol is always root of tree.

Root will always be identified uniquely.

  Try to parse remaining part of input recursively(This will be our left sub-tree). When one sub-tree is parsed  return.

Here this left sub-tree parsing will start with input $5,N,N,5,3,N,N,2,N,N$ and will return after input $5,3,N,N,2,N,N$ left to be processed.

  Try to parse yet remaining part of input recursively(This will be our right sub-tree).

Post-order traversal: This is similar to pre-order.

inorder traversal: This does not always yield unique binary tree. Here is counterexample.

Consider preorder traversal $N,5,N,6,N,3,N,5,N,2,N$. And following two binary trees.

        6                    5
       /  \                /  \
      5    5              6    2
     / \  /  \           / \  / \
    N  N 3    2         5   3 N  N
        / \  / \       / \ / \
       N   N N  N     N  N N  N


Visualizing a Non Deterministic Decider I know that we can visualize a Non deterministic TM as a TM which splits into multiple copies of itself whenever it sees a non deterministic path (Yes, I also know that this is just a visualization and is usually used by beginners like me for understanding non determistisism).

Further, I also know that a Decider is a TM that halts on all possible inputs.

Now, my question is how can I visualize a Non determistic Decider? Does a non-determistic decider mean a TM where

All the copies must halt, (OR)
At-least one copy halts.

Kindly explain in detail why so. Thanks.

For a nondeterministic decider the answer is At-least one "copy" halts on a "yes"/"no" state; copy-paste from another answer:

for a Nondeterministic Turing machine (NDTM) processing an input $x$ there can be infinite computations (paths); some of them will halt on the accept state $q_Y$, some will halt on the reject state $q_N$, some will run forever;

a string $x$ is accepted by a Nondeterministic Turing machine if at least one of its computations halts on the accepting state $q_Y$;

we say that "$M$ accepts $x$ in $m$ steps" if $M$ accepts $x$ and $m$ is the length of the shortest accepting computation on input $x$;

a language $L_M$ recognized by a NDTM $M$ is the set of $x$ accepted by $M$ (this is independent of whether $N$ is a decider or not);

the definition of time complexity for a Nondeterministic Turing Machine $M$ is slightly different from the definition of time complexity for a Deterministic Turing Machine:
$T_M(n) = max ( \{1\} \cup \{ m \; : \; $ there is an $x \in L_M$ such that   $|x|=n$ and $M$ accepts $x$ in $m$ steps $\})$

we say $M$ is a decider if $T_M(n)$ is computable.

See Garey&Johnson, "Computers and Intractability"


To reach k set consensus (k=2) If I can use FIFO queue and read/write registers, can I reach wait free 2 set consensus if I have 3 processes? I thought is I can, but I saw a conclusion from text book says "we cannot achieve 2 set consensus on 3 processes in shared memory system", so I'm confused now.

Quoted from Chapter 16 of the book:
Distributed Computing: Fundamentals, Simulations, and Advanced Topics (2004):

  (Page 345) We now show that there is no algorithm for solving $k$-set consensus in the presence of $f \ge k$ failures.

and

  (Page 351) Theorem 16.7 There is no wait-free algorithm for solving $2$-set consensus problem in an asynchronous shared memory system with three processors.

The proof is quite complicated. See also the paper: The Asynchronous Computability Theorem for $t$-Resilient Tasks.


A many-to-many mapping data structure What would be a good way representing:
i. Given a key, return all the data values associated with that key
AND
ii. Given a data value, return all the keys that are associated with that data.

So far, all I can think of is to maintain all keys in a sorted linked list where each "key" node has a key value and a vector of pointers to data nodes (in addition to linked list bookkeeping). Likewise, maintain all data values in a sorted linked list and each "data" node has a data value and a vector of pointers to the relevant keys.

Could you please offer me a hint for a more appropriate solution to this problem?

Use two indices: the first index allows you to map a key value to the corresponding tuples that contain that key value; the second index allows you to map a data value to the tuples that contain that data value.  Each index can be implemented as a hash table, binary tree, or any other data structure you like that provides fast lookups.

For instance, databases implement ideas like this to enable fast lookups and searches.


How to cover maximum points with a fixed length line segment? The problem is defined as:

  Given a set of $N$ points $(x_1, x_2, x_3, \ldots, x_n)$ and $L$ the fixed length of a segment.

  Find the number of maximum points which you can cover with a segment line of length $L$.

  Ranges

  $1 \leq N \leq 100 000$

  $1 \leq L \leq 10^{10}$

  $0 \leq x_i \leq 10^{10}$

I call sub-optimal ranges, ranges which are in the form $[x_n,x_n+L]$. The optimal range is the one which contains the maximum points of all ranges.

I've tried to consider the problem using that algorithm (pseudo-code):

Let be S, the set which contains all the N points.
Let be R, the set which contains ranges.
Let be maxPoints, the number of maximum points that we can have (set it to 0).
For all points p I have in my set S
     Store in R the range $[p, p+L]$
For all ranges r I have in my set R
     nPoints = 0
     For all points p I have in my set S
         If the point p is in the range r, then increment nPoints
     maxPoints = maximum value between maxPoints and nPoints
Display maxPoints

I think that the complexity of this algorithm is $O(N^{2})$, is there a way to make it faster? And is it really correct (in the sense, that it solves all cases of this problem).

You haven't explained how to implement how many there is point in the range r. You do this operation N times, so unless it takes $O(1)$, your algorithm won't be $O(N)$.

There is a simple algorithm that runs in time $O(N\log N)$:

Sort the input points.
Go over all the points in order, maintaining a data structure keeping track of the points at distance at most $L$ from the current point.

You can implement each iteration of the second step in amortized $O(\log N)$ using a balanced binary search tree.

Can we do it asymptotically faster? In many restriction computation model, the problem of element uniqueness (given a list of integers, determine whether they are all unique) requires $\Omega(N\log N)$ operations. Since element uniqueness reduces to your problem, in these models your problem requires $\Omega(N\log N)$, so the algorithm broadly outlined above is asymptotically optimal.

Of course, in practice you might benefit from algorithms which are more sensitive to the input distributions. In fact, assuming the answer is $M$, the algorithm outlined above runs in time $O(N\log M)$. If you expect $M$ to be very small, it might be worthwhile to use a list rather than a balanced binary search tree.


Need help in understanding these relational algebra queries I just finished reading about operators in relational algebra and tried to solve this problem. But I dont even understand what the first statement is doing. From what I know, $π$ (project) is a unary opeartor that takes a single relation and selects some attributes from all of the attributes (columns) of that relation. Then what does $\pi_{R-S,S}(r)$ mean? Also, why have they used $r$ as the argument to project operator? Shouldnt it be $R$ as that is the name of the relation given in the problem?
Let R and S be relational schemes such that $R={a,b,c}$ and $S={c}$. Now consider the following queries on the database:

$\pi_{R-S}(r) - \pi_{R-S} \left (\pi_{R-S} (r) \times s - \pi_{R-S,S}(r)\right )$
$\left\{t \mid t \in \pi_{R-S} (r) \wedge \forall u \in s \left(\exists v \in r \left(u = v[S] \wedge t = v\left[R-S\right]\right )\right )\right\}$
$\left\{t \mid t \in \pi_{R-S} (r) \wedge \forall v \in r \left(\exists u \in s \left(u = v[S] \wedge t = v\left[R-S\right]\right )\right ) \right\}$
Select R.a,R.b
From R,S
Where R.c = S.c

Which of the above queries are equivalent?

1 and 2
1 and 3
2 and 4
3 and 4

Recall the definition of schema: The name of a relation and the set of attributes for a relation is called schema. An example of schema of a Movies relation is:
Movies(title, year, length, genre)

In the question, $r$, $s$ represent relation names; $R$, $S$ represent schema. Thus, we have $R = r(a,b,c)$ and $S = s(c)$. A schema consists of a set of attributes. Notation $R - S$ means the set difference between $R$'s set of attributes and $S$'s set of attributes. Thus, we have $R - S = \{a,b\}$. Now we have $\Pi_{R-S,S}(r) = \Pi_{a,b,c}(r)$.
Back to the question we have, let's work with the following example: suppose $r$ has two tuples: $(1,3,5)$ and $(2,4,8)$ with first value corresponds to $a$, second value corresponds to $b$, and the third value corresponds to $c$. $s$ has two tuples: $(5)$, $(5)$. Note we use bag semantics, which aligns with SQL semantics.
Let's consider option 1 first.
$$
\begin{align*}
\Pi_{R-S}(r) - \Pi_{R-S}(\Pi_{R-S}(r)\times s - \Pi_{R-S,S}(r))
&= \Pi_{a,b}(r) - \Pi_{a,b}(\Pi_{a,b}(r)\times s - \Pi_{a,b,c}(r)) \\
&= \Pi_{a,b}(r) - \Pi_{a,b}(\Pi_{a,b}(r)\times s - r)
\end{align*}
$$
Evaluate $\Pi_{a,b}(r)\times s$ will lead to tuples: $(1,3,5)$, $(1,3,5)$, $(2,4,5)$, $(2,4,5)$. Then, $\Pi_{a,b}(r)\times s - r$ means take out all the tuples that show up in $r$, which leads to $\{(2,4,5),(2,4,5)\}$. Then $\Pi_{a,b}(\Pi_{a,b}(r)\times s - r)$ leads to $\{(2,4),(2,4)\}$. $\Pi_{a,b}(r)$ is $\{(1,3),(2,4)\}$. The set difference between $\{(1,3),(2,4)\}$ and $\{(2,4),(2,4)\}$ is $\{(1,3)\}$, which is the result after evaluating option 1.
Now, let's consider option 2.
$$
\{t | t \in \Pi_{R-S}(r) \land \forall u \in s (\exists v \in r (u = v[S] \land t = v[R-S]))\}
$$
we have the following notation

$v$ is a tuple in $r$
$t \in \Pi_{a,b}(r)$ means that $t$ can be $(1,3)$ or $(2,4)$
$u$ is a tuple in $s$

Let's focus on $\forall u \in s (\exists v \in r (u = v[S] \land t = v[R-S]))$ part. Because it is for every $u$, we have

when $u = (5)$, there is a $v$: $(1,3,5)$ that satisfies the requirement:
$v[S] = v[c] = (5) = u$ and $v[R-S] = v[\{a,b\}] = (1,3) = t$ where $t = (1,3) \in \Pi_{R-S}(r)$. Thus $(1,3)$ belongs to the result set of option 2.
now we look at the second $u = (5)$ in $u$ and by the same analysis above, we see $(1,3)$ belongs to the result set of option 2.

Thus, the result set of option 2 is $\{(1,3),(1,3)\}$.
Let's consider option 3.
$$
\{t | t \in \Pi_{R-S}(r) \land \forall v \in s (\exists u \in r (u = v[S] \land t = v[R-S]))\}
$$
Option 3 has the same set of notation as option 2. Let's focus on $\forall v \in s (\exists u \in r (u = v[S] \land t = v[R-S]))$:

for $v = (1,3,5)$, there is a $u = (5)$ such that the requirement is satisfied:
$v[S] = v[c] = (5) = u$ and $v[R-S] = (1,3) = t$. Thus, $(1,3)$ belongs to the final result set of option 3
for $v = (2,4,8)$, there is no such $u$ satisfies the constraint.

Thus, the final result set of option 3 is $\{(1,3)\}$.
Let's consider option 4. The SQL is evaluated to $\{(1,3),(1,3)\}$.
From the above example, we can see that

option 1 and option 2 are not equivalent
option 2 and option 3 are not equivalent

Now, let's consider another example where $r$ has tuples $\{(1,3,5),(2,4,6)\}$ with the first value corresponds to $a$, the second value corresponds to $b$, and the third value corresponds to $c$. $s$ has tuples $\{(5),(6),(7)$}.
By repeating the same evaluation like we did with the first example, we can see option 1 is evaluated to $\emptyset$ whereas option 3 is evaluated to $\{(1,3),(2,4)\}$. Thus, option 1 and option 3 are not equivalent.
Thus, we show that option 2 and option 4 are equivalent.


Average Case runtime for random choice search Assuming we have an array with $n$ Elements and want to find an unique element by randomly (uniformly) choosing. What would be the average case runtime?

My thoughts so far:

The chance to find the element is $\frac{1}{n}$ in every step. Thus, to find the element after $k$ steps is $(\frac{1}{n})^k$. Now we can calculate the expected value and get $\frac{n}{(n-1)^2}$. But: that doesn't really make as it returns results $< 1$ for $n > 2$.

The probability you find the element in each guess is $1/n$. The number of guesses until you find it is a geometric random variable with success probability $1/n$, whose expectation is $n$.

Your formula is wrong – the probability to find the element after $k$ steps is $(1-1/n)^{k-1} (1/n)$.


Applications of the LU factorization in computer science I have been searching for the applications of the LU factorization/decomposition in computer science. From Wikipedia, I have found some of the applications, but these don't seem to be relevant to computer science.

Applications I found are

Solving linear equations
Inverting a matrix
Computing the determinant

Is there any application of LU factorization/decomposition in computer science?

LU decomposition is a basic technique in numerical linear algebra, which is "numerical analysis for linear algebra", or (roughly speaking) the study of numerical algorithms for matrices. Numerical linear algebra has many applications, since many numerical algorithms reduce to linear algebra, which is at the heart of multivariate calculus. You can find a list of areas of application on the Wikipedia article.


Why is this control flow graph correct? Given the following method written in Java:
private void collatz(List<Integer> values) {
     int size = values.size();
     if (size == 0 ||
              values.get(size=1) <= 1) {
              return;
     } else {
        int last = values.get(size = 1);
        if (last%2 == 0) {
           values.add(last/2);
        } else {
           values.add(3*last+1) ;
        }
        collatz(values);
   }
}

My textbook gives the following CFG for the code:

Where each vertex describes the corresponding line of code.  Why is this correct? What I don't understand is the edge between the vertex $13$ and the end vertex, shouldn't this edge be from $13$ to $2$ instead, since we're recursively calling the function? Would really appreciate your input.

Often control-flow graphs don't include call's or other interprocedural control-flow in the graph.  So, a call node does not lead to an edge from the call site to the callee, and in this case, that means there would be no edge from 13 to 2.


Approximating the biggest acyclic subgraph of a given weighted digraph $G= (V,E)$ The base scenario is this: We're given a weighted, directed graph $G= (V,E)$, and are tasked to find an approximating algorithm which returns a digraph $G' = (V,E')$ (i.e. which only deletes edges) so that $G'$ is acyclic, and so that the sum of the weights of the remaining edges $\sum_{e\in E'} weight(e)$ is as big as possible.

Furthermore, the approximation shall be at worst half as good as the optimal solution (i.e. the sum of weights the approximation algorithm returns is at least half as big as the sum of weights of the optimal solution)

This is a homework problem, and I'm looking for hints how to solve it, as I can't seem to figure out any tactic to somehow compare the approximation algorithm ideas to any bound on the optimum solution.

I've come up with 4 ideas of choosing nodes/edges, from which 2 could go arbitrarily bad, and from which I believe 4) has the best chance of succeeding.

So far I have the following results:

1)
Using an algorithm to identify the strongly connected components, I can partition $G$ into a set of subgraphs (one for every strongly connected component), and solve for each subgraph individually (all edges between these subgraphs never create a cycle, and can always be taken into the solution).

2)
Using the tactic to iteratively identify a cycle and remove the one edge of it which has the lowest weight can go arbitrarily bad .

The optimal subgraph $\hat G = (\hat V, \hat E)$ has a topological sorting.
Therefore, there exists a numbering $v_1,..,v_{|V|}$ of the nodes so that with $T:= [v_1,..,v_{|V|}]$, the sum
$$\sum_{j=1}^n \sum_{ k=2}^j  weight(v_j\to v_k)
$$
is minimal. (The sum represents for each node $v$ in $T$ the weight of all edges $(v,v')$ that is lost because $v'$ appears before $v$ in the list, and thus there mustn't exist an edge $v\to v'$

Therefore, an approximation algorithm might guess the topological sorting of the optimal graph.

3)
Going from left to right, and always picking the node that brings with it the highest weight (as sum of its outgoing edges that are eligible) can go arbitrarily bad.

4)
However, so far I haven't found any counter-example for going from right to left, and always picking the node which loses the least weight.

For the last approach, we can show the following inequality:
Let $T:= [v_1,..,v_{n}]$ be the result of the approximation algorithm, then holds:
$$
 \sum_{k=1}^{j-1} weight(v_j\to v_{k}) \le \sum_{j=2}^n\sum_{k=2}^j weight(v_1\to v_k) = \sum_{j=1}^{n-1} (n-j)weight(v_1\to v_j)
$$

First: The upper bound is as stupid as they come: Namely, that at most, the optimal solution contains all edges.

With this upper bound, our approximating algorithm now asserts the following statement:
In every weighted, directed graph $G =(V,E)$ there exists a subgraph $G' = (V,E'), E'\subseteq E$ so that $G'$ is acyclic, and $\sum_{e\in E'} weight(e) \ge \frac 1 2 \sum_{e\in E} weight(e)$, i.e. we can choose the edges in $E'$ so that they accumulate at least half of the weight of all edges in $E$.

To find such a graph $G'$, we enumerate the vertices in $V$ as $x_1,...,x_n$, and now create two edge sets using it:
$$
E_1 = \{(x_i,x_j)\in E\mid x_i<x_j \} \\
E_2 = \{(x_i,x_j)\in E\mid x_i>x_j \}
$$
Differently put, imagine the graph $G$. Now move the vertices, so that they form the line $x_1,...,x_n$ from left to right (while keeping the edges intact).
Now, for $E_1$, you remove all edges going left.
For $E_2$, you remove all edges going right.

Each of the corresponding graphs $G_1 := (V,E_1), G_2:=(V,E_2)$ is acyclic, and $E_1\dot\cup E_2=E$, i.e. $E_1, E_2$ contain all edges in $E$ exactly once.

Therefore, either $G_1$ or $G_2$ has to contain at least half of the edge weight, and thus one of them is the wanted subgraph.


Build a balanced binary tree from list in linear time I couldn't figure this one out. Given an unsorted list, we want to build a balanced binary tree (not a search tree, namely - left child is of lower key, and right child of higher key). Can we do it in linear time? Thanks!

Answer #2.

An alternative approach (arguably more elegant). This basically does the same operations as my other answer, just in a different order. It is as follows:

build-tree(list A of length n):
  if n == 1:
    return singleton tree of the 1 element in A.

  let m be the median element of A  # linear time select

  let L be all elements in A less than m
  let R be all elements in A greater than m

  construct a max-heap HL from L in linear time
  construct a min-heap HR from R in linear time

  let m be the root node of tree T
  let the structure of HL be the structure of all  left-children in T
  let the structure of HR be the structure of all right-children in T

  return T

Let's try an example on $[8,12,9,15,5,1,10,3,11,14,2,4,13,7,6]$.

First we find the median $m = 8$.
We find $L = [5,1,3,2,4,7,6]$ and $R = [12,9,15,10,11,14,13]$.
Then we have max heap HL as shown below:

Then we have min heap HR as shown below:

Then we fill in the structure of T as follows:

The dotted lines represent the underlying structure of each original heap.

Analysis

The running time is as follows:

$O(n)$ for finding the median.
$O(n)$ for constructing the two heaps.
$O(n)$ for merging the two heaps.

Thus, the total time is still $O(n)$.


How to check if my language is context-free can't seem to solve it using pumping lemma I have a language and I am trying to see if it's context-free or not, by trying to use a pumping-lemma but I can't figure it out, been reading a lot of other posts but still struggling to apply it to my example

this is the language (sorry for using an image, i know how to write number exponents but i don't know how to write letters as exponents):

Thanks

One can proof that a language is CF by constructing a CFG or a PDA for it. I will give an example CFG for this language.

Let the start symbol be $S$.

In the definition we see that we can add arbitrarily many $m$'s, and for each $m$ there have to be two $t$'s.
$$M \rightarrow mMtt|\epsilon$$

The same for the $e$'s, but now with one $t$ fot each $e$.
$$E \rightarrow tEe|\epsilon$$

Then finally, there has to be an extra $t$. This gives following CFG:

$$S \rightarrow MtE$$
$$M \rightarrow mMtt|\epsilon$$
$$E \rightarrow tEe|\epsilon$$


Show that a language is decidable iff some enumerator enumerates the language in decreasing order Show that a language is decidable iff some enumerator enumerates the language in decreasing order.
I know a language is decidable iff some enumerator enumerates the language in the standard string order (increasing order), but I am not sure if this makes sense in decreasing order. Can anyone prove it?

If there is an enumerator in decreasing order then the language is finite and hence decidable.
But that means any infinite language wont have such an enumerator, and in particular there is some infinite language that is decidable (such as $\Sigma^*$) and it wont have such an enumerator.
So, this theorem is incorrect


Knapsack-like problem oriented on contiguous selection Problem inputs is an ordered array $A = [a_1, a_2, \ldots, a_n]$ with $\text{weight}(a_i) = w_i$.
We define a $subgroup$ of $A$, denoted by $B$, whose elements' indices are continuous in integer. For example, if $A = [a_1, a_2, a_3, a_4, a_5]$, then $[a_2,a_3, a_4]$ is a subgroup of $A$, while $[a_1, a_3, a_4]$ is not. And we say a $subset$ of $A$ is a collection of non-overlapping subgroups of $A$.
Our goal is to find a subset $\mathcal{S}$ with $k$ elements in $A$, such that total weight $\displaystyle\sum_{s \in \mathcal{S}}\text{weight}(s)$ is maximized, while the number of subgroups is less than a given $m$. For example, suppose the corresponding weights of elements in $A$, $[8,1,6,2,7]$ and $k=3$, $m=2$, then the optimal is $\{[a_1], [a_4, a_5]\}$.

You can use dynamic programming.
Define $T^{0}(k_0,m_0,i)$- the optimal subset $S$, that uses $k_0$ elements from the set  $\{a_i,a_{i+1},\ldots,a_n\}$, includes $a_i$  uses less than (or equal to)  $m_0$ subgroups. We define similarly $T^{1}(k_0,m_0,i)$ but it does no includes the element $a_i$. We define $W(S)=\sum_{s\in S} Weight(s)$ for every subset $S$.

For every $k,m\geq 2$ there exists $j>i$ such that begins with the subgroup $[a_{i},a_{i+1},\ldots, a_{j-1}]$. Thus, if we denote $T_j=\{[a_{i},a_{i+1},\ldots, a_{j-1}]\}\bigcup T^1(k_0-(j-i),m_0-1,j)$ then $T^{0}(k_0,m_0,i)$ is the subset with maximum weight among the $T_j$'s, i.e.,

$$T^{0}(k_0,m_0,i)=\arg\max_{T_j| \min(n,k_0+i)\geq j>i} W(T_j)$$

In addition, if the first element of $T^{1}(k_0,m_0,i)$ is $a_j$, then  $T^{1}(k_0,m_0,i)$ equals to $T^{0}(k_0,m_0,j)$. Therefore,
 $$T^{1}(k_0,m_0,i)=\arg\max_{T=T^{0}(k_0,m_0,j)|n\geq j>i} W(T)$$

Note that the initial conditions are  $T^{0}(1,m_0,i)=\{[a_i] \}$, $T^{0}(k_0,1,i)=\{[a_i,a_{i+1},\ldots,a_{i+k_0-1} ]\}$.

The optimal solution for the problem is the subset with the largest weight among the subsets $\{ T^{0}(k,m,1), T^{1}(k,m,1)\}$

We can compute each entry of $T^{0}(k_0,m_0,i_0)$ and $T^{1}(k_0,m_0,i_0)$ in $O(n)$ time. Since there are $O(k\cdot m\cdot n)$ entries of $T^{1},T^{2}$ the time complexity is $O(k\cdot m\cdot n^2)$.


Why is XML hard to parse? I was chatting with a friend about my love/hate relationship with XML.  He made the comment that, "xml is broken primarily because parsers for recursive self-defined document are basically impossible to get right."
I've heard the critique that XML is very difficult to parse before, but my understanding is limited to difficulties around balancing memory usage (i.e. streaming) and the impedance mismatch between XML and most programming languages (such as not supporting basic primitives like an array).
What is unique about XML as a self-defining document that makes parsing difficult?

Thanks for posting your question! See, normally parsers implement huge usage of regex or regular expressions. But regular expressions are just for text manipulation and cannot count. Because of this defect of regular expressions, it becomes quite difficult to balance number of open and close tags. Hence, software engineers have to do some extra work to deal with it. You can read more about regular expressions at Mozilla Developer Network Docs and at this post on Medium.


Can a PDA guess more than once? L = {aⁿ bⁱ aⁿ | i,n > 0 } PDA = Pushdown Automata

Let's assume I have this language:

$L = \{a^nb^ma^n | m,n \ge 1\}$

Would the first approach with one node be enough - in that case it guess twice the $\lambda$. In the second approach it's deterministic, which is fine.

Here is a solution with one stack.

Start inserting a's into the stack.
Stop inserting a's when we encounter the first b. Halt any operations with respect to the stack as long as we get b's.
Start popping stack contents immediately when the b's stop and a's start.


Radon transform for advanced 3d graphics and games? The Radon transform is used to take 2d projections of an object and create a 3d representation.

It seems like it would be possible to apply such a transform in 3d graphics in games (although possibly too slow to be practical).

For example, a very simple way to display an object is to use a 3d rectangle and texture map each side. This is relatively fast but the 3d detail is limited. When a side is parallel with the visual plane it will represent the detail 100% (so the visual detail would be limited to that of the texture map). Of course it won't represent external 3d effects properly, like lighting.

But by using the Radon transform one could gain a true 3d approximation of the object from the six textures/projections used. By increasing the number of textures/projections the approximation is better.

I'm curious if the idea has potential. Possibly for high-quality 3d models it might pay off in performance and size. Of course 3d models can be optimized to limit their size which also increases speed but visually doesn't change much.

I've been studying the use of OpenGL and DirectX and even though I am at an intermediate level, I believe this is where the use of bump maps, light maps etc comes into play. These are encapsulated in the idea of a Shader. The hardest part about the shader and lighting to work correctly with the 3D object with respect to the angle of the camera view directly depends if your normals are defined correctly. As for what you are describing it does make sense using 3D approximation, however my linear algebra is a little rusty, I am not sure if the conventional 4x4 matrices will work, and when it comes to motion with rotations you might have to redefine your quaternions too.