Pumping lemma for context-free languages - Am I doing it right? I have an exam coming up in three days, and there's a thing that I really need to be able to completely understand - that is, of-course, pumping lemmas for CFL. I know how to do prove that a regular language is not regular using PL, but for CFL it's a bit more variables, and I am not entirely sure how to split a string. Below, I will provide with an exercise and my attempt. I want to know, am I doing this correctly and if not, what do I need to do to make it correct?
The exercise (although quite similar to the previous question I asked, that question was for regular language and not CFL - in short they are two different questions)

Show, using pumping lemma, that $L2 = ${ $ 0^m 1^k 2^n | n = km $} is not context-free

My attempt goes as following:
If L2 is context-free, then there exist a constant $P$ such that $ S \in L2 $ and $|s|\ge P $ which implies that there exist strings uvxyz such that the following are satisfied:

$(1) uv^ixy^iz \in L2 $ for every $ i \ge 0 $

$(2) |vy| > 0 $

$(3) |vxy| \le P$

We must first assume that $L2$ is context-free
$L2$ must have a Pumping length $P$
Must also take strings $0^P 1^P 2^{p^{2}} $ (since n = km)

There are 3 cases

case 1) VXY does not straddle a boundary, belongs to just one
So we have $0^P 1^P 2^{P^{2}}$, let's split that into $UVXYZ$,

$U = 0^P$,  $ V = 1^r $, $ X = 1^t $, $ Y = 1^{P-r-t}$, $Z= 2^{P^{2}} $
and then we select $i = 2$, which gives us
$uv^2xy^2z = 0^p 1^{2r} 1^t 1^{2p-2r-2t} 2^{p^{2}} =  0^p 1^{2p-t} 2^{p{^2}} \notin L2$

case 2) VXY straddles the first boundary;
like above, we split into $uvxyz$ where
$u = 0^r $
$v = 0^{p-r} 1^t $
$x = 1^r $
$y = 1^{p-t-r} $
$z = 2^{p{2}} $

if we, yet again, select $i = 2$

$uv^2xy^2z = 0^r 0^{2p-2r} 1^{2t} 1^{r} 1^{2p-2t-2r} 2^{p{2}} = 0^{2p-r} 1^{2p-r} 2^{p{2}} \notin L2 $

case 3) vxy straddles the second boundary;
again, like above we split the string into 5 parts $uvxyz$ where
$ u = 0^p $
$ v = 1^t $
$ x = 1^r $
$ y = 1^{p-t-r} 2^t$
$ z = 2^{p{2} - t} $

if we select $i = 2$
we get $uv^2xy^2z = 0^p 1^{2t} 1^r 1^{2p - 2t - 2r} 2^{2t} 2^{p{2}-t} = 0^p 1^{2p-r} 2^{p{2}+t} \notin L2$

Thus we have contradictions for all three cases, which concludes that the language is not context-free!

My general question is am I selecting a string correctly? I.e. does it have to satisfy $|vxy| \le p$ in-order for the $uv^ixy^iz $ where $ i = 2 $ to work? OR must $vxy$ be chosen so that the length is $\le p$? Have I missed cases?

Thank you in advance!

Bascially your approach is correct. I have not checked every detail, but have a few remarks:

you miss the cases where v or y include a border like v=0011; here pumping destroys the general structure of the word besides the number relations.
case 1 would have to be done for the 0s and the 2s, too


Solving Subset Sum Without the Use of Dynamic Programming I am looking for algorithmic techniques to solve the Subset Sum Problem in pseudopolynomial time. There is, of course, a textbook dynamic programming approach for Subset Sum. Have any other algorithmic techniques (Randomized, Linear Programming...) been successfully applied to this problem?

In [1], the authors state that "[T]the only algorithm known to solve subset sum (in time polynomial in the numbers involved) is dynamic programming" (page 3). This paper, however, is 8 years old and it might be possible that some progress has been made in the recent past.

[1] Reid Andersen, and Uriel Feige. Interchanging distance and capacity in
probabilistic mappings. Available at https://arxiv.org/abs/0907.3631v1

Yes.

This paper has applied polynomial arithmetic to that problem.


Finding Permutations with Exclusions Recently, I was given a puzzle by a friend of mine, which has 6 pieces. Giddy to try it out, I took it apart without batting an eye to follow what I was removing or moving or sliding.

I've been struggling with this puzzle for over a year and a half now, and so thought I would write an algorithm that would list all the possible orientations or possibilities of pieces.

To make it more general, I numbered each piece 1 though 6. But, each piece can be rotated and placed, so I extended this to 1 through 12. So now each piece has two numbers, 1 and 12 is one piece, 2 and 11, 3 and 10, etc... Now to the root of my question:

Is it even possible to write a recursive algorithm to display all possible permutations of the 12 (6) pieces such that if piece 1 is used, 12 cannot, and so forth. Reason I ask is because if this were recursive, we wont know what we picked above (unless we keep running down in the recursion tree our last picked items) so that we can skip others.

Or, even better, would it be better to write a non recursive function?

Just as a note: I am not looking for code, per se. Pseudo code or concepts, or pointers would be so grateful and helpful.

Relevant References :

The Math behind Combinations with Restrictions

The Math behind Permutations with Restrictions

Just as a note:
Seeing as this may come up; I know the number to this solution is massive, but I've already written functions that tell me if a said permutation can even be played on the board (do certain blocks collide), if at least one block is moveable (we won't want gridlock), and if the placement of blocks conforms to the size of the puzzle enclosure. All this will, hopefully, eliminate quite a bunch, and let me try by hand the remaining games.

Generate all permutations of 1,...,6 (outer loop below), and all binary numbers of length 6 (inner loop below), then combine each permutation in the first set with each one from the second set:
for π in permutations(1,...,6):
    for x in 000000,...,111111:
        output C(π[1],x[1]),...,C(π[6],x[6])

where $C(n,0) = n$, $C(n,1) = 13 - n$.


Odd cycle transversal and linear programming Suppose we have a graph $G$ with $n$ vertices. Suppose LP is a linear programming problem where there is a variable for each vertex of $G$, each variable can take value $≥0$, for each odd cycle of $G$ we add to LP the constraint $x_a+x_b+x_c+\dots +x_i≥1$ where $x_a,x_b,x_c,...,x_i$ are the vertices of the cycle. The objective function of LP is $\min \sum\limits_{1}^{n}{x_i}$.
Suppose $S$ is an optimal solution of LP. If a variable $x_v$ takes on a value $>0$ in $S$, is it guaranteed that there exists a minimum odd cycle transversal that contains $v$?  By minimum odd cycle transversal, I mean an odd cycle transversal with the fewest number of vertices.

No, $v$ does not have to belong to any minimum odd cycle transversal.
Consider the following undirected graph. The vertices are split into eight groups: $C_i$ for $i \in [0, 3]$, each of them containing $4$ vertices and $F_i$ for $i \in [0, 3]$, each containing $3$ vertices. The following edges (and only them) are present in the graph:

All edges between $C_i$ and $C_{(i + 1) \bmod 4}$ for every $i \in [0, 3]$
All edges between $C_i$ and $F_i$ for every $i \in [0, 3]$
All edges between $F_0$ and $F_2$, all edges between $F_1$ and $F_3$

Let's prove the following statements:

Any OCT that contains a vertex from one of the $C_i$'s has size at least $7$, but there are OCT's of size $6$ (for example, $F_0 \cup F_1$).
In any optimal solution to the LP relaxation, the variables corresponding to vertices from $F_i$'s are set to zero. Moreover, there is only one optimal solution to the LP relaxation: set all variables corresponding to vertices of $C_i$ to $1/3$.

If both are true, then, for every nonzero variable in the optimal solution to the LP, there is no minimal OCT that passes through the corresponding vertex. Because the graph is small enough, you can verify both these statements on a computer.
But I will give a short "human" proof to both.
For the minimum OCT part, it is clear that we should either delete each of the vertex group either fully, or not touch it at all (because just a single vertex from the group is "good enough representative" for the whole group). Moreover, we can see that deleting one $C_i$ group is not enough. If we delete, say, the group $C_0$, there is still an odd cyle $F_1 \to C_1 \to C_2 \to C_3 \to F_3 \to F_1$. Hence, we still have to delete at least one other group, for $7$ vertices in total. On the other hand, $F_0 \cup F_1$ is an OCT with size $6$.
Now let's deal with LP part.
It can be seen that all odd cycles in the graph pass through at least $3$ vertices from $C_i$. Hence, assigning weight $1/3$ to each vertex of each $C_i$ yields a solution with total cost $16/3$. On the other hand, consider all cycles of length $5$ in our graph. It can be proven that all vertices from $C_i$'s lie on exactly $3/16$ fraction of them, but all vertices from $F_i$'s lie on exactly $1/6$ fraction of them (the proof is a bit tedious to write down, so I will add it only by request). Then, by averaging the inequalities $x_a + x_b + \ldots + x_\ell \geqslant 1$ over all these cycles, we get $\frac{1}{6} \sum\limits_{v \in \bigcup F_i} x_v + \frac{3}{16} \sum\limits_{v \in \bigcup C_i} x_v \geqslant 1$, implying $\sum\limits_{v \in V} x_v \geqslant \frac{16}{18} \sum\limits_{v \in \bigcup F_i} x_v + \sum\limits_{v \in \bigcup C_i} x_v = \frac{16}{3} \left(\frac{1}{6} \sum\limits_{v \in \bigcup F_i} x_v + \frac{3}{16} \sum\limits_{v \in \bigcup C_i} x_v \right) \geqslant \frac{16}{3}$. Moreover, the inequality is strict if some $x_v$ with $v \in F_i$ is not zero. Hence, in each optimal LP solution, non-zero weights are assigned only to vertices from $C_i$'s. Moreover, it is possible to prove that there is only one optimal solution, with all weights of $C_i$'s set $1/3$. It is not too important, though, because we already proved that all optimal LP solutions are pairwise disjoint from all optimal OCT's.


Why a separate ALU is needed, since any integer can be represented as floating point numbers? Most of the operations in computers are using floating-point arithmetic, and why a Floating Point Unit alone is not sufficient? Can we do away with ALU? Is FP operations are resource-intensive alone be the reason for this, over the advantages provided by FP operations?

Any 64 bit integer can be represented as an 80 bit IEEE 754 extended precision floating point numbers. Many processors (PowerPC and POWER, ARM) don't support extended precision floating point, so there is your first argument gone. They can't represent every integer number as a floating point number.

Most operations on integers can be done very cheaply with integers represented in an integer format, but are much more expensive if you try to implement them with numbers in a floating point format. That will reduce your clock speed and at the same time raise energy consumption, costing you battery life on any portable device.


Maximum weight vertex-disjoint paths I have a complete (every vertex is  connected by an edge to every other vertex) undirected positively weighted graph. I want to find vertex-disjoint paths in the graph whose total weight is as large as possible.

To me this sound like a mix of the longest path problem (NP-complete) and minimum spanning tree. Finding the best solution is not required, so maybe some greedy algorithm or something would be a good fit.

Any ideas and algorithms on how to approach this problem?

This is not NP-Complete as far as I know. Below is a way to solve it.

You can convert the problem to finding the minimal path cover of your graph by making all the weights negative. The minimal path cover is a collection of disjoint paths covering all vertices.

One way of solving this is to convert your graph into a bipartite graph by doubling the vertices and making sure every edge goes from one side to the other. You then find the maximum bipartite matching, which will give you all the edges used in the disjoint path covers, and you can then find the paths from this set.

To get the maximum bipartite matching you can convert the graph into a flow network with unit weights on edges and use Ford-Fulkerson algorithm. All edges in the max flow will be in the maximum bipartite matching. You can then stitch the edges together as there will be only one way to assemble it with minimum number of paths.


Minimum number of exchanges needed to get all negative values left of all positive ones Suppose we want to arrange n numbers stored in an array such that all negative value occur before the positive ones. What will be the minimum number of exchanges in the worst case ?

You can keep a pointer to the currently first positive value in the list, which initializes to 0. Then scan through the list, when you see a negative value swap it with the positive value, and increment your pointer.

You get O(n) swaps in the worst case.

If the first half is positive and second half is negative, you have to have at least n/2 swaps, as the second half needs to swap places with the first half.

To actually get n/2 swaps, you can first count the # of positive values, and if the positive values are greater, iterate the list in reverse order, and keep a pointer first negative value in the list. You can then stop if you have swapped all the positive or negative values.


On uniform randomness of the weight of the remaining edges of a graph after deleting some of them Suppose we have a graph $G(V,E,W)$, where $V$ and $E$ are the set of vertices and edges and $W$ is non-negative weight on the edges. Let $w(e)$ be the weight of edge $e$ and $N(e)$ be the neighboring edges of $e$. An edge $e$ is locally subdominant if its weight is smaller than all of its neighbors. With this background Let we have the following algorithm,

for e in E
if w(e) is locally sub-dominant
    delete e from the graph G
    double weights of all e in  N(e)

My question is after this loop ends what can we say about uniform randomness of the remaining edges. Are they still uniform random?

Let us consider the simplest case, that of a path of length two edges, which are drawn uniformly and independently from $[0,1]$. Let us suppose that the first edge is sub-dominant, which happens with probability 1/2. The probability that the weight of second edge is at most $t \in [0,1]$ is
$$
\Pr[x \leq y \leq t \mid x \leq y] = \Pr[x,y \leq t] = t^2.
$$
Here $x$ is the weight of the first edge, and $y$ is the weight of the second edge. We see that even before doubling, the distribution of $y$ is non-uniform.

Next, let us examine the case of a star with three edges, again drawn uniformly and independently from $[0,1]$. Again suppose that the first edge is sub-dominant, which happens with probability 1/3. The probability that the weight of the second edge is at most $t \in [0,1]$ while that of the third edge is at most $u \in [0,1]$ is
$$
\Pr[y \leq t, z \leq u \mid x \leq y,z] =
3 \int_0^{\min(t,u)} (t-x)(u-x) \, dx = \\
3tum - \frac{3}{2}(t+u)m^2 + m^3.
$$
Here $x,y,z$ are the weights of the first, second, and third edges, respectively, and $m = \min(t,u)$. Substituting $u = 1$, we obtain
$$
\Pr[y \leq t \mid x \leq y,z] = \frac{3t^2-t^3}{2}.
$$
Calculation shows that for generic $t,u$,
$$
\Pr[y \leq t, z \leq u \mid x \leq y,z] \neq
\Pr[y \leq t \mid x \leq y,z] \Pr[z \leq u \mid x \leq y,z],
$$
that is, the remaining weights are no longer independent.


Retrieving data from hash table ordered by insertion time By default, a hash table is unordered.  I have a simple question on the retrieval of elements in a hash table

  Can we retrieve elements from a hash table in the same order as they are put inside?

Once you've put an element in any kind of container data structure like map or set, ordered or unordered, the data structure no longer remembers the order in which you called insert().  (The "ordered/unordered" distinction is whether the data structure keeps the elements in order by their key with respect to the less-than operator.)

If you want to know the order in which some events happened you will need to keep another container data structure, or some auxiliary information in the objects you are storing.  For example if you want to be able to iterate through in the order in which you inserted: keep both an unordered_map and a vector of references to the objects you inserted.  Every time you do an insertion you also push_back a reference to what you just inserted.  (But be careful, if you are doing this in C++, that you aren't also removing objects from the unordered map, because then the references in the vector will become invalid.)

If you want a number associated with each element stored in the map ("this was the 42nd inserted"), then you should augment your map datatype with, (a) a global counter and (b) a way to store both an object and a number (e.g., store struct {T the_object; int insert_order;} instead of objects of type T), and (c) wrap the insert operators so that they increment the counter and insert the new number along with the new object.


Search a sorted array that ends with zeros in O(log n) time I have an array of size $m$, $[1,1,2,2,3,4,5,...,f,0,0, \cdots,0]$, where the first $n$ elements $1,1,2,2,3,4,5,\cdots, f$ are sorted.

If I make a binary search including the 0's I get $O(\log(m))$.
I'm trying to make the algorithm better and to get complexity of $O(\log(n))$ with no success.

I thought maybe something with medians?
Any idea will be great.

Here is a simple algorithm to solve the problem as in Yuval's comment.
Algorithm
Input: A positive number $w$ and array $A$ of $m$ numbers, $A[0],\cdots, A[m-1]$. The first $n$ numbers of $A$ are non-decreasing positive numbers and the rest are 0s.
Output: An index $k$ such that $A[k]=w$ or -1 if $w$ is not an element of $A$.
Procedure:

Check elements at index $1,2,4,8,\cdots$, until a zero is found or the index overflows. Let the index thus found be $p_0$. Let $p$ be the smaller of $p_0$ and $m-1$. Note $n\le p\lt 2n$.
Consider 0 as greater than all positive numbers so that $A[0], A[1], \cdots, A[p]$ becomes a sorted array. Conduct a binary search for $w$ on that array. If $w$ is found, return the index; Otherwise, return -1.

Algorithm analysis
Step 1 checks at most $\log_2(2n)=1+\log_2 n$ elements. Step 2 checks at most $\log_2(p+1) + 1 \le 2 + \log_2n$ elements. So the time-complexcity of the algorithm is $O(\log n)$.
This problem is a variation of the classic problem of searching sorted, unbounded/infinite lists. The algorithm above is a simple variation of the exponential search explained in this Wikipedia article. You are encouraged to take a look at that article for more intriguing variations. For example, a basic version of Bentley and Yao's algorithms checks elements at index 2, 4, 16, 256, 65536, $\cdots$ first.
Exercises
Exercise 1. (One minute or two) Assume that $w$ might not be positive and the first $n$ element of $A$ might not be positive instead. Adapt the algorithm slightly so that it still works.
Exercise 2. (One minute or two) Improve the algorithm so that it runs in $O(\log k)$ time where $k$ is the smaller of $n$ and the index of the first element in $A$ that is no less than than $w.$
Exercise 3. Let $B$ be a sorted array of $n$ distinct elements, one of which is $w$. Devise an algorithm that finds $w$'s index in $O(\min(k, n-k))$ time, where $k$ is $w$'s index.


Master Theorem linearithmic function I am trying to find the running time of the given recurrence by the Master Theorem: $T(n)=16T(\frac{n}{2})+n^3\log^4 n$

I get $a=16$, $b=2$ and $f(n)=n^3\log^4n$, It seems that it's Case 1 of the master theorem. because $f(n)=O(n^{4-\epsilon})$ for some $\epsilon >0$ (?)

but I can't find this epsilon, and I am doubting if I can truly use the Master Theorem in this case.

What's I am missing?

It's easy to prove that

$\qquad\displaystyle n^3 \log^k n \in o(n^{3+x})$

for all $k \geq 0$ and $x > 0$. That should give you plenty of $\epsilon$ to choose from.


How to detect outliers using DBSCAN? I am working on a Fraudulent Cash Transaction Detection System using DBSCAN and I want to know what is the proper way to identify outliers?
Thank you
##Edite##
I had a problem how to represent the outer points extracted by the DBSCAN algorithm in Python visualization techniques, and found the solution here:
https://www.youtube.com/watch?v=eq1zKgCFwkk
Enjoy your time

There are two parameters to DBSCAN: minPts, and ε.
You have an outlier point if there are fewer than minPts points within ε of it (using the appropriate distance metric). If this isn't the case, it's a sufficiently dense region that there is a cluster here.


How does an inverted index reduce storage requirements? In p. 7 of the book "Introduction to Information Retrieval" (by Manning et al), the authors explain how, given a collection of text documents, an inverted index is built by tokenizing,  then sorting the (term, docID) pairs, merging multiple occurrences of the same pairs, and the pairs for each term are grouped into a posting list.  It is then mentioned that "Because a term generally occurs in a number of documents, this data organization already reduces the storage requirements of the index."  My question is: how are the storage requirements reduced?  It seems to me that if a term occurs in $k$ documents, then these $k$ documents' ID's must all be mentioned in the linked list for this term.
If a term occurs multiple times in the same document, then because the inverted index mentions a  docID at most once in a term's list, there is a reduction in storage.  But this condition is different from the condition that a term occurs in multiple (distinct) documents.

I think the author meant that by separating the index into the "dictionary" part and the "postings" part, we reduce the storage requirements of the strings themselves, because now we only have to store one string for each unique word. It's as if you are storing the vocabulary of the language itself, independent from the documents. It is also mentioned later that the dictionary is usually kept in memory, so it is important to make sure it doesn't take up much space.


Rules of converting a weighted digraph to an undirected graph? What are the rules of converting a weighted digraph to a weighted, undirected graph?

I understand that the edges should go in both directions from vertex to vertex. However, do the weights of each edge to/from other edges need to be the same? If not, how does one decide which weight to attach to the undirected vertices?

For example, can this adjacency matrix representation of a weighted digraph be converted into an undirected weighted graph?

There aren't any rules. Do whatever is most appropriate to your specific situation. What do the weights mean? That should probably tell you what weights to use in the new graph.

If there is no meaning, translation doesn't make sense: translation is, by definition, an operation that preserves meaning.  For example, suppose I give you the following exercise:

  Translate the program function int int (hello_) repeat end begin int into Java.

The program doesn't mean anything so it can't be translated. You can't possibly give me a Java program and say "This is the right one" because there's no definition of "right". Similarly, without saying what the edges and weights of some digraph mean, there's no way to justify the claim "This undirected graph is the correct translation."

There's no intrinsic equivalence between directed and undirected graphs. Usually, one associates an undirected graph with the directed graph in which every edge is replaced by a directed edge in each direction.  In many contexts, these behave the same way (e.g., if I can get from A to B in the graph, I can follow the same route in the digraph). In other circumstances, though, they might be different. For example, an undirected edge might represent the existence of a two-way road between two cities, whereas a pair of directed edges might represent separate one-way roads in each direction.


A physical algorithm that finds all integer partitions of a number If this is not the right forum for this question let me know.

I am looking for a physical algorithm that can be easily followed by anyone not knowing much mathematics to get integer partitions of a number.

I have come up with the following way - but there is an issue (described later).

Suppose I want to divide number 11 into all its integer partitions (order is not important).

For finding partitions of size 2 we do following.

Take 11 coins of identical widths. Take a paper. Write 1 and 2 on it

1    2

Below the first number, keep all 11 coins one upon another to make a tower of height 11. This is represented as -

1      2

11c   0c

Now, shift 1 coin from first column to second column.

1      2

10c   1c

Here, height of tower 1 = 10, height of tower2 = 1

Keep on doing this, only if Height of tower 1 >= Height of tower2

On each step of the algorithm, we get new integer partition.

This "physical algorithm" is easy to understand by anyone knowing
basic mathematics.
Preferrably, each step in the physical algorithm must show a new
partitioning way.
There should be an end condition to the algorithm.
When the algorithm reaches end condition, all possible partitioning
ways must have been shown.

If we now want to find all partitions of size 3, the problem gets a bit tricky.

We have 3 towers, with following restrictions
Height of tower 1 >= Height of tower2 >= Height of tower3

But thing is, there are certain positions, from which we cannot go to next stage without destroying earlier stage - what do I mean by this? See below

Step1

1      2     3

9c    1c     1c

Step2

1      2     3

8c    2c     1c

Step3

1      2     3

7c    3c     1c

Alternative Step3

1      2     3

7c    2c     2c

At step 3 the algorithm creates two branches - people could either put new coin in tower2 or tower1. How should the algorithm statements be written so that by the time the algorithm is finished, all partitions of size 3 are known?

If you could come up with a new algorithm, that's welcome too!

Let us aim at generating the partitions in the following order (below, for $n=6$):

$$
\begin{align*}
& 6 \\
& 5 \, 1 \\
& 4 \, 2 \\
& 4 \, 1 \, 1 \\
& 3 \, 3 \\
& 3 \, 2 \, 1 \\
& 3 \, 1 \, 1 \, 1 \\
& 2 \, 2 \, 2 \\
& 2 \, 2 \, 1 \, 1 \\
& 2 \, 1 \, 1 \, 1 \, 1 \\
& 1 \, 1 \, 1 \, 1 \, 1 \, 1
\end{align*}
$$
We start with the partition $n$.

To generate a new partition, identify the last non-1 entry in the preceding partition (if there is no such, we’re done); reduce it by 1, and delete all following entries; complete it to a partition by repeatedly adding the maximum possible number, under the constraint that the partition is non-increasing.

You can check that this indeed generates all partitions.


Shortest path in a graph where edges are forbidden depending on the path taken I have a problem similar to Shortest path problem where edge weight depends on path taken but not quite the same. In my case each edge has either a fixed finite weight, or an infinite weight, depending on which path has been followed. So depending on the path taken through the graph, some edges from the current node are not allowed while others are. My graph is a DAG otherwise.

The shortest path can consist of many edges so I can't really represent the path history in the graph by duplicating nodes otherwise the number of nodes would increase exponentially and would be intractable.

Would Dijkstra's algorithm for finding the shortest path between two nodes still produce the correct answer in this particular type of graph? What else can I do?

The decision version of the problem you describe seems to be coNP-complete (assuming that the weight function description is polynomial in the size of the description of the graph).

The language corresponding to the decision version would be $L=\{G,w,s,t,p : p  \text{ is the shortest path in G between s and t according to } w\}$

Lets take the complement of the language Hamilton Cycle, denoted by
 $\overline{HC}=\{G\big| \text{There is no hamiltonian cycle in G}\}$ (hamiltonian cycle is a cycle that visit every vertex of G exactly once).

It is well known that $\overline{HC}$ is coNP-complete.

Now we can reduce $\overline{HC}$ to $L$ (in polynomial time):

On input graph $G$:

Take an arbitrary vertex $u$, split it into two $u_{start}$,
$u_{end}$ and connect them to all neighbors of $u$.
Create a weight function w in which all edges connected to $u_{end}$ has
$\infty$ weight unless the path we have followed visits each vertex
in $V \setminus \{u_{end}\}$ exactly once, and all other edges has weight 1
(this condition can be checked by a "short code" therefore $|w|$ is
polynomial).
Add an edge $e'$ between $u_{start}$ and $u_{end}$ with a constant weight of $n+1$.
Output $(G,w,u_{start},u_{end},p)$ where $p$ is the path $u_{start} \underset{e'}{-}v_{end}$

The reduction is polynomial, and observe that there is no Hamiltonian cycle in $G$ if and only if $u_{start} \underset{e'}{-}v_{end}$ is the shortest path in $G$ between $u_{start}$ and $u_{end}$.

So there is no polynomial algorithm for your problem (unless P=NP).


Allowing an empty (epsilon) transition in a PDA I'm trying to allow an empty transition in a PDA for the following language:

Alphabet: $Σ = \{a, b, c\}$
Language: $L = \{ a^ib^j \mid i \neq j \} \cdot \{ c \}^\ast$

Examples of words in $L$:

$\varepsilon$
$aabccc$
$abbccc$

Not in $L$:

$abcc$
$aabbc$

Here is what I came up with:

The diagram above uses JFLAP - where the symbol $Z$ reflects the empty stack. The symbol $λ$ is the empty symbol $ϵ$.

It accepts everything as it should, but I don't know how to let epsilon get through. q7 to q8 is when there is more b than a. So there should be a way to allow q7 to q9 where a is more than b but also epsilon can get through. Thoughts? I would like to simply set epsilon through but than aabbc can get through easily enough.

Some key points:

The only case where you want to accept $\epsilon$ is when you haven't had any other input and your stack is empty. Therefore you need an accepting state right at the beginning.
You need to take into consideration inputs such as: $bac, aac,...$ that will never result in an accepting state, or $abbb$ that results in an accepting state without containing any $c$'s
If you get a $b$ and your stack is empty you have more $b$'s than $a$'s so you need an accepting state
If you get a $c$ and and your stack is not empty you have more $a$'s than $b$'s so you need an accepting state
You reject everything else.


To prove or disprove that language is regular Suppose the language L = {w | w is an integer whose sum of digits is a multiple of 2}. I strongly feel like this is non-regular language, but how should I choose a string to apply the pumping lemma?

The language $L$ is regular as shown by the following "flip-flop" style minimal and deterministic automaton $\mathcal{A}$, the crux is that you need only two states (not an unbounded amount of memory) to check parity. $\mathcal{A} = \langle \{odd,even\}, \{0..9\}, even, \{even\}, \delta \rangle$ which transition function $\delta$ is defined by :

$\delta(x,even) = even$ when $x\in \{0,2,4,6,8\}$
$\delta(x,even) = odd$ when $x\in \{1,3,5,7,9\}$
$\delta(x,odd) = even$ when $x\in \{1,3,5,7,9\}$
$\delta(x,odd) = odd$ when $x\in \{0,2,4,6,8\}$


Approximate value iteration for continuous state space MDPs I have a continuous state space MDP as a generative model. I input the state and action and it outputs the reward and the next state. Assume that I sampled $n$ state-reward-states. I wonder how I can implement value iteration using a function approximator. I couldn't find any implementation example online. Can you please point me some references?

There are two primary methods to deal with continuous state MDPs.
1. State-space discretization.
2. Value function approximation.
As for value function approximation, you can either go for a deterministic/stochastic black-box model or opt for fitted value iteration. You can find the algorithm for the same in pages 10-13 of this link.


Being a computer organizations and architecture expert One of the greatest challenge in learning one is how broad the literal computer science is. Just talking about memories and CPUs would just took you to endless adventure of this technology. How does the expert manage to understand all of this if I ever want to be one of them?

Maybe someone ever be on my position, not just want to survive the exam but wanted to be the expert of this field especially on the hardware side and rarely ever grasp all the concepts.

Study and practice for years.  Years and years.
No one understands all of it.  Everyone specializes.
People get a broad sense of the field, but they don't learn all of it.  Then, they learn what they need to know, when they need to know, and only then.

So, keep at it.  You can understand enough to be effective, even if you don't know everything.


Language involving irrational number is not a CFL I am working through a hard exercise in a textbook, and I just can't figure out how to proceed. Here is the problem. Suppose we have the language $L = \{a^ib^j: i \leq j \gamma, i\geq 0, j\geq 1\}$ where $\gamma$ is some irrational number. How would I prove that $L$ is not a context-free language?

In the case when $\gamma$ is rational, it's pretty easy to construct a grammar that accepts the language. But because $\gamma$ is irrational, I don't really know what to do. It doesn't look like any of the pumping lemmas would work here. Maybe Parikh's theorem would work here, since it would intuitively seem like this language doesn't have an accompanying semilinear Parikh image.

This exercise is from "A Second Course in Formal Languages and Automata Theory" by Jeffrey Shallit, Exercise 25 of Chapter 4.

I would really appreciate any help, or nudges in the right direction. Thank you!

According to Parikh's theorem, if $L$ were context-free then the set $M = \{(a,b) : a \leq \gamma b \}$ would be semilinear, that is, it would be the union of finitely many sets of the form $S = u_0 + \mathbb{N} u_1 + \cdots + \mathbb{N} u_\ell$, for some $u_i = (a_i,b_i)$.

Obviously $u_0 \in M$, and moreover $u_i \in M$ for each $i > 0$, since otherwise $u_0 + N u_i \notin M$ for large enough $N$. Therefore $g(S) := \max(a_0/b_0,\ldots,a_\ell/b_\ell) < \gamma$ (since $g(S)$ is rational). This means that every $(a,b) \in S$ satisfies $a/b \leq g(S)$.

Now suppose that $M$ is the union of $S^{(1)},\ldots,S^{(m)}$, and define $g = \max(g(S^{(1)}),\ldots,g(S^{(m)})) < \gamma$. The foregoing shows that every $(a,b)$ in the union satisfies $a/b \leq g < \gamma$, and we obtain a contradiction, since $\sup \{ a/b : (a,b) \in M \} = \gamma$.

When $\gamma$ is rational, the proof fails, and indeed $M$ is semilinear:
$$
\{ (a,b) : a \leq \tfrac{s}{t} b \} = \bigcup_{a=0}^{s-1} (a,\lceil \tfrac{t}{s} a \rceil) + \mathbb{N} (s,t) + \mathbb{N} (0,1).
$$
Indeed, by construction, any pair $(a,b)$ in the right-hand side satisfies $a \leq \tfrac{s}{t} b$ (since $s = \tfrac{s}{t} t$). Conversely, suppose that $a \leq \frac{s}{t} b$. While $a \geq s$ and $b \geq t$, subtract $(s,t)$ from $(a,b)$. Eventually $a < s$ (since $b < t$ implies $a \leq \frac{s}{t}b < s$). Since $a \leq \frac{s}{t} b$, necessarily $b \geq \lceil \tfrac{t}{s} a \rceil$. Hence we can subtract $(0,1)$ from $(a,b)$ until we reach $(a,\lceil \tfrac{t}{s} a \rceil)$.


Can two deterministic turing-machines avoid each other in a sidewalk? Imagine a turn-based game where two robots are placed on opposite sides of a 16x16 board, facing each-other. Each robot, at each turn, can perform one of 2 moves: move (moves forward), turn (turns 90 degree; clockwise for the first robot, anti-clockwise for the second). They can also send messages to each-other, and behave according to arbitrary deterministic computations.

|_|_|_|_|v|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|^|_|_|_|_|

For simplicity, assume the behavior of the robots is determined by a Python function such as:

# just an example, not used
state = {}

# always go forwards
def brain(otherPos, myPos, message):
    return ("move", "hello")

This behavior is, of course, stupid, as it always goes forward and broadcasts the same message, ignoring the position of the other robot and the message sent by it. On this case, the robots would just go forward, until they colide and stop moving forever. But any logic could be implemented and the robots could collaborate in arbitrary ways. An improvement would be:

# just an example, not used
state = {turn: 0}

# always go forwards
def brain(otherPos, myPos, message):
    if state.turn === 0:
        return ("turn", "I'm turning")
    elif state.turn === 1:
        return ("move", "I'm moving horizontally")
    elif state.turn <= 4:
        return ("turn", "I'm turning again")
    else:
        return ("move", "Now I'm going forward, forever!")

This one would cause both robots to turn 90 degrees, move, then turn 3 times, and then move forward forever. They'd still collide and get stuck on the same column, though, because, as one turns clockwise, the other one turns anti-clockwise.

My question is: is it possible to program a brain function in such a way that, after N turns, each robot ends up on the other side?

You have to teach the robots how to keep track of their identity, either by remembering the initial position, or by signing their messages.
Then they can perform their individual programs.
Something like this:

t = "turn"
m = "move"
program1 = [t, m, t, t, t, m, m, m, m, m, m, m]
program2 = [t, t, t, m, t, m, m, m, m, m, m, m]

def brain(otherPos, myPos, message):
    if message == "1":
        return (program1.pop(0), "2")
    else:
        return (program2.pop(0), "1")


maze solving algorithms (pledge algorithm) I saw this maze, and tried to apply pledge algorithms to it. But I am not able to solve this maze using this algorithm. What am I missing/doing incorrectly?

PLEDGE ALGORITHM: in both cases we don't get to exit.

you can read about these algorithms at:

http://en.wikipedia.org/wiki/Maze_solving_algorithm

http://www.astrolog.org/labyrnth/algrithm.htm

If you use wall following with the right hand, you should place your hand on the right wall.

For the pledge algorithm your source says

  It's a guaranteed way to reach an exit on the outer edge of any 2D Maze from any point in the middle, however it's not able to do the reverse, i.e. find a solution within the Maze.

There is no guarantee that the exit reached is the one labeled "Exit" instead of the one labeled "Start".


Can anyone help me understand the matches to this regular expression? My professor gave us this pattern "/[aeiou]+[1234567890]*[a-z]?/" and I'm trying to find matches in "ae12abc r2d2 a1steaksauce".

The resulting matches the professor gave us are ae12a, a1s, eak, auc, and e.

I think I'm totally misunderstanding how this is supposed to work. Why are ae12abc, r2d, or a1steaksauce not possible matches? Thanks in advance, I really appreciate any help with this!

Well let's walk through it. You need one or more vowels, followed by any number of numbers (including none), followed by (optionally) a letter.

ae matches your vowels, 12 matches the numbers, then a counts as your optional letter. The engine starts again and looks for the next vowel. It skips bc r2d2 since there are no vowels there.

Then it finds a for your vowels, 1 for your numbers, and s as the optional letter. Then the engine starts again and looks for the next vowel.

It finds ea for your vowels. There are no numbers, so it grabs k as the optional letter. Then it starts again looking for vowels...


How exactly the "load word" instruction loads from RAM? PS: MIPS architecture

This is a model of a memory RAM of 4GB: it has 4,294,967,295 addresses, and each address has 32 bits. Can somebody tell me why the load word instruction needs an offset to the address? My book says that the offset must be multiplied by 4, but for me, I could simply give the address of the array, and then specify which word I wanted to load by saying that the first word is the number 1, the second is the number 2...
So why I need to multiply the offset?
Update:
My book says MIPS architecture adresses bytes, not words like I thought. So... wtf? So each address of a memory RAM stores only 8 bits? Does it means that when I access a 32bit address of the RAM via the bus, the RAM outputs just 8 bits data through the same 32 bit BUS? Then,the load word instruction would have to access the RAM 4 times just to transfer the entire word to the register. I don't understand it.

Responding only to your UPDATE: MIPS always had load/store byte.  The original models may not have allowed unaligned word accesses.  Load byte is (relatively) easy on a 32-bit bus.  For example, you could fetch the entire word from memory (by setting the bottom 2 address bits to "0") and then add a little circuit so that when the word reaches the processor you use the bottom 2 address bits to shift and mask the correct byte into the destination register.

Store byte is somewhat more complicated.  At the beginning of the store-byte operation the processor shifts the byte into the desired position in the 32 bit word, and then sends the entire 32-bit word along with the entire address (including the 2 low-order bits) to the cache.  The cache uses the 2 low-order bits to control which bytes do and do-not get written.  (The cache has such control (at the word level) anyway, since typically the SRAM array is something like 256x256 bits (= 8Kbytes) or 512x512 bits (= 32Kbytes).)

The only recent architecture I can think of that didn't include load/store byte instructions was the DEC Alpha 21064 (released 1992).  Instead they added a lot of special bit shift-and-mask operations to extract bytes from words.  If you needed to store a byte on the 21064, I think you may have had to load the word that contained the byte, shifted and masked in the byte that you wanted to write, and then write back the entire word.

They added load/store byte instructions in the 21164A (released 1996) because the extra instructions to do all that extra work in software were making the instruction cache less effective than it should have been for programs with a lot of byte operations.


Time complexity of solving a set of 2-sat instances? Suppose I have a set of 2-SAT instances, the set is of size $2^{3C}$ for some constant $C$. What is the time complexity of solving all instances using the fastest known 2-SAT solver?

Although 3SAT problem is NP-complete, there is a polynomial algorithm making use of the beautiful SCC (Strongly Connected Component) directed graph algorithm.

Suppose there are $n$ variables and $m$ clauses in the 2SAT instance $\mathcal{I}$. The parameters $n$ and $m$ represent the size of $\mathcal{I}$

The 2-SAT instance is modeled by a directed graph $\mathcal{G_I}$, with

$2n$ vertices: for each variable $x$ in $\mathcal{I}$, there are two vertices $v_x$ and $v_{\bar{x}}$ (i.e., variable and its negation).
$2m$ edges: for each clause $x \lor y$, there are two directed edges $\bar{x} \to y$ and $\bar{y} \to x$. Note that the latter two implicative forms are equivalent to $x \lor y$.

The polynomial algorithm (it is actually a linear algorithm) proceeds as follows:

Obtain the SCCs of $\mathcal{G_{I}}$ in linear time $O(n + m)$;
Assign True to each literal (Notice: not the variable) in the destination SCC (denoted $SCC_d$);
Delete $SCC_d$ and its corresponding source SCC ($SCC_s$). (Note the symmetry in the graph $\mathcal{G_{I}}$);
Repeat (2) and (3) until $\mathcal{G_{I}}$ is empty.

For example:

$\mathcal{I} = (x_1 \lor x_2) \land (\bar{x_2} \lor x_3) \land (\bar{x_1} \lor
  \bar{x_2}) \land (x_3 \lor x_4) \land (\bar{x_3} \lor x_5) \land (\bar{x_4} \lor
  \bar{x_5}) \land (\bar{x_3} \lor x_4)$

The graph $\mathcal{G_{I}}$ is:


Does every large enough string have repeats? Let $\Sigma$ be some finite set of characters of fixed size. Let $\alpha$ be some string over $\Sigma$. We say that a nonempty substring $\beta$ of $\alpha$ is a repeat if $\beta = \gamma \gamma$ for some string $\gamma$.

Now, my question is whether the following holds:

  For every $\Sigma$, there exists some $n \in \mathbb{N}$ such that for every string $\alpha$ over $\Sigma$ of length at least $n$, $\alpha$ contains at least one repeat.

I've checked this over the binary alphabet, and this is quite easy for that case, but an alphabet of size 3 is already quite a bit harder to check, amd I'd like a proof for arbitrarily large grammars.

If the above conjecture is true, then I can (almost) remove the demand for inserting empty strings in my other question.

No, unfortunately not. There are even infinite square-free words if your alphabet has at least three symbols.

This apparently natural border (two-element alphabets have only finitely many square-free words) is observed in many places, for instance:

$\{xyyz \mid x,y,z\in \Sigma^+\}$ is co-finite for $|\Sigma|\leq 2$ but not context-free for $\Sigma>2$.
The class of languages generated by terminal-free patterns can be learned in the limit if $|\Sigma|>3$ but not so if $|\Sigma|=2$ [Reid2004].


Converting Polynomials into Binary form How can a polynomial such as $x^3 + 1$ be converted to its binary form of $1001$. Likewise, $10100001 = x^7 + x^5 + 1.$

Just put the value of $x=10$ then

$$10^3+1=1001$$


Finding a value in a sorted array in log R time, R is the number of distinct elements The standard binary search algorithm gives log N time, where N is the total number of elements in the array. When the array has duplicates, I don't see how you could detect those duplicates ahead of time. (Iterating through the array takes N time, which is too much.) Consequently how do you improve the performance from log N to log R?

There is no such algorithm.  Here's an information-theoretic proof that it can't be done, inspired by gnasher79's answer.

Let's focus on the special case where $R=3$.  Suppose there is a constant $c$ and an algorithm that examines at most $c$ elements of the array, regardless of $n$.  Then this algorithm can't possibly solve your problem.

In particular, consider all arrays of the form $[0,\dots,0,1,2,\dots,2]$, i.e., containing some number of 0's, followed by a single 1, followed by 2's.  Let's imagine what the algorithm does when you ask it to find a $1$.  There are $n-1$ different possible positions for the $1$.  However, after doing $c$ probes, the algorithm learns only $c \lg 3$ bits of information about the position of the $1$.  Thus, if $n-1 > 2^{c \lg 3}$, the algorithm can't possibly work correctly for all such arrays: there exists some pair of arrays where the algorithm outputs the same thing in both cases, but the correct answers differs, so the algorithm must be wrong for at least one of those two cases.  In other words, if we take $n$ to be sufficiently large (namely, $n> 3^c + 1$), the algorithm will be incorrect.

This implies there is no algorithm for the case $R=3$ whose running time is upper-bounded by a constant.

It follows that there is no algorithm whose running time is $O(\lg R)$ (and whose running time doesn't depend on $n$): if there was, plugging in $R=3$ would give us a $O(1)$-time algorithm for the special case where $R=3$... but I just proved that no such algorithm can exist.

However, the special case $R=2$ can be solved in $O(1)$ time: simply look at the first and last element of the array, and pick whichever one matches the value you're looking for.


Why the $\textbf{PCP}(\log n, 1)$ construction of completeness $c$ and soundness $s$ for an $NP$ language $L$ implies $s/c$ inapproximability for $L$? In the introductory chapter of $\textbf{PCP}$ in Arora and Barak, I read the proof that why a $\textbf{PCP}(\log n, 1)$ of completeness 1 and soundness 1/2 for an $NPC$ language $L$ will imply that there exists a $\rho$ for which $\rho$-approximation algorithm for MAX-3-SAT does not exist unless $P = NP$. But in the paper, https://www.cs.cmu.edu/~odonnell/papers/maxcut.pdf authors say that "We construct a PCP that reads two bits from the proof and accepts if and only if the two bits are unequal. The completeness and soundness are $c$ and $s$ respectively. This implies that MAX-CUT is $NP$-hard to approximate within any factor greater than $s/c$." What is the proof for this?

The authors give a reduction $x \mapsto f(x)$ from some NP-hard problem $X$ to MAX-CUT with the following properties:

If $x$ is a YES instance then $OPT(f(x)) \geq c$.
If $x$ is a NO instance then $OPT(f(x)) \leq s$.

Here $OPT(y)$ is the optimal value of the MAX-CUT instance $y$.

Suppose now that you had an algorithm for MAX-CUT with approximation ratio $\rho > s/c$, which means that for every instance $y$, $ALG(y) \geq \rho OPT(y)$, where $ALG(y)$ is the value of the instance produced by the algorithm. We can use this algorithm to solve $X$, since $x$ is a YES instance of $X$ iff $OPT(f(x))>s$ (I'll let you verify that).

This informally explains the statement in the paper. Any more formal explanation requires a definition of "NP-hard to approximate". One possibility is as follows. Let $Y$ be a maximization problem. We say that $Y$ is NP-hard to approximate within a factor of $\rho$ if for every problem $X \in \mathsf{NP}$ there exists a polytime computable reduction $f$ which on input $x$ produces a tuple $(y,v)$, where $y$ is an instance of $Y$ and $v$ is a number, with the following properties:

If $x$ is a YES instance of $X$ then $OPT(y) \geq v$.
If $x$ is a NO instance of $X$ then $OPT(y) < \rho v$.

This generalizes the usual definition of NP-hardness for optimization problems, which corresponds to the choice $\rho = 1$.
Under this definition, if $Y$ is NP-hard to approximate within a factor of $\rho$ and there is a polytime $\rho$-approximation algorithm for $Y$, then $\mathsf{P} = \mathsf{NP}$.
Finally, according to this definition, MAX-CUT is indeed NP-hard to approximate to within any factor strictly larger than $s/c$.


Trust in online platforms dealing with virtual goods I am implementing an online platform, where third-parties sell virtual goods to clients on a subscription basis. Let's take for example ebooks as a virtual good in this case.
How can the third-parties trust my platform? How can they know that I don't cheat with the number of subscriptions I report back to them? Do any solutions exist for this or some papers? I can't possibly be the first with this kind of problem. The problem is I even don't know what to search for.

As far as I know, sellers can't fully verify that the platform is behaving honestly, so you'll need to trust the platform.  A malicious platform could always sell a copy to someone without giving the seller their cut.


Why is the complete state of a turing machine representable by a finite word? At the moment I'm just reading through this article on the word problem for groups (https://projecteuclid.org/euclid.bams/1183548590), and I'm wondering about a certain snippet.
On page 40 the article describes a word that can encode the state of a turing machine, namely $S_{k_{u}}...S_{k_{1}}q_{i}S_{j_{1}}...S_{j_{v}}$ where $S_{k_{u}}...S_{k_{1}}S_{j_{1}}...S_{j_{v}}$ is the tape expression, $q_{i}$ is the current internal state of the turing machine, and $S_{j_{1}}$ is the currently scanned symbol.
I'm just wondering why this word is necessarily finite. Why can't the input of the turing machine have an infinite amount of non-zero characters?

I'm just wondering why this word is necessarily finite. Why can't the input of the turing machine have an infinite amount of non-zero characters?

No, it can not.

When the Turing machine starts, the tape contains the input (a finite-length word) followed by an infinite amount of blank symbols (often written as #). It is common to simply omit the trailing infinitely many blanks, and just represent a finite prefix instead, adding blanks as needed when the head moves right past the end of the tape.

When the machine runs, in each step it can at most (over-)write over one tape symbol, and move right by at most one position. This is an essential feature of any Turing machine.

Hence, after finitely many steps, we still have a finite amount of non-blank symbols. The tape again contains infinitely many trailing blanks (usually not represented), so it can be represented by a suitable finite prefix.


Deteremine if Language is in $R$ or $RE$ $$L =\left \{ \langle M \rangle \mid \exists x\in \Sigma^* \left(\left | x \right |\leq 10000 \wedge H(M, x\right) \right \}$$
Where $H(M, x)$ denotes whether Turing machine $M$ halts on input $x$.
My guess is neither $R$ or $Re$ because I would have to run infinite TM's in order to find out if every TM halts on x or is not halting on x. Is my intuition correct?

The language is in RE: simply generate all inputs $x$  with $|x|\le 10000$ (they are finitely many), and simulate $T$ on all inputs in parallel. Whenever one simulation halts, accept.
The language is not in co-RE, as otherwise it would be decidable and we could solve the Halting problem.
Indeed, to decide whether a Turing machine $T$ halts on empty input, we could create a new machine $M$ that simulates $T$ if $x=\varepsilon$ and does not halt otherwise. Then $M \in L$ if an only if $T(\varepsilon)$ halts.


How can I prepare for CS in university How can I prepare for an introductory CS college course?

I am currently in Grade 12 and next year I will be studying Computer Science at a university in South Africa (syllabus is here). However CS has a very high dropout rate here in South Africa, more than any other course, and I'm nervous because of that. My experience with programming is limited to Java in the Net beans environment.  I understand the basics of programming (loops, arrays, methods and classes, reading and understanding other languages, etc).

My question is how can I be more prepared? I'm willing to learn new languages or take online courses or anything that can help me next year.

I'm not well aware of study pattern in your region, but I can advise you according to my own experience of 6 years in this field. I am in post graduation course.
One of the many things you need to know is CS is not all about programming, although most of the concepts you can relate to it and easily understand. Most importantly, its useless to learn every language, but mastery in any one language would be very helpful. Slowly you'll start understanding that all you need to understand is declaring variables, loops, functions and some built-in or library functions for a language, and it'll do most of your basic work.

Secondly, theory alone is of little use, except in the field of algorithms. From programming to digital and networking, you need to understand the practical examples. You need to start from "How will I do this?" then go for "what are the problems in my ways?" and then you'll almost always end up with adopting standard ways of doing things, this methodology will give you a lot of help.

Nothing is too difficult if you work hard and follow right approach. Computer science is a field where either you'll understand things or you won't. There is little to no use of understanding half things. You can't know half algo. You can't know OSI architecture upto 3 layers. You'll forget things if you do them that way. But once you have struggled enough, things would start relating so nicely that you'll easily be able to forecast solutions to a problem in one subject due to your experiences from other subjects.

My advice would be to go for the course if there is some curiosity in you when you think how facebook works? How Windows work? How am I connected? Why is everything 0 or 1? WHAT is 0 and 1?
All the best.


Function is recursive iff its graph is recursively enumerable So I understand that a function is recursive if there exist a Turing Machine that accepts it and halts on every input, since function is defined everywhere.
But how to prove that function is recursive if and only if the language {x#f(x) |x∈(Г -{#})*)} (graph) is recursively enumerable?

In order to prove your claim, you need to prove two things:

If a function is recursive then its graph is r.e.
If the graph of a function is r.e. then it is recursive.

Let's see what you have to do to prove these two claims.

Claim 1. Suppose that $f$ is recursive, i.e. it is computable by some program. You have to come up with another program that enumerates $x\#f(x)$. For example, assuming the inputs are natural numbers, it could output $1\#f(1),2\#f(2),3\#f(3),\ldots$.

Claim 2. Suppose that $\{x\#f(x)\}$ is r.e., that is, some program enumerates $x\#f(x)$ for all legal inputs $x$, in some order. Given an input $y$, we need to use this enumeration to compute $f(y)$. It is natural to wait for $y\#f(y)$ to be enumerated and extract $f(y)$.

Your task now is to flesh out these proof sketches.


What is the computational class of a pushdown automaton with real values? Say there is a push-down automata, in this example I'll use a deadfish-like set:
+: increase x by 1
0: set x to 0
ln: set x to ln(x) <-- real valued result
With x being an infinite precision real-valued variable, does this allow said machine to have more power than if it was operating on integers? Or am I misunderstanding something?

Since none of your instructions can influence the behavior of the pushdown automaton (they can only influence the value of $x$), this does not change which languages the pushdown automaton can accept.


Measuring availability from CAP theorem I wonder how to check availability property from CAP theorem.
Consistency check is conceptually easy: if at least once somehow same query at the same time returns different results, then the system may be considered inconsistent (or under some circumstances eventually consistent).

But what about availability? If it takes 1 millisecond for the system to respond, it probably should be considered available. If 1 second for a huge query - probably also available. But what about 50 seconds for a simple query?.. Where is the threshold - how much time should the system take to respond in order to consider it unavailable?

Well, one possible threshold is to consider system unavailable only if it throws some error immediately or doesn't respond at all. But with such definition we may consider available any system that lets the user wait for a long time until all inconsistencies and partitions are resolved.

So my questions are:

1) How do we check if system satisfies availability property as defined in CAP theorem?

2) How do we distinguish the following cases:

System is available, but it may take 10 minutes to process some
huge query.
Actually system is not available, but there is some
wrapper (user calls it instead of the original system) that each time when original system is not available simply waits
until it becomes, so to the outside user it looks like the system is
available and is simply processing the query.

This is indeed a concern for those building real-world applications - how does one measure "availability" - not the binary property discussed in the CAP theorem, but the experience for users of the system.

There is industry agreement around this concern, and a standardized method of measuring it applicable to all systems. (Note: as stated in the comments, this is a separate concept from the theoretical concept of availability, which is analyzed from an algorithm, or perhaps from a simulation of a system.)

The Apdex method assumes you have a definition of "satisfied service" at some response time. Let's say you consider a sub-1-second response time to satisfactory to define "available." Then, by convention, "tolerable" service is 4 times the target time: in our case, a response time from 1 to 4 seconds. Response times longer than 4 seconds are considered "frustrated."

Then, the Apdex score is the number of satisfied requests, plus half the number of tolerable requests, plus none of the frustrated requests (i.e. 0), all divided by the total number of requests.

For example, if you had 100 total requests, and 30 of them were satisfied (< 1s), 50 were tolerable (>1s but <4s) and 20 were frustrated (>4s), the apdex score for your service for the period of time those requests were serviced would be (30+25+0)/100, or 0.55. (An apdex score, by virtue of being a ratio, is always between 0 and 1)

Fun fact: a bunch of businesses then teamed up to turn this quite simple idea into a fully-fledged business. If you are a business, you can pay the Apdex Alliance money so they can produce education, webinars, and blogs, as well as certify compliant business so they may use the Apdex name and logo(!)

(I am not affiliated with the Alliance. I just like standards.)


Why is $\emptyset L = L\emptyset = \emptyset$ correct? I am taking a course on Automaton where I faced the algebraic laws of regular expressions.
First two were ok:

$\emptyset + L = L + \emptyset = L$: Union of a language $L$ with empty language gives the language $L$ itself.

$\epsilon L = L\epsilon = L$: Concatenation of empty string with strings belonging to certain language $L$ gives back the set of string of language $L$

But the third one is confusing me:

$\emptyset L = L\emptyset = \emptyset$

I felt it should be  $\emptyset L = L\emptyset = L$, since concatenation of strings of language L with string of empty language which is essentially no strings at all (which essentially means nothing to concatenate), should give back the language $L$ itself. Where I am thinking wrong?

$L_1L_2$ means the set of all strings you can make by choosing one from $L_1$ and one from $L_2$ and concatenating the two strings.  So how many ways can you choose a string from the empty set of strings and one from $L$?  None at all! So there are no such concatenations and $\emptyset L = \emptyset$.

The key point is that $\emptyset$ is the language that contains no strings at all. The empty string is a string (it's the string with no letters at all) so the empty string is not a member of the empty language: $\{\epsilon\}\neq\emptyset$.


Are regular expressions $LR(k)$? If I have a Type 3 Grammar, it can be represented on a pushdown automaton (without doing any operation on the stack) so I can represent regular expressions by using context free languages. But can I know if a type 3 grammar is $LR(1)$, $LL(1)$, $SLR(1)$, etc. without constructing any parse tables?

All regular languages have LL(1) grammars.  To obtain such a grammar, take any DFA for the regular language (perhaps by doing the subset construction on the NFA obtained from the regular expression), then convert it to a right-recursive regular grammar.  This grammar is then LL(1), because any pair of productions for the same nonterminal either start with different symbols, or one produces ε and has $ as a lookahead token.  Consequently, all regular languages are also LR(1), since any LL(1) grammar is LR(1).  Additionally, using an important result from this paper, you can show that any LR(1) language has an SLR(1) grammar, meaning that any regular language has an SLR(1) grammar.

However, the regular languages are not all LR(0).  The LR(0) languages have very specific properties - in particular, they must be prefix-free.  Thus the regular language {a, aa} is not LR(0), though it's clearly regular (regex a|(aa)).  However, the LR(0) languages are not properly contained within the regular languages; this grammar for { 0n21n | n ≥ 1 } is LR(0), but the language is not regular:

S -> E
E -> 0E1 | 2

Hope this helps!


Can partial sorting help with lookup cost in arrays? Looking something up in an unsorted list is a task with time complexity $O(n)$. However, if the list is sorted, the time complexity is $O(\log(n))$. That means it is sometimes worthwhile to sort an array. However, that is a trade-off as a sorting algorithm has a time complexity of $O(n\log(n))$.

As far as I know, you can not sort an array in less than $O(n\log(n))$  time. I am however wondering if there is any algorithm that can partially sort the array in less time than that? I am pretty sure you can not look up a value in such a partially sorted array in $O(\log(n))$ time, but can you do better than $O(n)$?

In short, is it possible to process an unsorted array with an algorithm faster than $O(n\log(n))$ such that a lookup algorithm can do a search faster than $O(n)$, though not as fast as $O(\log(n))$?

If you run "balanced Quicksort" (using the exact median at every step) up to depth $k$ (at the cost of $O(n k)$), you get a partition of the original array into $2^k$ sorted parts of $n/2^k$ unsorted elements each. Given an element, we can locate the correct part in time $O(\log(2^k)) = O(k)$ using binary search, and then look it up using an additional $O(n/2^k)$, for a total complexity of $O(n/2^k + k)$.

If $k = o(\log n)$ then the partial sorting takes time $o(n\log n)$. If $k = \omega(1)$ then the lookup algorithm takes time $o(n)$. Thus if $1 \ll k \ll \log n$ we get $o(n\log n)$ preprocessing time and $o(n)$ lookup time. For example, if $k = \log\log n$ then preprocessing takes $O(n\log\log n)$ and lookup takes $O(n/\log n)$.


Is $(a^nb^m)^r$ regular? I took my theory of computation exams a few weeks ago, and this was one of the questions:

Assume language $L=\{(a^nb^m)^r \mid n,m,r\ge 0\}$
Is L regular? If yes provide a regular expression or an automaton for it.

After I briefly asked him the answer after the exam, it appears it really is regular (I believe he said the expression is the simple $(a^*b^*)^*$). However I cannot seem to understand why that is. The way I see it, its concatenating $a^nb^m$ r times, like this:

$a^nb^ma^nb^ma^nb^m...a^nb^ma^nb^m$,

which isn't regular since there is no way for an automaton to recall n and m every time. Where am I at fault here?
EDIT: I talked to the professor again, he admitted it was a mistake. The language is indeed not regular.

The language $L$ is not regular, as can be proved using Nerode's method. Consider the following words $w_n = a^n b$ for $n \in \mathbb{N}$. Then $w_n^2 \in L$, but for $n \neq m$, $w_n w_m \notin L$. Hence any automaton for $L$ must be in a different state after reading each $w_n$, which contradicts its finiteness.


How do you represent LISP as mathematical / logical model? I asked this in stackoverflow, but the question probably fits here better.

This question arose from the objection that LISP is regarded as a functional language with some simple principles, namely functions, variables, and operators that roughly correspond to predicates, propositional variables, and connectives in logic respectively.

How would you define recursive structure and "data is a function is a data" paradigm central in LISP as a mathematical model? How about list processing feature? Can we derive LISP from simple mathematical foundations starting from propositional logic up to some specific factored logic?

Surely there must be a model, not only for LISP, but many similar "old" languages. So, I'd like to know, what are the necessary concepts of mathematics to define LISP-like language.

Point is not on what paradigm LISP fits the best, but to find out the simplest mathematical model for the language in question.

Lately, I found this paper of McCarthy (1960) which may answer the question: http://www-formal.stanford.edu/jmc/recursive.pdf

Logic, arithemic and automata by Church (1962) also seems a useful source: http://www.mathunion.org/ICM/ICM1962.1/Main/icm1962.1.0023.0058.ocr.pdf

"Old" programming languages like Fortran, Cobol and LISP arose before serious mathematical theory of programming languages was developed. They inspired the development of such theory, but are full of idiosyncracies and features which from a mathematical point of view can best be described as "warts". However, each of the old languages in essence has a mathematical core. We can extract their cores and see what mathematical models those have.

For LISP the core would be a small subset of Scheme. Let us focus just on the list processing part, and forget about the fact that in LISP and Scheme one can change state with setq and the like.

A small core for LISP could contain the atoms, S-expressions and functions, by which we mean some basic functions, $\lambda$-abstractions, and recursive functions. There are several ways to model this much of LISP, but perhaps the neatest is by domain theory.

Consider the following simplified statement about (a core of) LISP. Every value is

either an atom (a literal),
or a cons,
or a function.

Let us try to express this idea mathematically. We should find a set $D$ of LISP values which

contains the set $A$ of all atoms (whatever they are)
contains $D \times D$ because every cons is a pair of values (car and cdr)
contains $D \to D$ because "functions are data"

We can express this idea as a requirement that
$$A + D \times D + (D \to D) \subseteq D.$$
Unfortunately, this is not possible because $D \to D$ is larger than $D$, unless $D$ contains just one element (but there are many atoms).

However, there is a way out: the set $D \to D$ of functions is larger than $D$ only if we take all functions -- but we only need to consider the computable functions, or some slightly larger set of them. Indeed, as was shown by Dana Scott a long time ago, we should look for a space $D$ (rather than a set) and then take $D \to D$ to be the space of continuous functions (because every computable map is continuous). As it turns out, there are several kinds of "spaces" that we could use, all of which have in common that they capture the idea of information content and information processing. I cannot go into technical details on how this is done, but you can read about domain theory to find out more.

Let us just think about what $D$ must contain. Of course, it contains various atoms, includnig an element corresponding to nil. Then, it contains all finite lists of elements, since a list (x1 ... xn) is just a lot of nested pairs (x1, (x2, ..., (xn, nil)). Next, it contains lot and lots of functions: anything that can be defined by a lambda, and with a bit of care also anything that can be defined by recursion.

In summary, the answer to your question is that the mathematical essence of LISP is a space $D$ which contains the atoms, its own product $D \times D$ and its own function space $D \to D$.

The stuff about logic and propositional connectives, you should forget that on the first round of studying mathematical models of LISP. Maybe come back to it later, and look up something like Curry-Howard correspondence and realizability.


solve a rational equation as fast as possible I would like to find the first positive solution(if there is one) to this equation:
$$\frac{ax^2+bx+c}{dx^2+ex+f} = gx+h$$
The simplest way I fond would be to do the following:
$$ax^2+bx+c = (dx^2+ex+f) * (gx+h)$$
$$(=)$$
$$ax^2+bx+c - (dx^2+ex+f) * (gx+h) = 0$$
$$(=)$$
$$Ax^3+Bx^2+Cx+D = 0$$
and find the roots of the cubic.
But, finding the roots of a cubic is computationally expensive.
As it requierers the use of sqrt, cos and sin.
(I am only looking for the smallest positive if there is any, if you know some algorithm that does that even for cubics, I would like to know more about it).
So my question is: "is there another way to find the solutions of this equation?"
Like IF the equation was:
$$(ax^2+bx+c) * (dx+e) = 0$$
it could be solved by solving the quadratic and the linear separately instead of calculating the resulting cubic and solve it afterward.
Any help is appriciated!
Thanks in advance.

It depends on what kind of answer you want. Finding closed-form algebraic solutions is different from finding numeric solutions.
Having said that, I agree with plop here. Your best bet is to get bounds on the roots, and then use an iterative algorithm. The good news is that for a cubic, it's not difficult to find bounds.
First off, I assume that you know to compute the roots of a quadratic using the Citardauq formula when appropriate. If $b\ge 0$ then:
$$x_1 = \frac{-b - \sqrt{b^2 - 4ac}}{2a}$$
$$x_2 = \frac{2c}{-b - \sqrt{b^2 - 4ac}}$$
Otherwise:
$$x_1 = \frac{-b + \sqrt{b^2 - 4ac}}{2a}$$
$$x_2 = \frac{2c}{-b + \sqrt{b^2 - 4ac}}$$
Using this method, the addition/subtraction of $b$ and the square root of the discriminant have the same sign, so there is no cancellation there.
To find all roots of a cubic $p(x) = a x^3 + b x^2 + cx + d$ numerically, first find the roots of the derivative $x_1$ and $x_2$, and evaluate the cubic at those two points. Assuming that $x_1 \le x_2$, you have four cases to consider.

If $x_1 = x_2$, then the cubic is of the form $a(x - x_1)^3 + d - ax_1^3$. This means it has one real root at $\sqrt[3]{x_1^3 - \frac{d}{a}} + x_1$. If $ax_1^3=d$ then it's a triply-repeated root.
If $p(x_1)$ and $p(x_2)$ have opposite sign, then the cubic has
three distinct real roots. Specifically, there is a real root in each of the following ranges: $\left(-\infty,x_1\right)$, $\left(x_1,x_2\right)$, $\left(x_2,\infty\right)$. Use this to get an initial estimate and use a numeric root finder.
If $x_1 \ne x_2$ but $p(x_1)$ and $p(x_2)$ have the same sign, then the cubic has only one real root. It is either in the range $\left(-\infty,x_1\right)$ or $\left(x_2,\infty\right)$, depending on the sign of $a$.
If one of $p(x_1)$ or $p(x_2)$ are zero, then there is a repeated real root at that point and a third real root elsewhere. Again, it is either in the range $\left(-\infty,x_1\right)$ or $\left(x_2,\infty\right)$, depending on the sign of $a$.

Because you need the smallest positive root, you can eliminate ranges from consideration. For example, suppose you find yourself in case 2. If $x_2 \le 0$, you only need to check the range $\left(x_2,\infty\right)$ for a positive root, as the other two roots are guaranteed to be negative. You never have to perform the iterative algorithm on all three ranges in case 2.
Doing this kind of exhaustive case analysis becomes unwieldy for higher-degree polynomials, which is why we tend to prefer different methods there. This is beyond the scope of the question, but as a general guide:

It's usually worth performing squarefree factorisation if possible, because numeric methods tend to converge more slowly around repeated roots.
You can bound the roots using Vincent's theorem (or Sturm's theorem, which is slower but a bit easier to understand) and then use numerical root finding if you only need the real roots.
You can use something like Aberth's method if you need complex roots.


What are drawbacks of Tree Sort algorithm (with balanced tree) vs Tree Sort (with unbalanced tree)? Tree Sort algorithm with unbalanced tree may yield $O(n^2)$ worst-case time complexity/performance. But Tree Sort algorithm with balanced tree guarantees $O(n\log n)$ worst-case time performance.

So I do not see any practical use-cases to prefer unbalanced tree variant of Tree Sort algorithm - Tree Sort with balanced tree seems to be a clear winner on all accounts.

Is my conclusion correct? Is Tree Sort algorithm with balanced tree is always the best choice (when Tree Sort is applicable generally)?

In what cases Tree Sort algorithm with unbalanced tree can be better in some respect?

The advantages of unbalanced trees over balanced trees in practical situations are little to none. A large number of predefined algorithms/ data structures that many programming languages use implement a variety of the Tree Sort algorithm in order to keep time complexity of emplacement and retrieval of data to a minimum (keeping in mind that space complexity stays the same). Such varieties are AVL trees and Red-Black trees.

For instance, in STL (Standard Template Library in C++), structures such as map/ multimap, set/ multiset implement a BST as to keep the time factor to a minimum value.

An example of usage of an unordered tree (although not a binary tree) is a tree used to represent TRIE structures. You can find more about these from Wikipedia or Geeksforgeeks.

Hope this was helpful!


Basic exercises on decision trees I am a pure math person doing some ML self-study and I am pretty lost.
I am trying to solve the following exercises on decision trees:

Exercise 1. Consider the following training set where
$X_1,X_2,X_3,X_4$ are the attributes and $Y$ is the class variable.
$$ \begin{matrix} Y & X_1 & X_2 & X_3 & X_4 \\ 1 & 0   & 1   &  0  & 1
 \\ 1 & 1   & 0   &  1  & 0   \\ 1 & 1   & 1   &  1  & 0   \\ 1 & 0   &
 0   &  0  & 1   \\ 1 & 1   & 1   &  1  & 0   \\ -1& 0   & 0   &  1  & 1   \\
 -1& 0   & 0   &  0  & 0   \\
 -1& 0   & 0   &  1  & 0   \\
 -1& 1   & 0   &  0  & 0   \\
 -1& 0   & 0   &  1  & 1   \\ \end{matrix} $$

Learn a decision tree using the ID3 algorithm.
Draw a decision tree having only 4 leaf nodes, 3 internal nodes and depth bounded by 2, that has 100% accuracy on the given dataset.

Exercise 2. Let $x$ be a vector of $n$ Boolean variables
${X_1,...,X_n}$ and let $k$ be an integer less than $n$. Let $f_k$ be
a target concept which is a disjunction consisting of $k$ literals.
State  the  size  of  the  smallest  possible  consistent  decision
tree  (namely  a  decision  tree  that correctly classifies all
possible examples) for $f_k$ in terms of $n$ and $k$ and describe its shape.

Now, I've done the first part of Exersice 1 as follows: first I noticed that $X_2$ is pure and so I chose it as root; then I used Information Gain to find the nodes. The second question confuses me: my understanding was that ID3 already gives the smallest tree, so how am I supposed to make it smaller? Or if am I wrong can anybody help me clarify?
For the second problem, I really don't know where to start from, so any hint would be appreciated.

ID3 is a heuristic. It is not guaranteed to generate an optimal decision tree.
Here is an algorithm for Exercise 1:

If $X_3 = 1$, then answer $2X_1-1$.
If $X_3 = 0$, then answer $2X_4-1$.

For Exercise 2, suppose $f_k = X_1 \lor \cdots \lor X_k$. An optimal decision tree simulates the following algorithm:

If $X_1 = 1$, output 1, else continue.
If $X_2 = 1$, output 1, else continue.
...
If $X_k = 1$, output 1, else output 0.

Indeed, every decision tree for $f_k$ must query all of $X_1,\ldots,X_k$ in the worst case.


Merge k sorted arrays of exponentially increasing lengths I've seen many answers to merge identical-sized arrays, but haven't seen the answer to this question yet.

Given $A_1, A_2, ..., A_k$ sorted arrays where $|A_i| = 2^i$, what is the most efficient way to merge them all?  I'm looking for a comparison-based algorithm with the best asymptotic running time possible.

We can describe any merging algorithm in a tree form (each internal node corresponds to a merged array). Suppose that the cost of merging two arrays $B,C$ is exactly $|B|+|C|$. Then the total cost equals $\sum_{i=1}^k d_i |A_i|$, where $d_i$ is the depth of the leaf $A_i$.

Consider now an arbitrary merge tree $T$. Suppose that $A_k$ is not a child of $T$. In that case, we can form a new tree $T'$ as follows: let $T^-$ be $T$ with $A_k$ removed (and its sibling promoted to its father), and let $T'$ be the tree with children $A_k$ and $T^-$. The cost of $T'$, denoted $C(T')$, satisfies
$$
C(T') = 2^k + C(T^-) + \sum_{i=1}^{k-1} 2^i < 2\cdot 2^k + C(T^-) < C(T).
$$
Here $2^k$ is the cost of $A_k$ and $\sum_{i=1}^{k-1} 2^i$ is the additional cost of all other leaves (since they are all one level deeper).

We conclude that $A_k$ must be merged last. Continuing this way, we see that the optimal schedule merges $A_1,A_2$, merges the result with $A_3$, merges the result with $A_4$, and so on.


Why won't a Turing machine halt? I am reading Sipsers. The book introduces halting problem and proves that is a turing recognisable language but not a turing decidable language. Thus giving a Turing machine which does not halt on some inputs. The language to be precise is
$L=\{\langle M,w \rangle| \ M \text{is a turing machine and } w \text{ is a string M accepts} \}$. Let $D$ be the turing machine that recognises $L$. Inability of $D$ to halt on some inputs is due to the fact that there exist Turing Machine $M$ which do not halt on some input. Thus the reason for not halting is kind of recursive ( if I consider only this example ).
I am still not able to understand in crux why a turing machine won't halt. But can't come up with language over $\{0,1\}$ which is turing recognisable but not decidable. What are all the reasons a Turing machine won't halt ?

A TM s just a program. It does whatever you program it to do. If, for instance, you program it to perform the following:

while (true)
{
   do_nothing
}

, then it will never halt!

The language $L$ goes over all possible machines $M$, and therefore it must encounter some machines that don't halt, for instance, the one stated above.

There is a deep difference between the reason the above machine doesn't halt (it is just programmed to do so), and the reason that any machine for $L$ will not halt–no machine for $L$ exists since that language is undecidable.

regarding your question about finding a more "natural" language that is undecidable, see Is there a “natural” undecidable language?. You may get some more intuition about undecidable languages here.


How do I detect and rotate a square? I have recently written code for detecting path colors in a 2D grid and printing the corresponding path costs and it works fine for me.
Here's my code; I am currently new to OpenCV and know only C++ (no python).

The image that I had for the project was:

Now I may get an image like this for the same task:

I need an algorithm to detect the square in the middle of the arena, rotate it to the angle by which it becomes like the image above, and then crop the rest of the image off.

I am currently at a fix about doing this.

Since you asked for algorithms, I suggest you look at the Hough transform and other techniques for finding lines in an image.  I suspect this will help you determine where the lines are, where the intersections are, and how much to rotate to recover the original image.


Why is computation of this function numerically unstable? Why is computing the function at certain ranges of h
$$f(x) = \dfrac{\sqrt{-x+a} - \sqrt{2x+a}}{ 4a}$$
unstable? How would I rewrite this function so that it is stable?

The question has been changed since this answer.

Another alternative is
$$\begin{align}f(x)&=\frac{\sqrt{x+h}-\sqrt{x-h}}{2h}\\
&=\frac{\sqrt{x+h}-\sqrt{x-h}}{2h}\cdot\frac{\sqrt{x+h}+\sqrt{x-h}}{\sqrt{x+h}+\sqrt{x-h}}\\
&=\frac{1}{\sqrt{x+h}+\sqrt{x-h}}\end{align}$$

Now, even if $h$ becomes very small, the value approaches $$\frac{1}{2\sqrt{x}}$$ as it should.


What data-structure is best suited for escape analysis? I'm making a compiler using LLVM and LLVM's shadow-stack. I thought I might easy the load of the GC by using escape analysis and allocate some variables on the stack. Can I use my typed AST for this algorithm, or must I use a graph data-structure?

Escape analysis is a static analysis that determines whether the
lifetime of data exceeds its static scope. As such, it is not really
about stack vs heap allocation, just about lifetimes.

I don't think you can use your typed AST for escape analysis, because
what you are analyzing is the data flow of the program. The
appropriate structure for that is a graph, not a tree, because the
data flow is cyclic. So what you want is to build a control flow graph
(cfg), and perform data flow analysis on it.

Data flow analysis is a method or family of methods used for
implementing a whole range of compiler optimizations. Among them,
escape analysis. In it, you keep track of all objects, variables and
references of your program in a points-to graph. Each object and
variable is a node in the graph and, depending on how you implement
it, references between them can either be nodes or edges.

For example, consider this Java method:

public Pair myMethod(Pair[] pairs) {
    Foo f = new Foo();
    Pair p1 = new Pair(1, 2);
    Pair p2 = new Pair(3, 4);
    p1.value = f;
    pairs[0] = p1;
    return new Pair(5, 6);
}

Escape analysis would work roughly like this:

Line 1: An array of type Pair is passed into the method and a
Pair is returned from it. Add two nodes to the graph, one labelled
pairs and another labelled RETURN both with flagged foreigner.
Line 2: An object called f is created in the myMethod
method- Add a node labelled f with flag native to the graph.
Line 3-4: Add two more native nodes labelled p1 and p2.
Line 5: The field value of p1 is set to refer to f. Add an
edge from node p1 to f.
Line 6: First element of the pairs array is set to refer to
p1. Add an edge from pairs to p1.
Line 7: A new pair object is returned. Add an anonymous native
node representing the pair object to the graph. Then add an edge
from the RETURN node to this anonymous node.

After this step, traverse the graph beginning at the foreigner nodes
and flag all nodes visited as foreigner. It is exactly the same task
as the mark step in a mark and sweep garbage collector.

Then all objects that weren't reached by the traversal retain their
native flag and are eligible for stack allocation provided that the
compiler can statically determine their sizes. The rest must be
allocated on the heap.

I highly recommend watching the Youtube lectures of this professor:

https://www.youtube.com/watch?v=NVBQSR_HdL0
https://www.youtube.com/watch?v=LfAYWms9gUc

The
paper
Escape analysis for Java
also provides a fairly good description on how the algorithm works.


Why this problem has such a simple solution? How would you avoid looking for more complex solutions first? There's a problem whose solution startles me because at first sigh, I wouldn't imagine that it could be solved so easily. The problem is:
There are n tasks, each task t_i has a weight w_i and a length l_i. Find an order of tasks t_1, ... t_j, ..., t_n that minimizes the total cost of completion, where the cost of completion of each task is c_j * w_j, where c_j is the time it has passed since you started working on the first task until you finished the jth task.
If we analyze the problem a bit, we can see that the task that we choose to complete first will impact the cost of all the remaining tasks. For example, say you only have 2 tasks:
task_1 with w_1 = 1 and l_1 = 5 and
task_2 with w_2 = 4 and l_2 = 2
If we started first task_1, its cost would be 5 * 1 = 5 while if we started first task_2, its cost would be 2 * 4 = 8. But, the cost of completing task_2 after task_1 is (5+2) * 4 = 28. This shows clearly that the order of completion of one task affects the cost of completion of all the remaining tasks.
Considering how each task we decide to complete next impacts the cost of all the remaining tasks, it startles me that the best order is simply the order we get by sorting the tasks by their ratio w_i/l_i.
Which part of the problem hints that the solution doesn't require to check all the possible orders?
The problem is taken from Algorithms Illuminated 3 by Tim Roughgarden.

In this case: It is obvious that you start with some task immediately, start a second task as soon as the first task is finished, then start a third task immediately after this etc.
It is obviously that you can swap the order of two consecutive tasks without affecting any other task. In an optimal solution, swapping the order of two consecutive tasks cannot improve the solution.
Now you look for a criterion when swapping two tasks would improve the solution. For an optimal solution, that criterion must fail for any two consecutive tasks. And lucky enough there is a simple criterion.
So any problem where tasks must be performed consecutively, and where swapping two tasks doesn't affect all the other tasks, you can solve if you can determine which order of the two tasks is better.
This doesn't work for the travelling salesman problem for example, because swapping two cities affects other cities as well.


Session Memory in the Windows Kernel While reading the paper Effective Data-Race Detection for the Kernel  by
John Erickson and Madanlal Musuvathi. I was stuck on a slightly tricky sentence.

"Similarly, a range of kernel-address space, called session memory, is mapped to different address spaces based on the session the process belongs to. When a sampled access lies in the session memory space, DataCollider sets a data breakpoint but checks if the conflicting accesses belong to the same session before reporting the conflict to the user."

I can not figure out in practice what the session memory is at process level.
Is the session related to the user owning the process? Or is it something more specific of the Kernel?

I know that I am probably missing something important but this is not basically my field of study so, although I tried, I couldn't find substantial answers. Is there someone who can explain me briefly what I am missing?

Cheers

I think that what is going on here is this.

In most operating systems, including Windows, there are lots of data structures inside the kernel that the kernel "shares" between all the processes running on the machine.  In early versions of Win32 (starting maybe with Windows 95?) there are some kernel data structures, specifically those having to do with the graphics device interface (GDI)) that are shared by all the processes that are using the same desktop.  In early versions of the OS there was only one desktop, so only one session, so these data structures were just shared like all the others.  In the Server versions of Windows each remote login gets a "terminal" which, I think, is sort of a virtual desktop.  So now they needed to "virtualize" those GDI data structures inside the kernel that weren't previously virtualized.  I think that a "session" is that set of virtualized GDI datastructures.  They are shared by all processes running on the same "terminal", and each "terminal" has its own version of the data structures.

The reason this matters in the DataCollider paper you referenced is that they are using data breakpoints, which are set on virtual addresses rather than physical addresses.  But race detection (in the kernel) really makes more sense from the physical address perspective.  For most kernel data structures there is a one-to-one mapping from virtual addresses to physical addresses.  You set a data-breakpoint on a particular virtual address and when it "fires" you know that the physical address corresponding to that virtual address is still the same.  All processes, from all users, from all "terminals" are really sharing those data structures, and if there is a race, there is a race.

The problem, for DataCollider is that in "session memory" this one-to-one mapping doesn't hold.  In the case of session memory the virtual addresses are the same for every process, but the physical address that virtual address is mapped to is different when the kernel is working on behalf of processes from different terminals.  So when the data breakpoint fires you need to do some extra bookkeeping to figure out whether the virtual address is pointing to the same physical address that you intended when you set the breakpoint.


For a cycle with $n$ vertices, how many distinct chords are possible? Note: This is almost certainly an elementary problem with a well known solution. Therefore pointers to existing references will be accepted as good answers.

  Question: Given a cycle with exactly $n$ vertices, how many distinct chords are possible?

This question is motivated by the definition of chordal graph, which only requires the cycles in the graph to have chords if the cycles have four or more vertices.

Doodling on paper I realized that this is because, for the smallest possible number of vertices in a cycle, namely three, the existence of a chord is impossible. But as soon as the cycle contains at least four vertices the existence of a chord is possible.

For the four-vertex cycle, it seems that there are only two possible chords. Since a chord is formed between two distinct vertices in a cycle, and $2$ might be the first term in a sequence of coefficients of the form $\binom{f(n)}{2}$ for some $f(n)$, I thought that the solution might be similar to the handshake problem and involve $\binom{n}{2}$ or $\binom{n-1}{2}$ somehow.

But this seems to fail already when $n = 5$, because instead of getting $\binom{4}{2} = 6$, which I had expected, instead I counted 5 distinct chords. So then I thought that maybe the answer is the Catalan numbers, since after $1$ they start with $2,5,\dots$, have a form similar to the $\binom{n}{2}$ from the handshake problem, and show up in all sorts of unexpected places.

But this conjecture also fails, since for the cycle with $n=6$ vertices I counted 9 (or maybe 8) distinct chords, and this obviously isn't the third non-unit Catalan number 14, nor is it $\binom{5}{2} = 10$. I somewhat expect the numbers/sequences to differ for odd and even number of vertices however, for a reason analogous to why a graph is Eulerian if and only if each of its vertices has even degree.

I would like to know the answer not only out of sheer curiosity, but also for some intuitive insight into how one can then go on to count the number of possible chordal completions of a graph (which one then uses to calculate the treewidth) -- that is all outside the scope of this question however.

A chord consists of a vertex $i$ and a different nonadjacent vertex $j$. There are $n$ options for $i$, and $n-3$ options for $j$ (since we can't choose $i$ or any of its two adjacent vertices). Since we can switch $i,j$ and get the same chord, we have to divide by 2. Overall, we get that the number of chords is $$ \frac{n(n-3)}{2}. $$
When $n=3,4,5,6$, this gives $0,2,5,9$, matching your values.


Context-free grammar how to have same number of variables within a language I am trying to get a CFG for the language:

  The set $A$ of odd-length strings in $\{a,b\}^*$ whose first, middle and last symbols are all the same.

(some example of correct answers would be: a, aaa, ababa, aababba, some incorrect answers include: ɛ, aaaa, abbaa)

This is what I've done so far:

S = a|b|aTaTa|bTbTb
T = aT|bT|ɛ

However the problem is, I need T to be a string of any combination of 'a's and 'b's but of the same length, but I'm not sure how to express this. As you can see above, I can get strings made up of any combination, but they won't be the same length when passed to S.
Any help is appreciated!

Your approach won't work. Whenever you try to match the length of two non-terminals, that should be a big red flag your approach won't work.

Here's a hint: expand from the middle out, after starting with $S = a \mid b \mid aAa \mid bBb$. Can you take it from here?


Feature values range Suppose I am about to use SVM for learning a classification or ranking function. Suppose that my feature vectors are two dimensional and that values for one dimension are, say, natural numbers and the values for the other dimension are real numbers in $[0,1]$. Can this difference in magnitudes somehow negatively affect learning? Are there some guidelines for scaling feature values? Any references appreciated.

I don't see how there should be any negative consequences of this. To see why, you can "vectorize" your feature matrix so that you still have scalars for each "new" feature. That is, instead of a matrix of n features each with k values, you have a vector of length n×k with scalar features. SVMs with a mixture of categorical/integral + real components is standard.


How do you go from $\log P = \log N$ to the next step? Let
  \begin{align*}
    &P=2^{\log_2 N}\\
    &\Rightarrow \log_2 P = \log_2 N\\
    &\Rightarrow P=N\\
    &\Rightarrow 2^{\log_2 N}=N\,.
  \end{align*}

I don't understand how can you just drop the logs and go straight to $P = N$. Can someone please explain this to me? Am I missing a log rule?

Two positive real numbers are equal if and only if their logarithms are equal. This is because $\log$ is a strictly increasing function that grows without bound and is defined for all positive reals: it is, therefore, a bijection from $\mathbb{R}_{>0}$ to $\mathbb{R}$.

Clearly, if $x=y$ then $\log x=\log y$. If $x\neq y$ then suppose $x>y$ (the case $x<y$ is identical). Because $\log$ is strictly increasing, $x>y$ implies that $\log x>\log y$ so, in particular, $\log x\neq \log y$.  Therefore, $x=y$ if, and only if, $\log x=\log y$.


Recognizing finite state machines with repetition I'm interested in finite state automata which have the capacity to require repetition.  That is, the machine may be in a state in which the next character may be any character from set $S$, but, whatever character there is, it must be repeated 3 times.  Or it may be in a different state, which requires a character from set $T$ repeated twice.

I could in theory make a different state for each character in set S, and for each character in set T.  But that overcomplicates things and obscures the pattern - it can be any character in set S, but the same character must be repeated.

Is there any standard approach to this? I'm interested both in terminology and in practical code.

Motivation: I do not know the full makeup of the set $S$ or $T$.  I'd like to be able to communicate effectively about the FSM, draw state diagrams, and do implementation, without having to define $S$ or $T$.  In fact, $S$ and $T$ change based on the scenario.  (Now, given a character, it's trivial to tell if it's part of $S$ or $T$ — but, a priori, it's impossible to enumerate them.)

At the least, I'd like a good way to draw a state diagram for these types of machines.  Perhaps I should use a standard FSM with some type of annotation? Could state charts help with this?

Finite automata in which the transitions are regular expressions might be the model you are looking at. Indeed you could have transitions of the form $p \xrightarrow{aa + bbb} q$ to indicate that in order to go from $p$ to $q$, you need either 3 $a$'s or 2 $b$'s.
This model has the same expressive power as NFAs and DFAs.


Can radix sort reach exponential time complexity? For example, assume the input array is $$[121212,212121]$$
Say we are in base 10, so count sort will work in $O(n)$ time. We have 6 iterations which is approximately $n^2$. Is this a worst case example for radix sort?

If so, can I generalize this and say that given $k$ is the total number of digits, a worst case for the sort would be $\frac{k}{2}$ elements to sort?

Let $n$ be the number of integers to sort, $M$ be the maximum integer, and $b$ be the chosen base.

Each execution of counting sort will take time $O(n + b)$ and the number of such executions is $O(\log_b M)$.
The total time complexity is then $O((n+b) \log_b M)$.

If you want to ensure that this complexity is exponential in the input size $s$ (which is at most $O(n \log_2 M)$) you need to select an exponential value of $b$, e.g., $b = 2^n$ if $M = O(2^{\text{poly}(n)})$.

If $b$ is constant (e.g., base $10$) then the time complexity of radix sort will always be $O(n \log M)$, which is always polynomial in the input size $s = \Omega(n + \log M)$ since $O(n \log M) = O( (n + \log M )^2 ) = O(s^2)$.
This bound is tight when $M = \Theta(2^n)$.