Master method recurrence question This is specifically a question pertaining to solving reccurences via the Master Theorem/Method, particularly for a specified $f(n)$ (as denoted below).

For a recurrence of $$T(n) = a T(\frac{n}{b}) + f(n)$$

where f(n) is $\Theta{(n)}$, would we be comparing $n^{\log_b(a)}$ with $n^{1}$ - meaning we would be comparing $log_b(a)$ with 1? Since the rate of growth is linear?

what about where f(n) is $\Theta{(1)}$ (aka some constant?), would we be comparing $n^{\log_b(a)}$ with $n^{0}$? '0' since there is no rate of growth for a constant?

I think the question is asking how to translate $f(n)$ into Big-Theta notation to be used for the Master Theorem. You have the right idea about switching between notations.

Another way to write the Master Theorem is as follows:

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

So, yes, if you have a linearly growing function, then $f(n)$ may be substituted with $\Theta(n)$.

Then you may proceed with your comparisons.


Deriving the average depth for a randomly generated binary search tree If $D(n)$ is the internal path length (sum of the depths of all nodes) for some tree $T$ with $n$ nodes then we have the following recurrence relation: $$D(n)=D(i)+D(n-i-1)+N-1$$ where I simply taken an arbitrary tree with a left subtree containing $i$ nodes and the right subtree containing $n-i-1$ nodes.

Correct me if I'm misunderstanding this, but since these left and right subtrees can be anything (where $i=0,1,2,...,n-1$) then the average of $D$ is given by $$\langle D \rangle=\dfrac{1}{n}\left(2\sum_{i=0}^{n-1}D(i)+\sum_{i=0}^{n-1}(n-1)\right)$$ where I divided by $n$ since there are $n$ different left/right-subtree possibilities. What I don't understand is that online sources and my textbook equates this to $D$ itself. In other words, I don't quite understand why we're allowed to set $\langle D(n) \rangle = D(n)$.

Ignoring that, I continued on and I'm also running into the problem where my book is writing $$ D(n) =\dfrac{1}{n}\left(2\sum_{i=0}^{n-1}D(i)+(n-1)\right)$$ and seems to be ignoring the sum altogether. The reason why I say this is because later the book claims that $$ nD(n) =2\sum_{i=0}^{n-1}D(i)+n(n-1)$$ This doesn't make any sense to me since I had a $$\sum_{i=0}^{n-1}(n-1)\in O(n^2)$$ term in my expression so multiplying by another $n$ should be give me something like $$ nD(n) =2\sum_{i=0}^{n-1}D(i)+O(n^3)$$ instead. I feel like I'm missing something obvious but I can't quite figure it out. Any ideas?

Suppose that $T$ is a random tree on $n$ vertices, according to the distribution you consider. Let $T_L,T_R$ be its two subtrees, and let their size be $N_L,N_R$. Let $P$ be the total path length of $T$. Let $P_L(i)$ be the total path length of $T_L$ if $N_L=i$, and zero otherwise, and define $P_R(i)$ similarly. We have
$$
P = \sum_{i=0}^{n-1} (P_L(i) + P_R(n-1-i)) + n-1.
$$
According to linearity expectation, we have
$$
\mathbb{E}[P] = \sum_{i=0}^{n-1} (\mathbb{E}[P_L(i)] + \mathbb{E}[P_R(n-1-i)]) + n-1.
$$
By definition, $\mathbb{E}[P] = D(n)$, where $D(n)$ is the expected internal path length of a random tree on $n$ vertices.

According to your probability distribution, the probability that $N_L=i$ is $1/n$. When that happens, $T_L$ is just a random tree on $i$ vertices. Therefore
$$
\mathbb{E}[P_L(i)] = \Pr[N_L=i] \mathbb{E}[P_L(i)|N_L=i] + \Pr[N_L\neq i] \mathbb{E}[P_L(i)|N_L\neq i] = \\ \frac{1}{n} \cdot D(i) + \left(1-\frac{1}{n}\right) \cdot 0 = \frac{D(i)}{n}.
$$
Therefore we obtain the recurrence
$$
D(n) = \frac{1}{n} \sum_{i=0}^{n-1} (D(i) + D(n-1-i)) + n-1 = \frac{2}{n} \sum_{i=0}^{n-1} D(i) + n-1.
$$
Equivalently,
$$
nD(n) = 2\sum_{i=0}^{n-1} D(i) + n(n-1).
$$
The initial condition is $D(0) = 0$.

We can solve this recurrence using generating functions. Let $P(x) = \sum_{n=0}^\infty D(n) x^n$. First,
$$
P'(n) = \sum_{n=1}^\infty nD(n) x^{n-1}.
$$
Second,
$$
\frac{P(n)}{1-x} = \sum_{n=0}^\infty [D(0) + \cdots + D(n)] x^n.
$$
Third,
$$
\sum_{n=0}^\infty n(n-1) x^{n-2} = \frac{d^2}{dx^2} \frac{1}{1-x} = \frac{2}{(1-x)^3}.
$$
Putting everything together, we obtain
$$
P'(x) = \sum_{n=1}^\infty nD(n) x^{n-1} =
2\sum_{n=1}^\infty (D(0) + \cdots + D(n-1)) x^{n-1} +
\sum_{n=1}^\infty n(n-1) x^{n-1} = \\
\frac{2P(x)}{1-x} + \frac{2x}{(1-x)^3}.
$$
The solution to this ODE is
$$
P(x) = \frac{-2\log (1-x)-2x}{(1-x)^2} = \frac{1}{(1-x)^2} \sum_{n=2}^\infty \frac{2}{n} x^n,
$$
which implies that
$$
D(n) = 2\sum_{m=2}^n \frac{n-m+1}{m} = 2(n+1)(H_n-1)-2(n-1) = 2(n+1)H_n-4n.
$$
Since $H_n = \ln n + \gamma + 1/2n + O(1/n^2)$, we deduce that
$$
D(n) = 2(n+1)(\ln n + \gamma + 1/2n + O(1/n^2)) - 4n = \\
2n\ln n + 2\ln n + (2\gamma-4) n + 2\gamma + 1 + O(1/n).
$$


Efficient way to concatenate strings to find specific split up values I'm working with a list of objects ("Section") that contains a string value among other fields. The strings in all of the sections can be concatenated to form the complete text. I am, however, wanting to implement a method that searches for a specific (given) value and returns the Section object(s) it found the value in. There are however two different scenarios as described below.

Value: restaurant

Scenario 1

"John went to the restaurant to pick " ✔
"up the food he ordered online before "
"he went to his mother's house."

Current behaviour: Found in Section 1

Desired behaviour: Found in Section 1

Scenario 2

"John went to the restaura"
"nt to pick up the food he ord"
"ered online before he went to his mother's house."

Current behaviour: Couldn't find the value

Desired behaviour: Found in list(Section 1, Section 2)

Scenario 1 is easily solved as the value is found completely in section 1. In the 2nd scenario, the value is never found as it is split up between sections. I have written an algorithm that tries to stitch these sections together. It appears to work when the given value is simple e.g., "car" or "boat". I'm having troubles with compound strings such as "the supermarket" or "a green flower". I wrote the code a couple of months ago and tried debugging it, but even I fail to understand my own code here.

I deliberately left my code out of this post as it has rough hardcoded rules and has extreme levels of code complexity. I'd like to rethink the algorithm without looking at the current one to refrain from blatantly copying sections of the existing code.

The code is written in Java in case anyone knows some handy Java functions that might help.

If all the words are going to be English words, you can run all the words through a dictionary. If you find any non-dictionary words at the start or end of the sections and you are unable to find the "key", you can just combine those words until the key is found.

Alternatively, you can trivially just combine the the words (once) at the start/end of sections until the word is found. I don't believe this will to too inefficient computationally since the described sections are quite large.


Known problems in BQP \ NP? The introduction to Nielsen and Chuang has an Euler diagram of the suspected relationships between various complexity classes which shows $\text{BQP}$ extending slightly outside of $\text{NP}$. Is $\text{BQP} \not\subset \text{NP}$?  Are there any specific problems known or suspected to be in $\text{BQP}$ but outside of $\text{NP}$? If so, what's the simplest known example?

If there was a problem known to be in $\text{BQP}$ but not $\text{NP}$, that would prove $\text{BQP} \not\subset \text{P}$. But $\text{BQP}$ vs $\text P$ is also still an open problem.

It is suspected that $\text{BQP} \not\subset \text{NP}$. In fact it's suspected that $\text{BQP} \not\subset \text{PH}$ via the "Recursive Fourier Sampling" problem. But proving separations between complexity classes is surprisingly hard. I don't think anyone's even managed to show that $\text{BQP} \not\subset$ $\text{LSPACE}$.


Maintaining an array supporting sum requests We have to maintain an array $a_1,\ldots,a_n$ supporting the following operations:

Assign $a_i = x$
Given $\ell,r$, return $\sum_{i=\ell}^r a_i$
Given $\ell,r$, return $\sum_{i=\ell}^r \sum_{j=\ell}^r a_i a_j$
Given $\ell,r$, return $\sum_{i=\ell}^r \sum_{j=\ell}^r \sum_{k=\ell}^r a_i a_j a_k$

After $O(n)$ initialization, these operations should run in amortized $O(\log n)$ time.

Suppose for simplicity that $n = 2^N$ (otherwise, extend the array by zeroes). Maintain the following values:
$$
a_1, \ldots, a_n \\
a_1 + a_2, a_3 + a_4, \ldots, a_{n-1} + a_n \\
a_1 + \cdots + a_4, a_5 + \cdots + a_8, \ldots, a_{n-3} + \cdots + a_n \\
a_1 + \cdots + a_8, a_9 + \cdots + a_{16}, \ldots, a_{n-7} + \cdots + a_n \\
\cdots \\
a_1 + \cdots + a_{n/2}, a_{n/2+1} + \cdots + a_n \\
a_1 + \cdots + a_n
$$
By computing each line from the preceding one, you can compute all of these sums in $O(n)$.

Operation 1 can be implemented in $O(\log n)$ since each element is only involved in $\log n$ sums.

Operation 2 can be implemented in $O(\log n)$ since the sum can be broken into $O(\log n)$ sums of the type above.

Operation 3 and Operation 4 easily reduce to Operation 2 (exercise).

Details left to you.


I'm asked to draw DFA for this {$\epsilon$, 0} however I do not understand what {$\epsilon$, 0} mean I'm asked to draw a DFA of this {$\epsilon$, 0} but have no clue what it means. Can someone help me understand what the automata is supposed to do?

I know that $\epsilon$ is the symbol for empty word.

As an example having to make an automata for this {w| w contains at least two 0s and at most one 1} is pretty understandable but {$\epsilon$, 0}
not so much.

To put it simply I do not understand the problem question I'm asked.

**Edit: I forget to specify that we have the alphabet {0,1}

The problem is to find a DFA, such that the only two words it accepts are '$\epsilon$' - the empty word, and '0'


Determining the minimum number of edges to add in order to be 3-connected A graph $G$ is said to be $3$-connected if it has no $2$-vertex cutsets (i.e., at least three vertices must be deleted to disconnect the graph). As far as I know, it is possible to determine if a simple graph is $3$-connected in $O(n)$ time (example: http://www2.tu-ilmenau.de/combinatorial-optimization/Schmidt2012b.pdf), but I would find it useful to efficiently determine which edges to add in order to make our graph $3$-connected if it isn't already (ideally, the minimum number of edges if this can be done efficiently). Is anyone aware of such an algorithm? If so, I would appreciate a reference or two.

For this special case of $3$-connectivity, it has been solved by Watanabe and Nakamura. The algorithm runs in $O(n(n+m)^2)$ time, where $n$ and $m$ are the number of vertices and edges of the input graph, respectively.

There is a polynomial time algorithm to find the minimum number of edges to add to a $k-1$-connected graph to produce a $k$-connected graph. See chapter 3 of László A. Végh's PhD thesis. The thesis states that it is not known if adding a minimum number of edges to produce a $k$-connected graph is NP-hard in general.


Operating system maintains copy of page table for each process I am quoting a paragraph in Operating System Concepts by Silberschatz, in paging chapter,

  In addition, the operating system must be aware that user processes operate
  in user space, and all logical addresses must be mapped to produce physical
  addresses. If a user makes a system call (to do I/O, for example) and provides an address as a parameter (a buffer, for instance), that address must be mapped to produce the correct physical address. The operating system maintains a copy of the page table for each process, just as it maintains a copy of the instruction counter and register contents. This copy is used to translate logical addresses to physical addresses whenever the operating system must map a logical address to a physical address manually. It is also used by the CPU dispatcher to define the hardware page table when a process is to be allocated the CPU.

I don't understand why OS would copy the page table, isn't it the one creating and maintaining it?
And as given further, why does it keep copy of instruction counter and register contents?

why does it keep copy of instruction counter and register contents?

It's because of process scheduling.

Let's say a process comes in execution first time and executes some lines of instruction. The registers contain values as per the instructions executed till now. Now if the process switches from running state to waiting state (due to I/O or preemption) and then comes back to the running state, it must have the same register values for further execution. So OS stores a copy of each register in the program control block(PCB).

  I don't understand why OS would copy the page table, isn't it the one
  creating and maintaining it?

Again, if the process goes out of execution, OS must save the information regarding frames of memory allocated to the process.


Do arbitrary/Byzantine failures include omission failures and timing failures? Distributed Systems 5ed by Coulouris says on p68

  2.4.2 Failure Models

  Omission Failures ...

  Arbitrary Failures
  The term arbitrary or Byzantine failure is used to describe the worst
  possible failure semantics, in which any type of error may occur. For example, a process
  may set wrong values in its data items, or it may return a wrong value in response to an
  invocation.

  Timing Failures ...

Are arbitrary/Byzantine failures arbitrary? (Sounds yes to me.)

Do arbitrary/Byzantine failures include omission failures and timing failures? (I guess not. Otherwise, why does it describe omission failures and timing failures separately?)

The book on p660 says

  15.5.1 System model and problem definitions

  Our system model includes a collection of processes communicating by
  message passing. An important requirement that applies in many
  practical situa- tions is for consensus to be reached even in the
  presence of faults. We assume, as before,  that communication is
  reliable but that processes may fail. In this section we consider
  Byzantine (arbitrary) process failures, as well as crash failures.

Does the above quote imply that crash failures (a kind of process omission failures, as the book said in Section 2.4.2) are not Byzantine (arbitrary) process failures?

Thanks.

Arbitrary failure means exactly what it says. It means that the failing process should be treated as if an opponent is choosing the process's behavior to try to break your system.

Other types of failure, such as omission failures and timing failures, are special cases of this. They are relevant because certain algorithms only guarantee correct results in all cases if, for example, it is assumed that a process may fail to respond to a message (omission failure) but cannot fail in other ways, such as by responding with incorrect data.


Is a function looking for subsequences of digits of $\pi$ computable? How can it be decidable whether $\pi$ has some sequence of digits? inspired me to ask whether the following innocent-looking variation is computable:

$$f(n) = \begin{cases}
  1 & \text{if \(\bar n\) occurs in the decimal representation of \(\pi\)} \\
  0 & \text{otherwise} \\
\end{cases}$$

where $\bar n$ is the decimal representation of $n$ with no leading zeroes.

If the decimal expansion of $\pi$ contains all finite digit sequences (let's call this a universal number (in base 10)), then $f$ is the constant $1$. But this is an open mathematical question. If $\pi$ is not universal, does this mean that $f$ is uncomputable?

Note that $f$ can be the constant $1$ even if $\pi$ is not a normal number. (In French we say if $f$ is constant that $\pi$ is a nombre univers. I don't know the corresponding term in English)

For what it's worth: it could be, in the following way:

Proving $f$ is computable would not necessarily imply the resolution of the open question whether $f$ is constant or not. For example you can build $g$ that is computable but such that the constantness of $g$ is equivalent to Goldbach's conjecture.

Of course that does not even begin to answer your question, but it's likely open to me.


Why is this language regular? If you could include your thought process in determining why it's regular it would help me a lot.

$L_1 = (0^*(10)^*11)$
$L_2 = \{ \langle M \rangle \mid M \text{ is a Turing machine that halts on all inputs from }L_1 \}$
$L_3 = \{ x \in \{0,1\}^* \mid \exists y \in L_2. xy \in L_1 \}$

Why is $L_3$ regular? It's a set of strings, I need to determine if there's a DFA that can accept it. Do I even care about $L_2$ and $L_1$ in this case?

Short answer. The language $L_1$ is clearly regular. Further, $L_3 = L_1L_2^{-1}$ is a quotient of $L_1$ and hence it is regular since the quotient of a regular language by any language (regular or not) is regular. So you don't care about $L_2$, but you do care about $L_1$.

More details. Let $L$ and $R$ be languages. Then $LR^{-1} = \{ u \in A^* \mid ur \in L \text{ for some }r \in R\}$. Therefore $LR^{-1} = \bigcup_{r \in R} Lr^{-1}$. If $L$ is regular, there are only finitely many languages of the form $Lr^{-1}$, each of which is regular (this is the dual form of Nerode's lemma) and hence $LR^{-1}$ is a finite union of regular languages and thus it is regular.


Why is the address-of operator in C/C++ represented with the "&" symbol? I've started learning C++, and I know a little bit of C. Something that always struck me as somewhat off was that the address-of operator is represented with the seemingly random ampersand (&) symbol instead of, say, the "at" symbol (@). Is there some kind of history behind this?

Because B did!
A user on software engineering.sx contacted Ken Thompson:

From: Ken Thompson
c copied from b so & and * are same there.
b got * from earlier languages - some assembly,
bcpl and i think pl/1.
i think that i used & because the name (ampersand)
sounds like "address." b was designed to be run with
a teletype model 33 teletype. (5 bit baud-o code)
so the use of symbols was restricted.


Constructing a sphere ($S^2$) in HoTT directly? (this is a repost of https://stackoverflow.com/questions/29802501/constructing-a-sphere-s2-in-hott-directly, which was voted out of SO)

I understand the construction of $S^2$ as a suspension of $S^1$ in homotopy type theory. I wonder whether one can build $S^2$ in one step as a base point and an open 2-surface. Something like this:

data Sphere where
  base : Sphere
  skin : Id (Id Sphere base base) refl refl

The above is probably something like a sausage with endpoints identified, though.

So my question is: Can an $S^2$ be built as a HIT from a closed 1-ball whose boundary is identified?

This was asked once on the HoTT-cafe list. The answer is "yes" and I composed a short video which explains exactly how this happens.


Prove a statement about searching in binary search tree Suppose search $n$ times in  a given binary search tree $T$ with $n$ nodes. each searching have cost $C_i$, and $\sum_{i=1}^{n}C_i=O(n\log n)$. Now the problem is to find height of $T$. I think it be $O(\sqrt{n\log n})$, but after reading this post, what is correct proof to get that result?

Let $h$ be longest path from root $T$ to leaves. We must read $h+1$ nodes. So searching for root of $T$ we have cost $1$, for child of root we have cost $2$ , and etc. it's sufficient to sum over cost at each nodes on $h$. As a result we have
\begin{gather*}
1+2+3...+h=O(h^2).
\end{gather*}
Now as mentioned in question,
$O(h^2)$ must be $O(n\log n)$. More formally, $O(h^2)=O(n\log n)$ that we can conclude that $h=O(\sqrt{n\log n})$.
For example consider a binary search tree with $n$ nodes such that root have sub tree with height $\sqrt{n\log n}$, and right sub tree of root have height $\log (n-\sqrt{n\log n}).$


comparisons vs arithmetic complexity I'm trying to find out which operation is fast, evaluating a comparison vs doing an arithmetic option on a single word (e.g subtract, add). Can anyone point me in the right direction with some blogs, books and other material?

It principle it could depend on the processor. However, I imagine that comparison are done using the same circuitry as subtraction, so the complexity should be comparable. I'm assuming that by comparison you mean an instruction comparing two registers and setting some flags (or another register). A conditional jump might interfere with pipelining and so would be costlier.


Lower bound on approximation degree in Nisan-Szegedy In Nisan and Szegedy's 1994 paper "On the degree of boolean functions as real polynomials"[1] Lemma 3.8, how does proof work for $\widetilde{\deg(f)}\geq \sqrt{\,\tfrac16\mathrm{bs}(f)\,}$? It clearly works for $\deg(f)$ and only this portion is shown in Jukna's book [2, Theorem 14.11]. Why does the proof work for $\widetilde{deg(f)}$?

Here $f$ is boolean function, $\widetilde{\deg(f)}$ is the $\tfrac13$-approximation degree of $f$, $\deg(f)$ is real degree of $f$ and $\mathrm{bs}(f)$ is block sensitivity of $f$.

[1] Noam Nisan and Mario Szegedy, "On the degree of boolean functions as real polynomials". Computational Complexity 4(4):301–313, 1994 (SpringerLink)
[2] Stasys Jukna, Boolean Function Complexity. Volume 27 of Algorithms and Combinatorics, Springer, 2012. (Homepage)

If you believe Lemma 3.8 for $\deg f$, you should also believe it for $\widetilde{\deg} f$. An earlier lemma states that if $f$ is a Boolean function on $n$ variables such that $f(\mathbf{0}) = 0$ and $f(\mathbf{x})=1$ for all $|\mathbf{x}|=1$ then $\deg f \geq \sqrt{n/2}$ and $\widetilde{\deg} f \geq \sqrt{n/6}$. Applying the first part of this lemma,  we conclude the first part of Lemma 3.8, namely $\deg f \geq \sqrt{\operatorname{bs}(f)/2}$. Applying the second part of this lemma, we conclude the second part of Lemma 3.8, namely $\widetilde{\deg} f \geq \sqrt{\operatorname{bs}(f)/6}$.


Finding the values of x and y using base 8 In finding the values of x and y, if  (x567) + (2yx5) = (71yx) ( all in base 8) I proceeded as under.

I assumed x=abc and y=def and followed.

  (abc+010 def+101 110+abc 111+101)=(111 001 def abc) //adding ()+()=() and equating LHS=RHS.
  abc=111-010=101 which is 5 in base 8 and then def=001-101 which is -4
  so x=5 and y=-4

Now the Question is that the answer mentioned in my book is x=4 and y=3.

I think the issue with your method is that your subtracts are neglecting to account for the carry values that happen during the addition. If we instead go right to left and account for carries, we get:

(abc+010 def+101 110+abc 111+101)=(111 001 def abc)
                         100
                 (110 + 100 + 1) // carrying the 1 here from the addition in the previous place
                 011
         (011 + 101 + 1) // carrying a 1 from the previous place again
         001
(100 + 010 + 1) // again, carrying a 1
111

Thus, we have that:

111 001 011 100 = (111 001 def abc)

Meaning that 100_2 = abc_2 and 011_2 = def_2, implying x=4 and y=3.


Polynomially reducing NP-Complete problem clarification I am having trouble solving the following question.

I am given a following problem X: Given a graph G, we want to know whether there is an edge e in G such that G − e is 3-colorable.

I want to show that $X \leq_p 3Col$

My attempt is to look at the complement of G, and say that the complement of G shows us that the graph plus the edge is not 3-colorable if and only if the G - e is 3-colorable.

Does this make sense and is it correct?

Since 3COL is NP-hard and X is clearly in NP, by definition there is some many-one reduction from X to 3COL, though it may be awkward to state. There is a simple oracle reduction along the lines outlined in the other answer: remove each edge at a time, and check if the resulting graph is 3-colorable.

More interesting, perhaps, is a reduction going the other way, thus showing that X is NP-hard (and so NP-complete). Given a graph, we adjoin to it $K_4$, the clique on 4 vertices. The new graph is a Yes instance of X iff the original graph is 3-colorable (exercise).


Have I proved $\sum_{i=1}^{\lg n} 2^{i-1} = \Theta(n\lg n)$? I have an exercise problem and don't know why its answer is like this.
$$ \sum_{i=1}^{\lg n} 2^{i-1} \in \Theta(2^{\lg n}) = \Theta(n).  $$

Regarding this equation, I think it would be,
$$ \sum_{i=1}^{\lg n} 2^{i-1} \in \Theta(\lg n \cdot 2^{\lg n}) = \Theta(\lg n \cdot n),  $$
with the proof,
$$ \sum_{i=1}^{g(n)}f(i) \le \sum_{i=1}^{g(n)}f(g(n)) = g(n)\cdot f(g(n)).  $$

My thought with this question,  $ f(n) =  2^{i-1} $ and $ g(n)= \lg n $. Then result would be $ \lg n \cdot 2^{\lg n - 1} $.

Can anyone point out where I made a mistake? (I am not asking grading mine, but tell me where I mis-think)

Your argument shows that
$$
\sum_{i=1}^{\lg n} 2^{i-1} = O(n\lg n).
$$
It doesn't show the matching lower bound, which is actually false.


Working Optimization Algorithm This is my basic setup: I have five time slots (A, B, C, D, E; each day has these five time slots) over 60 days that all need to be filled with n people each (n must remain a variable). However, each person has a different availability (ex. ABDE, BCDE, AE, BCD, etc.). I want this to be distributed equally so all workers get the same number of shifts, but some workers should be able to input in a number of shifts that they want to do.

I recognize that this is a subproblem of the nurse scheduling problem, and I have spend a few hours trying to grind through some academic papers on it. However, it gets very convoluted very quickly and I get lost somewhere in the mix, as I do not have a knowledge of these kinds of algorithms. This seems to be a simpler version with fewer constraints, so I was wondering what a simple yet effective algorithm would be to solve this problem and if you could provide details on it.

I have come up with a two crude algorithm ideas, and I don't know which of these (if any at all) would be the most effective:

First distribute work to the person with (1) the least number of shifts assigned so far and then (2) with the least number of availabilities.
Distribute all work days to those with the least number of availabilities, but fill a person's entire schedule before progressing on to the next person. Shifts get assigned by determining which time slot (A/B/C/D/E) has the least number of people working it.

The thing that I don't like about each of these algorithms is that it seems very easy to get stuck at any given point, and from there I really wouldn't know what to do.

Thanks.

The simplest solution (in terms of saving you the time of understanding the literature) is probably going to be to use integer linear programming (ILP / MILP).  You can formulate it as an ILP instance, then apply an off-the-shelf ILP solver.

Introduce zero-or-one variables $x_{i,j}$, with the goal that $x_{i,j}=1$ means that the $i$th person is assigned to $j$th time slot, and $x_{i,j}=0$ means that they're not assigned to that time slot.  Now you can write down some linear inequalities/equations constraining these, e.g.,

$\sum_{i} x_{i,j} = n$ for each $i$ (each time slot needs to be filled with $n$ people)

$\sum_j x_{i,j} = c_i$ for each $i$, where $c_i = $ the number of shifts the $i$th worker should be assigned

Also if the $i$th worker isn't available for the $j$th slot, then add a constraint that $x_{i,j}=0$.

Also, $0 \le x_{i,j} \le 1$ (to force each $x_{i,j}$ to be zero or one).

The combination of all of these constraints gives you an integer linear program.  Ask the ILP solver to find a feasible solution, and boom, you're done.  This might not be the most efficient possible algorithm, but it will be simple to implement and play around with, and I expect that it'll give high-quality solutions and be fast enough for the size of problem you're likely to encounter in practice.


Help needed with lesson on recursion I'm studying CS online, and I'm reading this lecture on recursion, see "3.2. A Mathematical Example".

I understood the beginning and I even made a program that calculates $X$ to the power of $N$ using recursion.

Reading on, I quote from the lesson's content:

  Find an algorithm for raising a number $X$ to the power $N$, where $N$ is a positive integer. You may use only two operations: multiplication, subtraction. We would like to multiply $N$ copies of $X$ all at once, but, like the piles of books, we do not have an operation that directly allows us to do that: we can only multiply two numbers at a time. In other words, the problems we can solve directly are these:

  Raise $X$ to the power $1$: answer = $X$.
  Raise $X$ to the power $2$: answer = $X \times X$.
  Any other problem we have to solve indirectly, by breaking it down into smaller and smaller problems until we have reduced it to one of these base cases.
  So, if $N > 2$, we split the original problem into two subproblems:

  $P1$: raise $X$ to the power $I$. The answer to this is $S1$.
  $P2$: raise $X$ to the power $N-I$. The answer to this is $S2$.
  To get the final answer, $S$, combine $S1$ and $S2$: $S = S1 \times S2$.

  How do we solve $P1$ and $P2$? They are problems of exactly the same type as original problem, so we can apply to them exactly the same strategy that we applied to the original problem. We check to see if we can solve them directly... if $I=1$ or $I=2$ we can solve $P1$ directly; if $N-I=1$ or $N-I=2$ we can solve $P2$ directly. The problems we cannot solve directly, we solve recursively, as just described. An interesting feature of this strategy is that it works no matter how we split up $N$.

What I don't understand is, how I'm supposed to split it up into bigger chunks to achieve greater speed.

Since the game rules are that I can only use multiplication and subtraction operators, so how can I divide $X$?
If I know that $N-I=2$, how can I solve $P2$ directly, it's $X \times X \times X$, meaning two multiplications?
Is each $P$ a separate recursion?

Here are several approaches to compute $x^n$ from smaller powers of $x$:

doing $x \times x^{n-1}$. The former is $P(1)$ the latter is $P(n-1)$.
doing $x^2 \times x^{n-2}$. The former is $P(2)$, the latter $P(n-2)$.

But we don't need to use $P(1)$ and $P(2)$ at each step, right? we can use any $P(k)$ with $k<n$. So how about,

doing $x^{n/2} \times x^{n/2}$?
(or in general $x^{k} \times x^{n-k}$)

Now, assume each multiplication takes $M$ time. Which approach is the fastest?

EDT after comments:

the main idea of recursion (somewhat similar to induction), is that we can "solve" some problem by using the solutions of smaller problems.

So $P(n)$ can be easily computed by $P(n/2) \times  P(n/2)$ (assuming $n$ is even and above 2). But how do we compute $P(n/2)$? well, that's the magic, the above idea works for any number $n$ and specifically also for the number $n/2$ (as long as it is even and above 2); So how do we compute $P(n/2)$? We recurse!

  $P(n/2)  = P( (n/2)/2) \times P( (n/2)/2) $

Why does it work? because eventually ((n/2)/2)...)/2 will be either 1 or 2, and this is $P(1)$ or $P(2)$ that we know how to solve.

To sum up, the recursion will look like this:

function P(n):
if n=1 or n=2  return ....
else
   if n is even, return P(n/2) * P(n/2)
   if n is odd, return  ..... (very similar)...

I leave you to work out the details.

This is of course the faster way. The slower way, but maybe simpler to understand, is to do the recursion step by step. The function in this case will look like:

function P(n):
if n=1 or n=2  return ....
else
   return P(n-1) * x

This one works for any number $n$ and returns $x^n$. The last line just instantiates the function again with a smaller parameter.


Would $\sf RP = NP$ imply $\sf NP = coNP$? If $\sf RP = NP$ then the hierarchy collapses to its second level (by the Karp-Lipton theorem). But what about $\sf NP$ and $\sf coNP$?

I tried to prove that $\sf BPP$ is contained in $\sf NP$ (the other direction is trivial if $\sf RP = NP$) but to no avail, and I'm not even sure that it's true.

What do you think?

If we will able prove that RP is closed under complement then we can say that
If RP = NP then it imply NP = Co-NP.

But we don't know whether RP=Co-RP or not.  BPP = P can be proved under some reasonable assumptions but RP $ \subseteq $ BPP.

If we show that RP = BPP then your statement will be correct.

References:

RP in Wikipedia
Notes on Randomized Algorithms (pdf)
RP in the Complexity Zoo


What is the difference between $x:A$ and $x \Xi A$? Given a type hierarchy $(\tau,\sqsubseteq)$ and a signature $(VSym, FSym, PSym, \alpha)$, one says that the typing function $\alpha$ assigns to each variable symbol $x \in VSym$ a non-empty type $A \in \tau \setminus\{\bot\}$ and is written as:
$$ x: A \tag1$$
Furthermore, for every type $A \in \tau \setminus\{\bot\}$, there is a predicate symbol $\Xi A \in PSym$ called the type predicate which tells us if or not a certain $x$ is an instance of type $A$. We write it as:
$$x \Xi A \tag2$$
That makes me think what set constitutes the domain of a predicate symbol. Clearly, if the domain is $VSym$, then $(1)$ and $(2)$ mean exactly the same thing, and therefore, would be a redundancy of definition.
If not, which is surely the case, how do they differ? In particular, can you tell if a certain object is an instance of a certain type and not just a variable symbol with the given type assigned to it (or vice versa)?
More precisely, if a predicate symbol is a function from a certain domain to the set $\{\mathrm{True},\mathrm{False}\}$, what exactly is the domain of this map? Is there any overlap of this domain with $VSym$?
I am reading the chapter on first order logic from Deductive Software Verification – The KeY Book. (I am not fully sure if this question fits in a mathematics or a computer science forum.)
Thank you for your time.

Background:
Please refer to this document (the first couple of pages actually) to update yourself with the relevant ideas and definitions. Here's a brief summary.

A type hierarchy is a pair $\mathscr T = (\tau,\sqsubseteq)$, where

$\tau$ is a set of type symbols;
$\sqsubseteq$ is a partial ordering on $\tau$, called the subtype relation;
there are two designated type symbols, the empty type $\bot \in \tau$ and the universal type $\top \in \tau$ with $ \bot \sqsubseteq A \sqsubseteq \top \forall A \in \tau$.

A signature (for a given type hierarchy $\mathscr T$) is a
quadruple $\Sigma = (VSym, FSym, PSym, \alpha)$ of

a set of variable symbols $VSym$,
a set of function symbols $FSym$,
a set of predicate symbols $PSym$, and
a typing function $\alpha$,

such that

$\alpha(v) \in \tau_q := \tau \setminus\{\bot\}\ \forall v \in VSym$,
$\alpha(f) \in \tau_q^* \times \tau_q\ \forall f ∈ FSym$, where $\tau_q^*$ is the set of all (possibly empty) sequences of elements in $\tau_q$, and
$\alpha(p) \in \tau_q^*\ \forall p \in PSym$.
There is a function symbol $(A) \in FSym$ with $\alpha((A)) = ((\top),A)$ for any $A \in \tau_q$, called the cast to type A.
There is a predicate symbol $\doteq \in PSym$ with $α(\doteq) = (\top,\top)$.
There is a predicate symbol $\Xi A \in PSym$ with $\alpha(\Xi A) = (\top)$ for any $A \in \tau$, called the type predicate for type A.

Notation: We write

$v : A$ for $\alpha (v) = A$,
$f : A_1,...,A_n \to A$ for $\alpha(f)=((A_1,...,A_n),A)$,
$p: A_1,...,A_n$ for $\alpha(p)=(A_1,...,A_n)$,
$x \Xi A$ (read: $x$ is an instance of $A$) for $\Xi A(x)$,
$x \doteq y$ for $\doteq(x,y)$.

NOTE: Some texts (such as the document linked above) implicitly do the type assignment carried out by $\alpha$ and write down the definition in the standard notation mentioned above.

$x:A$ is a statement about objects in the formal system, like, for example, $\vdash 2+4:\texttt{int}$, whereas
$x\Xi A$ is an expression in the formal system, like $\texttt{if}~ 2 + 4 ~\texttt{==}~5 ~\texttt{then}~ e_1~ \texttt{else} ~e_2$.


Combinatory interpretation of lambda calculus According to Peter Selinger, The Lambda Calculus is Algebraic (PDF). Early in this article he says:

  The combinatory interpretation of the lambda calculus is known to be
  imperfect, because it does not satisfy the $ξ$-rule: under the
  interpretation, $M = N$ does not imply $\lambda x.M = \lambda x.N$ (Barendregt, 1984).

Questions:

What kind of equivalence is meant here?
Given this definition of equivalence, what is a counter-example of the implication?

The equivalence is just equivalence in the equational $\lambda$-theory under discussion. In this case, it's the theory outlined in Table 1. Note that this theory does not include $\eta$: doing so would make the theory extensional, and the point is eventually that $\xi$ respects $\lambda$'s intensionality, while it would make CL partially extensional. I am not sure why the other answer mentions $\eta$.

Note that in $\lambda$:

$$(M =_\beta N) \Longrightarrow (\lambda x.M =_\beta \lambda x.N) \tag{1}$$

This should be intuitively obvious: if $M$ is $\beta$-convertible to $N$ when it stands by itself, then it is also $\beta$-convertible to $N$ when it is a subterm of $\lambda x.M$.

The $\xi$-rule, defined as
\begin{align}
M &\;= N \\
\hline
(\lambda x.M) &\;= (\lambda x.N)
\tag{$\xi_\lambda$}
\end{align}
makes this inference directly possible when it is part of a $\lambda$-theory. Its CL analogue would be:
\begin{align}
M &\;= N \\
\hline
(\lambda^* x.M) &\;= (\lambda^* x.N)
\tag{$\xi_{CL}$}
\end{align}

Now, the point is that in CL, the following does not hold:

$$(M =_w N) \Longrightarrow (\lambda^* x.M =_w \lambda^*x.N) \tag{2}$$

In other words, if two terms are weakly equal, then this is not necessarily true for their pseudo-abstracted versions.

Consequently, if we add $\xi_{CL}$ to a CL theory, then we start equating terms which have different normal forms.

Note. Here, $M =_w N$ denotes weak equality. It means that $M$ can be converted into $N$ (and vice versa) by a series of $\mathsf{S}$ and $\mathsf{K}$ contractions (possibly also $\mathsf{I}$, if it is part of the theory). As you probably know, $=_w$ is the CL analogue of $=_\beta$.

$\lambda^*$ is the pseudo-abstractor as defined on page 5 of your document. It has the following property:

$$(\lambda^*x.M)N \rhd_w [N/x]M \tag{3}$$

This property makes it easy to find a CL analogue for any $\lambda$-term: just change $\lambda$ to $\lambda^*$ and apply the translations according to the definition of $\lambda^*$.

To be clear, the 'counter-example' in this answer is not a counter-example to (2). Because if we have:

$$M = x \tag{4}$$
$$N = (\lambda^*z.z)x \tag{5}$$

Then $N$ really denotes (applying the translations of page 5, and the fact that $\mathsf{I}$ is defined as $\mathsf{SKK}$ at the end of page 4):

$$N = (\lambda^*z.z)x = \mathsf{I}x = \mathsf{SKK}x \tag{6}$$

Since $\mathsf{SKK}x \rhd_w \mathsf{K}x(\mathsf{K}x) \rhd_w x$, we indeed have that $M =_w N$. However, if it is a counter-example, we should then have that $(\lambda^* y. M) \not=_w (\lambda^* y. N)$. But if we translate, we actually get:

$$(\lambda^* y. M) = (\lambda^* y. x) = \mathsf{K}x \tag{7}$$
$$(\lambda^* y. N) = (\lambda^* y. \mathsf{SKK}x) = \mathsf{K}(\mathsf{SKK}x)\tag{8}$$

And is easy to verify that (7) and (8) are still weakly equal, for:

$$\mathsf{K}(\mathsf{SKK}x) \rhd_w \mathsf{K}(\mathsf{K}x(\mathsf{K}x)) \rhd_w \mathsf{K}x \tag{9}$$

Now, a proper counter-example to (2) would be:

$$M = \mathsf{K}xy$$
$$N = x$$

Since $\mathsf{K}xy \rhd_w x$, we definitely have that $M =_w N$. However, if you translate carefully for the abstracted versions, then you will see that both are distinct normal forms - and these cannot be convertible according to the Church-Rosser theorem.

First we check $M'$:

\begin{align}
M' &= \lambda^* x.\mathsf{K}xy \\
&= \mathsf{S}(\lambda^* x.\mathsf{K}x)(\lambda^* x.y)\\
&= \mathsf{S}(\lambda^* x.\mathsf{K}x)(\mathsf{K}y) \\
&= \mathsf{S}(\mathsf{S}(\lambda^* x.\mathsf{K})(\lambda^* x.x))(\mathsf{K}y) \\
&= \mathsf{S}(\mathsf{S}(\lambda^* x.\mathsf{K})(\mathsf{I}))(\mathsf{K}y) \\
&= \mathsf{S}(\mathsf{S}(\lambda^* x.\mathsf{K})(\mathsf{SKK}))(\mathsf{K}y) \\
&= \mathsf{S}(\mathsf{S}(\mathsf{KK})(\mathsf{SKK}))(\mathsf{K}y)
\end{align}
Here you can verify that $M'$ is a normal form. Here you can check that $(\lambda^* x.Kxy)P \rhd_w P$, as you should expect if $\lambda^*$ is supposed to behave like an abstractor for CL. (Click the blue links to perform weak contractions.)

Now we check $N'$:
\begin{align}
N' &= \lambda^*x.x \\
&= \mathsf{I} \\
&= \mathsf{SKK}
\end{align}

Which is obviously a normal form different from $M'$, so $M' \not=_w N'$ by the Church-Rosser theorem. Note also that $N'P \rhd_w P$, i.e. $M'$ and $N'$ 'produce the same output' for arbitrary inputs $P$.

We have now proven that (2) does not hold in CL, and that a CL theory incorporating $\xi$ would therefore equate terms that are not weakly equal. But why do we care?

Well, first of all, it makes the combinatory interpretation of $\lambda$ imperfect: apparently not all metatheoretic properties carry over.

In addition, and perhaps more importantly, while there exist extensional theories of $\lambda$ and CL, they are originally and commonly kept intensional. Intensionality is a nice property because $\lambda$ and CL model computation as process, and from this perspective two different programs (specifically, terms that have a different normal form) that always produce the same results (given equal inputs) are not to be equated. $\xi$ respects this principle in $\lambda$, and if we want to make $\lambda$ extensional, we could just add e.g. $\eta$. But the introduction of $\xi$ in CL would no longer make it completely intensional (in fact, only partially so). And this is the reason for $\xi$'s 'notoriety', as the article puts it.


Smallest $s$-component in mincut Suppose there is a directed graph $G=(V,E)$, with source $s$ and sink $t$, and I compute the max flow on it. Then I know that I can find a min-cut $(A,B)$, by letting $A$ be the set of vertices that are reachable from the source $s$.

My question is is this set $A$ the smallest possible $s$-component? I think it is.
To be precise, does there exist a subset of vertices $A^*$, such that $(A^*, V\setminus A^*)$ is a min-cut, and for all other possible subsets of vertices $A$ such that $(A, V\setminus A)$ is a min-cut, we have $size(A^*) \leq size(A)$.

Furthermore, for any other min-cut $(C,D)$, do we have $A \subset C$?.  I also think this is the case. But I can't prove it.

Any intuition / hints are much appreciated!

Edit

Definition of $s$-component:
The min-cut is the partition of the vertices of $G$ into two disjoint sets $(A,B)$, where $A$ contains the source $s$ and $B$ contains the sink $t$. The $s$-component w.r.t. a min-cut is then the set $A$.

By "smallest" $s$-component I mean $s$-component with smallest cardinality. I'm wondering if there can be several different minimal $s$-component w.r.t. set inclusion, i.e. $s$-components with same cardinality, but are not equal as sets. Equivalently, wondering if there is a minimum $s$-component; a set of vertices that is in ALL $s$-components.

I believe that the answer is yes: any min-cut constructed in this way from a max-flow will also have minimum possible cardinality, among all possible min-cuts.

There can be multiple min-cuts, all with the same cost.  They form a lattice structure: the intersection of two min-cuts is another min-cut, and the union of two min-cuts is another min-cut.  You can identify a "smallest" element in this lattice by taking the intersection of all min-cuts; this will be another min-cut, and it will have the smallest cardinality of all min-cuts.

As I understand it, it is possible to prove that the min-cut obtained from a max-flow is always this "smallest" min-cut.  Or, to put it another way, if you think of the source $s$ on the left and the sink $t$ on the right, then any min-cut obtained from a $s,t$-max-flow will be always be a "leftmost" cut.  Also, it will follow that any other min-cut will be a superset of this cut found by max-flow, exactly as you conjectured.

For references to these results, and other related material, see the following questions (note: you may need to double-check some of the claims yourself, as I have not personally verified them):

Does Ford-Fulkerson always produce the left-most min-cut

https://stackoverflow.com/a/8101250/781723

https://stackoverflow.com/q/26696312/781723

https://stackoverflow.com/q/9210755/781723

https://stackoverflow.com/q/41964288/781723


Runtime Analysis: What grows faster? I was wondering which runtime is a tight upper bound for $f(n,m)= n^2 + 1/2^k$ with $k = n - m$
Intuitively I thought that $f(n,m)$ is in $O(n^2)$ but the longer I am thinking about this the more I tend to say that $f(n,m)$ is in $O(2^k)$.
Can anyone help me?

Since $k=n-m \ge 0$ you have that $n^2 < f(n,m) \le n^2 + (1/2)^0 = n^2+1$, showing that $f(n,m) \in \Theta(n^2)$.


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

The consensus from the available information I've found points to SNOBOL4, released in 1967, as the earliest implementation of "associative arrays".

This post on the Software Engineering community is very similar to your question and has some great info.

Chicago University - Intro to TCL course: Associative Arrays

  Associative arrays were first used in the programming language Snobol4 in the mid-1960s. They are a very common data structure in the Unix environment, being provided as the major data structure by languages like Awk, Perl, etc.


Why are there only NOR and NAND flashes? According to my lecture and wikipedia NOR and NAND flashes are the most common used. However there isn't really explained why people decided to use these logic gates instead of others. Can someone explain me, what are the factors deciding which gates to use and show how these gates match those properties best?

NAND and NOR are the only two binary gates that are functionally complete, which means that using just one gate type you can implement any circuit.

This greatly simplifies fabrication. As long as you can construct a single type of gate many times using the same technique, and can connect them arbitrarily, you can create any circuit.


Greatest matching values in matrix Problem:

Looking for an efficient algorithm to find the largest value that exists in all columns.

Constraints:

The values in each column are always decreasing

My algorithm:

Check the first row for match
Use the lowest value from first row to search for match
Use the value from row x, column y to search for match
Increase row index until n
Increase column index until n

Examples:

Best case
$$A=\begin{bmatrix}17 & 17 & 17\\ 14 & 14 & 16\\ 13 & 10 & 15\\ 11 & 8 & 13\end{bmatrix}$$

Select Row1,Col1 to match
17, 17, 17

Result is 17

Average case
$$B=\begin{bmatrix}13 & 10 & 15\\ 11 & 8 & 13\\ 10 & 7 & 12\\ 9 & 5 & 10\end{bmatrix}$$

Select Row1,Col1 to match
13, 10, 15

Select lowest value in Row1 (10)
10, 10, 10

Result is 10

Worst case
$$C=\begin{bmatrix}14 & 14 & 16\\ 13 & 10 & 15\\ 11 & 8 & 13\\ 10 & 7 & 12\end{bmatrix}$$

Select Row1,Col1 to match
14, 14, 16

Select lowest value in Row1 (14)
14, 14, x

Select Row2,Col1 to match
13, x, 13

Select Row2,Col2 to match
10, 10, x

Select Row2,Col3 to match
x, x, 15

Select Row3,Col1 to match
11, x, x

Select Row3,Col2 to match
x, 8, x

Select Row3,Col3 to match
13, x, 13

Select Row4,Col1 to match
10, 10, x
(repeated!)

Select Row4,Col2 to match
x, 7, x

Select Row4,Col3 to match
x, x, 12

Result is no matches

Build single hash table from any column and augment it with counter, set it to 1.
Add second column to the hash table discarding not existing values from the second column. Optionally you can remove values that are still singular.
Add third column element by element, store the maximal encountered triplet.

This will run in expected $\mathcal O(n)$ time, where $n$ is column length.

What you have proposed looks a bit like selection sort. Making it explicit, sort columns in descending order and start checking for triplet. It would give $\mathcal O(n\log(n))$ runtime.


$a_k$ is $\{L :\exists M$ a pushdown automaton with bounded stack of size $k$ which accept $L\}$ what is the set $\bigcup_1^\infty a_k$? A related question:
How to prove that a bounded pushdown automaton is regular?

Well I proved that $a_k$ for each $k$ is the set of all the regular language. Thus $\bigcup_1 ^{\infty} a_k = \bigcup_1 ^{\infty}\{$ the set of all regular languages} = $\{$ The set of all regular languages $\}$.

However before noticing that $a=\bigcup_1^\infty a_k$ is taking unions of the same set, I thought that the Context-Free-Languages might be a subset of $\bigcup_1^\infty a_k$. So, I wish for someone to point out the flaw of the next explanation:

Let $L$ a CFL, and $M$ a pushdown automaton which accepts $L$. Now denoting $L_k = \{w\in L : M$'s stack size $\le k$ throughout $w$'s reading process $\}$ each $L_k$ is a regular language because $L_k \in a_k$. (I think that was the shaky point, but I can't explain why this claim is wrong). So $L = \bigcup_1^\infty L_k  \in\bigcup_1^k a_k =a$.

The flaw is in the claim $\bigcup_{k=1}^\infty L_k  \in\bigcup_{k=1}^\infty a_k$.  That is not a valid conclusion.  It doesn't follow from the fact that $L_k \in a_k$ for each $k$.
(Consider: just because $3 \in S_1$ and $5 \in S_1$, it doesn't follow that $3+5 \in S_1 \cup S_2$.  Just because $L_1 \in S_1$ and $L_2 \in S_2$, it doesn't follow that $L_1 \cup L_2 \in S_1 \cup S_2$.  Just because $L_k \in a_k$ for each $k$, it doesn't follow that $\bigcup L_k \in \bigcup a_k$.  In fact, it is correct that $L_k \in \bigcup a_k$ holds for each $k$, but $\bigcup L_k \in \bigcup a_k$ doesn't hold; the regular languages are not closed under infinite unions.)
You won't always have us to check every dubious proof, so let me teach you two techniques you can use if you run across a proof that you are suspicious/skeptical of:

If you're not sure whether to be convinced of a proof, try taking each individual step and writing out a detailed proof of it.  If you started with a 4-line proof sketch, this might turn into a 40-line proof, so it's tedious, but it's often a good way to discover whether the proof is valid (sometimes when it comes time to write down the justification, you discover that that step that looks obvious in writing isn't actually so obvious).

Pick a specific example and work through what the logic of the proof is saying about that example.  Check whether the logic is valid for that particular example.
For instance, pick $L= \{0^n 1^n : n \in \mathbb{N}\}$; this is perhaps the canonical CFL that isn't regular.  Work through what your proof claims about that $L$, and check each statement to see if it is valid.  Well, $L_k = \{0^n 1^n : n \le k\}$, and sure enough, it is correct that $L_k \in a_k$ for each $k$.  It is also correct that $L = \cup_{k=1}^\infty L_k$.  However, when you check the claim that $\bigcup_{k=1}^\infty L_k  \in\bigcup_{k=1}^k a_k$, you discover that the claim is not correct, as the left-hand side is $L$ and the right-hand side is the set of all regular languages and $L$ is not regular.  So, that's the step you should be suspicious of.


UCT1 Algorithm: What does "total number of simulations" mean? When reading up on the UCT1 algorithm (I'm writing a Monte Carlo tree search), I'm having trouble with the formula.
$$\frac{w_i}{n_i} + \sqrt{\frac{\ln t}{n_i}}$$
Wikipedia, this guy, and this guy all say that $t$, or whatever else they use for that variable, equals the "total number of simulations". What does this mean, exactly? The total number of simulations in the entire tree? The child nodes of that particular node? The "sibling" nodes? So, what is the $t$ is this equation? Thanks!

The UCT1 algorithm is actually an algorithm for a multi-armed bandit. There is a machine with several arms. At each round you pull one of the arms and get some reward. Your goal is to maximize your total reward. In this algorithm, $t$ is the round number: $t = 1$ in the first round, $t = 2$ in the second round, and so on.

When using UCT1 to perform Monte Carlo tree search, you treat each explored node as a multi-armed bandit. Monte Carlo tree search consists of several rounds of simulations: in each round a complete game is played out. The value of $t$ for a particular node is the number of rounds at which you passed through the node.

$n_i$ is the number of simulations through the $i$th child, i.e. how many simulations encountered that state in their simulations. A simulation consists of an entire game played out. Once it exits the node it invariably goes through one of its children. So $t$ is the sum of the $n_i$.

You ask:

  I made some images. Is it like this or like this?

It's more like the latter.


Difficulty in understanding this summations to analyze time complexity I wanna know if what this link https://stackabuse.com/shell-sort-in-java/'s calculation of the complexity of shell sort is true.

Here's the shell sort algorithm:

void shellSort(int array[], int n){
    for (int gap = n/2; gap > 0; gap /= 2){
      for (int i = gap; i < n; i += 1) {
        int temp = array[i];
        int j;
        for (j = i; j >= gap && array[j - gap] > temp; j -= gap){
          array[j] = array[j - gap];
        }
        array[j] = temp;
      }
    }
}

Let me attach the site author's calculation using summations:

Where did he get the o(n log n) from? And why O(n^2)?

Shellsort is notoriously difficult to analyze (surprising for such a simple algorithm). In Knuth's "Sorting and Searching" it gets an inordinate scrutiny, papers on its performance get published regularly.

Then again, the Busy Beaver function (At most how many ones does an $n$ state Turing machine write starting on an empty tape before halting?) is known only up to $n = 4$, the current record holder with 6 states writes $3.515×10^{18267}$ ones before halting...


What are skew arithmetic circuits? I am trying to understand the definition of skewed circuits in these slides which is given as follows:

A circuit is skew if in each product gate, at least one product has degree $\le 1$.

I think author wants to say that each product gate is either a leaf node or one level above the leaf node.

Skew arithmetic circuits are usually defined a bit differently: in every multiplication gate, one of the inputs of the gate is a constant or an input of the circuit (we assume that multiplication gates are binary).
This is very similar to your definition, if linear is interpreted as syntactically linear. That is, one of the inputs of any multiplication gate is either a constant, an input of the circuit, or the output of an addition gate whose inputs are inputs of the circuit or constants. Using the distributive rule, we can take a circuit satisfying this definition and turn it into a circuit satisfying the usual definition.
Another interpretation would be that one of the inputs of any multiplication gate is a linear function of the inputs, that is, it is semantically linear. For example, $(a+b)^2-(a-b)^2$ is semantically linear but not syntactically linear. This is probably not the interpretation which is meant here.


Is it possible to make a Turing Machine that accepts the language $\{\alpha\alpha\alpha | \alpha \in \{a, b\}^∗\}$? I'm having a lot of problems trying to make a Turing Machine that accept that language, is it even possible to make it? and if so, how can I proceed to make the Turing Machine?

Here is a particularly simple algorithm for the slightly simpler language $\{\alpha\alpha \mid \alpha \in \{a,b\}^*\}$; a similar approach works in your case.

The Turing machine starts by checking whether the input is empty (if so, accept) and whether it has even length (otherwise, reject). Next, we are going to find the midpoint of the input. The idea is to put a "chip" on each end of the input, and at each step, advance each chip toward the middle, until the two chips coincide. If done correctly, we can mark the middle of the input, which is the starting point of the second copy of $\alpha$. All that remains to be done is to check that the first half of the input is identical to the second half, which can be done using a simple iteration.


Context-free Language - Pumping Lemma? im having some problems when it comes to Pumping Lemma of Context-free Language ... this is the Language :

$$L = \{a^n b^n c^m | n\ge 0 , 0 \le m \le 2n \}$$

Here is my attemp to prove that the language is not context-free:

Assume $L$ is context-free. Let $p,r>0$ be the pumping length given by the lemma.

Let $z=a^p b^p c^r$, then $z∈L$

Than according to the lemma, z can be written as z=uvwxy where the following properties hold:

$$|vx|≥1$$
$$|vwx|≤n$$
for every $i≥0$, $uv^iwx^iy∈L$

for the cases $i$ always had some problems ... there is one ..

$vx = a^n b^n$ (no $c$'s )

i really have some problems understanding the PL for CF Language

The solution which I provide below is very similar to Example 2.37 in classical Sipser's book "Introduction to the theory of computation"

  Let $p,r>0$ be the pumping length given by the lemma.

I think you have a little abuse of notation. Look carefully at definition. It states that if $L$ is $CFL$ then, there exists some constant $p$ (pumping length) that for every string $s \in L$ such that $|s| \ge p$, $s$ can be divided on five parts such that the following properites hold:

  $|vx|≥1$ $|vwx|≤n$ and for every $i≥0, uv^iwx^iy∈L$

So, let us take $s = a^nb^nc^{2n}$, where $n+n+2n > p$. Then the conditions for lemma are hold, and it follows that $s = uvwxy$ with all those properties. From the first property we get that at least one of $v$ or $x$ is non-empty string. Now, we should consider several cases:

1) At least one of $v$ or $x$ contains diffent letters of the alphabet (for example, $v$ = $zabt$, $|z|, |t| \ge 0$). Then $uv^2wx^2y$ doesn't has the form $a^nb^nc^m$ (problems with order, in my example $v^2 = zabtzabt$), so we get a contradiction.

2) Either $v$ or $x$ contains only one letter from alphabet. Here we get such cases:

2.1) $v$ and $x$ don't contain the letter $c$. By lemma the string $s_1 = uv^0wx^0y \in L$. But $s_1$ has less than $n$ letters $a$ or $b$, while it contains $2n$ letters $c$. So, the property $m \le 2n$ doesn't hold in this case and we get a contradiction.

2.2) $v$ or $x$ contain the letter $c$, so either $a$ or $b$ doesn't belong to $v$ and $x$. Then string $s_1 = uv^2wx^2y$ contains at least $2n + 1$ $c$'s, and only $n$ $a$'s or $b$'s. Again, we get a contradiction.


Concrete and simple applications for bipartite graphs I am looking for concrete and simple problems that may be solved using bipartite graphs or bipartite graph properties. Any idea along with explanations are welcome.

Assignment Problem would be one such example:

  There are a number of agents and a number of tasks. Any agent can be
  assigned to perform any task, incurring some cost that may vary
  depending on the agent-task assignment. It is required to perform all
  tasks by assigning exactly one agent to each task and exactly one task
  to each agent in such a way that the total cost of the assignment is
  minimized.

Hall's Marriage Theorem would be another:

  Imagine two groups; one of n men, and one of n women. For each woman,
  there is a subset of the men, any one of which she would happily
  marry; and any man would be happy to marry a woman who wants to marry
  him. Consider whether it is possible to pair up (in marriage) the men
  and women so that every person is happy.

The Mutilated Chessboard Problem can be solved using The Hall's Theorem:

  Suppose a standard 8x8 chessboard has two diagonally opposite corners
  removed, leaving 62 squares. Is it possible to place 31 dominoes of
  size 2x1 so as to cover all of these squares?


Fair division of two-dimensional cake I am interested in procedures for fair division of land (i.e. envy-free division, or at least proportional division).

In contrast to the well-studied cake-division problem, land-division is two-dimensional, i.e., the preferences of the users may vary both horizontally and vertically. Therefore, it is not practical to limit the algorithm to parallel cuts.

The only reference I found so far is Karthik Iyer and Michael Huhns, 2007. They say that "We have not come across any constructive (algorithmic) solutions so far to the generic land division problem. All the papers have
offered existential solutions to qualified versions of the problem."

They themselves prove an O(n^2) algorithm for proportional land division, with certain limitations (e.g. each of the n agents must mark n rectangular regions with utility 1/n, and if the rectangles don't overlap too much, the algorithm guarantees that each agent gets one of its rectangles).

Do you know of any newer references on this problem? I am interested specifically in practical algorithms, and they may be approximate.

The authors you cite have another paper on the topic.

Would you be satisfied with a model which assumes that the properties of the surfaces to be allocated can be summarized by an arbitrarily large but finite set of one-dimensional parameters (say length, depth, northmost point, eastmost point,... really as many as you want but finite) ?

If this is satisfying to you, and you are ok with assuming that people have preferences over surfaces as described by the values of these parameters, you might find useful insights in the theory of fair allocation of bundles of multiple goods. A great (and free) introduction is "Fair Allocation Rules" by William Thomson.

Of course when the dimensions represent parameters describing the shapes to be allocated, you are likely to have unusual preferences which are hard to work with and do not fit nicely with the existing results. Might be worth giving it a try though...


Difference between an a microcontroller and a system on a chip? I pulled this right from Wikipedia to compare, staring with an SoC:

  A system on a chip or system on chip (SoC or SOC) is an integrated circuit (IC) that integrates all components of a computer or other electronic system into a single chip.

And to compare, here's the microcontroller:

  A microcontroller (sometimes abbreviated µC, uC or MCU) is a small computer on a single integrated circuit containing a processor core, memory, and programmable input/output peripherals.

What is the difference? If they are both small computers that integrate all components on a single integrated circuit, and are limited, why are they regarded as different concepts or terms? A microcontroller has everything an SoC has, so why are they claimed to be different?

To elaborate further, what draws any tangible line here on any noteworthy differences?

They both are in the area of embedded systems, but aside from minimal differences, they are both seemingly exact in almost every way.

The microcontroller definition is, at best, poorly worded.  The distinction between an SoC and a microcontoller may be a bit fuzzy, but not that fuzzy.  A microcontroller might be included as one element of an SoC, but it is not an SoC.

SoC means (approximately) "single chip solution."  The SoC in a cell phone might have a 32-bit ARM processor running Linux (Android) and any apps that the user has installed.  In addition it would have a GPU, the wireless transceiver and modem, the video and audio decoders for streaming video, GPS, controllers for the accelerometer, controllers for battery management, and who knows what else.  There might be many microcontrollers in a SoC.

The "peripherals" included on the microcontroller itself are going to be a lot less specific.  They are really registers for communicating with the off-chip devices (or at least off-module, if the microcontroller is embedded in an SoC) that you are controlling with the microcontroller.  The peripherals might include some analog-to-digital or digital-to-analog converters, and/or a USB controller and/or I2C bus controller.

More often than not the microcontroller will be running a single program (no operating system, no apps), and that program will be stored in a read-only-memory (Flash).  (Usually the flash memory is included in the same chip as the microprocessor.)

As an example.  Here's the specs for the Microchip PIC16F77:

  This powerful (200 nanosecond instruction execution) yet easy-to-program (only 35 single word instructions) CMOS FLASH-based 8-bit microcontroller packs Microchip's powerful PIC® architecture into an 40- or 44-pin package and is upwards compatible with the PIC16C5X, PIC12CXXX and PIC16C7X devices. The PIC16F77 features 8 channels of 8-bit Analog-to-Digital (A/D) converter with 2 additional timers, 2 capture/compare/PWM functions and the synchronous serial port can be configured as either 3-wire Serial Peripheral Interface (SPI™) or the 2-wire Inter-Integrated Circuit (I²C™) bus and a Universal Asynchronous Receiver Transmitter (USART). All of these features make it ideal for more advanced level A/D applications in automotive, industrial, appliances and consumer applications.

It also has 14KB of flash to store the program and 368 bytes of RAM.  (Yes you read that right, bytes.)


Finding paths of certain length in trees In a graph tree, is there any "smart/existing/efficient" algorithm to find linear segments of defined length?

For example given a tree graph:

g = {1 -> 2, 2 -> 4, 3 -> 6, 4 -> 8, 6 -> 12, 1 -> 3, 2 -> 5, 3 -> 7,
   4 -> 9};
TreePlot[g, VertexLabeling -> True]

How can one find all linear segments of length 4. In this example this would be

1 2 4 8
1 2 4 9
1 3 6 12
2 1 3 7
2 1 3 6
9 4 2 5
...

This is probably a common problem, but I guess I have not yet found the right keywords for google. The naive implementation would be to visit every node, then recursively try to get four nodes away and delete all duplicated segments at the end...

Idea: Root the tree in an arbitrary node. For every node, count

paths in its subtrees,
paths that start in a subtree and end in the root, and
paths that start in one subtree, traverse the root and end in another subtree.

That is, for a given node $v$ with children $u_1, \dots, u_m$, the number $p(v,k)$ of paths of length $k$ (counting nodes) in the subtree $T_v$ rooted in $v$ is

$\qquad\displaystyle\begin{align*}
  p(v,k) &= \sum_{i=1}^m \biggl[ p(u_i,k) \biggr] \\
         &\ + \sum_{i=1}^m \biggl[ p_r(u_i,k-1) \biggr] \\
         &\ + \sum_{i=1}^{m-1}  \sum_{j=i+1}^m \sum_{l=1}^{k-2} \biggl[ p(u_i,l) \cdot p(u_j,k-1-l) \biggr]
\end{align*}$

for $k \geq 2$; we anchor the recurrence in $p(v,1) = 1$ for all $v$. For the paths ending in the root, we get the (simpler) recurrence

$\qquad\begin{align*}
  p_r(v,k) &= \sum_{i=1}^m p_r(u_i,k-1)
\end{align*}$

which also anchors in $p_r(v,1) = 1$.

These recurrences immediately imply a recursive algorithm (computing both simultaneously).

The runtime is in "$\Theta(m^2k)$" per node of degree $m$; hence, on trees with finitely bounded degree, the algorithm runs in time $\Theta(nk)$. Otherwise, it may take time $\Theta(n^2k)$ (e.g. on stars).


Create a Turing-machine that decides $A=\{0^{3^n} | n\ge 0\}$ I need to find a Turing machine that decides $A=\{0^{3^n} | n\ge 0\}$.
I tried doing the same as Sipser does on page 172 in his back, where he creates a Turing machines that decides $A=\{0^{2^n} | n\ge 0\}$, by iterating over the input, and crossing (by writing $x$) on every other $0$.
I wanted to cross every third $0$, but I failed getting to any possible machine. Either I create a machine that does not accept $000$, or a machine that accepts $00000$ or $000000$.
I found a solution that for each iteration cross off $2/3$ of the $0$ over the tape, meaning after each iteration we remain with third of the $0$. But is it possible to get to a solution as I wanted? where on each iteration we cross off third, and remain with $2/3$?

Okay I can't draw and the only tools for visualizing Turing machines aren't the most practical so I'll give you a list of states and how they behave. Note that next refers to the next state and that if next and write aren't assigned the machine doesn't move to another state / doesn't write something.
A brief verbal description since the machine is somewhat big (9 states). There are states for count 0/ count 1 and count 2. Which count zeros...; Now when the machine reaches a third zero it is replaced with X and we are back to "count 0". Every of those three states has a "back" state responsible for moving back to start if we encounter an "empty". Notice that if we do not encounter a zero on our way back we are done and have to report accept or reject. If however we encounter a zero on our way back "count i back" switches to state "count i not finished" which if it encounters a "empty" (while moving left) will switch back to "count i" ($i \in \{0,1,2\}$.
"count 0" (initial state)
    read 0: {move: right, next: "count 1"}
    read X: {move: right}
    read empty: {move: left, next: "count 0 back"}
"count 1"
    read 0: {move:  right, next: "count 2"}
    read X: {move: right}
    read empty: {move: left, next: "count 1 back"}
"count 2":
    read 0: {move: right, write: X, next: "count 0"}
    read X: {move: right}
    read empty: {move: left, next: "count 2 back"}
"count 0 back"
    read X: {move: left}
    read 0: {move: left, next: "count 0 not finished"}
    read empty: reject
"count 1 back"
    read X: {move: left}
    read 0: {move: left, next: "count 1 not finished"}
    read empty: accept
"count 2 back"
    read X: {move: left}
    read 0: {move: left, next: "count 2 not finished"}
    read empty: reject
"count 0 not finished"
    read X/0: {move: left}
    read empty: {move: right, next: "count 0"}
"count 1 not finished"
    read X/0: {move: left}
    read empty: {move: right, next: "count 1"}
"count 2 not finished"
    read X/0: {move: left}
    read empty: {move: right, next: "count 2"}

Hope you get the idea!


Subgraph of an interprocedural control flow graph Say I have the interprocedural control flow graph (ICFG) of a program.

Now I am only interested in the control flow between two functions f1 and f2.

What is the most straight-forward way to remove the non-relevant part
of the ICFG?
Is there a standard performance-optimized algorithm for this task?
Does the result, that is, the interprocedural control flow "subgraph", have a special name?

I guess it would not be appropriate to call this a "slice" because its creation is based on the control flow graph reachability but not on data dependency relations. But I am not 100% sure.

EDIT:

I have to clarify: I am interested in the control flow starting at function f1, optionally passing via other functions, but eventually ending at function f2. In other words, the subgraph that contains all paths in the ICFG whose start node is f1 and whose end node is f2. This also includes paths with other nodes in between f1 and f2. Sorry in case my first explanation was not clear enough.

You are asking several questions. Here are answers to some of them. Your process is obtained by contracting all vertices not belonging to $f_1,f_2$, a process which is similar to the process of contracting edges in the definition of graph minors (though your graph is directed). Semantically, you can produce the graph by repeatedly performing the following contracting procedure for each vertex $v$ which is not $f_1,f_2$:

  Let $(x_i,v)$ be all the incoming edges, and $(v,y_j)$ all the outgoing edges. Delete $v$ and replaces the edges adjacent to $v$ by the edges $(x_i,y_j)$ for all $i,j$.

I don't know what is the most efficient implementation of this process, though I suspect you could find it in the literature once you determine what this operation is known as.


Ways to implement a decision making process involving complex rules I'm investigating different solutions for solving what looks like a decision making problem. Although the domain I'm working on is different, for the problem at hand, it's quite easy explaining with an example of online shopping cart.

Suppose you have a shopping cart like you have in every online retailer but this one checks some criteria and allow you to proceed only if the cart conforms to some criteria. Those criteria can depend on:

a property of the item you add to your cart (ex: minimum quantity allowed for the item you add)
combinations of the items you add (ex: if you have in your cart an item from sports category, you need to add an item from nutrition category)
properties of the cart itself (ex: option to give multiple orders from the same cart but only if certain type of items are in the cart)
and many other rules with exceptions...

So at a given time, your cart is in one of two states: valid or invalid. It starts with the state invalid: An empty cart. And at each action you take the state changes.

Some of the actions that change the state of the cart are:

adding an item to cart
changing a property of the item added, like color, size, quantity, etc
changing a property of the cart, like applying a discount code.

What I'm trying to achieve is to find a clean way to decide after every action, whether the cart is in a valid state or not.

The current code base for this is a mess. A method of hundreds lines of code, taking 15 arguments and filled with ifs and fors.

I wonder what are the possible solution patterns I can use to refactor this into a cleaner and maintainable implementation.

I've investigated finite state machines but couldn't figure out how to represent this into states and actions. Decision making trees I've seen are for pretty simple flows when you can answer yes or no easily. And they were implemented with nested ifs and elses which is quite similar to the current (messy) solution. My investigation lead me to AI and expert systems but I stopped there. As you can guess, I have no previous experience dealing with these kind of problems. Maybe what I'm trying to solve is a complex one and it's ok to have complex solutions to complex problems. But maybe this is a generic problem where you can give some direction to focus my research.

It sounds to me like the techniques here are not a matter of science (e.g., clever algorithms) so much as engineering (e.g., program structuring).

The approach I would suggest is to have a list of validators.  Each validator is a function or object that, when passed a shopping cart, checks whether the cart satisfies a particular criterion.  You have one validator per criterion in your business rules.  Then, to check whether a shopping cart is valid, you can simply iterate over all the registered validator.

This lets you structure the program logic in a cleaner way.  Each criterion is separated out into its own function or subclass.  Thus, while you still might have hundreds of lines of code in general, this way there is some structure, and if you're lucky, most or all validators can be written in a fairly concise way, as each one deals with only a single concern/criterion.


what would be the time complexity of DBSCAN algorithm? what would be the time complexity of DBSCAN algorithm if we use it for graph(sparse) clustering $O(n^2)$ or $O(n \log{n})$?

As the graph is sparse, if you have a data structure to query in $O(\log{n})$, you can reach to $O(n \log{n})$ for your case. More details in this link:

DBSCAN visits each point of the database, possibly multiple times (e.g., as candidates to different clusters). For practical considerations, however, the time complexity is mostly governed by the number of regionQuery invocations. DBSCAN executes exactly one such query for each point, and if an indexing structure is used that executes a neighborhood query in $O(\log n)$, an overall average runtime complexity of $O(n \log n)$ is obtained (if parameter $\varepsilon$ is chosen in a meaningful way, i.e. such that on average only $O(\log n)$ points are returned). Without the use of an accelerating index structure, or on degenerated data (e.g. all points within a distance less than $\varepsilon$), the worst case run time complexity remains $O(n^2)$. The distance matrix of size $(n^2-n)/2$ can be materialized to avoid distance recomputations, but this needs $O(n^2)$ memory, whereas a non-matrix based implementation of DBSCAN only needs $O(n)$ memory.


Edge removal to convert a non-planar DAG to a planar DAG while maintaining reachability? Is there an algorithm that removes edges to convert a non-planar DAG to a planar DAG while maintaining reachability? For example, the graph $G$ below is non-planar:

but, by removing certain edges to produce $G'$, it can be made planar but every vertex still has the same transitive closure (meaning vertex $t$ is reachable form vertex $s$ in $G'$ iff the same is true in $G$)

Is there an algorithm to do this for any general DAG (or return an error if it's not possible)?

My use case is that I'd like to use Thorup's algorithm for reachability, but it only works on planar graphs.

Yes, there's a nice algorithm for this.  Compute the transitive reduction, then check whether the result is planar.

Why does this work?  The transitive reduction is the graph with the smallest number of edges, that has the same reachability relationships as the original graph.  It is also unique.  Moreover, any other graph with the same reachability relationships must include all the edges in the transitive reduction (plus possibly some others).  Thus, if the transitive reduction isn't planar, no other graph with the same reachability relationship will be planar (as adding more edges to a non-planar graph can never make it planar).


Why is the lower bound $m \log n$ for this make-set, union and find-set sequence? Look at this solution:

Is the lower bound $m\log n$ because we are only looking at the lower bound for union by rank only? If we make $n$ MAKE-SET operations, then there would be $\log n$ UNION operations, and then $m - 2n + 1$ FIND-SET operations. The lower bound seems larger to me but what am I missing?

You are asking two questions.

  Is the lower bound only for this specific implementation?

Yes. If you also use path compression, the running time will be $o(m\log n)$.

  The lower bound seems to large to me.

Your mistake is that you assume that there are only $\log n$ UNION operations, whereas there are $2^{\lfloor \log_2 n \rfloor}-1 = \Theta(n)$, as the answer clearly .


Origins of the Segment tree data structure I'm interested in the first appearance in the CS literature of the data structure described here which is used to answer Range Queries. Although I have come across the same data structure many times with the name segment tree (mostly in algorithmic competition sites), it seems that the same name is also used for this data structure which is quite different from the first one and has application in computational geometry.

I'd like to know who introduced the data structure described in the TopCoder tutorial and if another name was initially used as there seems to be a confusion between the two data structures that go by the same name.

It seems to me that the Segment tree in the Wikipedia article is exactly the same as the segment tree you're used to hear about.

Segment trees as used in programming competitions can be generalized as working over any data type which forms a Semigroup (that is, any data type over which some binary associative operation can be defined on). As a reference, I've been implementing them in Haskell, the source code can be found here.

In this particular case, you'd have to notice that the power set of a set forms a commutative monoid with union, and monoids are, in particular, semigroups. Hence, the particular case described in Wikipedia is a segment tree where the data type is an Interval, and the associative operation is the union operation!.


What are the characteristics of a typeless programming language? Assume that we have an imaginary programming language that allows you to assign a Literal to a variable, but does not allow you to set the the data type of the variable, for example

Allocate4Bytes   an_int_variable        123456;
Allocate2Bytes   a_short_int_variable   123;
Allocate4Bytes   a_float_variable       2.1;

And this programming language also provides different operators to work with different data types, for example:

The + operator is used to add an int to a short int.
The #+ operator is used to add a float to an int.
the = operator is used to assign an int to an int.
the #= operator is used to assign a short int to a short int.
etc.

So it is the job of the programmer to keep track of the data type of each variable and use the appropriate operator on it.

Is this programming language considered to be a typeless programming language, or can we say that this programming language have data types (even though it does not have operator overloading and type safety, etc.)?

It depends on what happens if the programmer tries to do something like add two things with the wrong operator.  If it causes a compile-time error, the language is probably statically typed.  If it throws a runtime error complaining that the two have the wrong type, the language is probably dynamically typed.  If it doesn't throw an error and just tries to add those two things (possibly resulting in gibberish), it might be untyped.

To put it another way, it depends how those operations are implemented.  If they are implemented to keep track of the type of the variables and check that those types match what is expected, it is typed.  If it doesn't keep track of types, then it is untyped or weakly typed.

See https://en.wikipedia.org/wiki/Type_system and https://www.sitepoint.com/typing-versus-dynamic-typing/.


Efficiently pick a largest set of non-intersecting line segments Given a set of line segments, how do we identify a subset of maximal cardinality where all line segments are pairwise non-intersecting?

Brute force we would get $2^n$ sets to check where $n$ is the number of line segments, so that isn't viable. Anyone got a bright idea how the do this efficiently? I tried doing it this way: remove a line segment that intersects with the most other line segments, iterate until no line segments intersect anymore; but that didn't work.

Here is a "ready to help me" place, where you can test your solution; it visualizes the set of line segments.

To try it out, please implement your attempt in the following function on the linked site:

function showAnalysis() {
    debug("Just do it");
}

and then click on the top canvas. The fiddle generates randoms segments in the top canvas, and the bottom canvas is the place where an optimal subset will be displayed.

EDIT: Falk Hüffner gave a reduction in his comment to the question, the problem is in fact NP hard. What follows is pretty useless for that reason. I'll leave it up anyway so the answer doesn't look butchered.

This might be an NP-hard problem (as Teepeemm rightly pointed out, I did the reduction in the wrong direction, and I can't come up with one in the right direction), which would mean no one knows a subexponential algorithm. Brute force approach: check all sets whether some segments in them intersect, pick the largest one. This will cost you exponential time.

You can speed it up somewhat. Let n be the number of segments you have, then you can do a binary search like this: start out with checking whether there is a set with k1 := n/2 segments. If there is, check k2 := n*3/4, if there isn't, check k2 := n*1/4. Always remember all sets of the largest size for which you know that there exists something, because going up only supersets of those can work.

But to be completely honest, your best bet is to reduce this to SAT and use a SAT-solver. Anything you whip up yourself will pale in comparison to the finely tuned tools that SAT-solvers are nowadays. I don't know whether there is a SAT-solver you can easily use in Javascript though, you might have to use one on your server and let Javascript deal with the interpretation of results.
Another option would be to look into the algrithms mentioned on the sites that @MvG linked to in his comment to your question.


The padding argument in the proof of NTIME(n) ⊆ DTIME(n^1.2) implies Σ2-TIME(n^8) ⊆ NTIME(n^9.6) In "Computational Complexity, A modern approach", Arora & Barak proof the following claim (Claim 5.11.2):

  Suppose that $\mathsf{NTIME}(n) \subseteq \mathsf{DTIME}(n^{1.2})$. Then $\Sigma_2$-$\mathsf{TIME}(n^{8})  \subseteq \mathsf{NTIME}(n^{9.6})$,

which they prove in the following way:

If $L \in \Sigma_2$-$\mathsf{TIME}(n^8)$, then $\exists$ TM $M$ which runs in time $O(|x|^8)$ s.t.
$x \in L \leftrightarrow \exists u \in \{0,1\}^{c|x|^8} \forall v \in
\{0,1\}^{d|x|^8} M(x,u,v) = 1$
But if $\mathsf{NTIME}(n) \subseteq \mathsf{DTIME}(n^{1.2})$, then

  by a simple padding argument, we have a deterministic algorithm $D$ that on inputs $x, u$ with $|x| = n$ and $|u| = cn^8$ runs in time $O((n^8)^{1.2}) = O(n^{9.6})$ and returns $1$ iff there exists some $v \in \{0,1\}^{dn^8}$ such that $M(x,u,v) = 0$

I struggle to see what this "simple padding argument" might be? That is, how do we get respective deterministic algorithm $D$ if we have the TM $M$?

The language
$$L_1 = \{(x,u) ~|~ \exists v\in \{0,1\}^{d|x|^8}M(x,u,v) = 0\}$$ belongs to $NTIME(n)$ by design, since $|v| = O(|x| + |u|) = O(|x|^{8})$. By the assumption of the theorem, $L_1$ is decidable by some deterministic $D$ in $O((|x|+|u|)^{1.2}) = O(|x|^{9.6})$ steps. The recipee for $D$ isn't important, but the existence of such algorithm $D$ leads to the last step of the proof.


What does 'RTU' mean? While I was reading about Base & Bounds memory protection mechanism, I noticed the use of the abbreviation RTU as indicated in the slide below:

However I didn't know what it means.
So after searching for 'RTU', I found only this article on Wikipedia; But I'm not sure whether it matches the term.
Does anyone have any idea?

RTU stands for Return To User. This is invoked when the OS first accesses a physical memory range, and upon doing so will return the memory range address (code).


Generalized Büchi Automata - Formal definition of a state appearing infinitely often? I am studying generalized Büchi automata and I don't really understand when a state is considered to appear infinitely often. The definition I have is:

A state $s$ appears infinitely often if there exists an infinite set of points $i \in N$ such that the $i$th state of the execution is $s$.

But there's also an example which I think contradicts this definition.

According to the example, the language accepted by this automaton is the language where the string $ab$ appears infinitely often.

Why isn't it just $a$ appearing infinitely often? State 2 would be reached even if we only had $a$ as input. Which is wrong, the example or the definition? Or did I misunderstand the definition?

The definition and example are both correct.

If the automaton reads $a$ in state $2$ or reads $b$ in state $1$, then it rejects, because it has no state to go to.  So, if the machine reads an infinite amount of its input, then it must read $a$ every time it is in $1$ and read $b$ every time it is in $2$.  If the machine reads $b$ only a finite number of times, it only enters $2$ a finite number of times, so it must reject. Therefore, any string that's accepted must contain an infinite number of $b$s.  Since $b$s can only be read in state $2$ and the only way of getting there is to read an $a$ from state $1$, any accepted string must contain an infinite number of $ab$s.


How does the system know how to read the correct block from a disk? I am watching this video (https://www.youtube.com/watch?v=aZjYr87r1b8) and up to the ~6 minute mark, he explains the disk structure and how when you want to read a block, the spinner spins to the correct sector and the arm to the correct track. How do the spinner know where the correct sector is? How does the arm know where the correct track is? And how do they know they are reading from the beginning of the block and not in the middle of it?

Finding the right track is relatively easy. There is a motor which can be moved a precise distance. Then the head can measure magnetism to the right and the left and use this to move to the precise centre of the track.

The sectors all have a header. The read head passes sectors at high  speed. The start of the header has a distinct pattern that cannot be found inside a sector. So the read head can wait until it finds the start of a sector. The header also contains a number identifying the sector so the read head knows when it reaches the correct sector and can start reading.

In practice, all sectors on the track will be read in case another sector is needed soon after.


Would a parser for this left-recursive grammar require infinite input? I am considering this left recursive language grammar production rule:
Expr = Expr, "a" ;

As a production rule, I believe that this can be used to produce an infinite sequence of aaa by describing the rule like this:

Given a non-terminal Expr, expand it to Expr followed directly by the literal a.
Example: if Expr is initially b, it may be expanded to ba. Expr is now ba, and may be expanded again producing baa and this process repeats infinitely to produce ba, baa, baaa, and so on.

I have tried to visualize this grammar as follows:

I believe the grammar cannot terminate in its production, as it requires infinite recursion (in theory.)
Given that this is a valid production rule, I would believe that it is possible this grammar could also then be used as the definition to write a parser. I would describe that parser as:

It accepts any sequence of non-terminals (the Expr) followed by an infinite sequence of a.

However, what is not clear to me is if a parser for this language would require an infinite sequence of a or if a finite sequence of a would be admissible: would baa actually be a valid input, or would a theoretical machine parser for this effectively produce an error saying:
baa
   ^ found termination, expected "a"

Appreciate any guidance you can provide me in thinking about this problem.

Your grammar captures the empty language. To see this, you need to use the definition of a language described by a context-free grammar.
A context-free grammar is a tuple $(T,N,S,P)$, where $T$ is the set of terminals (a non-empty finite set), $N$ is the set of nonterminals (a non-empty finite set disjoint from $T$), $S \in N$ is the starting symbol, and $P$ is a collection of productions $A \to \alpha$, where $A \in N$ and $\beta \in (N \cup T)^*$.
In your case, $T = \{a\}$, $N = \{\mathrm{Expr}\}$, $S = \mathrm{Expr}$ (you are not stating this explicitly, but this is the only choice), and $P$ consists of the single rule $\mathrm{Expr} \to \mathrm{Expr} \, a$.
We say that $\beta$ produces $\gamma$ in one step, in symbols $\beta \Rightarrow \gamma$, if there exists a production $A \to \alpha \in P$ and two strings $\lambda,\mu \in (N \cup T)^*$ such that $\beta = \lambda A \mu$ and $\gamma = \lambda \alpha \mu$.
We say that $\beta$ produces $\gamma$, in symbols $\beta \Rightarrow^* \gamma$, if either $\gamma = \beta$, or $\beta \Rightarrow \delta \Rightarrow^* \gamma$ for some $\delta \in (N \cup T)^*$. This is the reflexive-transitive closure of $\Rightarrow$.
Finally, the language produced by the grammar is $\{ w \in T^* : S \Rightarrow^* w \}$.
In your case, a simple induction shows that $\mathrm{Expr} \Rightarrow^* \alpha$ iff $\alpha = \mathrm{Expr} \, a^n$ for some $n \in \mathbb{N}$. Since $\mathrm{Expr} \, a^n \notin T^*$, we conclude that the language produced by your grammar is the empty language.


What exactly is computation? I know what computation is in some vague sense (it is the thing computers do), but I would like a more rigorous definition.

Dictionary.com's definitions of computation, computing, calculate, and compute are circular, so it doesn't help.

Wikipedia defines computation to be "any type of calculation that follows a well-defined model."
It defines calculation as "the deliberate process that transforms one or more inputs into one or more results, with variable change." But it seems this definition includes many actions as computations even though they aren't typically thought of as computation.

For example, wouldn't this entail that, say, a bomb exploding is a computation, with the input being the fuse being lighted and the output being the explosion?

So, what exactly is computation?

Perhaps the problem here is looking a for a highly specific definition of a very general concept. I don't see the problem of viewing virtually everything as a computation. Although we don't think about it, everything we do is expressible in terms of the Physics of the component parts, down to at least quarks buzzing about. We have the same situation with computation. There's inputs, outputs and a process (all of which could be trivial). Whether they're interesting or useful as computations or models of computation is a very different question.

The strongest working definition we have comes via the (strong) Church-Turing Thesis, which states that every possible physically realizable model of computation is no more powerful than a Turing Machine. If you believe that this is true, then although we may have lots of way to express things, ultimately we can reduce every computation to a Turing Machine, hence giving a definition of computation as "anything we can reduce to a Turing Machine".

In this model, the exploding bomb is a computation. It's not a widely applicable one (we hope ;) ), but we can model in some fashion with a Turing Machine (though there is an argument here about the nature of the output and the equivalence with the TM's output). It's also not a good model of computation in general, in that it seems unlikely that the exploding bomb model is Turing complete.


Particle Swarm Optimization Algorithm I am studying about Particle Swarm Optimization (PSO) and I was wondering what the user-defined constants in the update equations are for.

First update equations:
$v(t) = w*v(t) + c_1*rand*(x_{best} - x) + c_2*rand*(g_{best} - x)$

$w$ is known as the weight/inertial constant. Usually values here are in the interval $(0,1)$.
What are $c_1$ and $c_2$ for?

Thanks

they are known as the Learning factors: c1 and c2 usually equal to 2. However, other settings were also used in different papers. But usually c1 equals to c2 and ranges from [0, 4]

if you need more information about PSO i'd have a quick read of the tutorials at http://www.swarmintelligence.org/tutorials.php