Probability of probing $t$ locations in a Cuckoo hash is $O(\frac{1}{2^{t/2}})$ locations in the worst case I was told this question may be better received here.

  Prove that the probability that an insertion into a cuckoo hash table
  probes $t$ array locations is $O(\frac{1}{2^{t/2}})$. Keep in mind that there are two tables, each with size $s \ge 2n$, where $n$ is the number of elements in the set.

I'm trying to use induction, but I don't know if this is the best method to go about proving this.

The worst case to probe $1$ array location would be when all $n$ element are stored in the first table, and we get probability $\frac{n}{2n} = \frac{1}{2} = O(\frac{1}{\sqrt{2}})$ for insertion.

The worst case to probe $2$ array locations would be when all $n$ elements are stored in the first table, we hit the first table, and we succeed in the second table. This has the same probability as it does to probe $1$ array location.

However, I don't know how to continue the analysis. For example, what's the worst case probability to probe $4$ array locations? The question statement implies that the worst case is $O(\frac{1}4)$, but how do we achieve this result? If the first and second tables each have $\frac{1}4$ of their array locations occupied, then the worst case to probe $4$ elements would be hitting in the first table, hitting in the second table, hitting in the first table again, then finally inserting into the second table $\Rightarrow \frac{1}4\cdot\frac{1}4\cdot\frac{1}{4}\cdot\frac{3}4 = \frac{3}{256} \not = \frac{1}4$.

Does anyone have a clearer way of thinking about this problem?

Basically, you just write down everything that is necessary to have $t$ evictions and then use the universality of your hash functions to bound the probability.

Assume you want to insert $x$ and your hash functions are $f,g$. Then if you have $t$ probes if $f(x)$ is occupied that is
$$
\begin{align}
\mathbb{P}[t=1]& =\sum_{y \neq x} \mathbb{P}[f(x)=f(y)]\\
&\le n \cdot 1/s \le 1/2.
\end{align}$$
since your hash function are $(1,k)$-universal (I assume).

Now for $t=2$, the place of $f(x)$ have to be occupied by some element $y$ (that is $f(x)=f(y)$), and the alternative for $y$ is blocked by some other element $z$ (that is $g(y)=g(z)$). Summing up over all possible values for $y$ and $z$ gives
$$
\begin{align}
\mathbb{P}[t=2]& =\sum_{y,z \neq x} \mathbb{P}[f(x)=f(y) \text { and } g(y)=g(z) ]]\\
&\le n^2 \cdot 1/s^2 \le 1/4.
\end{align}$$

The summands of the sum are bounded by $1/s^2$ due to the universality of the hash functions, and you have less than $n^2$ summands.

I think from here you can continue by yourself.


SCC of a Directed Acyclic Graph My instructor asked me to prove that strongly connected component of a DAG is also a DAG. I don't get it. How can a graph be DAG and strongly connected at the same time?

Consider a graph on two vertices "u" and "v" and assume that it is strongly connected as well as a DAG. A path from u to v exists as well as a path from v to u which creates a cycle. No?

This is difficult to answer because in part we have to guess what your instructor actually meant, but that said, I can't see a way to reconcile the statement.

You could ask if the components that are strongly connected in the underlying undirected graph are DAGs, but this is trivial, any subgraph of a DAG is also a DAG - we're not adding any edges, so we can't introduce a cycle.

Alternatively, we could ask for strongly connected components of a DAG, but here your observation is correct, there are no non-trivial strongly connected components in a DAG. The trivial ones are just each vertex by itself, which is trivially a DAG too, so that kind of works, if your instructor is looking to test your understanding of the definitions.

The last thing I can think of is that if you take a directed graph (not necessarily acyclic), and shrink each strongly connected component to a single vertex, the resulting graph is a DAG (called the "condensation" of the original graph). The condensation of a DAG is the DAG itself (we're back to the trivial strongly connected components again).


Proving a language is not regular with pumping lemma I'm having a little bit of an issue with a pumping lemma problem. I've successfully completely all my other problems but this is the last one and I'm a little confused I must say. If anyone can help me out, it'd be much appreciated.

\begin{equation}
A = \{a^n b^m c^l    \mid      n\leq m  \vee  m\leq l\}
\end{equation}

To expand a little on Ran G.'s comment, given a pumping length of $p$, we can take the string $s=a^{p}b^{p} \in A$, then splitting into $s=xyz$, the $y$ section (the part that can be pumped) must be all $a$s, so pumping up leaves us with a string $s'=a^{p+k}b^{p} \notin A$.


Empty intersection of longest path in connected graph Do all longest paths share a common point? (Gallai 1966)

A few years later, Walther  produced a counterexample on 25 vertices (a). The simplest counterexample was found by both Walther and Zamfirescu independently and has 12 vertices (b).

I found this examples in numerous study, but i couldn't find a vertex that does not appear in all longest paths.

Could you explain how should i see these graphs? Where are paths which intersection are empty?

You need not find a vertex that does not appear in all longest paths (in fact you can't). This is neither sufficient nor necessary. It is sufficient to prove that for each vertex $v$, there exists a longest path that does not contain $v$.

Easy to see the length of the longest path is 10. For convenience, let's encode the vertices as follows.

     1
     2
    3 4
   5   6
  7 8 9 10
11        12

Then for vertices 1,2,7,11,10,12, for example, 1, there is a longest path 11-7-8-4-6-5-3-9-10-12 that does not contain 1.

For vertices 3,4,5,6,8,9, for example, 3, there is a longest path 1-2-4-6-5-7-8-9-10-12 that does not contain 3.


Solving Recurrences via Characteristic Polynomial with Imaginary Roots In algorithm analysis you often have to solve recurrences. In addition to Master Theorem, substitution and iteration methods, there is one using characteristic polynomials.

Say I have concluded that a characteristic polynomial $x^2 - 2x + 2$ has imaginary roots, namely $x_1 = 1+i$ and $x_2 =1-i$. Then I cannot use

$\qquad c_1\cdot x_1^n + c_2\cdot x_2^n$

to obtain the solution, right? How should I proceed in this case?

Yes, the solution is in fact $T(n) = \alpha(1+i)^n + \beta(1-i)^n$ for some constants $\alpha$ and $\beta$ determined by the base cases.  If the bases cases are real, then (by induction) all the complex terms in $T(n)$ will cancel, for all integer $n$.

For example, consider the recurrence $T(n) = 2T(n-1) - 2T(n-2)$, with base cases $T(0)=0$ and $T(1)=2$.  The characteristic polynomial of this recurrence is $x^2-2x+2$, so the solution is $T(n) = \alpha(1+i)^n + \beta(1-i)^n$ for some constants $\alpha$ and $\beta$.  Plugging in base cases gives us
$$
T(0) = \alpha(1+i)^0 + \beta(1-i)^0 = \alpha+\beta = 0\\
T(1) = \alpha(1+i)^1 + \beta(1-i)^1 = (\alpha+\beta) + (\alpha-\beta)i = 2
$$
which implies
$$
\alpha + \beta = 0 \\
\alpha - \beta = -2i
$$
which implies
$\alpha = -i$ and $\beta = i$.  So the solution is
$$
T(n) = i\cdot ((1-i)^n - (1+i)^n).
$$

This function oscillates between $\sqrt{2}^n$ and $-\sqrt{2}^n$ with a "period" of 4.  In particular, we have $T(4n) = 0$ for all $n$, because $(1-i)^4 = (1+i)^4 = -4$ (and because I chose the base case $T(0)$ carefully).


Time Complexity of Rabin-Karp matching algorithm I asked a question on Rabin-Karp Searching algorithm here, which I am reading from the book "Introduction to Algorithms" 3rd edition Cormen et al..
After reading few para of the section on Rabin-Karp, I got some more confusions:
In the third paragraph the authors say that the if we could find p  (decimal value of pattern P[1....m] )  in  time O(m) and all the ts values (i.e decimal value of length-m sub-string T[s+1....s+m], s=0,1,2,,,,n-m) in time O(n-m+1),  then we could determine all valid shifts s in time O(m) + O(n-m+1) by comparing p with each of the ts values.
How is this possible? O(m) is for finding p, O(n-m+1) is for finding all ts, so total pre-processing time so far is O(m) + O(n-m+1). This is the total pre-processing time; the comparison has yet to start, I have to spend some extra $ for doing comparison of a decimal p with each of the (n-m+1)-ts values.
1-Then why the authors say in the first para that the pre-processing time is O(m)? Why it is not O(m) + O(n-m+1) which include processing time of p and all ts values?
2- Now if we talk about worst case matching time, what should be that? So in the worst my decimal number p (already calculated ) will be compared with each of the another (m-n+1) decimal numbers, which are the values of ts (already calculated, no extra cash needed for doing this job now ). The worst case is when I am most unlucky and I have to compare every value of ts with p. Right?
Based on my understanding,(if I am right) the worst case matching time should be O(m-n+1) and not O((m-n+1)m) as claimed by the authors in the first para. For example let us say my Pattern is P[1...m]=226 and Text is T[1....n]=224225226. so  my p is decimal 226, and ts is decimal value of T[s+1, s+2, s+3], for s=0,1,2...6 as n=9, and m=3. The ts values will be as follows:

s=0 => T[224]=> ts=224
s=1 => T[242]=> ts=242
s=2 => T[422]=> ts=422
s=3 => T[225]=> ts=225
s=4 => T[252]=> ts=252
s=5 => T[522]=> ts=522
s=6 => T[226]=> ts=226

Now you will be comparing p=226 with all these values. So are you not making n-m+1=7 comparisons to achieve search for 226 in T, and not (n-m+1)m =7 x3=21? So the worst case time should be O(n-m+1) and not O((n-m+1)m).
In short I understand that:

Total pre-processing time = O(m) + O(n-m+1) (including for both p and
all the ts values)
Total matching time in worst case = O(n-m+1)

Where I am making mistake?

As pointed out by vzn above, the wiki article has all the details you are looking for.

Firstly, what is pre-processing and what is the online runtime, depends on what is remaining constant and what is varying. For example, if we are given some fixed text and are asked to match various small strings with that text, pre-processing would be hashing the text.

In this case, let us say we have only one string to be compared with one text, to avoid confusion about pre-processing. The operations that we need to perform are

Hash for string to be searched for ($p$) = $O(m)$
Hash for each $m$-sized substring in the text ($T$) (assuming rolling hash) = $O(n-m+1)$
Number of hash comparisons (one per each $m$ sized substring in $T$) = $O(n-m+1)$
If there are $r$ matches in the hashes, then we compare each of those substrings of $T$ with $p$ (each comparison being $O(m)$) = $O(rm)$

But in worst case, the number of matches in hash can be as large as $n-m+1$. So worst case complexity will be $O(m(n-m+1))$.


GCD binary representation time complexity 1.  Consider the following algorithm for deciding GCD:

“On input :

1. If z doesn’t divide x or y, reject.               O(n)

2. For i from z + 1 to min(x,y) do:                  O(2^n)

    2.1. If i divides both x and y, reject.         O(n)

3. Accept.”                                           O(1)

Analyze the algorithm’s time complexity (in big-O notation).

n is the length of the max(x,y)
So I was given an algorithm, the time complexity to the right is My addition and not part of this question. I want to make sure this is correct.
I was thinking diving binary numbers is O(n) using long devision and step 2 just adds 0 or 1 to each previous number thus making the time exponential.
Am I right ?
Also, is there an algorithm that solves this in polynomial time ?
Thanks

Assuming x <= y and no particularly clever division, it's O (x log x log x), if you don't divide y by I if x is already not divisible by I.

If z divides x and y then you just need to check if gcd (x/z, y/z) = 1. And only test 2 <= I <= sqrt (x) and x itself.


Are all languages in P? Are all languages in $\mathbf{P}$?

Note: The definitions of all the symbols and functions here follow the document [1].

The following is my attempt to answer the question. Assume that we design a special Turing machine $M_1$, no matter what the input is, $M_1$ will jump to the state $q_{\rm accept}$ (the accepting state). Because no matter what the input $w$ is, $M_1$ only needs one step to finish the calculation, $T_{M_1}(n) = 1\ \forall n \in \mathbb{N}$. Let $k=1$, then $T_{M_1}(n) \leq n^1 + 1 = n + 1$. Therefore, $M_1$ runs in polynomial time. Then, all languages $L$ are in $\mathbf{P}$.

Reference

[1] S. Cook, The P versus NP problem, [Online] http://www.claymath.org/sites/default/files/pvsnp.pdf.

You are misunderstanding how accepting a language works. A language $L$ is in P iff there is a deterministic Turing Machine that decides whether a word $w$ belongs to $L$ in polynomial time.
Deciding means that it return a positive answer iff $w \in L$ and a negative otherwise.

Your approach will return a positive answer in every case. Thus your TM will accept the language $\Sigma^*$ where $\Sigma$ is the input alphabet of your TM.


Can you add up all the nodes of a special binary tree in polynomial time, in respect to the number of levels? Let's say you have a binary tree defined by a group $S=\{a:[5,6],b:[7,67],c:[45,12],...\}$ (this group is just an example). The binary tree is constructed so that there are two starting parent nodes, $a[0]$ and $a[1]$. Each of those nodes have two child nodes $b[0]$ and $b[1]$. Each of those nodes ($b[0]$ and $b[1]$ from both $a[0]$ and $a[1]$) have two child nodes, $c[0]$ and $c[1]$, and so on and so on. To evaluate such a tree, you start at the bottom of the tree, add up the two leaf nodes in each of the last parent nodes, and multiply that by its parent node. This is now the new value of the parent nodes. This process is repeated upwards until you do $a[0](b[0]+b[1])+a[1](b[0]+b[1])$ (remember that $b[0]$ and $b[1]$ are no longer $7$ and $67$, respectively at this point). Can you do this evaluation in polynomial time, in respect to the number of levels of the tree?
Follow up: Can it still be done in polynomial time if some of the leaf nodes are missing?
EDIT: Here is a picture with what I mean:

No.  A complete binary tree has $\ell$ levels and about $2^\ell$ nodes.  Any algorithm must examine all nodes to get the correct answer, so the running time has to be exponential in the number of levels.
(A small note of caution: "polynomial time" typically means polynomial in the size of the input, so it could risk some confusion to talk about it as "polynomial time" when you mean a polynomial in the number of levels.)


Representing FP relations using witnesses Let a relation $R$ be A-polynomial if there is a polynomial $p$ and a polytime algorithm $A$ such that for each $x$:

If $(x,y) \in R$ then there is a witness $w$ of length at most $p(|x|)$ such that $A(x,w) = y$.
For each $w$ such that $A(x,w)$ halts, we have $(x,A(x,w)) \in R$.

Prove or disprove: Each $R$ in FP is A-polynomial.

My attempt: I think the statement is incorrect, and so I'm looking for a counterexample. Let $R$ be a relation in FP where the algorithm $A$ helps us decide the undecidable halting problem. I thought maybe about $R= \left\{0,1\right\}^*\times \left\{0,1\right\}^*$, but perhaps there is a simpler counterexample?

An $A$-polynomial relation can't have two many pairs agreeing on the first coordinate. Namely for any $x$ there can be at most $2^{p(x)}$ $y$'s such that $(x,y)\in R$. This shows that the simple relation $R=\{0,1\}^*\times\{0,1\}^*$ is in FP but not A-polynomial.


Are all context-free and regular languages efficiently decidable? I came across this figure which shows that context-free and regular languages are (proper) subsets of efficient problems (supposedly $\mathrm{P}$). I perfectly understand that efficient problems are a subset of all decidable problems because we can solve them but it could take a very long time.

Why are all context-free and regular languages efficiently decidable? Does it mean solving them will not take a long time (I mean we know it without more context)?

Regular language membership can be decided in $\cal{O}(n)$ time by simulating the language's (minimal) DFA (which has been precomputed).

Context free language membership can be decided in $\cal{O}(n^3)$ by the CYK Algorithm.

There are decidable languages that are not in $\sf{P}$, such as those in $\sf{EXPTIME}\setminus \sf{P}$.


MinHeap represented by an array - two simple statements I'm trying to prove/disprove two statements. I just want to make sure with you I'm on the right line.

These are the following statements:

Preface : Let A[n] be an array of min-heap (a min-heap represented by an array], whereas all the elements in the heap are different from each other.
Let i and j be two indexes in the range : $0 \le i, j \le n-1$.

Prove or disprove :

If $i < j $ then $A[i] < A[j]$
If $A[i] < A[j] $ then $i < j$

I believe I managed to disprove both of them using the following heap:

$\qquad [2, 6, 7, 11, 14, 13, 12, 12, 13,15, 16, 71, 72, 13, 81]$

For:

Simply plug in the following indexes: $i = 4$ and $j = 13$.

So $i < j$ but $A[i] > A[j]$.
Simply plug in the following indexes: $i = 13$ and $j = 4$.

So $A[i] < A[j]$ but $i > j$.

Am I missing something here? Or It is really that easy?

You're not missing anything, this problem really is that easy. Your solution works, but I feel like I should point out that you can disprove both statements with a much smaller heap. In particular

\begin{array}{}
[2, 7, 6]
\end{array}

with $i = 1$ and $j = 2$ for the first statement and swapping them for the second.

Furthermore, I'm pretty sure those two statements only hold if the array is sorted (assuming distinct elements).


Oblivious Machines and Input Dependency So I know the Oblivious Turing Machines head position depends on the size of the input word and a number of steps. Can it be modified in such a way that it's not dependent on the size of the input word?

According to the WP article on Turing machine equivalents, oblivious machine head position is independent of input and is a function of time instead. To wit:

  An oblivious Turing machine is a Turing machine where movement of the various heads are [sic] fixed functions of time, independent of the input. In other words, there is a predetermined sequence in which the various tapes are scanned, advanced, and written to.

REFERENCES

https://dl.acm.org/citation.cfm?doid=322123.322138

SEE ALSO

Head Position Function of Oblivious Turing Machines
https://stackoverflow.com/questions/14847080/how-does-an-oblivious-turing-machine-work


What is the relation between the quantity of information of $A_i$ and $A$, where $A=\bigcup_iA_i$? Let $A$ be an event divided into 4 events $A_i$ with the same probability. Why does the quantity of information of $A_i$ satisfy
$$ I(A_i) = I(A) + \log (4)?$$

I believe that the correct formula is
$$
I(A) = \log \frac{1}{\Pr[A]}.
$$

In this case, we have
$$
I(A_i) = \log \frac{4}{\Pr[A]} = \log \frac{1}{\Pr[A]} + \log 4 = I(A) + \log 4.
$$


how to deduce a function subtype rule from a given function type definition This question relates to liskov substitution principle seems to have two conventional meanings but is really a different question, so I'm posing it as a new question.

I'm doing a bit of research into an old language, Common Lisp, which defines function-type as follows:
An object f is of type (function (A) Y)  if every call (f x) is semantically equivalent to (the Y (f (the A x))).

"the" is a special operator which specifies that the value returned by the form is of the specified type.

My question is whether this definition of function-type is enough to derive subtype rules, and type intersection/union/complement rules?

For example if f is both (function (A) Y) and simultaneously of type (function (B) X), then can we say from the definition that f is of type (function ((and A B)) (and Y X)), or perhaps can we say that it is (function ((or A B)) (and X Y))?

The language (specified in the mid 1980s) specifies that the intersection rule, but not the complement nor the union rules.  The intersection of two function types is the former (function ((and A B)) (and Y X)), which might surprise some people.  I'm wondering

Whether this intersection rule follows from the definition?
Whether the rule is a contradiction?
Can we also derive the complement and union rules from the definition?
Can we derive a subtype rule?   I.e., if f is in (function (A) Y), then f is also in (function (B) X) if ...what....?

With regard to (4) we would like to say that if $Y \subset X$ and $B \subset A$, then $(A\to Y) \subset (B\to X)$, but that would violate the intersection rule.

The intersection rule should be derivable, but it isn't purely a subtyping rule. Basically we reason as follows (I've translated into a notation that's a bit more familiar to me):

I'm presuming that subtyping says $A \cap B \subseteq A \subseteq A \cup B$
Subtyping means that $f : (A \to Y) \cap (B \to X)$ leads to both $f : A \to Y$ and $f : B \to X$
If $f : A \to Y$, it is then the case that $x : A ⊢ f \; x : Y$. But subtyping $A \cap B \subseteq A$ means that $x : A \cap B ⊢ f \; x : Y$ follows.
The same argument means that $f : B \to X$ leads to $x : A \cap B ⊢ f \; x : X$
These two judgments together lead to $x : A \cap B ⊢ f \; x : X \cap Y$
This leads back to $f : A \cap B \to X \cap Y$

Another way to specify this is that $f : (A \to X) \cap (A \to Y)$ leads to $f : A \to X \cap Y$. Subtyping allows us to broaden the original $A$ and $B$ to the common $A \cap B$, and then apply this intersection rule. But the intersection rule isn't subtyping, it is the rule for deducing that something has an intersection type via two separate deductions.

Pure subtyping can allow you to go from $f : A \to Y$ to $f : A \cap B \to X \cup Y$. Note that this is refining the input and broadening the output, and we could do each individually.

For union types, there is an opposite sort of rule. $f : (A \to Y) \cap (B \to Y)$ leads to $f : A \cup B \to Y$. So, if you can map both $A$ values and $B$ values to $Y$ values, you can map their union to $Y$ values. However, note that this doesn't allow us to deduce your rule with a union. Instead, we can only get from $f : (A \to Y) \cap (B \to X)$ to $f : A \cup B \to X \cup Y$, because this time we can broaden the result type of both functions and apply the union rule.

But, there is no way (I think) to get to $f : A \cup B \to X \cap Y$, which makes sense if you think about it. Just because we know that $f$ takes $A$ values to $Y$ values and $B$ values to $X$ values doesn't imply that it takes all $B$ values to $Y$ values and $A$ values to $X$ values, which is what that specification says.

So, to sum up:

The rule is derivable (with some standard assumptions, I think).
The rule is not a contradiction.
We can derive a union rule, but not the one you wrote. And I'm unsure what 'complement' rule you're talking about.
Subtyping works as usual, but it is not the only basis for the intersection/union rules.

Edit: Here's a summary of the rules that I believe hold, as I think it might lead you less astray than the long stuff above:

$$(A \to Y) \cap (B \to X) \subseteq (A \cap B) \to (X \cap Y)$$
$$(A \to Y) \cap (B \to Y) \cong A \cup B \to Y$$
$$(A \to X) \cap (A \to Y) \cong A \to X \cap Y$$

In particular, note that the first relationship is subtyping, not equivalence. The intersection of the function types carries more information than the function between intersection types. If the lisp documentation you're looking at says those are the same, it's wrong. Consider, just because we know that a function takes $A \cap B$ to $X \cap Y$ doesn't tell us anything about what it takes $A - B$ to. However, if it's merely saying that knowing $f$ has the first two types, we can conclude it also has the third type, that is correct.


What are the examples of scalable and non-scalable data structures? Big data era, people say the big data systems must use the scalable data structures and store.

I didn't get the point here. I need some examples.

What are the good examples of (1) scalable and (2) non-scalable data structure respectively?

Can any one give me an idea on it?

If I understand correctly, scalable structures refer to structures that can grow with the input grows without concern for memory. Off the top of my head I'd imagine scalable structures such as a tree structure that can grow and search elements quickly, generally O(log(n)) even tho they're a bit more memory intensive.

Where a non scalable structure would be something like an array or any type of structure that has its memory statically allocated to it. While it takes longer to search, generally O(n) but has a predictable memory size. I hope this helps. Note that trees (or other structures that often are dynamically allocated) can be written as array based such as an array based heap that has both static memory allocation but O(log(n)) search capabilities.

It would make sense for big data to use scalable structures since the amount of data is by definition- big and they likely need to query it in an efficient way.  I hope I understood your question and this helps.


how to draw a complement of a Turing Machine? I am now pretty confident on how I would turn something into a Turing Machine. Now my question is how do you convert TM into a complement of a Turing Machine. From what I can remember in Finite Automata, complementing it you would just turn a start state into a ending state, also if you have an ending state you would make it into a start state..How would you do complement of a Turing Machine ?

For example here I have a simple TM of a Palindrome and I want a Palindrome'

You cannot do it in general.

It would make the complement of your language semi-decidable, like the language itself. Hence they would be both decidable by running both machines in parallel.

Of course, this concerns only the case of semi -decidable languages for which the TM does not always halt for words not in the language.

If you have a decidable language for which the TM always halt with a yes or a no, you just exchange the yes and the no.

However there are some precautions to be taken:

compatibility of accepting and non-accepting configurations

Depending on your chosen definition of Turing Machines, accepting and
halting non-accepting configurations may not be compatible, hence may
not be
interchangeable. If it is allowed for an accepting state to have
transitions that could be used, then making it a normal state may
just make the computation go on, rather than halt without
accepting. Hence some rather simple precautions must be taken
regarding how acceptance and rejection are identified and how to
exchange them.
non-deterministic machines

Non deterministic machines are anti-managers. When a manager says
"no" it means no, and when he says "yes" it means "maybe".

Non deterministic machines do the opposite: when they say "yes" it
means "yes", and when they seem to say "no" (halting in a non-accepting configuration) it means "maybe". The reason it means maybe is that it might have answered yes with a different non-deterministic choice of some transitions. Actually, non-deterministic automata should be more accurately supposed never to give a negative answer. It is convenient with deterministic automata, but means nothing with non-deterministic ones.
It is also "maybe" when they do not terminate, for two reasons: (1) another transition choice might have produced acceptance, and (2) you cannot assert non acceptance as the computation may go on.

Hence it is not easy to complement a language recognized by a
non-deterministic or non halting device. You cannot simply exchange
"yes" and "no", since you only have "yes" and "maybe". You would only
get a managerial machine answering only "no" or "maybe", not
recognized by the Automata Theory Union. Automata must accept by terminating and answering "yes" unambiguously iff the word to be recognized is in the
language. Being able to answer no in some cases is just a bonus of deterministic machines, when kind enough to halt.

So, you must first convert your machine into a deterministic
one. Then you can exchange accepting and rejecting configurations
(with due respect to the previous point above), assuming furthermore
that the machine always halt.

To get the complement of a regular set, it is convenient to first
buid a DFA that recognizes it.

A Turing machine can always be turned into a deterministic one, but
it may not halt, thus leaving room for "maybe". Hence it is not
always possible to complement a language recognized by a Turing
Machine, as stated above. But it is possible for a (determinized) TM
that always halt with a yes/no answer.


How does the slow All-pairs-shortest-paths algorithm work? I am trying to fully understand the following algorithm from CLRS book:

I like to think that it works similarly to Bellman-Ford algorithm by relaxing all edges once for every vertex in the graph. Then we repeat the process for every source vertex $s \in V$. But then looking at the three nested loops in EXTEND-SHORTEST-PATHS and the additional loop in SLOW-ALL-PAIRS-SHORTEST-PATHS I am confused what is happening in every loop. The book says that in every iteration of the loop in SLOW-ALL-PAIRS-SHORTEST-PATHS it computes a matrix of size at most $m$ edges which confuses me even more.

Could someone please explain in simple terms how the algorithm works? Also in line 7 in EXTEND-SHORTEST-PATHS does it mean:
$$l^{'}_{ij} > l_{ik} + w_{kj} \Rightarrow l^{'}_{ij} = l_{ik} + w_{kj}$$
or
$$l^{'}_{ij} >= l_{ik} + w_{kj} \Rightarrow l^{'}_{ij} = l_{ik} + w_{kj}$$
While there might not be a difference in both of these cases on computing shortest path distances, it does, however, produce different results when computing predecessor-subgraph.

Thanks in advance.

Let me tell you what Bellman-Fords is actually doing because the sentence by relaxing all edges once for every vertex in the graph is not very accurate. In Bellman-Ford you care about single-source-shortest-path. Since every path in the graph have at most $n$ nodes it has at most $n-1$ edges.

Let's say the source node is $s$, then create a table $distance[\cdot]$ such that $distance[s] = 0$ and it is $\infty$ elsewhere. Let's solve the following dynamic programming problem, compute shortest path from $s$ to $u$ (for every $u$) that uses at at least $t$ edges.

The table we already filled is correct for the case of $t=0$. If you have this table already computed for some $t$ after relaxing all edges (in any order) it will be correct for $t+1$, since you extend all shortest path that uses $t$ edges with at least one more edge by relaxing the end of the path. Notice that you don't need to relax every edge $n$ times, but $n - 1$ times since largest path will have at most $n - 1$ edges.

The algorithm you showed is doing that for every pair of nodes in parallel. The first loop only runs $n - 2$ (instead of $n - 1$ times as I stated above) because you started with a matrix with all shortest path of length 1 already calculated (your base case is $t = 1$ instead of $t = 0$).

First loop of Extend-shortest-path is selecting the source node and following two loops are iterating through all edges (it assume the graph is complete) and relax the path that starts at $i$ ends in $j$ and use the edge $j-k$ next.

Old answer below (I miss-read the question and assumed it was asking  about Floyd-Warshall)

The key element that makes Floyd-Warshall (All-pairs-shortest-path) works is very different from Bellman-Fords key element.

Floyd-Warshall solves the following problem using dynamic programming. Calculate shortest path from every pair of vertex that use only first k vertex as intermediate hops. At the beginning it is the initial weight of existing edges and $\infty$ elsewhere (That is the base case).

Assume you have calculated such matrix for the first $k$ vertex and let's try to compute it for the first $k+1$ vertex. We should take into account paths that uses first $k$ vertex and goes through vertex $k+1$. Denote by $dp_k(u, v)$ the shortest path from $u$ to $v$ using first $k$ vertex, then it follows that the optimal path from $u$ to $v$ using $k+1$ vertex don't use this new vertex or indeed use it, so we get minimum from both values:

$$dp_{k+1}(u, v) = min(dp_k(u, v), dp(u, k) + dp(k, v))$$

In practice, the same table is reused on every step, so the algorithm only requires $O(n^2)$ spatial complexity. Temporal complexity is $O(n^3)$.


Efficient algorithm for determining if $\pm c_1 \pm c_2 \dots \pm c_n = 0$ Suppose that we're given $n$ integers $c_1, c_2, \dots, c_n$. We want
  to know if there is any assignment of $+$ and $-$ signs such that

  $$ \pm c_1 \pm c_2 \dots \pm c_n = 0. $$

Does anyone know of a polynomial-time way to do this? Since there are $n$ integers, there are $2^n$ assignments of signs to consider, which grows rather quickly.

I've tried to phrase this problem in such a way that I can make use of dynamic programming, but DP usually lends itself to optimization sorts of problems, and this problem does not fall into that category (at least as stated).

Hint: This is just the well-known NP-complete problem PARTITION.


A double recursive function (ping-pong) between function to itself complexity analysis def RecFunc(n):
   if n <= 3:
      return 1

   return RecFunc( RecFunc(n/3) + RecFunc(n/2) + RecFunc(n/2) )

How should I start if it is nested inside? I know how to solve it without the outer RecFunc (with a recursive tree I assume) - But here there is an outer RecFunc and I don't know what to do!

Thanks to Steven for noticing a mistake I made (Misread the question and made it so RecFunc(4) will not halt)

Notice that the outer RecFunc call is just a "decoy" thrown in there to make the exercise seem more complicate than it is.
Indeed, it is irrelevant as far as the asymptotic time complexity is concerned. This is because every call to RecFunc eventually returns $1$ (that's the only possible returned value, you can prove by induction that RecFunc eventually returns), and therefore the last (outer) call to RecFunc will just be RecFun(3), which terminates in constant time. We can charge this constant time to the caller function.
Since the caller is going to spend $\Theta(1)$ time anyway, this doesn't change anything.
Then you want to analyze:
def RecFunc(n):
   if n <= 3:
      return 1

   return RecFunc(n/3) + RecFunc(n/2) + RecFunc(n/2)

Whose running time is described by the recurrence equation:
$$
T(n)=2T(n/2) + T(n/3) + \Theta(1),
$$
which can be solved using the Akra–Bazzi method. Let $p$ such that:
$
2 \cdot \frac{1}{2^p} + \frac{1}{3^p} = 1.
$
Clearly $p>0$. Then:
$$
\int_{u=1}^n \frac{1}{u^{p+1}} \mathrm{d}u =
\int_{u=1}^n {u^{-p-1}} \mathrm{d}u =
-\frac{1}{p} \cdot  \left| u^{-p} \right|_{u=1}^n
= \frac{1}{p} \cdot \left( 1 - \frac{1}{n^p} \right)
= \Theta(1),
$$
and you have:
$T(n) = \Theta(n^p)$. An approximation of $p$ is $1.3646$.
The space complexity is clearly $\Theta(\log n)$ since this is the maximum recursion depth.


What is a range of an attribute in data mining? In my data mining course, we are working with a data set. I have to identity the ranges of each attribute. I am given the set of data for all 150 points and i am given the visualization (charts) of all attributes. However I do not know how to use that set of data or the charts to find the ranges of each attribute. I do not know what is meant by range either.

I'm working on the data set for Iris plants and I have three classes of the flower.

The range of the attribute is the interval where the values of the attribute varies. For Real numbers, is the closed interval [min,max].

For example, for an attribute $A$ with values $\{0.1, 0.5 , 1 , 10 , 100\}$ the range is the interval $[0.1,100]$

The concept is also valid for Integers, however there are no widely know notation to describe that. Ways of describing it would be:

$i = 1,...,10$

or

$(i \in \mathbb{Z}) \wedge (i \in [0,10])$


Is there an algorithm to share parts of strings? Let's say that we have the strings Hello, World, Hello and World. The algorithm I am thinking of would create an immutable buffer that contains Hello, World and the previous three would then become references or slices of that one like buf[0,11], buf[0,4], buf[7,11].

A way to implement this algorithm would be to compare all new strings to the existing buffer and reuse it if possible or append the new string if that's not the case. This would be very slow, but it should work. However, it does not efficiently handle a case like Hey, Hello because it would either append it to the buffer, adding Hello again, or add Hey, to the beginning and update all the indices.

If saving space is the optimal solution, then the final buffer would be Hey, Hello, World.

Is there any algorithm that does something similar?

I have read about ropes, and read this article, but I do not see how these would help.

EDIT: this is indeed a shortest superstring problem, but the implementations I have found (1,2) assume that no string in the array could be a substring of another one, which is not the case here.

It is a shortest superstring problem and not allowing internal substrings is just an implementation detail.


Does it make sense to have both the concept of 'null' and 'Maybe'? While creating a client for a web API in C#, I ran into a problem regarding null as a value where it would represent two different things:

nothing, e.g. a foo may or may not have a bar
unknown: by default the API response only includes a subset of properties, you have to indicate which additional properties you want. So unknown means that the property was not requested from the API.

After some searching I found out about the Maybe (or Option) type, how it's used in functional languages and how it "solves" null dereferencing problems by forcing the user to think about the possible absence of a value. However, all of the resources I encountered talked about replacing null with Maybe. I did find some mentions of three-valued logic, but I don't fully understand it and most of the times its mentioning was in the context of "it's a bad thing".

I'm now wondering if it makes sense to have both the concept of null and Maybe, to represent unknown and nothing respectively. Is this the three-valued logic I read about, or does it have another name? Or is the intended way to nest a Maybe in a Maybe?

The null value as a default present everywhere is just a really broken idea, so forget about that.

You should always have exactly the concept that best describes your actual data. If you need a type which indicates "unkown", "nothing", and "value", you should have precisely that. But if it does not fit your actual needs then you should not do it. It is a good idea to see what other people use and what they have proposed, but you do not have to follow them blindly.

People who design standard libraries try to guess common usage patterns, and they usually do it well, but if there's a specific thing you need, you should define it yourself. For instance, in Haskell, you could define:

data UnknownNothing a =
     Unknown
   | Nothing
   | Value a

It may even be the case that you should be using something more descriptive that is easier to remember:

data UserInput a =
     Unknown
   | NotGiven
   | Answer a

You could define 10 such types to be used for different scenarios. The drawback is that you won't have available pre-existing library functions (such as those of Maybe), but this usually turns out to be a detail. It's not that hard to add your own functionality.


Represent unsigned 12-bit octal numbers. Results in octal I have an HW question where I found an answer that matches mine, but their breakdown confuses me.
Ques: What is 4365 - 3412 when these values represent unsigned 12-bit octal numbers? The result should be written in octal.
I used binary and then looked up the Octal to obtain 753
Found solution: 4365-3412 = 0753
This is because 5-2 = 3 (makes sense), 6-1 = 5 (yep), 8+3-4=7 #we need a carry here, since 3<4 and 4-4=0
I can see where they got 8 (I think) 3+5=8, but why did they do that and how are we getting a carry for the ending of 4-4=0. Appreciate any help/reference.


$NP\subseteq TIME[O(n^{\log n})]$ Is it more plausible that $NP\subseteq TIME[O(n^{\log n})]$ than $NP\subseteq P$? I don't see this mentioned much and is there a reason why? If this question doesn't make sense, explain why.

It is definitely more plausible, for the simple reason that $NP \subseteq TIME[O(n^{\log n})]$ is implied by $NP \subseteq P$. However, it is conjectured that $NP$ requires exponential time (this is known as the Exponential Time Hypothesis), and so both statements are conjectured to be false.


Bit representation of the hashing multiplication method In the picture below from CLRS, I fail to understand why exactly $h(k)$ = the $p$ highest-order bits of the lower w-bit half of the product.

For context, this is supposed to compute
$h(k) = \lfloor m (k A \;  \text{mod} 1) \rfloor $

For further context, CLRS mentions the following, but I still don't quite get why those $p$ highest-order bits are the ones we are looking for.

$(kA \bmod 1)$ is in the range $[0,1)$. So multiplying that by $2^p$ gives a number in the range $[0,2^p)$. That is:

$$\left\lfloor 2^p (kA \bmod 1) \right\rfloor = \left\lfloor 2^p (kA \bmod 1) \right \rfloor  \bmod 2^p$$

Once you've worked that out, it's not too hard to see:

$$\left\lfloor 2^p (kA \bmod 1) \right \rfloor  \bmod 2^p = \left\lfloor kA 2^p  \right\rfloor \bmod 2^p = \left\lfloor \frac{ks}{2^{w-p}}  \right\rfloor \bmod 2^p$$

So you can implement this by taking $ks$, shifting it $w-p$ bits to the right, then taking the lowest order $p$ bits. Which is exactly the same as taking the highest order $p$ bits of the low word.


Constructing an FSA, where Ratio of number of states of FSA to its Minimal DFA Equivalent < 0.5 I need to choose a language, design a finite automaton M such that L = L(M). Construct a minimum-state DFA M′ equivalent to M in such a way that the ratio of the number of states in M to the number of states in M′ is less than 0.5.

I have zero idea as to how I should approach this. I've tried considering a few DFA's, as its the best place to start, considering that NFAs obviously have fewer states than their corresponding DFAs, but I'm not able to think of an approach to derive or contemplate a DFA with it's minimal counterpart having states < 0.5 times number the original DFA.

What the question is really asking you is:

  How much saving can be achieved by "compressing" a DFA to its equivalent minimal DFA?

The answer is: the amount of saving which can achieved is unbounded. There are (at least) two ways to measure the saving:

Number of states which are eliminated.
Number of states in the new automaton as a fraction of the original number of states.

The number of states which are eliminated is unbounded, and the number of new states as a fraction of the number of original states can be arbitrarily close to zero.

An example is not hard to come by: pick you favorite minimal DFA, and add as many dummy states as you want. These dummy states will not be reachable from the initial state of the original DFA, so thy won't affect the language accepted by the DFA; but they will increase the number of states by an amount of your choice.

What if we disallow this example by asking all states in the DFA to be reachable? What if ask, moreover, that there be an accepting state reachable from any state? (This makes sense as stated if we're allowing the DFA to get stuck, in other words, for the transition function to be a partial function; but a similar condition can be defined for DFAs with total transition functions.) The statements above still hold true, and an example is not difficult to come up to. I challenge the readers to figure out such an example.


Do Self Types make the Calculus of Inductive Constructions obsolete? Self Types are an extension of the Calculus of Constructions [1] that allow the language to express algebraic datatypes encoded through the Scott Encoding. The Scott Encoding provides one the ability to pattern-match in O(1), which is one of the main motivators for the inclusion of inductive definitions on CC. Yet, Self Types are make for a much simpler and elegant base theory, and are seemingly no less powerful.

Do Self Types, under a theoretical point of view, make CIC obsolete, or is there still some aspect on which CIC is favorable in relation to Self Tyes?

[1] http://staff.computing.dundee.ac.uk/pengfu/document/talks/mvd-2012.pdf

I'm not an expert in this work, but it seems to me that the major current issue is a lack of SN proof, even with restrictions. These proofs are notoriously tricky though, even when the calculus is correct, so I'd give it a little time. The work is certainly very promising.

One thing to note is that these restrictions are actually quite non-trivial to express, which is a large part of the complexity of the formulation of the inductive families in the CIC. The real selling point of an approach like this would be to concisely formulate these conditions.

It's been a somewhat longstanding open problem to have a dependently typed language which is

Consistent/Normalizing
Can express all the type families from Coq (or even Agda)
Allows for a simple expression of recursion over these families
Simple or has a small number of core constructions ($\Pi,\Sigma,\mu$).

One such attempt that I know of is the Altenkirch & al $\Pi\Sigma$ language, which similarly lacks a full meta-theoretical study (and also isn't consistent without further restrictions).


Unrestricted grammar which generates $\{ a^1\#a^2\#a^3\#\dots \#a^k \mid k >0 \}$ I am looking for an unrestricted grammar which generates the following language:

$\{ a^1\#a^2\#a^3\# \dots \#a^k \mid k >0 \}$

That is, words like $a\#aa\#aaa\#aaaa\# \dots \# \text{$k$ times '$a$'}$.

If the grammar can be really unrestricted (meaning the variables are allowed to totally disappear) the design of the grammar is not complicated.

Start with left and right boundaries. Assume the string already is of the wanted form (with boundaries): $L a^1\#a^2\#\dots\#a^k R$.

We can obtain the next string by adding one $a$ to each of the segments of $a$'s. We do this by having a symbol $W$ walking over the string from left to right while adding an $a$ after each $\#$. Basically this uses the production rule $W\#\to \#aW$. Of course $W$ starts at the left $L$ and disappears at the right $R$. Of course when the walker starts an extra $a\#$ at the left end must be generated.

A little tuning will make this work. At the end check that you did not forget to generate the string $a$.


Graph families with high $k$-community Just a quick question here, is there a known description of a graph family where for every graph $G=(V,E)$ it holds that for every $(u,v) \in E$ you have $|N(u) \cap N(v)| \geq k$? There was a definition for such graph as $k$-community. Even non-trivial examples (e.g., cliques) might be interesting.

Also, how to construct a graph which is a $k$-community, but does not have a $k+2$ clique? Is it possible at all?

Note that non-trivial cases also exclude not connected graphs and 1-vertex graphs.

Strongly regular graphs fit the bill, i.e., one property is that adjacent vertices have (exactly) $\lambda$ common neighbors. Paley graphs should give you an infinite family and an explicit construction.


Collision resistant hash function A function is $(\varepsilon, t)$-collision resistant if there is no boolean circuit (using "not", "and", "or") of size at most $t$ which outputs a collision with probability at least $\varepsilon$.

Let $h_0:\{0,1\}^{2m}\rightarrow\{0,1\}^m$ be a $(\varepsilon, t)$-collision resistant hash function and $i\in\mathbb{N}_{\geq 1}$.
Define a hash function $h_i: \{0,1\}^{2^{i+1}\cdot m}\rightarrow \{0,1\}^m$ recursively using $h_{i-1}$ in the following way:
Interpret the bit string $x\in \{0,1\}^{2^{i+1}\cdot m}$ as $x=x_1 x_2$, where both $x_1,x_2\in \{0,1\}^{2^i\cdot m}$.

Then the hash value $h_i(x)$ is defined as

$$h_i(x)=h_0(h_{i-1}(x_1)h_{i-1}(x_2)).$$

For which $(\varepsilon_i, t_i)$ is $h_i$ $(\varepsilon_i, t_i)$-collision resistant?
And can we successfully use the birthday attack on this hash function to find collisions?

The birthday attack applies to any hash-function, regardless of its structure, and also to $h_i$.

For your first question, here is a possible hint. Note that

if we can find a collision in $h_i$ then we can find a collision in $h_0$ (by considering the top-most $h_0$, for instance).
if we can find a collision in $h_0$ then, we can find a collision for $h_i$ (by replacing one of the inner-most $h_0$ with it's collision).


What is the relation between First Order Logic and First Order Theory? I thought that any FOT is a subset of FOL, but that does not seem to be the case, because FOL is complete (every formula is either valid or invalid), while some FOT (like linear integer arithmetic) is not complete.

So, is FOL more expressive than any of FOT? Or incomparable?

Also, the statement "there are statements that are valid in LIA but cannot be proved using axioms of LIA" is weird. How can the statement be valid if we cannot prove its validity? I always thought that if you cannot prove the validity of the statement, then you cannot claim it is valid.

First-order logic is a mathematical subject which defines many different concepts, such as first-order formula, first-order structure, first-order theory, and many more. One of these concepts is first-order theory: it is a set of first-order formulas. Often we consider the first-order theory generated by a finite number of axioms and axiom schemes. Such a theory is closed with respect to logical derivations, and we usually only consider theories satisfying this condition.

A first-order theory is complete if for every statement $\sigma$, it contains either $\sigma$ or its negation. Not every theory is complete. Indeed, Gödel's incompleteness theorem highlights the fact that many interesting first-order theories are necessarily incomplete.

A model of a first-order theory is a valid interpretation of the theory (we leave the exact definition for textbooks). For example, the first-order theory of groups consists of all statements that follow from the group axioms. Every group is a model of the first-order theory of groups.

For every given model, very given sentence is either true or false. Gödel's completeness theorem states that if a first-order sentence is true in all models of a first-order theory, then it is provable from a finite number of sentences in the theory. For example, every first-order statement in the language of groups which holds for all groups is provable from the group axioms.

LIA is (presumably) a first-order theory which is interesting enough to be incomplete due to Gödel's incompleteness theorem. However, in the standard model – the "true" integers – every sentence is either true or false. In particular, if $\sigma$ is a statement such that neither $\sigma$ nor $\lnot \sigma$ belong to LIA, then either $\sigma$ or $\lnot \sigma$ holds for the true integers, but this fact isn't provable in LIA.


How can we prove that $g = O(f) $ (Big-Oh notation) Problem description
I am trying to understand the first example of Big-Oh notation in Computational Complexity:A Modern Approach page 9.
If $f(n) = 100nlogn$ and $g(n) = n^2$ then we have the relations $f = O(g)$, $g = Ω(f)$, $f = o(g)$, $g = ω(f)$.

I understood why $f = O(g)$ and $f = o(g)$ . As for the rest I didn't. For instance in order for $g$ to be equal to $Ω(f)$ we must have $g = O(f)$.

Question
How can we prove that $g = O(f)$ and $g=o(f)$?

I think you have the wrong definition for $\Omega$. When we write $g=Ω(f)$, informally this means that $g$ is bounded below by ${\displaystyle f}$  asymptotically. So, it is basically just the reverse way of saying $f=O(g)$, which means that $|f|$ is bounded above by ${\displaystyle g}$ (up to constant factor) asymptotically.

What you are describing is closest to the definition of Big theta $\Theta$.


Time complexity of min() and max() on a list of constant size? If you use min() or max() on a constant sized list, even in a loop, is the time complexity O(1)?

That depends what exactly you mean by "constant sized". The time to find the minimum of a list with 917,340 elements is $O(1)$ with a very large constant factor. The time to find the minimum of various lists of different constant sizes is $O(n)$ and likely $\Theta(n)$ where $n$ is the size of each list. Finding the minimum of a list of 917,340 elements takes much longer than finding the minimum of a list of 3 elements.


Let M be an $\epsilon$-NFA and let $S\subseteq Q$. Prove $\epsilon (S) = \epsilon (\epsilon (S))$ Let M be an $\epsilon$-NFA and let $S\subseteq Q$. Prove $\epsilon (S)= \epsilon (\epsilon (S))$.

I would like to prove this by contradiction but I don't know if my idea is correct.

  Definition of $\epsilon -closure$:
  $\epsilon : 2^Q \rightarrow 2^Q $

  a) $S \subseteq \epsilon (S)$ Base case

  b) If $q \in \epsilon (S)$ then $\delta(q,\epsilon )\subseteq \epsilon (S)$ Recursive case

  c) and nothing else is in $\epsilon (S)$

Prove i) That $\epsilon (S) \subseteq \epsilon (\epsilon (S))$.

By contradiction, suppose $\exists x \in \epsilon (S)$ such that $x \notin \epsilon (\epsilon (S))$.

Using definitions of $\epsilon (S)$ , we know $S \in \epsilon (S)$. So $x \in S \in \epsilon (S)$, and $\delta(x,\epsilon ) \subseteq \epsilon (S)$.

Using definitions again, we know $S \in \epsilon (S)$, so $x \notin \epsilon (\epsilon (S))\notin \epsilon (S)$. Also $\delta (x, \epsilon) \nsubseteq \epsilon (\epsilon (S))$

We have a contradiction because $x \notin \epsilon (S)$ and we said $x \in \epsilon (S)$.

Therefore i) is true.

Your definition of $\epsilon$-closure is quite problematic. Here is a better formulation:

  $\epsilon(S)$ is the intersection of all sets $T \subseteq Q$ such that (i) $T \supseteq S$ and (ii) if $q \in T$ then $\delta(q,\epsilon) \subseteq T$.

Here is a series of claims which imply $\epsilon(S) = \epsilon(\epsilon(S))$.

Claim 1. $\epsilon(S) \supseteq S$.

Proof. $\epsilon(S)$ is the intersection of sets containing $S$, and so contains $S$.

Claim 2. If $q \in \epsilon(S)$ then $\delta(q,\epsilon) \subseteq \epsilon(S)$.

Proof. If $q \in \epsilon(S)$ then $q$ belongs to all sets $T$ in the definition. Property (ii) implies that all of these sets contain $\delta(q,\epsilon)$, and so $\epsilon(S)$ contains $\delta(q,\epsilon)$.

Claim 3. $\epsilon(\epsilon(S)) \supseteq \epsilon(S)$.

Proof. Follows directly from Claim 1.

Claim 4. $\epsilon(\epsilon(S)) \subseteq \epsilon(S)$.

Proof. $\epsilon(S)$ satisfies the $T$-conditions for $\epsilon(S)$: (i) is trivial, and (ii) follows from Claim 2.

Claim 5. $\epsilon(\epsilon(S)) = \epsilon(S)$.

Proof. Follows from Claim 3 and Claim 4.


Is there an equivalent of lambda calculus for object oriented languages? Lambda calculus serves as a foundation for all sorts of functional languages and its various extensions are compiler targets for languages like Haskell, ML, etc. So what is the equivalent for object oriented languages? Is there a minimal object calculus that serves as the foundation for object oriented languages?

So what is the equivalent for object oriented languages?

Lambda calculus.

I mean, there is Cardelli's object calculus (and a handful of derivatives), but in general, there's nothing fancy about object oriented languages that requires a new approach to computation.

It's well known (see TaPL for example) how to extend/encode Records and Mutation (and sub-typing/dispatch) onto/in lambda calculus. The underlying structures don't need to change, even though there are often layers above it that add semantic restriction and make things more usable (member access, implied this, object layouts, etc).


Minimum number of intersections to arrive at specific set Say I have a large number of sets (on the order of ~1000) with a smaller number of potential entries (~200), and a widely varying number of entries per set. An example:

$s_1 = \{1, 42, 133\}$

$s_2 = \{27, 283, 292, 172, 66, 62\}$

$s_3 = \{1, 42, 292, 66\}$

$...$

$s_{1000} = \{1, 133, 72\}$

Is there an algorithm more efficient than Monte-Carlo / brute force to find the minimum set of sets that I need to intersect to get a result containing exactly one specific item?

For example, given the above four sets, I would need to intersect $s_1, s_3,$ and $s_{1000}$ to arrive at a result containing only the element $1$ - the algorithm would need to find this solution (or a different solution requiring the same or a smaller number of sets), for arbitrary elements appearing in at least one set.

I have a feeling that this could be transformed into a set packing problem (which would make it an NP problem), but I am not an expert on this topic. Any input would be appreciated.

Your problem (or rather, its decision version: are there $k$ sets whose intersection is a singleton) is NP-complete, so I doubt there is a simple solution that always works, even for your numbers.

The problem is clearly in NP. We show that it is NP-hard by reduction from SAT. Let $\varphi$ be a CNF on variables $x_1,\ldots,x_n$ and clauses $C_1,\ldots,C_m$. We form an instance of your problem on the universe $x_1,\ldots,x_n,C_1,\ldots,C_m,\Delta$. For every $x_i$ and every truth value $t$, there is a set $S_i^t$ which contains (1) $\{x_1,\ldots,x_n\} \setminus \{x_i\}$, (2) all clauses not satisfied by $x_i=t$, and (3) $\Delta$.

All sets contain $\Delta$. In order to get rid of all $x_i$, we need to choose at least one set $S_i^t$ for each $i$. The intersection consists only of $\Delta$ if and only if the choice corresponds to a satisfying assignment. Hence there are $n$ sets whose intersection is a singleton iff $\varphi$ is satisfiable.


Use the pumping lemma to prove that the following language is not context free Can anyone help with the following problem ?

Let $B = \{ a^{n}b^{m}c^{m}d^{2n} | n,m ≥ 0 \}$, use the pumping lemma to prove B is not context-free

Thanks in advance.

Consider the following Context Free Grammar $G$:

$S \rightarrow aSdd\  |\ X\ |\ \epsilon$
$X \rightarrow bXc\ |\ \epsilon$

The language $L(G)$ generated by $G$ corresponds to the set of all the strings $\{\epsilon, add, aadddd, ..., bc, bbcc,..., abcdd, abbccdd,...\}$.
More generally, it corresponds to $ \{ a^{n}b^{m}c^{m}d^{2n} | n,m ≥ 0 \}$.


Linked lists in practice I have some questions about the ideas proposed in this video.

The speaker shows an array that holds values and pointers, and he also shows a separate "free" linked list, that is updated whenever an item is added/removed.

Why are these used? Doesn't using an array / limiting yourself to a set of free nodes defeat the purpose of a linked list?

Isn't one of the perk of using a linked list the ability to traverse fragmented data?

Why use these free nodes, when you can dynamically allocate storage?

The proposed structure, to me, doesn't seem dynamic at all, and is in fact a convoluted and inefficient array.

I have not watched the video, so I'll go by your description. There is an array of items which contain pointers to other items. These pointers form a linked list structure.

This sort of data structure tends to arise when a collection of items needs to be easy to traverse in multiple different orders. For example, a priority queue may need to be traversed both according to the elements' age and according to the elements' priority. This can be implemented with an array of elements, with new elements added at the end so that they're in age order, and a linked list or a search tree for priorities.

One common case for linked lists of array items is in a memory allocator. You ask, “Why use these free nodes, when you can dynamically allocate storage?” Well, what about the cases when you can't dynamically allocate storage, because you're implementing the dynamic storage allocator? The concept of “free list” is common to most memory allocators. A block of memory that isn't in use is an element of the free list. With fixed-size blocks, to free a block, you write a pointer to the current head of the free list at the beginning of the block, and you set the head of the free list to the address of this block. To allocate a block, you take the current head of the free list as the block to use, and set the head of the free list to the block that
was second in the list. In pseudocode:

allocate() :=
    block := free_list_head
    if free_list_head is null: raise out_of_memory
    free_list_head := free_list_head.next
    return block
free(block) :=
    block.next := free_list_head
    free_list_head := block

Allocators for variable-sized blocks typically use fancier data structures so as to be able to merge adjacent blocks and find blocks of an appropriate size.


Proving that $f(n) = o(g(n))$ implies $2^{f(n)} = o(2^{g(n)})$ I can't find a counterexample to
$$f(n) = o(g(n)) \text{ implies } 2^{f(n)} = o(2^{g(n)})\,,$$
but I do not know a formal way of proving it. Can anyone lead me in the right direction? I asked this exact question yesterday in Stack Overflow by accident (meant to post here) but no one could come up with a valid way of approaching this question.

This is "little-$o$" notation by the way. So a strict upper bound
It should be for monotonically increasing functions

Hint:

We want to prove $2^{f(n)} = o(2^{g(n)})$. This is equivalent to $\lim_{n\to\infty} \dfrac{2^{f(n)}}{2^{g(n)}} = 0$.
We can rewrite the expression inside the limit as $2^{f(n)-g(n)}$, and, exploiting the hypothesis $f(n) = o(g(n))$, we have $\lim_{n\to\infty} f(n)-g(n) = \cdots$


How to tell if a spanning tree is a shortest-spanning tree of a DAG? I know how to calculate the shortest paths from source s to all other reachable vertices in a DAG (with no negative weight on the edges)

By iterating the topological sort of the graph and relax each adjacent vertices. Which take O(V+E)

However - I'm required to determine if a certain spanning tree is the shortest-path tree of some directed (may be cyclic) graph in time O(E)

I've got a hint from my professor to use the algorithm to find shortest paths... but I fail to see how that helps me.
All I've gotten so far is just building the shortest-path tree and comparing it with the tree given and return true or false.

Draw the tree you're given and add all edges from the initial graph in a different color (e.g. red). Then the tree is a shortest-path tree of the graph (there might be several of them) iff. no red edge breaks "the shortest-path structure", i.e. iff. it is never faster to go through a red edge than only through tree edges.

Therefore, if you pre-compute the distance $d_T(u)$ from the source to every node $u$ in your input tree, you just have to check, for every red edge of length $l$ between two nodes $u$ and $v$, whether:

$$d_T(v) \le d_T(u)+l$$


I don't understand what this regular language is asking for? Find a grammar for L(G) = {w || w | is odd,∑ = (0, 1) } I don't understand what this regular language is asking for? Find a grammar for L(G) = {w || w | is odd,∑ = (0, 1) }. What does the " || " mean I know a single " | " means or.

Yup, I can see why that would be confusing.  The typesetting is probably making this harder to follow.  I'm guessing what's written is $\{w \mid |w| \text{ is odd}, \ldots\}$.   This is the set of all $w$ such that $|w|$ is odd etc.  Here $|w|$ typically represents the length of the word $w$.

It might have been clearer if the author had used a colon instead of a vertical line in our set builder notation: then it would have been written $\{w : |w| \text{ is odd}, \ldots\}$, and maybe it would be easier to see what is going on..


A BST can be broken by accessing one of its nodes, how can I always make sure this happens? I have an assignment that asks for this. So I am not looking for the answer itself but a hint on how to find a value that will always break the BST condition by myself.

If I have access to any node N of a BST that has at least 2 nodes in its root, and where every node will always be different.

If I were to replace N.key with x, what should the value of x be in order for the tree not to be a BST anymore?

I can use the following operations:
GetPre = key before N when seen from an inorder transverse.

GetSuc = key after N when seen from an inorder transverse.

MAX = gets the node value from the sub-tree that has N as root.

MIN = gets node value from the sub-tree that has N as root.

I broke it in several subcases, but I am sure this can be written as one single formula.

I came up with:

$x = N.key - GetPre(N)$ but it doesn't work as I expected.

I appreciate any insight.

Hint: In a BST, an inorder traversal produces the keys in sorted order. If we had N.key = $20$ and the inorder traversal was $2, 4, 10, 11, 17, 20, 28, 31, 40$, what $x$ values would break the sorted order when put in the place of $20$?


Is it legal to use non-terminal twice in Backus-Naur grammar It's a school assignment:
The problem is:
Write a BN grammar for +67.

The given solution I have been given is following:

<digit>  ::= 6 | 7
<number> ::= <digit> | <digit> <number>
<+67>    ::= + <number>

My question is, when given this simple task, could it be derived like this?

<digit>  ::= 6 | 7
<number> ::= <digit> <digit>
<+67>    ::= + <number>

More precisely, can I use same non-terminal twice in same rule?

Yes, you are allowed to use the same non-terminal more than once in a rule.

Note that the two grammars you give do not express the same set of strings.
The first grammar gives any sequence of 6 or 7 following the +, as  can be applied recursively. The second defines exactly four strings +66, +67. +76, +77.


Recursive and recursively enumerable language definition for a layman I've come across many definitions of recursive and recursively enumerable languages. But I couldn't quite understand what they are .

Can some one please tell me what they are in simple words?

A problem is recursive or decidable if a machine can compute the answer.

A problem is recursively enumerable or semidecidable if a machine can be convinced that the answer is positive.


Deterministic finite automata that accepts the only the string "aabb" Lets construct a DFA over{a,b} That accepts only the string "aabb" in it.
My problem with this video is that the tutor has
moved arrow from state D to B why didn't he set a self loop on D .Im really helpless .

Move forward to minute 11

Your purpose is to detect a substring $aabb$. When the FA is in state $D$ it already has read $aab$ (pay attention that in order to get to $D$ from the start state the FA must read $aab$ or $a\dots aab$). While in state $D$ there are two possible inputs: $a$ or $b$. If it reads $a$ it enters the state $B$ because it already has $a$ (it remains to read $abb$). On $b$ it enters the accept state. If on $a$ it stays on $D$ then it would accept a wrong string, for example, $aabab$ which does not contain $aabb$ as a substring. In other words, on $a$ you should send it back to the state $B$ as if FA switches from state $A$ into state $B$.


Minimax algorithm when all the options are the same tl;dr What does the Minimax algorithm do when all its options are the same?

Consider this Minimax tree:
(Green means the ends, orange minimize, blue maximize)

(Source: Myself)

Imagine this is the tree for a game (tic-tac-toe, maybe?). What should the computer do? Pick one at random? Pick the one which on average has the best score (the second one)?

Background

I'm making a program to play Quoridor, and I figure that the Minimax algorithm is the best choice (with some pruning of the really bad ones; otherwise, it would be way too big). The problem is, every choice you can make (the beginning ones in particular) have a chance to loose, and every loss has the same value (-1). So how can I pick the best moves, if all the options are the same?

Shaull's answer is absolutely correct, and by referring Zermelo's theorem it is pointing in the right direction.

However, beyond the observations done on the rationality of your opponent, the point here is that Minimax is pretty good for strategical games where a single mistake could lead to a disaster, e.g., chess ---where just overlooking a single move can lead to checkmate. On the other hand, if no such strategical flaws are likely (e.g., Omweso and I think Quoridor also to some extent) then Monte-Carlo sampling is a much better option.

For a thorough study on the topic, see:

Raghuram Ramanujan and Bart Selman. Trade-Offs in Sampling-Based Adversarial Planning. Proceedings of the Twenty-First International Conference on Automated Planning and Scheduling. Freiburg, Germany, 2011.

(which was actually awarded a honorable mention for best student paper). In this case, the purpose of such algorithm is to follow good lines of action instead of preventing a loss. Monte-Carlo sampling is also the best option to use in case your branching factor is too large (so that minimax and any of its variants such as alpha-beta become infeasible), e.g., Go.

Be aware however, that one of the options used much often in Monte-Carlo sampling, UCT, does not seem to be so good in the end. For a good discussion on the topic, see:

Carmel Domshlak, Zohar Feldman. To UCT, or not to UCT?. Proceedings of the Sixth Annual Symposium on Combinatorial Search. Leavenworth, Washington, USA, 2013.

Hope this helps,


Priority queue with unique elements and sublinear time merge? Some priority queues, like the height-based leftist tree (or here) support merging in $\mathcal O\left(\log n\right)$ time.

I am looking for a priority queue that merges in (expected|average|amortized|worst-case) sub-linear time, but also has the following properties:

Elements are unique
peek and pop should work in (expected|average|amortized|worst-case) sub-linear time

Is this impossible?

Keep your elements in linked lists of buckets. Buckets will have size $O(\lg^2 n)$ when stored in a list with $n$ total elements. Buckets are stored as balanced search trees with $O(\lg n)$ insert (and, since each bucket has size $O(\lg^2 n)$, this is actually $O(\lg \lg n)$), $O(1)$ extractMin, $O(n+m)$ merge, $O(\lg n)$ split, and no duplicates. The liked list should be sorted by the size of the buckets, though not their key values.

To maintain the bucket invariant, we need to occasionally combine or split buckets. To pay for this, we assign each priority queue a potential. This lets us use the physicist's amortization.

Each bucket will be assigned a potential of $0$ if it has size within $1$ of $\lg^2 n$ and a potential of $c \lg^2 n$ if it is size $\lg^2 n/d$ or $d \lg^2 n$ (for constants $c$ and $d$ to be determined later), varying bitonicly and linearly in the size of the bucket.

The tricky method is merge. Assume we are merging two lists of size $n$ and $an$, for $a>1$. We split into two cases depending on whether $a < \lg^2 n$.

If $a < \lg^2 n$, then we join the lists by merging them like in merge sort, so that the buckets stay sorted by size. Since the buckets have size $O(\lg^2 n)$, the linked lists have length $O(n/\lg^2 n)$ and $O(an/\lg^2 an)$, so merging them takes time $O(an/\lg^2 an)$ which is $o(an)$, and so is sublinear.

It also may increase the potential. Each bucket gets at most $O(\lg^2 (1+a)n - \lg^2 n) = O(\lg^2 (1+a) + \lg n \lg (1+a))$ closer to criticality. This is $O(\lg n \lg \lg n)$, and there are $O(an/\lg^2 an)$ buckets, so the increase in potential is at most $O(an \lg n \lg \lg n/\lg^2 an)$, which is $o(an)$ and thus sublinear.

Finally, we traverse the head and tail of the list, splitting and joining supercritical buckets until no supercritical buckets are left. This is "free", paid for by the potential we release. (To place them properly, we need to maintain a finger to the point in the list where buckets are exactly the right size. This is $O(1)$ extra work on each operation.)

If $a > \lg^2 n$, we destroy the smaller priority queue and insert its items one-by-one into the larger queue. As long as insert is $o(\lg^2 n)$ amortized, this is sublinear.

Insert adds an element to the smallest bucket. This increases its potential by at most $O(1)$ and increases the potential of the rest of the buckets by at most $O(\lg^2 (n+1) - \lg^2 n) = O(\lg n/n)$. Since there are $O(n/\lg^2 n)$ buckets, the total increase in potential is $O(1/\lg n)$. If the smallest bucket is large, some splitting may be required, but this is amortized free (paid for by the potential we get back). The total amortized cost of insert is thus the cost to insert it into a bucket, which is $O(\lg \lg n)$.

extractMin traverses the bucket list and identifies the buckets with minimum key. It removes the minimum key from each of these buckets, rearranging the bucket list as necessary to maintain order. The total structure size may change by $O(n/\lg^2 n)$ if we remove a key from each bucket. This induces a potential change of at most $O(\lg n)$ in each bucket, for a total potential change of $O(n/\lg n)$. The traversal and removal take time linear in the number of buckets, which is $o(n)$.

Note that these operations, including an extractMin that extracts every copy of the minimum, are sublinear in the number of elements, not the number of unique elements. The number of unique elements in a priority queue of size $n$ may be as low as $\Theta(\lg^2 n)$.


How is functional property guaranteed in type theory when function type is defined? I understand that functions are not defined in type theory the same way they are defined in set theory, hence functional property is not directly defined when defining function type in type theory. But I want to know which part of function type definition in type theory guarantees functional property even if it is done so indirectly and implicitly?

Type theory shows that every element of a function type has the "function property". Let $A$ be a type and $B(x)$ a dependent type with $x : A$. We can construct an element of
$$\Pi (x : A) (y , z : B(x)) \,.\, f x =_{B(x)} y \to f x =_{B(x)} z \to y =_{B(x)} z$$
quite easily, because we just use symmetry and transitivity of equality. For instance in Coq:

Definition functional_property (A : Type) (B : A -> Type) (f : forall x, B x)
  : forall (x : A) (y z : B x) (p : f x = y) (q : f x = z),  y = z
  :=
   fun _ _ _ p q => eq_trans (eq_sym p) q.

What this means is that, as others already pointed out, the "functional property" is there by construction. It may help to say the following: in type theory we do not think of mathematical objects as existing independently and beforehand. Instead, type theory is a theory of how objects are constructed. Thus, the elements of the function type are constructed in a certain way (known as "$\lambda$-calculus") that guarantees the desired properties by construction. There is no such thing in type theory as "a thing that wants to be a function but isn't because it doesnt have the right properties". That sort of thinking simply does not apply: if you have a thing, then it was constructed according to the rules of some type and therefore the thing has that type.

You are probably thinking set-theoretically, i.e., given a relation $R \subseteq A \times B$, we should be able to get a function out of it, provided that $R$ is single-valued (what you call "functional property") and total. There is a corresponding statement in type theory, but it is not the definition of functions. It is instead a theorem stating that the function type $A \to B$ is equivalent to the type of total functional relations.


How can I show context free grammars are strictly more expressive than regular expressions with an example? I need to show a CFG can express everything that can be expressed by a regular expression, and something that cannot..

I have no idea what example is traditionally used for this.

The canonical example is the language $L=\{a^nb^n\mid n\ge 0\}$. It's easy to produce a CFG for this and it's nearly as easy to show that it's not a regular language. For your first question, note that any regular language can be generated by a left-linear grammar and these are CFGs, so any regular language is also context-free.


Proving non-regularity of $u u^R v$? This particular language:

$$L = \{ u u^R v \,:\, u, v \in \{0, 1\}^+\}$$

is giving me a lot of trouble.
I highly suspect that its non-regular, considering that $\{ u u^R : u \in \{0, 1\}^+\}$ is non-regular, and I can't seem to reason out a DFA for it.

However, trying to achieve a contradiction with the pumping lemma is giving me a lot of trouble. because of the arbitrary $v$ in the construction.
In particular, if the string starts with $00$ or $11$ it is automatically in the language because we can pick $v$ as the remainder and the first two characters are trivially the reverse of each other.

Issues like this seem to thwart my every attempt at applying the pumping lemma. With $p$ as the pumping length, I tried something like $(01)^p (10)^p 1$ but you can simply pump up the starting character to obtain a string that starts with $00$ (and pumping down also works), so this string doesn't work for contradicting the pumping lemma.

I'm pretty stuck on ideas for strings that will contradict the pumping lemma, so I could appreciate a hint on the problem. (Perhaps it is regular? That's still in the back of my mind too)

When you are stuck in a place like this, it pays to check if the method can work at all. That is, try to prove the opposite. Since the Pumping lemma does not characterise REG, this is actually possible.

Claim: Your language $L$ fulfills the conditions of the Pumping lemma with $p=1$.

Let $w = uu^Rv$ for $u, v \in \Sigma^+$; say $|w|=n$ and $|u|=m$. With the (canonical) notation from the Pumping lemma, pick $x = \varepsilon$, $y=w_1$ and $z = w_2\cdots w_n$.

By definition, $|y| \geq 1$ and $|xy| \leq p$. Furthermore,

$xy^0z = (u_2\cdots u_m) \cdot (u_2\cdots u_m)^R \cdot u_1 v \in L$,
$xyz = w \in L$, and
$xy^iz = u_1 u_1^R (u_2 \cdots u_m) u^R v \in L$, for $i \geq 2$.

Q.e.d. -- $L$ has the Pumping property.

That is, the Pumping lemma can not be used here, you need other methods.


Intersections of some context-free languages Suppose We have Some language as follows:

$L_1=\{w^* | w=x \text{ and } x \in \Sigma^*\}$

$L_2=\{ww^R ww^R | w \in ( \Sigma  + \Sigma)^*\}$

$L_3=\{w | w=xy, x,y \in \Sigma^*, y \text{ is a substring of } x\}$

1) there is a PDA (push down automata) that accept $L_2 \cap L_3$

2) there is a PDA (push down automata) that accept $L_2 \cup L_3$

3) there is a PDA (push down automata) that accept $L_1 \cap L_3$

4) there is a PDA (push down automata) that accept $L_1 \cup L_2$

I read in some sites that:

(a) is false, and we can say 3 and 4 are wrong because we have no language that is not closed under union but closed under intersection.

I read a lot of material for finding the answer of this question mentioned by Prof. M. Farshchi on Entrance Exam in 2012, but I failed. I need some one to help me with a bit detail for each one. Thanks.

Notice that $L_3 = \Sigma^*$, since you can always choose $y=\epsilon$ (the empty string is a substring of any string) and then choose $x$ from $\Sigma^*$. $L_1$ is also $\Sigma^*$, since $L$ is always a subset of $L^*$ and we're basically saying $L_1 = (\Sigma^*)^*$. These observations imply the following: the answers to #2, #3 and #4 are "yes" (indeed, there's a DFA with one state accepting each of these, which are all $\Sigma^*$)... and the intersection in #1 is simply $L_2$, so the question is really "is $L_2$ context-free?"

Please also note that we have other questions on the site about proving and disproving that languages are context-free.

To clarify:

$L_2 \cap L_3 = L_2 \cap \Sigma^* = L_2$
$L_2 \cup L_3 = L_2 \cup \Sigma^* = \Sigma^*$
$L_1 \cap L_3 = \Sigma^* \cap \Sigma^* = \Sigma^*$
$L_1 \cup L_2 = \Sigma^* \cup L_2 = \Sigma^*$

As for $L_2$:

First note that I'm assuming $(\Sigma + \Sigma)^*$ is a funny way of writing $\Sigma^*$. Plus usually stands in for union when dealing with regular expressions, and I'm guessing that's the intention here as well, though it would be well to confirm this.

Assume $L_2$ were context free. By the pumping lemma for context-free languages, we could write any word $w \in L_2$ of length at least $p$ as $uvxyz$ where $|vxy| \leq p$, $|vy| > 0$ such that $uv^kxy^kz \in L$ for all $k \geq 0$. Consider the word $(0^p1^p)(1^p0^p)(0^p1^p)(1^p0^p)\in L_2$ (parentheses added for clarity). We consider cases for the assignment of $vxy$:

$vxy$ consists entirely of $0$s from the first (parenthesized) part of the string. Pumping will change the number of $0$s without changing the number of $1$s in the first part, leading to a string that can't possibly be in the language.
$vxy$ consists of a mix of $0$s and $1$s from the first (parenthesized) part of the string. Pumping will change the numbers of $0$s and $1$s in the first part without affecting the other parts, leading to a string that cannot be in the language.
$vxy$ consists of a $1$s from the first (parenthesized) part only. See argument in point 1 above.
$vxy$ consists of $1$s from the first part and $0$s from the second. See arguments above.

etc. There are 15 cases in total, but the arguments are all basically the same: you always get some parts out of sync (the $p$s won't match). This means that the language is not context-free.


Can you give me an example word that is in the language $L = \{w | w ∈ \{a,b\}^∗ ∧ |w|_a = |w|_b\} $ Again, the language is $L = \{w | w ∈ \{a,b\}^∗ ∧ |w|_a = |w|_b\} $
Now I'm unsure about what the '*' indicates. Whether it means that either a or b can be repeated, or only one of them or if you can repeat a pattern made of a and b.
An explanation would also be appreciated but I thought one or more examples of what would be a word in the language and what not would be quicker.

Check your definitions: $*$ is the Kleene star.

So, $\{a,b\}^*$ is the set of all finite strings over alphabet $\{a,b\}$.


Testing whether an arbitrary proof is circular? I was thinking about proofs and ran into an interesting observation. So proofs are equivalent to programs via the Curry-Howard Isomorphism, and circular proofs correspond to infinite recursion. But we know from the halting problem that in general testing whether an arbitrary program recurses forever is undecidable. By Curry-Howard, does that mean there is no "proof checker" that can determine if a proof uses circular reasoning?

I've always thought that proofs are supposed to be composed of easily-checkable steps (which correspond to applications of inference rules), and checking all the steps gives you confidence that the conclusion follows. But now I'm wondering: maybe it is actually impossible to write such a proof checker, because there is no way for it to get around the halting problem and detect circular reasoning?

The vast majority of proof systems don't allow for infinite, circular proofs, but they do so by making their langauges non-Turing complete.

In a normal functional language, the only way to make a program go on forever is with recursion, and in terms of theory, usually we look at recursion as the $Y$ combinator, a program of type $\forall a \ldotp (a \to a) \to a$: that is, it takes a function which makes calls to some other "self" argument, and turns it into a single recursive function.

Now, apply the Curry-Howard isomorphism to this: we now have a proof that, for any proposition $a$, if $a$ implies itself, then we can prove $a$. We can prove anything this way!

The key here is that the Y-combinator is built-in to a language, it's taken as an axiom. So if you want it not to cause you problems, just get rid of it as an axiom!

Most formal proof systems, because of this, require your recursion to be well founded. They only accept functions that they can prove will halt. And as a result, they reject some programs that do halt, but which they can't prove it for.

Coq does this in a fairly limited way: it just requires that any recursive functions have an argument where any recursive calls only use strictly smaller versions of that argument. Agda does something similar, but with a little more fancy checking to accept a few more programs.


The meaning of symbols What does the following symbols or expression mean?

$x$ and $y$ are elements of a set $S$. For example, if $S = \{1, 2, 3\}$, we can select $x = 1$ and $y = 2$.

EDIT:
As pointed out by David below, $*$ could be multiplication or convolution, it's hard to tell from the context.

$\in$ means 'in', that is, that $x$ and $y$ are in a set. We can write 'x and y are elements of the set $S$ ' in math as:

$x, y \in S$

Again, following my example, that would be $1$ and $2$ are in the set $\{1, 2, 3\}$.

$\forall$ is verbalized 'for all'. It means for every element in the set, something is either true or false. For example:

$\forall x \in S, x < 5$ means that all of the elements in my set $S$ are less than 5.

$I$ is the identity function.

The entire phrase $I: \forall X.  X \rightarrow X$

(EDIT: removed example, as it was misleading)

means the identity function preserves the value of the variable $X$. More concretely, $I$ is the function that maps $X$ to itself. For all values of X, the output of the function is X.

Hope that helps!


Is it possible to evaluate $n!$ in $O(1)$? I'm working on a formula that'll evaluate the partial sum of the harmonic series from $t_1$ to $t_n$. The problem is that I'm almost certain the final formula will include factorials. But if the formula has a factorial, then it's runtime complexity would be at least $O(n)$. And this would defeat the entire point of having a general formula, because I can just iterate over the first $n$ terms and add those in $O(n)$. Utilizing the gamma function wouldn't help either since it'll require $n$ "integration by parts" steps. So is there any way to evaluate factorials faster than $O(n)$?

There are two scenarios:

Your integers are of fixed size. Then, you absolutely can compute $n!$ in $O(1)$. In fact, every algorithm that computes $n!$ satisfies this. Why? There are finitely many inputs to your algorithm. If it takes $f(n)$ steps to compute $n!$, and there are finitely many $n$ values, then there must be some maximum for $f$. That's the upper bound on your runtime.
Is this answer useful? No, since it doesn't give you any hints as for how to speed up an algorithm. But, it hints that maybe Big-O notation isn't an accurate measure of time for your particular application.

Your integers are of unbounded. Then there can't be an $O(1)$ way to compute it.
How do we know? Well, suppose you have an algorithm that takes at most $k$ steps for any input. Give it an input with $k+1$ bits. It can't possibly examine each bit, since looking up a bit requires a step. So your algorithm only looks at $k$ bits of the $k+1$-length function. But then, if you give the same input with the ignored bit flipped, it will give the same answer! This is impossible, since factorial is an injective function. Flipping a bit should always give us a different answer, so we must examine each bit, so we can't compute it in $O(n)$.


Names of power-of-two bit operations on bitsets that would not assume any number interpretation Three commonly used functions when it comes to bit manipulation are :

is_pow2: Checking that an integer is a power-of-two (only one bit  is set): $00010000 \Rightarrow yes$
floor_pow2: Finds the largest integer power of two not greater than the given value $00010010 \Rightarrow 00010000$ (msb on the left, lsb on the right)
ceil_pow2: Finds the smallest integer power of two not less than the given value $00010010 \Rightarrow 00100000$ (msb on the left, lsb on the right)

However, the concept of a power of two requires to assume a numeric interpretation of sets of bits. But fundamentally the functionality provided by these functions stay valid on bitsets without a numeric interpretation. For example, what is_pow2(x) is really asking is whether popcount(x) == 1. And popcount does not require to define any concept of power of two.

I was wondering if the three functions is_pow2, floor_pow2, ceil_pow2 had commonly accepted names in mathematics, computer science or computer engineering which do not rely on the concept of a power of two.

You can think of a bitvector as a set, by giving names to the various bits. For example, if we name the bits in an 8-bit integer using the numbers $0,\ldots,7$ (where $0$ is the LSB and $7$ is the MSB), then $00010010$ is the same as $\{1,4\}$.

Your first function asks whether the set has size $1$. If we name the bits using numbers as above, the second function is maximum and the third is minimum.


Since we need space for recursive calls, is the space complexity of the recursive factorial is n? As Wikipedia says, quickSort needs O(log n) extra space when the following conditions are met:

In-place partitioning is used. This unstable partition requires O(1)
space.
After partitioning, the partition with the fewest elements is
(recursively) sorted first, requiring at most O(log n) space. Then
the other partition is sorted using tail recursion or iteration,
which doesn't add to the call stack. This idea, as discussed above,
was described by R. Sedgewick, and keeps the stack depth bounded by
O(log n).

Now please consider the following method computing the factorial of n recursively:

private static int fact(int n) {
    if (n == 1) {
        return n;
    }
    return n * fact(n - 1);
}

There is no tail recursion. Does it mean that we need O(n) extra space for the call stack?

Yes, you need up to $n$ stack frames for the recursion.  Therefore, you'll need $\Theta(n)$ space for these stack frames.


Variations of the halting problem Let $M$ be an arbitrary Turing machine and $w \in \{0, 1\}^{*}$ be a binary string.

The language $\text{HALT} = \{\langle M, w \rangle : M ~\text{halts on input} ~w \}$ is undecidable by the famous diagonalization proof.

But what happens when we either fix the Turing machine $M$ or the input $w$?

Formally, for a fixed $M_{0}$ in the first case and a fixed $w_{0}$ in the second case, are these two languages still undecidable? Is there any dependence on the nature of $M_{0}$ or $w_{0}$?

$\text{HALT}_{M_{0}} = \{w : M_{0} ~\text{halts on input} ~w
   \}$
$\text{HALT}_{w_{0}} = \{\langle M \rangle : M ~\text{halts on input $w_{0}$}
   \}$

For the first language, I found a proof online (Proposition 17.2), but it seems specific to the nature of $M_{0}$ which is probably intuitive. I am more intrigued by the second case.

Whether $\mathsf{HALT}_{M_0}$ is decidable or not depends on $M_0$. For example, if $M_0$ always halts, the $\mathsf{HALT}_{M_0}$ is trivially decidable, whereas if $M_0$ interprets its input as a Turing machine $M$ which it runs on the empty input, then $\mathsf{HALT}_{M_0} = \mathsf{HALT}_\epsilon$ is undecidable (see below).

The language $\mathsf{HALT}_{w_0}$ is always undecidable, as a simple diagonalization shows. Suppose that $M$ could solve $\mathsf{HALT}_{w_0}$. Using the recursion theorem, one can construct a machine $M'$ which acts as follows:

Run $M$ on $M'$. If $M$ returns YES, go into an infinite loop, otherwise halt.

Notably, $M'$ doesn't depend on its input. Considering what happens when it is run on $w_0$, we reach a contradiction just as in the standard proof of undecidability of the halting problem.


Linear time algorithm to sort points of a simple polygon In triangulating a simple polygon, using the concept of sweep line helper vertices etc, the very first step is sorting the vertices of such polygon. Apparently this very step can be done in $O(n)$ (where $n$ is the number of vertices). I'm trying to work out why... Assume there's no degenerate case (for any pair of points belonging to the polygon their $y$ coordinates are different). Because of such property a strict order exists $y_1<y_2<\ldots<y_n$, assume each point is stored in floating point $y_i = (e_i,m_i)$, I can't really see how to sort these points in linear time... could anyone give me an hint?

Source :
Computational Geometry - Algorithm and application (DeBerg et all) chapter 3:

The claim is this

  We now analyze the running time of the algorithm. Constructing the
  priority queue $\mathcal{Q}$ takes linear time...

Any kind of priority involves order relationships, so I assume some kind of ordering algorithm is used. Eventually the priority queue can be implemented using binary trees or heaps (basically these are the same thing) but It would still require $O(n \log n)$. I know ordering algorithms that run in linear time, however I don't think any of those can be applied in case of floating point numbers.

You ask:

  the very first step is sorting the vertices of such polygon.
  Apparently this very step can be done in $O(n)$

but the book says

  We now analyze the running time of the algorithm. Constructing the priority queue QQ takes linear time...

Constructing a priority queue does not take as much time as sorting. Priority queues can be constructed in linear time. The most famous algorithm for doing this is called "heapify".


Which textbook can I use after a high school CS course? I just finished the AP Computer Science course in high school and since my school does not have any further classes, I was thinking about getting a textbook and continuing my study. APCS goes through Big O, Arrays + ArrayLists, Recursion, Linked Lists, a rough overview of some other data structures and some sorting and searching algorithms (all in Java).

I will start Calculus in school next year (if that helps to determine math level).

Since I was thinking about participating in CS tournaments, I thought it would be useful to learn more about algorithms and data structures.

I was looking at two textbooks, The Algorithm Design Manual by Steven S Skiena and Introduction to Algorithms by Cormen et. al. I was wondering which one, if any of these, would best fit my situation.

Personally, I recommend either Algorithms by Dasgupta, Papadimitriou, and Vazirani, or The Algorithm Design Manual by Skiena.

The Algorithm Design Manual is super-practical and full of excellent pragmatic advice, useful stories, and is well-written and easy to read.  If you want to help get ready for programming contests, I strongly recommend that one.

I think Dasgupta has a better introduction from the perspective of learning the conceptual material, the theory, the proofs underneath the algorithms, etc.  So, if you want to learn the theory, I recommend Dasgupta.

You won't go wrong with either; they are both outstanding.

Personally, I think they are better than Cormen.  I learned from Cormen, and it's a perfectly fine book, but it can be a bit dense in places and a bit challenging to learn from, so it wouldn't be my first recommendation.  Still, it's a reasonable contender and you wouldn't be led astray by it; I just think the others are better.


How specifically do I need to describe (in words) the language of a regular expression? For the regular expression $(a^*ba^*b)^*a^*$, I want to learn how to describe it in words. I know there are an even number of $b$s but how much do I need to explain it? Do I need to explain it enough that each possible string can be produced from my explanation?
Another example is $(a^*[ba^*c])^*$ where I would describe it as as string over $\{a,b,c\}$ where there are the same number of $a$s and $c$s.

The first language can be described as the set of words on the alphabet $\{a,b\}$ with an even number of $b$'s.

The second one is not the language of words on the alphabet $\{a,b,c\}$ with an equal number of $b$'s and $c$'s (this condition would define a non-regular language). You could use greybeard's description or say: the language contains the empty word, the last letter of the nonempty words of the language is a $c$ and if you delete the $a$'s, you are in $(bc)^*$.

It would be safe to provide a formal proof by computing the minimal automaton corresponding to each description.


Algorithm Request: "Shortest non-existing substring over given alphabet" I'm looking for an (efficient) algorithm to solve the following problem:

  Given a string $S$ and a set of characters $M$, find the shortest string composed only of characters in $M$ that is not contained in $S$.

Try as I might, I can't seem to map this problem to any of the standard CS string problems.

Here is the clean presentation (after going in circles around it).

First you consider all substrings of S that are in M*. From that you
build a trie, which may be understood as a tree structured FA that
recognizes these substrings. You build it so that you complete first the transitions of nodes that are closest to the root. As soon as you have a node from which
there is no arc for a given character in M, you have your answer which
is the string associated with that node concatenated with the missing
character.  Complexity is $O(n^2)$ where $n$ is the length of the
string S, because that is the maximum number of characters you may have to consider while building the trie.

Note regarding complexity: In the trie construction you have to
consider only the longest substring in $M^*$ starting at each position
in $S$, since shorter ones are automatically taken care of. Each state
thus created is an accepting state recognizing one substring. There
are at most $n$ substrings in $M^*$, each having at most $n$ characters. Each is considered in constant time.